【算法练习】leetcode算法题合集之数组和哈希表篇

本文主要是介绍【算法练习】leetcode算法题合集之数组和哈希表篇，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

重建数组（高频）

LeetCode283.移动零

双指针，记录已经处理好的序列的尾部

class Solution {public void moveZeroes(int[] nums) {int k = 0;for (int i = 0; i < nums.length; i++) {if (nums[i] != 0) {swap(nums, i, k);k++;}}}private void swap(int[] nums, int i, int k) {int tmp = nums[i];nums[i] = nums[k];nums[k] = tmp;}
}

Leetcode26. 删除有序数组中的重复项

思路是一样的，序列中是不重复的有序序列。

class Solution {public int removeDuplicates(int[] nums) {int k = 1;for (int i = 1; i < nums.length; i++) {if (nums[i] != nums[k - 1]) {swap(nums, i, k);k++;}}return k;}private void swap(int[] nums, int i, int k) {int tmp = nums[i];nums[i] = nums[k];nums[k] = tmp;}
}

双指针

剑指offer21.调整数组顺序使奇数位于偶数前面

一个指针向后，一个指针从尾部向前。i之前的元素都是奇数，j之后的元素都是偶数。

class Solution {public int[] trainingPlan(int[] actions) {int length = actions.length;int i = 0, j = length - 1;while (i < j) {while (i < j && actions[i] % 2 != 0) {i++;}while (i < j && actions[j] % 2 == 0) {j--;}swap(actions, i, j);}return actions;}private void swap(int[] actions, int i, int j) {int tmp = actions[i];actions[i] = actions[j];actions[j] = tmp;}
}

LeetCode11. 盛最多水的容器

使用双指针。更高的一方不动，调整矮的一方，使得整体的高度在上升。

class Solution {public int maxArea(int[] height) {int i = 0, j = height.length - 1;int res = 0;while (i < j) {if (height[i] < height[j]) {res = Math.max(res, height[i] * (j - i));i++;} else {res = Math.max(res, height[j] * (j - i));j--;}}return res;}
}

LeetCode1.两数之和

1. 两数之和

不能重复使用当下元素，有一个测试用例是这样的[3,2,4],6，由于索引为3的元素重复使用可以得到结果6.

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();int[] res = new int[2];for (int i = 0; i < nums.length; i++) {if (map.containsKey(target - nums[i])) {Integer index = map.get(target - nums[i]);res[0] = i;res[1] = index;break;}map.put(nums[i], i);}return res;}
}

LeetCode167. 两数之和 II - 输入有序数组

class Solution {public int[] twoSum(int[] numbers, int target) {int i = 0, j = numbers.length - 1;int[] res = new int[2];while (i < j) {int sum = numbers[i] + numbers[j];if (sum < target) {i++;} else if (sum > target) {j--;} else {res[0] = i + 1;res[1] = j + 1;break;}}return res;}
}

LeetCode15.三数之和

15. 三数之和

使用hash表来处理，无法避免重复数据。通过排序，使得重复元素只会使用一次。

三个数，第一个数遍历，第二个数和第三个数是i+1和nums.length - 1。并且要对重复元素进行过滤。

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length - 2; i++) {if (nums[i] > 0) {return res;}if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = nums.length - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum > 0) {right--;} else if (sum < 0) {left++;} else {res.add(Arrays.asList(nums[i], nums[left], nums[right]));while (left < right && nums[left] == nums[left + 1]) {left++;}while (left < right && nums[right] == nums[right - 1]) {right--;}left++;right--;}}}return res;}
}

LeetCode16.最接近的三数之和

排序+双指针。不需要对数组元素过滤重复元素。

class Solution {public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);int res = Integer.MAX_VALUE;for (int i = 0; i < nums.length - 2; i++) {int left = i + 1, right = nums.length - 1;while (left < right) {int sum = nums[left] + nums[right] + nums[i];if (Math.abs(res - target) > Math.abs(sum - target)) {res = sum;}if (sum > target) {right--;} else if (sum < target) {left++;} else {return sum;}}}return res;}
}

LeetCode88.合并两个有序数组

一下子就想到的方案就是比较，小的放入数组，但是会覆盖数组中的元素。

比较好的解决方案就是从后往前排，还有比较取巧的方法就是使用新数组存储。另外把数组2放到数组1的末尾，进行排序。

数组1的元素都用完了，还可以继续处理数组2的元素。

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p = m - 1;int q = n - 1;int tail = m + n - 1;while (p >= 0 || q >= 0) {if (p == -1) {nums1[tail] = nums2[q];q--;tail--;} else if (q == -1) {nums1[tail] = nums1[p];p--;tail--;} else if (nums1[p] > nums2[q]) {nums1[tail] = nums1[p];tail--;p--;} else {nums1[tail] = nums2[q];tail--;q--;}}}
}

LeetCode75. 颜色分类（*）

LeetCode75. 颜色分类

思路：将所有的2移动到最后，将所有的0移动到前面。

当移动2到最后的时候，进行交换。如果最后一个元素就是2，那么当前元素还是2，还需要和p2进行交换。

class Solution {public void sortColors(int[] nums) {int p0 = 0, p2 = nums.length - 1;for (int i = 0; i <= p2; i++) {while (i <= p2 && nums[i] == 2) {swap(nums, i, p2);p2--;}if (nums[i] == 0) {swap(nums, i, p0);p0++;}}}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

哈希表

LeetCode217. 存在重复元素

用Hash表来判重

class Solution {public boolean containsDuplicate(int[] nums) {HashSet<Integer> set = new HashSet<>();for (int i = 0; i < nums.length; i++) {if (set.contains(nums[i])) {return true;}set.add(nums[i]);}return false;}
}

LeetCode128.最长连续序列（**）

LeetCode128.最长连续序列

class Solution {public int longestConsecutive(int[] nums) {HashSet<Integer> set = new HashSet<>();for (int num : nums) {set.add(num);}int res = 0;int seq;for (int i = 0; i < nums.length; i++) {int num = nums[i];int next = nums[i] + 1;if (!set.contains(num - 1)) {seq = 1;while (set.contains(next)) {next++;seq++;}res = Math.max(res, seq);}}return res;}
}

原地哈希（*）

剑指offer03.数组中重复的数字

class Solution {public int findRepeatDocument(int[] documents) {for (int i = 0; i < documents.length;) {if (i == documents[i]) {i++;continue;}if (documents[i] == documents[documents[i]]) {return documents[i];}int tmp = documents[i];documents[i] = documents[tmp];documents[tmp] = tmp;}return -1;}
}

LeetCode41.缺失的第一个正数

将数值为正整数的数移动到对应的索引位置上，比如将数值为7的数字移动到索引为6的位置上。找到第一个索引和值不匹配的数据。

class Solution {public int firstMissingPositive(int[] nums) {for (int i = 0; i < nums.length; i++) {while (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]) {swap(nums, i, nums[i] - 1);}}for (int i = 0; i < nums.length; i++) {if (nums[i] - 1 != i) {return i + 1;}}return nums.length + 1;}private void swap(int[] nums, int index1, int index2) {int temp = nums[index1];nums[index1] = nums[index2];nums[index2] = temp;}
}

滑动窗口（*）

LeetCode209.长度最小的子数组

滑动窗口的题，理解起来还是比较简单的。但是重新上手有点困难。

大于等于target就符合要求，一旦符合要求，就尝试减去左边的字符。

    public int minSubArrayLen(int target, int[] nums) {int left = 0, len = nums.length;int ans = Integer.MAX_VALUE;int sum = 0;for (int right = 0; right < len; right++) {sum += nums[right];while (sum >= target) {ans = Math.min(right - left + 1, ans);sum -= nums[left];left++;}}return ans = ans == Integer.MAX_VALUE ? 0 : ans;}

LeetCode3. 无重复字符的最长子串

滑动窗口。使用set记录无重复的字符集合。当右边添加不进去的时候，尝试去减去左边的元素。

滑动窗口的关键，收缩窗口的条件。

class Solution {public int lengthOfLongestSubstring(String s) {int left = 0;int ans = 0;HashSet<Character> set = new HashSet<>();for (int right = 0; right < s.length(); right++) {while (set.contains(s.charAt(right))) {set.remove(s.charAt(left));left++;}set.add(s.charAt(right));ans = Math.max(right - left + 1, ans);}return ans;}
}

LeetCode76. 最小覆盖子串（**）

LeetCode76. 最小覆盖子串

记录有效字符的数量。ct.containsKey(c) && cs.get(c) <= ct.get(c)

删除字符串的左边字符。删除的条件，t没有当前字符或者cs中的字符个数大于t需要的字符数

当count满足条件的时候，且长度变小的时候，获取结果集。

class Solution {public String minWindow(String s, String t) {String ans = "";HashMap<Character, Integer> ct = new HashMap<>();for (int i = 0; i < t.length(); i++) {ct.put(t.charAt(i), ct.getOrDefault(t.charAt(i), 0) + 1);}HashMap<Character, Integer> cs = new HashMap<>();int left = 0;int count = 0;int len = Integer.MAX_VALUE;for (int right = 0; right < s.length(); right++) {char c = s.charAt(right);cs.put(c, cs.getOrDefault(c, 0) + 1);if (ct.containsKey(c) && cs.get(c) <= ct.get(c)) {count++;}while (left <= right && (!ct.containsKey(s.charAt(left))|| cs.getOrDefault(s.charAt(left), 0) > ct.getOrDefault(s.charAt(left), 0))) {cs.put(s.charAt(left), cs.getOrDefault(s.charAt(left), 0) - 1);left++;}if (count == t.length() && right - left + 1 < len) {ans = s.substring(left, right + 1);len = right - left + 1;}}return ans;}
}

旋转模拟

LeetCode48. 旋转图像

如果使用新的数组，这条题目主要难点就在于考察新旧数组的索引对应关系。新数组的 [0,0]来自于旧数组[0,2]，新数组的[0,1]来自于[1,0]。

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;int[][] res = new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {res[i][j] = matrix[n - 1 - j][i];}}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {matrix[i][j] = res[i][j];}}}
}

如果不使用新的数组，也是可以解决的。4个点一起旋转。[0,0]旋转到[0,2]，[0,2]旋转到[2,2]，[2,2]旋转到[2,0]，[2,0]旋转到[0,0]。另外考虑一下，如果n为奇数和偶数的区别。

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;//[0,3]-->[3,0]-->[4,3]for (int i = 0; i < (n + 1) / 2; i++) {for (int j = 0; j < n / 2; j++) {int tmp = matrix[i][j];matrix[i][j] = matrix[n - 1 - j][i];matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];matrix[j][n - 1 - i] = tmp;}}}
}

LeetCode54. 螺旋矩阵

使用定义边界，并且更新边界的方法。

class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> res = new ArrayList<>();int top = 0, left = 0, bottom = matrix.length - 1, right = matrix[0].length - 1;while (true) {for (int i = left; i <= right; i++) {res.add(matrix[top][i]);}if (++top > bottom) {break;}for (int i = top; i <= bottom; i++) {res.add(matrix[i][right]);}if (--right < left) {break;}for (int i = right; i >= left; i--) {res.add(matrix[bottom][i]);}if (--bottom < top) {break;}for (int i = bottom; i >= top; i--) {res.add(matrix[i][left]);}if (++left > right) {break;}}return res;}
}

LeetCode59.螺旋矩阵II

定义边界和num值。边界用来遍历数组，num值用来更新数组的元素值。

class Solution {public int[][] generateMatrix(int n) {int total = n * n;int[][] res = new int[n][n];int left = 0, right = n - 1, top = 0, bottom = n - 1;int num = 0;while (num < total) {for (int i = left; i <= right; i++) {res[top][i] = ++num;}top++;for (int i = top; i <= bottom; i++) {res[i][right] = ++num;}right--;for (int i = right; i >= left; i--) {res[bottom][i] = ++num;}bottom--;for (int i = bottom; i >= top; i--) {res[i][left] = ++num;}left++;}return res;}
}

LeetCode498.对角线遍历

i是斜线的个数，pos是记录结果数组的索引。

当斜线i==0，是向上的，偶数即向上；奇数向下。

class Solution {public int[] findDiagonalOrder(int[][] mat) {int m = mat.length, n = mat[0].length;int[] res = new int[m * n];int pos = 0;for (int i = 0; i < m + n - 1; i++) {//向上if (i % 2 == 0) {//x是行，y是列int x = i < m ? i : m - 1;int y = i < m ? 0 : i - m + 1;while (x < m && y >= 0) {res[pos] = mat[x][y];x--;y++;}} else {int x = i < n ? 0 : i - n + 1;int y = i < n ? i : n - 1;while (x < m && y >= 0) {res[pos] = mat[x][y];pos++;x++;y--;}}}return res;}
}

其他

Leetcode7. 整数反转

不断记录每一个位置上的数，并且判断是否超过最大值。

退出条件是x==0，可以避免个位数是0的情况。

class Solution {public int reverse(int x) {int res = 0;while (x != 0) {if (res > Integer.MAX_VALUE / 10 || res < Integer.MIN_VALUE / 10) {return 0;}int tmp = x % 10;res = res * 10 + tmp;x /= 10;}return res;}
}

Leetcode43. 字符串相乘

比字符串相加更难为人，2位数乘3位数，是5位数。另外，定义一个5位的数组存储数字。

class Solution {public String multiply(String num1, String num2) {if (num1.equals("0") || num2.equals("0")) {return "0";}int[] res = new int[num1.length() + num2.length()];for (int i = num1.length() - 1; i >= 0; i--) {int a = num1.charAt(i) - '0';for (int j = num2.length() - 1; j >= 0; j--) {int b = num2.charAt(j) - '0';int sum = res[i + j + 1] + a * b;res[i + j + 1] = sum % 10;res[i + j] += sum / 10;}}StringBuilder sb = new StringBuilder();for (int i = 0; i < res.length; i++) {if (i == 0 && res[i] == 0) {continue;}sb.append(res[i]);}return sb.toString();}
}

Leetcode169. 多数元素

投票法
Leetcode169. 多数元素

消除法，最后留下的一定是最多的元素。当然也可以用排序，获取中间的元素；用hashmap记录元素的个数。

class Solution {public int majorityElement(int[] nums) {int count = 0;Integer x = null;for (int num : nums) {if (count == 0) {x = num;}count += (x == num) ? 1 : -1;}return x;}
}

LeetCode31.下一个排列

123下一个排列是132,1234下一个排列是1243,13652下一个排列是15236。

class Solution {public void nextPermutation(int[] nums) {int i = nums.length - 2;while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}if (i >= 0) {int j = nums.length - 1;while (j >= 0 && nums[i] >= nums[j]) {j--;}swap(nums, i, j);}reverse(nums, i + 1);}private void reverse(int[] nums, int i) {int left = i, right = nums.length-1;while (left < right) {swap(nums, left, right);left++;right--;}}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}

LeetCode8. 字符串转换整数

LeetCode8. 字符串转换整数 (atoi)

获取符号位，计算有效数字位。如果有效数字位为0，返回结果0；

当获取的数是大于Integer最大值，获取的数就是最大值。正整数最大值是2147483647

class Solution {public int myAtoi(String s) {if (s.length() == -0) {return 0;}int i = 0;int sign = 1;while (s.charAt(i) == ' ') {i++;if (i == s.length()) {return 0;}}if (s.charAt(i) == '-') {sign = -1;}if (s.charAt(i) == '-' || s.charAt(i) == '+') {i++;}int res = 0;for (int j = i; j < s.length(); j++) {if (s.charAt(j) < '0' || s.charAt(j) > '9') {break;}if (res > Integer.MAX_VALUE / 10 || (s.charAt(j) > '7' && res == Integer.MAX_VALUE / 10)) {return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;}res = res * 10 + (s.charAt(j) - '0');}return res * sign;}}