LeetCode面试经典 150 题（Java题解）
一、数组、字符串
1、合并两个有序数组
从后往前比较，这样就不需要使用额外的空间
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int l = m+n-1, i = m-1, j = n-1;while(i >= 0 && j >= 0){if(nums1[i] >= nums2[j]){nums1[l--] = nums1[i--];}else{nums1[l--] = nums2[j--];}}while(i >= 0){nums1[l--] = nums1[i--];}while(j >= 0){nums1[l--] = nums2[j--];}}
}
2、移除元素
很巧妙的做法，使用到了数组拷贝
class Solution {public int removeElement(int[] nums, int val) {int n = nums.length;for(int i = 0; i < n; i++){if(nums[i] == val){System.arraycopy(nums, i+1, nums, i, n-i-1);// 有效数组长度-1n--;// 下标应该-1，这样才能对应后一个数字i--;}}return n;}
}
3、删除有序数组中的重复项
使用双指针，p指向不重复数组的最后一个元素，移动q寻找不重复元素。
class Solution {public int removeDuplicates(int[] nums) {if(nums == null || nums.length == 0)return 0;int p = 0, q = 1;while(q < nums.length){if(nums[p] != nums[q]){// 必须p先+1nums[++p] = nums[q];}q++;}return p+1;}
}
4、删除有序数组中的重复项 II
增加一个判断条件：重复元素个数小于等于2个时不用管，大于时删除
// class Solution {
// public int removeDuplicates(int[] nums) {
// if(nums == null || nums.length == 0)return 0;
// int p = 0, q = 1, cnt = 1;
// while(q < nums.length){
// if(nums[p] != nums[q]){
// nums[++p] = nums[q++];
// cnt = 1;
// }else if(nums[p] == nums[q] && cnt < 2){
// nums[++p] = nums[q++];
// cnt++;
// }else{
// q++;
// }
// }
// return p+1;
// }
// }// 化简后的代码
class Solution {public int removeDuplicates(int[] nums) {if(nums == null || nums.length == 0) return 0;int p = 0, q = 1, cnt = 1;while(q < nums.length) {if(nums[p] != nums[q] || cnt < 2) {cnt = nums[p] != nums[q] ? 1 : cnt + 1;nums[++p] = nums[q++];} else {q++;}}return p+1;}
}
5、多数元素
使用哈希表
class Solution {public int majorityElement(int[] nums) {Map<Integer, Integer> map = new HashMap<>();for(int n : nums){map.put(n, map.getOrDefault(n, 0)+1);}for(int n : nums){if(map.get(n) > nums.length/2)return n;}return 0;}
}
使用Boyer-Moore 投票算法
class Solution {public int majorityElement(int[] nums) {int cnt = 0, ans = 0;for(int num : nums){// 更新候选数if(cnt == 0)ans = num;cnt += ans == num ? 1 : -1;}return ans;}
}
二、双指针
1、验证回文串
方法1：先去掉非数字字母字符，再使用双指针判断
class Solution {public boolean isPalindrome(String s) {StringBuilder sb = new StringBuilder();for(char c : s.toCharArray()){if(Character.isLetter(c)){sb.append(Character.toLowerCase(c));}else if(Character.isDigit(c)){sb.append(c);}}char[] arr = sb.toString().toCharArray();int i = 0, j = arr.length-1;while(i < j){if(arr[i] != arr[j])return false;i++;j--;}return true;}
}
方法2：在原字符串中直接判断，不需要使用额外的空间
class Solution {public boolean isPalindrome(String s) {int l = 0, r = s.length()-1;while(l < r){while(l < r && !Character.isLetterOrDigit(s.charAt(l)))l++;while(l < r && !Character.isLetterOrDigit(s.charAt(r)))r--;if(l < r){if(Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))return false;l++;r--;}}return true; }
}
2、判断子序列
class Solution {public boolean isSubsequence(String s, String t) {int m = s.length(), n = t.length();int i = 0, j = 0;while (i < m && j < n) {if (s.charAt(i) == t.charAt(j))i++;j++;}return i == m;}
}
3、 两数之和 II - 输入有序数组
注意返回的下标从1开始
class Solution {public int[] twoSum(int[] numbers, int target) {int l = 0, r = numbers.length-1;while(l < r){int sum = numbers[l] + numbers[r];if(sum == target){return new int[]{l+1, r+1};}else if(sum > target){r--;}else{l++;}}return new int[]{l+1, r+1};}
}
4、盛最多水的容器
方法一：头尾双指针进行移动，哪边高度低移动哪边
class Solution {public int maxArea(int[] height) {int l = 0, r = height.length-1;int max = Integer.MIN_VALUE;while(l < r){max = Math.max(max, Math.min(height[l], height[r])*(r-l));if(height[l] < height[r]){l++;}else{r--;}}return max;}
}
方法二：也是双指针，但移动条件是 移动比上一次最低的边还要低或相等的边
class Solution {public int maxArea(int[] height) {int l = 0, r = height.length-1;int max = Integer.MIN_VALUE;while(l < r){// 记录上一次最低的边int cur = Math.min(height[l], height[r]);max = Math.max(max, cur*(r-l));while(l < r && height[l] <= cur){l++;}while(l < r && height[r] <= cur){r--;}}return max;}
}
5、三数之和
排序+双指针：先排序，再固定住第一个数字，使用两数之和寻找另外两个数字。
class Solution {public List<List<Integer>> threeSum(int[] nums) {// 先排序Arrays.sort(nums);int n = nums.length;List<List<Integer>> ans = new ArrayList<>();for(int i = 0; i < n-2; i++){// 重复的数字跳过if(i > 0 && nums[i] == nums[i-1])continue;int l = i+1, r = n-1, target = -nums[i];// 两数之和while(l < r){int sum = nums[l]+nums[r];if(sum == target){ans.add(Arrays.asList(nums[i], nums[l], nums[r]));// 重复的数字跳过while(l < r && nums[l] == nums[l+1])l++;l++; // 没有重复数字时也需要移动到下一位// 重复的数字跳过while(l < r && nums[r] == nums[r-1])r--;r--;}else if(sum > target){r--;}else{l++;}}}return ans;}
}