【算法练习】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;
    }

}