1. 兩數(shù)之和
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int minus = target - nums[i];
if (map.containsKey(minus)) {
return new int[]{map.get(minus), i};
} else {
map.put(nums[i], i);
}
}
return new int[0];
}
}
4. 尋找兩個(gè)正序數(shù)組的中位數(shù)
兩個(gè)數(shù)組的大小是m和n，找到第(m+n+1)/2和第(m+n+2)/2個(gè)數(shù)，取其平均值就是中位數(shù)。
定義一個(gè)函數(shù)findKth找到兩個(gè)數(shù)組中第k小的數(shù)。
分別在nums1和nums2中查找第K/2個(gè)元素，有可能某個(gè)數(shù)組沒(méi)有第K/2個(gè)數(shù)字，如果存在就取出來(lái)，否則就賦值上一個(gè)整型最大值。如果某個(gè)數(shù)組沒(méi)有第K/2個(gè)數(shù)字，那么我們就淘汰另一個(gè)數(shù)組的前K/2個(gè)數(shù)字即可。
比較這兩個(gè)數(shù)組的第K/2小的數(shù)字midVal1和midVal2的大小，如果第一個(gè)數(shù)組的第K/2個(gè)數(shù)字小的話(huà)，那么說(shuō)明我們要找的數(shù)字肯定不在nums1中的前K/2個(gè)數(shù)字，所以我們可以將其淘汰，將nums1的起始位置向后移動(dòng)K/2個(gè)，并且此時(shí)的K也自減去K/2，調(diào)用遞歸。反之，我們淘汰nums2中的前K/2個(gè)數(shù)字，并將nums2的起始位置向后移動(dòng)K/2個(gè)，并且此時(shí)的K也自減去K/2，調(diào)用遞歸即可。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int left = (m + n + 1) / 2;
int right = (m + n + 2) / 2;
return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
}
//i: nums1的起始位置 j: nums2的起始位置
public int findKth(int[] nums1, int i, int[] nums2, int j, int k) {
if (i >= nums1.length) return nums2[j + k - 1];//nums1為空數(shù)組
if (j >= nums2.length) return nums1[i + k - 1];//nums2為空數(shù)組
if (k == 1) {
return Math.min(nums1[i], nums2[j]);
}
int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
if (midVal1 < midVal2) {
return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
} else {
return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
}
}
}
11. 盛最多水的容器
class Solution {
public int maxArea(int[] height) {
int res = 0;
int lo = 0, hi = height.length - 1;
while (lo < hi) {
if (height[lo] < height[hi]) {
res = Math.max(res, height[lo] * (hi - lo));
lo++;
} else {
res = Math.max(res, height[hi] * (hi - lo));
hi--;
}
}
return res;
}
}
15. 三數(shù)之和
使用回溯，但是某些案例會(huì)超時(shí)。
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public void dfs(int begin, int sum, int[] nums) {
if (temp.size() == 3 && sum == 0) {
res.add(new ArrayList<>(temp));
return;
} else if (temp.size() == 3 && sum != 0) {
return;
}
for (int i = begin; i < nums.length; i++) {
if (i - 1 >= begin && nums[i] == nums[i - 1]) {
continue;
}
temp.add(nums[i]);
dfs(i + 1, sum + nums[i], nums);
temp.remove(temp.size() - 1);
}
}
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
dfs(0, 0, nums);
return res;
}
}
轉(zhuǎn)為兩數(shù)之和：
不能用哈希表做，還是會(huì)超時(shí)。
只能先對(duì)數(shù)組排序，再使用二分做，注意去重。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i - 1 >= 0 && nums[i] == nums[i - 1]) {//去重
continue;
}
int target = -nums[i];
int lo = i + 1, hi = nums.length - 1;
while (lo < hi) {
if (nums[lo] + nums[hi] > target) {
hi--;
} else if (nums[lo] + nums[hi] < target) {
lo++;
} else {
res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
lo++;
hi--;
while (lo < nums.length && nums[lo] == nums[lo - 1]) {//去重
lo++;
}
while (hi > i && nums[hi] == nums[hi + 1]) {//去重
hi--;
}
}
}
}
return res;
}
}
16. 最接近的三數(shù)之和
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i < nums.length - 2; i++) {
int lo = i + 1, hi = nums.length - 1, sum = target - nums[i], diff = 0;
while (lo < hi) {
if (nums[lo] + nums[hi] > sum) {
diff = nums[i] + nums[lo] + nums[hi] - target;
hi--;
} else if (nums[lo] + nums[hi] < sum) {
diff = nums[i] + nums[lo] + nums[hi] - target;
lo++;
} else {
return target;
}
if (Math.abs(diff) < Math.abs(minDiff)) {
minDiff = diff;
}
}
}
return target + minDiff;
}
}
18. 四數(shù)之和
和三數(shù)之和類(lèi)似。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 3; i++) {
if (i - 1 >= 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length - 2; j++) {
if (j - 1 >= i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int lo = j + 1, hi = nums.length - 1, sum = target - nums[i] - nums[j];
while (lo < hi) {
if (nums[lo] + nums[hi] > sum) {
hi--;
} else if (nums[lo] + nums[hi] < sum) {
lo++;
} else {
res.add(Arrays.asList(nums[i], nums[j], nums[lo], nums[hi]));
lo++;
hi--;
while (lo < nums.length && nums[lo] == nums[lo - 1]) {
lo++;
}
while (hi >= j + 1 && nums[hi] == nums[hi + 1]) {
hi--;
}
}
}
}
}
return res;
}
}
26. 刪除排序數(shù)組中的重復(fù)項(xiàng)
使用pos記錄待覆蓋的位置，只把不重復(fù)的元素覆蓋到數(shù)組中。
class Solution {
public int removeDuplicates(int[] nums) {
int pos = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
continue;
}
nums[pos++] = nums[i];
}
return pos;
}
}
27. 移除元素
和上一題類(lèi)似，使用pos記錄待覆蓋的位置。
class Solution {
public int removeElement(int[] nums, int val) {
int pos = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == val) {
continue;
} else {
nums[pos++] = nums[i];
}
}
return pos;
}
}
31. 下一個(gè)排列
先從右往左找到第一個(gè)不是單調(diào)遞增的數(shù)。 比如34987， 4就是第一個(gè)不是單調(diào)遞增的數(shù)，記錄它的位置index。
如果index等于-1，說(shuō)明整個(gè)數(shù)從右往左是單調(diào)遞增的，下一個(gè)排列就是把整個(gè)數(shù)反轉(zhuǎn)一下，比如 98765的下一個(gè)排列就是56789。
對(duì)于79654，index = 0，它的下一個(gè)排列是94567，觀(guān)察是將7與9交換之后，再把最后4個(gè)數(shù)反轉(zhuǎn)一下得到的。
所以要從右往左找到第一個(gè)比index指向的數(shù)大的數(shù)，與index交換，然后反轉(zhuǎn)index右邊的數(shù)即可。
class Solution {
public void nextPermutation(int[] nums) {
int index;
for (index = nums.length - 2; index >= 0; index--) {
if (nums[index] < nums[index + 1]) {
break;
}
}
if (index == -1) {
reverse(nums, 0, nums.length - 1);
} else {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[index]) {
j--;
}
swap(nums, index, j);
reverse(nums, index + 1, nums.length - 1);
}
}
public void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
public void reverse(int[] nums, int a, int b) {
while (a < b) {
swap(nums, a, b);
a++;
b--;
}
}
}
33. 搜索旋轉(zhuǎn)排序數(shù)組
如果中間的數(shù)大于等于最左邊的數(shù)，則左半段是有序的，若中間數(shù)小于等于最右邊數(shù)，則右半段是有序的，我們只要在有序的半段里用首尾兩個(gè)數(shù)組來(lái)判斷目標(biāo)值是否在這一區(qū)域內(nèi)，這樣就可以確定保留哪半邊了。
class Solution {
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] >= nums[lo]) {//左半段有序
if (target >= nums[lo] && target < nums[mid]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else {//右半段有序
if (target > nums[mid] && target <= nums[hi]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return -1;
}
}
34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
模板題，考察lowerBound和upperBound函數(shù)。
class Solution {
//返回第一個(gè)大于等于target的數(shù)
int lowerBound(int[] nums, int lo, int hi, int target) {
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] >= target) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
//返回第一個(gè)大于target的數(shù)
int upperBound(int[] nums, int lo, int hi, int target) {
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > target) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) {
return new int[]{-1, -1};
}
int pos1 = lowerBound(nums, 0, nums.length, target);
int pos2 = upperBound(nums, 0, nums.length, target) - 1;
if (pos1 >= nums.length || nums[pos1] != target) {
return new int[]{-1, -1};
} else {
return new int[]{pos1, pos2};
}
}
}
35. 搜索插入位置
考察lowerBound函數(shù)
class Solution {
public int lowerBound(int[] nums, int lo, int hi, int target) {
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] >= target) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
public int searchInsert(int[] nums, int target) {
return lowerBound(nums, 0, nums.length, target);
}
}
39. 組合總和
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public void dfs(int begin, int sum, int[] candidates, int target) {
if (sum > target) {
return;
} else if (sum == target) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = begin; i < candidates.length; i++) {
temp.add(candidates[i]);
dfs(i, sum + candidates[i], candidates, target);
temp.remove(temp.size() - 1);
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
dfs(0, 0, candidates, target);
return res;
}
}
40. 組合總和 II
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public void dfs(int begin, int sum, int[] candidates, int target) {
if (sum > target) {
return;
} else if (sum == target) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = begin; i < candidates.length; i++) {
if (i - 1 >= begin && candidates[i] == candidates[i - 1]) {
continue;
}
temp.add(candidates[i]);
dfs(i + 1, sum + candidates[i], candidates, target);
temp.remove(temp.size() - 1);
}
}
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
dfs(0, 0, candidates, target);
return res;
}
}
41. 缺失的第一個(gè)正數(shù)
使用HashSet，將所有的數(shù)都存入set中，然后從1開(kāi)始判斷，如果不存在于set中，說(shuō)明缺失。
時(shí)間復(fù)雜度On,空間復(fù)雜度On，不符合題目空間復(fù)雜度O1的要求。
class Solution {
public int firstMissingPositive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]);
}
for (int i = 1; i <= nums.length; i++) {
if (!set.contains(i)) {
return i;
}
}
return nums.length + 1;
}
}
優(yōu)化：
把數(shù)組本身當(dāng)做哈希表，把符合條件的數(shù)a，放在下標(biāo)為a-1的位置上。
比如一個(gè)數(shù)組為[3,1,2] 那么遍歷一次之后變成[1,2,3]。
數(shù)組的長(zhǎng)度為len，遍歷數(shù)組，只要nums[i]在1 ~ len范圍內(nèi)，且不在正確的位置上（nums[i]-1的位置上），就把它與nums[i] -1位置上的數(shù)進(jìn)行交換。
交換之后還需要循環(huán)判斷，因?yàn)檫@個(gè)交換過(guò)來(lái)的數(shù)，可能也不在正確的位置上，如果不處理它，往后遍歷時(shí)就把它忽略掉了。
最后再重新遍歷一次數(shù)組，只要某個(gè)位置i上存的數(shù)不是i+1，說(shuō)明是第一個(gè)缺失的數(shù)。如果都符合，那么缺失的數(shù)就是len+1。
class Solution {
public void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
public int firstMissingPositive(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
while (nums[i] >= 1 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
swap(nums, nums[i] - 1, i);
}
}
for (int i = 0; i < len; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return len + 1;
}
}
42. 接雨水
使用雙指針lo從左往右遍歷，hi從右往左遍歷。
leftMax記錄當(dāng)前左邊最高的柱子，rightMax記錄當(dāng)前右邊最高的柱子。
當(dāng)lo位置的柱子比hi位置的柱子高時(shí)，從右往左判斷，不斷更新rightMax值，只要hi對(duì)應(yīng)的柱子比rightMax小，那么一定可以在hi這根柱子上接到雨水。 接到的雨水大小為rightMax-height[hi]。
當(dāng)lo位置的柱子比hi位置的柱子矮時(shí)，從左往右判斷，不斷更新leftMax值，只要lo對(duì)應(yīng)的柱子比leftMax小，那么一定可以在lo這根柱子上接到雨水。接到的雨水大小為leftMax-height[lo]。
class Solution {
public int trap(int[] height) {
int lo = 0, hi = height.length - 1;
int leftMax = 0, rightMax = 0, res = 0;
while (lo < hi) {
if (height[lo] < height[hi]) {
if (height[lo] < leftMax) {
res += leftMax - height[lo];
} else {
leftMax = height[lo];
}
lo++;
} else {
if (height[hi] < rightMax) {
res += rightMax - height[hi];
} else {
rightMax = height[hi];
}
hi--;
}
}
return res;
}
}
45. 跳躍游戲 II
dp[i]代表從第i個(gè)位置出發(fā)，到達(dá)最后一個(gè)位置所需的最少步數(shù)。
邊界：
從最后一個(gè)位置出發(fā)，只需0步。
轉(zhuǎn)移方程：
從第i個(gè)位置出發(fā)，如果nums[i]等于0，那么不可能到達(dá)最后一個(gè)位置，令dp[i]等于-1，代表無(wú)法到達(dá)。
如果i+nums[i]大于等于最后一個(gè)位置，說(shuō)明一步可以到達(dá),dp[i] 等于1。
其余情況，遍歷從i位置出發(fā)可以到達(dá)的所有位置，只要其中某個(gè)位置j的dp值大于等于0，說(shuō)明從位置i出發(fā)也一定可以到達(dá)終點(diǎn)，且dp[i] = dp[j] +1。
我們需要找到能到達(dá)終點(diǎn)的dp[j]的最小值，再加上1就等于dp[i]。
最后返回dp[0]即可。
時(shí)間復(fù)雜度On2，空間復(fù)雜度On。
class Solution {
public int jump(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
dp[len - 1] = 0;
for (int i = len - 2; i >= 0; i--) {
if (nums[i] == 0) {
dp[i] = -1;//-1說(shuō)明無(wú)法到達(dá)
} else if (i + nums[i] >= nums.length - 1) {
dp[i] = 1;
} else {
int min = Integer.MAX_VALUE;
for (int j = i + 1; j <= i + nums[i]; j++) {
if (dp[j] > 0) {
min = Math.min(min, dp[j]);
}
}
if (min != Integer.MAX_VALUE) {
dp[i] = min + 1;
} else {
dp[i] = -1;
}
}
}
return dp[0];
}
}
優(yōu)化：
使用res記錄跳躍次數(shù)，end記錄跳躍次數(shù)增加的位置，maxPosition記錄當(dāng)前能到達(dá)的最遠(yuǎn)位置。初始都為0。
遍歷數(shù)組，不斷更新maxPosition，只要當(dāng)前到達(dá)了end位置，就使res加1。
然后end令為maxPosition。
最后一個(gè)位置不用遍歷，因?yàn)榈竭_(dá)終點(diǎn)之后就不用跳了。
class Solution {
public int jump(int[] nums) {
int end = 0, res = 0, maxPosition = 0;
for (int i = 0; i < nums.length-1; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]);
if (i == end) {
end = maxPosition;
res++;
}
}
return res;
}
}
48. 旋轉(zhuǎn)圖像
先進(jìn)行矩陣的轉(zhuǎn)置，再進(jìn)行列的翻轉(zhuǎn)。
class Solution {
public void transpose(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = i + 1; j < matrix.length; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
public void reverseCol(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
int lo = 0, hi = matrix[i].length - 1;
while (lo < hi) {
int temp = matrix[i][lo];
matrix[i][lo] = matrix[i][hi];
matrix[i][hi] = temp;
lo++;
hi--;
}
}
}
public void rotate(int[][] matrix) {
transpose(matrix);
reverseCol(matrix);
}
}
53. 最大子序和
簡(jiǎn)單動(dòng)態(tài)規(guī)劃題。
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 0) {
return 0;
}
int res = nums[0], pre = nums[0];
for (int i = 1; i < nums.length; i++) {
pre = Math.max(nums[i], pre + nums[i]);
res = Math.max(res, pre);
}
return res;
}
}
54. 螺旋矩陣
用LRUD代表左右上下四個(gè)邊界，不斷按螺旋遍歷即可。
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>();
int L = 0, R = matrix[0].length - 1, U = 0, D = matrix.length - 1;
while (true) {
for (int i = L; i <= R; i++) {
res.add(matrix[U][i]);
}
if (++U > D) {
break;
}
for (int i = U; i <= D; i++) {
res.add(matrix[i][R]);
}
if (--R < L) {
break;
}
for (int i = R; i >= L; i--) {
res.add(matrix[D][i]);
}
if (--D < U) {
break;
}
for (int i = D; i >= U; i--) {
res.add(matrix[i][L]);
}
if (++L > R) {
break;
}
}
return res;
}
}
