LeetCode(28) -- 590, 594, 598

P590. N-ary Tree Postorder Traversal (Easy)

后序遍历

我的思路

基础题，把昨天的代码调整一下顺序即可。

我的代码

public class E_590_N_aryTreePostorderTraversal {
    List<Integer> res = new ArrayList<>();
    public List<Integer> postorder(Node root) {
        if (root == null) return res;
        for (Node child : root.children) {
            postorder(child);
        }
        res.add(root.val);
        return res;
    }
}

100%

最优解

class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> result = new ArrayList<>();
        postOrderTraversal(root, result);
        return result;
    }

    private void postOrderTraversal(Node root, List<Integer> result) {
        if (root == null) {
            return;
        }

        for (Node child: root.children) {
            postOrderTraversal(child, result);
        }
        result.add(root.val);
    }
}

只是把变量声明在给定的方法里了，然后递归用了一个辅助方法。

P594. Longest Harmonious Subsequence (Easy)

和谐数组它的最大值和最小值的差正好为1。给出一个数组，找出它的最长的子序列，满足这个子序列是一个和谐数组。注意：子序列是可以不连续的。

Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

我的思路

子序列很可能是动态规划题。可是仅知道前一个子序列，实际上并没办法决定这个数“要”还是“不要”。

答案

public class Solution {
    public int findLHS(int[] nums) {
        HashMap < Integer, Integer > map = new HashMap < > ();
        int res = 0;
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
            if (map.containsKey(num + 1))
                res = Math.max(res, map.get(num) + map.get(num + 1));
            if (map.containsKey(num - 1))
                res = Math.max(res, map.get(num) + map.get(num - 1));
        }
        return res;
    }
}

28%

遍历数组，用HashMap记录每个数出现的次数。与此同时，如果map中包含比它大1的数， 就把这两个相邻的数出现次数的和求出来，跟现有的结果res进行比较，把res更新为两者中较大的数。如果map中包含比它小1的数，也做相同的操作。

最优解

class Solution {
    public int findLHS(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        int cnt_1 = 1;
        int cnt_2 = 0;
        boolean flag = false;
        for (int i = 0; i < nums.length - 1; i ++) {
            if (nums[i + 1] - nums[i] == 0) {
                cnt_1 ++;
                res = cnt_2 == 0 ? res : Math.max(res, cnt_1 + cnt_2);
            }
            else if (nums[i + 1] - nums[i] == 1) {
                cnt_2 = cnt_1;
				cnt_1 = 1;
                res = Math.max(res, cnt_1 + cnt_2);
            } else {
                cnt_1 = 1;
                cnt_2 = 0;
            }
        }
        return cnt_2 == 0 ? res : Math.max(res, cnt_1 + cnt_2);
    }
}

排序后就很简单了。

P598. Range Addition II (Easy)

给一个m*n的矩阵，再给一个二维数组。这个数组的内层数组长度都是2。比如[[2,2],[3,3],[5,2]]. 这个二维数组代表一系列操作。比如[2,2]表示对矩阵中横坐标小于2，纵坐标小于2的数都加1。

求矩阵中最大数的个数。

我的思路

找出所有操作中横坐标的最小值和纵坐标的最小值。乘起来就是答案了。

我的代码

class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        int minX = m;
        int minY = n;
        for (int i = 0; i < ops.length; i++) {
            minX = Math.min(ops[i][0], minX);
            minY = Math.min(ops[i][1], minY);
        }
        return minX * minY;
    }
}

100%

最优解

class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        if (ops.length == 0){
            return m * n;
        }
        int length = ops[0][0];
        int breath = ops[0][1];

        for(int i = 1; i < ops.length; i++){
            length = Math.min(length, ops[i][0]);
            breath = Math.min(breath, ops[i][1]);
        }
        return length * breath;
    }
}

跟我的差不多。这题比较简单，没什么讨论的。