月度归档： 2022年5月

如果两个字符串 word1 和 word2 中从 'a' 到 'z' 每一个字母出现频率之差都 不超过 3 ，那么我们称这两个字符串 word1 和 word2 几乎相等 。

给你两个长度都为 n 的字符串 word1 和 word2 ，如果 word1 和 word2 几乎相等 ，请你返回 true ，否则返回 false 。

一个字母 x 的出现 频率 指的是它在字符串中出现的次数。

示例 1：

输入：word1 = "aaaa", word2 = "bccb"
输出：false
解释：字符串 "aaaa" 中有 4 个 'a' ，但是 "bccb" 中有 0 个 'a' 。
两者之差为 4 ，大于上限 3 。

示例 2：

输入：word1 = "abcdeef", word2 = "abaaacc"
输出：true
解释：word1 和 word2 中每个字母出现频率之差至多为 3 ：
- 'a' 在 word1 中出现了 1 次，在 word2 中出现了 4 次，差为 3 。
- 'b' 在 word1 中出现了 1 次，在 word2 中出现了 1 次，差为 0 。
- 'c' 在 word1 中出现了 1 次，在 word2 中出现了 2 次，差为 1 。
- 'd' 在 word1 中出现了 1 次，在 word2 中出现了 0 次，差为 1 。
- 'e' 在 word1 中出现了 2 次，在 word2 中出现了 0 次，差为 2 。
- 'f' 在 word1 中出现了 1 次，在 word2 中出现了 0 次，差为 1 。

示例 3：

输入：word1 = "cccddabba", word2 = "babababab"
输出：true
解释：word1 和 word2 中每个字母出现频率之差至多为 3 ：
- 'a' 在 word1 中出现了 2 次，在 word2 中出现了 4 次，差为 2 。
- 'b' 在 word1 中出现了 2 次，在 word2 中出现了 5 次，差为 3 。
- 'c' 在 word1 中出现了 3 次，在 word2 中出现了 0 次，差为 3 。
- 'd' 在 word1 中出现了 2 次，在 word2 中出现了 0 次，差为 2 。

提示：

• n == word1.length == word2.length
• 1 <= n <= 100
• word1 和 word2 都只包含小写英文字母。

哈希、统计

class Solution {
    public boolean checkAlmostEquivalent(String word1, String word2) {
        int n = word1.length();
        int[] count = new int[26];
        while (--n >=0){
            count[word1.charAt(n)-'a']++;
            count[word2.charAt(n)-'a']--;
        }
        for (int i : count) {
            if (i>3 || i<-3){
                return false;
            }
        }
        return true;
    }
}

给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi, yi) ，右上顶点是 (ai, bi) 。

如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。

示例 1：

输入：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
输出：true
解释：5 个矩形一起可以精确地覆盖一个矩形区域。 

示例 2：

输入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
输出：false
解释：两个矩形之间有间隔，无法覆盖成一个矩形。

示例 3：

输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
输出：false
解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。

提示：

• 1 <= rectangles.length <= 2 * 104
• rectangles[i].length == 4
• -105 <= xi, yi, ai, bi <= 105

依葫芦画瓢

class Solution {


    public boolean isRectangleCover(int[][] rectangles) {
        HashMap<String,Integer> hashMap = new HashMap<>();
        HashSet<String> hashSetSingle = new HashSet<>();
        int totalArea = 0;
        int[] bigRectangle = new int[]{Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MIN_VALUE,Integer.MIN_VALUE};
        for (int[] rectangle : rectangles) {
            int[][]fourPoints = getFourPoints(rectangle);
            totalArea += getArea(rectangle);
            bigRectangle[0] = Math.min(bigRectangle[0],rectangle[0]);
            bigRectangle[1] = Math.min(bigRectangle[1],rectangle[1]);
            bigRectangle[2] = Math.max(bigRectangle[2],rectangle[2]);
            bigRectangle[3] = Math.max(bigRectangle[3],rectangle[3]);
            for (int[] point : fourPoints) {
                String key = hash(point[0],point[1]);
                if (hashMap.containsKey(key)){
                    hashSetSingle.remove(key);
                }else{
                    hashSetSingle.add(key);
                }
                hashMap.put(key,hashMap.getOrDefault(key,0)+1);
            }
        }
        if (hashSetSingle.size() != 4){
            return false;
        }
        if (totalArea != getArea(bigRectangle)){
            return false;
        }
        int[][] bigFourPoints = getFourPoints(bigRectangle);
        for (int[] bigFourPoint : bigFourPoints) {
            if (!hashSetSingle.contains(hash(bigFourPoint[0],bigFourPoint[1]))){
                return false;
            }
        }
        for (String s : hashMap.keySet()) {
            if ( !hashSetSingle.contains(s) && hashMap.get(s)!=2 && hashMap.get(s)!=4 ){
                return false;
            }
        }
        return true;
    }

    private int[][] getFourPoints(int[] rectangle){
        return new int[][]{
                {rectangle[0],rectangle[3]},
                {rectangle[2],rectangle[3]},
                {rectangle[2],rectangle[1]},
                {rectangle[0],rectangle[1]}
        };
    }

    //哈希
    private String hash(int x, int y) {
        return x + "_" + y;
    }

    //面积
    public int getArea(int[] rectangle){
        return ( rectangle[2] - rectangle[0] ) *  ( rectangle[3] - rectangle[1] );
    }


}

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

提示：

• 0 <= num < 231

带注解，动态规划

动态规划题，其实思路还是比较简单的，只是当中的if/else判断条件啰嗦了点，算不上复杂

把各种情况都理清楚的话，本题还是相当好解的

1. 当前数字独立成字母
2. 如果前面是0或者大于2，当前数字只能独立成字母
3. 如果前面数字是1，当前数字可以独立成字母，也可以和前面的1组成字母
4. 如果前面的数字是2，如果当前数字小于等于5，可以独立成字母，也可以和前面的1组成字母
5. 如果前面的数字是2，如果当前数字大于5，当前数字只能独立成字母

各种情况的数量

1. 当前数字独立成字母的时候。数量继承dp[i-1]
2. 和前一位数字组成字母的时候，数量为 “独立成字母的dp[i-1]” + “和前一位组成字母的时候继承的前前一位的dp[i-2]”
3. 如果dp[i-2]不存在，不妨简单假设个情况25，应当是 [2,5] + [25]两种情况，那么可知不存在的时候的dp[i-2]的值应当为1
4. 初始边界条件一个数字的时候只能为1，即dp[0] = 1

class Solution {
    final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
            99999999, 999999999, Integer.MAX_VALUE };

    public int translateNum(int num) {
        if (num<10){
            return 1;
        }
        int size = numSize(num);
        //构建 num数字拆分出来的数组，便于用下标处理
        int[] arr = new int[size];
        int idx = arr.length;
        while (num > 0){
            arr[--idx] = num % 10;
            num /= 10;
        }
        int[] dp = new int[size];
        dp[0] = 1;
        while (++idx < size){
            //如果前一位是0，或者前一位大于2，当前位置只能独立组成字母
            if (arr[idx-1] == 0 || arr[idx-1]>2){
                dp[idx] = dp[idx-1];
                continue;
            }
            //如果前一位为1，当前位置可以和前一位组成  1X  表示一个字母，那么当前位置可以组成的情况为
            // 当前位置单独成字母的情况  dp[idx-1]  加上  和前一位一起组成字母的情况  dp[idx-2]
            if (arr[idx-1] == 1){
                dp[idx] = dp[idx-1] + (idx>1?dp[idx-2]:1);
                continue;
            }
            //如果前一位为2，
            if (arr[idx-1] == 2){
                if (arr[idx] > 5){
                    //如果当前位置大于5，只能独立成字母
                    dp[idx] = dp[idx-1];
                }else{
                    //如果当前位置小于等于5，可以和前一位组成一个新字母
                    dp[idx] = dp[idx-1] + (idx>1?dp[idx-2]:1);
                }
            }
        }
        return dp[dp.length-1];
    }

    public int numSize(int num){
        int i = -1;
        while (++i < sizeTable.length){
            if (sizeTable[i] >= num){
                return i+1;
            }
        }
        return -1;
    }
}

本题和91. 解码方法是一样的，我还记得当初第一次做91的时候时候要命的提交了十多次，隔了两个月现在这题也能一次通过了。

都没啥问题的话可以再尝试下639 解码方法 II

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"

示例 2:

输入: [3,30,34,5,9]
输出: "3033459"

提示:

• 0 < nums.length <= 100

说明:

• 输出结果可能非常大，所以你需要返回一个字符串而不是整数
• 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

愣了好久没看懂，反复思考下：堆排序

class Solution {
    final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
            99999999, 999999999, Integer.MAX_VALUE };

    public String minNumber(int[] nums) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                int size1 = stringSize(o1);
                int size2 = stringSize(o2);

                int join1 = o1;
                while (size2>0){
                    join1 *= 10;
                    size2--;
                }
                join1 += o2;
                int join2 = o2;
                while (size1>0){
                    join2 *= 10;
                    size1--;
                }
                join2 += o1;
                return join1 - join2;
            }
        });
        for (int num : nums) {
            queue.offer(num);
        }
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()){
            sb.append(queue.poll());
        }
        return sb.toString();
    }


    public int stringSize(int x) {
        for (int i=0; ; i++)
            if (x <= sizeTable[i])
                return i+1;
    }
}

初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。

第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。

找出并返回 n 轮后有多少个亮着的灯泡。

示例 1：

输入：n = 3
输出：1 
解释：
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 

你应该返回 1，因为只有一个灯泡还亮着。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：1

提示：

• 0 <= n <= 109

1. 1 个开着 1*2 个关着
2. 1 个开着 2*2 个关着
3. 1 个开着 3*2 个关着
4. 后续省略

class Solution {
    public int bulbSwitch(int n) {
        if (n < 1){
            return n;
        }
        int count = 0;
        int idx = -1;
        while (true){
            if (++idx < n){
                count++;
            }else{
                break;
            }
            if (idx+(count * 2) < n){
                idx += count*2;
            }else{
                break;
            }
        }
        return count;
    }
}

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

提示：

1. 节点总数 <= 10000

注意：本题与主站 104 题相同：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

深搜模板直接套用

1. dfs()方法返回当前节点下的最大深度
2. 如果当前节点有值，深度加1
3. 递归左右节点，返回左右节点的最大深度
4. 左右节点的最大深度中返回较大的那个

class Solution {

    public int maxDepth(TreeNode root) {
        if (root==null){
            return 0;
        }
        return dfs(root,0);
    }

    public int dfs(TreeNode node, int deep){
        if (node==null){
            return deep;
        }
        deep++;
        int left = dfs(node.left,deep);
        int right = dfs(node.right,deep);

        return Math.max(left,right);
    }
}

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入：nums = [3,4,3,3]
输出：4

示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：

• 1 <= nums.length <= 10000
• 1 <= nums[i] < 2^31

凑合，记录下没啥参考意义

class Solution {
    public int singleNumber(int[] nums) {
        int[] arrCount = new int[32];
        for (int num : nums) {
            int idx = 32;
            while (--idx>=0 && num > 0){
                arrCount[idx] += num%2;
                num >>= 1;
            }
        }
        int res = 0;
        for (int count : arrCount) {
            res <<= 1;
            res += count%3;
        }
        return res;
    }
}