| 失效链接处理 |
|
LeetCode前400题Java精美版 PDF 下载
本站整理下载：
相关截图：
主要内容：
1. Two Sum Easy
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
if (map.containsKey(nums[i]))
return new int[] { map.get(nums[i]), i };
map.put(target - nums[i], i);
}
throw new RuntimeException("No Solution");
}
思路：求解过程可以分为两步：
a. 取数组中某一数a（情况总共有n种，因为总共n个数，遍历一遍）
b. 查找target - a是否在数组中。可以在遍历的同时建立索引，因为到目前为止（比如i位置），如果map
中没有对应结果，那么说明对应结果在没有遍历过的部分，因为map中已经索引了到i位置的所有元
素对应值。所以答案在未索引部分，故只要遍历一遍就可以。
2. Add Two Numbers Medium
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse
order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0), cur = new ListNode(0);
pre = cur;
int carry = 0, num = 0;
while (l1 != null || l2 != null) {
num = carry;
if (l1 != null) {
num += l1.val;
l1 = l1.next; }
if (l2 != null) {
num += l2.val;
l2 = l2.next; }
cur.next = new ListNode(num % 10);
cur = cur.next;
carry = num / 10; }
if (carry > 0)
cur.next = new ListNode(carry);
return pre.next; }
思路：数字进位问题，该位有效值为值%10，进位值为值/10。可以使用一个变量记录进位值。这种下次状态
和本次状态有关的处理，在循环结束后要检查是否要处理最后一次的结果（本题为进位）。
2
3. Longest Substring Without Repeating Characters Medium
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is
a subsequence and not a substring.
public int lengthOfLongestSubstring(String s) {
char[] sc = s.toCharArray();
Set<Character> cs = new HashSet<>();
int j = 0, maxLen = 0;
for (int i = 0; i < sc.length; ++i) {
char cur = sc[i];
if (!cs.add(cur)) {
maxLen = Math.max(i - j, maxLen);
while (sc[j++] != cur)
cs.remove(sc[j - 1]);
}
}
return Math.max(sc.length - j, maxLen);
}
思路：滑动窗口。以j计左界限，每次出现重复字符后j移动到该字后一位。核心操作其实是向前检索重复字符
（此处利用索引）。需要注意的是最后循环完成后，需要再算一下没有计算的那段的长度，在这些子段中取最
长的。O(n)
4. Median of Two Sorted Arrays Hard
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length, m1, m2;
int k = (m + n + 1) >> 1;
m1 = findKth(nums1, 0, nums2, 0, k);
k = (m + n + 2) >> 1;
m2 = findKth(nums1, 0, nums2, 0, k);
return (m1 + m2) / 2.0; }
int findKth(int[] nums1, int s1, int[] nums2, int s2, int k) {
if (s1 == nums1.length)
return nums2[s2 + k - 1];
if (s2 == nums2.length)
return nums1[s1 + k - 1];
if (k == 1)
return Math.min(nums1[s1], nums2[s2]);
Integer m1 = Integer.MAX_VALUE, m2 = Integer.MAX_VALUE;
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
