LeetCode(57) -- 64, 1099,

P64. Minimum Path Sum (Medium)

一个整数二维数组。找出从左上角到右下角所有数的和最小的一条路径。

我的思路

典型的动态规划。要点是一定不要从后往前递归，那样会有非常庞大的重复计算。要从左上向右下层层推进，每一步都已经算好了左边和上面的最小值，找到一个相对较小的，再加上本身，就是到达当前点的最小值。

我的代码

class Solution {
    public int minPathSum(int[][] grid) {
        int[][] memo = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (i == 0 && j == 0) {
                    memo[i][j] = grid[i][j];
                } else if (i == 0) {
                    memo[i][j] = memo[i][j-1] + grid[i][j];
                } else if (j == 0) {
                    memo[i][j] = memo[i-1][j] + grid[i][j];
                } else {
                    memo[i][j] = Math.min(memo[i-1][j], memo[i][j-1]) + grid[i][j];
                }
            }
        }
        return memo[grid.length-1][grid[0].length-1];
    }
}

90%

最优解

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0)
            return 0;
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        return dfs(grid, dp, m - 1, n - 1);
    }

    private int dfs(int[][] grid, int[][] dp, int m, int n) {
        if (m < 0 || n < 0)
            return Integer.MAX_VALUE;
        if (m == 0 && n == 0)
            return grid[0][0];

        if (dp[m][n] == 0)
            dp[m][n] = grid[m][n]
                    + Math.min(dfs(grid, dp, m - 1, n), dfs(grid, dp, m, n - 1));

        return dp[m][n];
    }
}

如果越界的话，就直接用最大的整数值挡在外面了。如果需要用到的数还没算过，就去算一下。时间复杂度应该和我是一样的。

P1099. Two Sum Less Than K (Easy))

在一个数组中，找出两个数的和小于K的最大的可能的值。

我的思路

一开始的思路：把所有数都存到一个hash数组里，然后每遇到一个数，用K减去这个数，从那个位置开始向下找，找到第一个数记下来。因为数的范围是1-1000，所以每次最多需要找1000次，而一共有100个数。所以这种办法非常慢。

我的代码

class Solution {
    public int twoSumLessThanK(int[] A, int K) {
        boolean[] set = new boolean[1000];
        for (int i : A) {
            set[i - 1] = true;
        }
        int s = -1;
        for (int i = 0; i < A.length; i++) {
            int j = K - A[i] - 1;
            while (j > 0) {
                if (j <= 1000 && j != A[i] && set[j-1]) {
                    s = Math.max(s, A[i] + j);
                    break;
                }
                j--;
            }
        }
        return s;
    }
}

12% 不要用这个方法，非常不好。

最优解

public class E_1099_TwoSumLessThanK {
    public int twoSumLessThanK(int[] A, int K) {
        Arrays.sort(A);
        int i = 0;
        int j = A.length - 1;
        int max = -1;
        while (i < j) {
            int sum = A[i] + A[j];
            if (sum < K) {
                max = Math.max(max, sum);
                i++;
            } else {
                j--;
            }
        }
        return max;
    }
}

先把数组排序。从两侧开始找。如果想让两个数的和最大，优先找最大的那个数，看有没有比较小的数能跟它匹配上。从两侧往中间“挤”的好处是，每次减小最大值是，前面所有的最小值都不需要再算了，因为比这个最大值更大的数都试过了，减小之后肯定更小，也就不用再试了。

P532. K-diff Pairs in an Array (Easy)

问一个数组里，有多少个不同的pair绝对值的差为k。

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

我的思路

当k等于0时，其实相当于问这个数组里有哪些数发生了重复；当k不等于0时，就检查一下以前出现过的数中，有没有跟当前这个数的绝对值差k的。

我的代码

class Solution {
    public int findPairs(int[] nums, int k) {
        if (k < 0) {
            return 0;
        }
        HashSet<Integer> set = new HashSet<>();
        HashSet<Integer> duplicate = new HashSet<>();
        int count = 0;
        for (int num : nums) {
            if (set.contains(num)) {
                duplicate.add(num);
            } else {
                if (set.contains(num + k)) {
                    count++;
                }
                if (set.contains(num - k)) {
                    count++;
                }
            }
            set.add(num);
        }
        if (k == 0) {
            return duplicate.size();
        }
        return count;
    }
}

80%

最优解

class Solution {
    public int findPairs(int[] nums, int k) {
        if (nums.length <=1 || k < 0) return 0;
        Arrays.sort(nums);
        int left = 0, right = 1, count =0;
        while (right < nums.length) {
            if (nums[right] - nums[left] > k)
                left++;
            else if (nums[right] - nums[left] < k || left == right)
                right++;
            else {
                count++;
                left++;
                right++;
                while(right < nums.length && nums[right] == nums[right - 1])
                    right++;
            }
        }
        return count;
    }
}

这个方法很妙，但一般情况下想不到。先排序，然后把两个指针前后调整，使它们的差为k。