2021 5月力扣刷题

五月一日：690.员工的重要性

发现用哈希表做的还是不熟，看了一下普通递归思路，这个比较好理解。这段时间看完设计模式和sql，就去看剑指offer，容器还是用少了，不太熟。

题目：https://leetcode-cn.com/problems/employee-importance/

参考：https://leetcode-cn.com/problems/employee-importance/solution/java-di-gui-by-jonnyhuang-kcyy/

/*
// Definition for Employee.
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
};
*/

class Solution {
    int sum=0;
    public int getImportance(List<Employee> employees, int id) {
        //foreach遍历list
        for(Employee e : employees){
            //找到Employee.id和输入id一样的Employee
            if(e.id==id){
                sum += e.importance;//统计重要度
                //对下属遍历
                for(int i : e.subordinates){
                    getImportance(employees,i);//还是执行getImportance进行递归，还是对整个list遍历，所以用employees
                }        
            }
        }
        return sum;
    }
}

五月二日：554.砖墙

今天还是学习官方解答思路，哈希做少了，确实自己看到题后没啥想法。

题目：https://leetcode-cn.com/problems/brick-wall/

参考：https://leetcode-cn.com/problems/brick-wall/solution/zhuan-qiang-by-leetcode-solution-2kls/

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(List<Integer> list : wall){
            int len=list.size();//list相当于数组即每层砖墙
            int sum=0;
            //i<len-1，依题意，最后一位不算缝隙
            for(int i=0;i<len-1;i++){
                sum += list.get(i);//按题意转换，如数组1，缝隙便是1、1+2、1+2+2，即1、3、5，这里通过累加来算缝隙。
                map.put(sum, map.getOrDefault(sum,0)+1);//将缝隙的值存入键，值对应缝隙出现过的次数。
            }
        }
        int max_count=0;//出现最多的缝隙的次数
        //使用Entry遍历map，entrySet()返回map键值关系的映射关系
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            max_count = Math.max(max_count,entry.getValue());//更新max_count,将每个缝隙出现的次数进行max比较
        }
        return wall.size()-max_count;//将list数组的总数 - 最多出现的缝隙次数 = 穿过最少的砖块数
    }
}

五月三日：7.整数反转

我看到题后想到的就是转成字符串，然后倒序输出，然后写着写着就发现卡住了，原因是我还只会将int存入string然后反向遍历，后来查了下StringBuild的reverce()函数便可实现反转，String、StringBuffer、StringBuilder这里面后两个我还是关注少了。绕了一圈还是去看了三叶姐的题解，好家伙直接数学思维搞定，我还是太菜了完全没想到😭。

题目：https://leetcode-cn.com/problems/reverse-integer/

参考：https://leetcode-cn.com/problems/reverse-integer/solution/gong-shui-san-xie-yi-ti-shuang-jie-bu-wa-3cuj/

/*
题意即反转数据为int型，4字节32位，超过32位则返回0，且不能使用8字节64位的long类型。
1、当我们使用int时，遇到超过int溢出数据则要自行判断。
2、若可以使用long时，则计算时不用判断，在返回位转型时判断即可。
*/
//解法1，符合题意的方法
class Solution {
    public int reverse(int x) {
        int res=0;
        //x=0，即在循环中x/10=0，说明个位数也取完了，终止循环。
        while(x!=0){
            if(res>0 && res > (Integer.MAX_VALUE-(x%10))/10 ) return 0;//当x为正数时，res*10 + x%10 > Ingeter;此时反转数据若超过int上界限则返回0。
            if(res<0 && res < (Integer.MIN_VALUE-(x%10))/10 ) return 0;//当x为负数时，res*10 + x%10 < Ingeter;此时反转数据若超过int下界限则返回0。
            res = res*10 + x%10;//两种溢出情况均排除后进行反转，res*10即表示依次按个、十、百位前进，x%10表示取x当前末位。
            x/=10;//更新x，int/10会直接舍去余数，即当前末位。方便下次取余。
        }   
         return res;   
    }
}
//解法2，使用long取巧
class Solution {
    public int reverse(int x) {
        long res=0;
        while(x!=0){
			res = res*10 + x%10;
            x/=10;
        }
        return (int)res = res ? (int)res : 0 ;//使用long在返回值处判断，当转int型和原数据相等时返回结果，说明此时未溢出int数据界限，当不相等时即发生了溢出返回0。   
    }
}

五月四日：1473.粉刷房子 3

今天直接瘫了，困难真顶不住，为了拿章子就ctrl v了。。。。。

参考：https://leetcode-cn.com/problems/paint-house-iii/solution/fen-shua-fang-zi-iii-by-leetcode-solutio-powb/

五月五日：740.删除并获得点数

今天题目用到dp。。。。。只能看懂题意，自行分析了但没法写。

参考：https://leetcode-cn.com/problems/delete-and-earn/solution/gong-shui-san-xie-zhuan-huan-wei-xu-lie-6c9t0/

五月六日：1720.解码异或后的数组

太简单了，那今天就补充一下异或相关的应用。

题目：https://leetcode-cn.com/problems/decode-xored-array/

//属实简单，了解异或即可
class Solution {
    public int[] decode(int[] encoded, int first) {
        int n=encoded.length;
        int[] arr = new int[n+1];
        arr[0]=first;
        for(int i=0;i<n;i++){
/*
encoded[i] = arr[i] ^ arr[i+1] 原题意
encoded[i] ^ arr[i] = arr[i+1] ^ arr[i] ^ arr[i] = arr[i+1]
arr[i+1] = encoded[i] ^ arr[i]
*/
            arr[i+1] = encoded[i] ^ arr[i];
        }
        return arr;
    }
}

异或：异或是按位运算符，即先将数据转换为二进制，然后在对每一位进行计算，其中同0、同1为0，01相异为1。

0^0=1^1=0	0^1=1^0=1
一般运用：
a^a=0;
a^0=a;
a^b=b^a;//交换
a^b^b=a;//题目中有用此转换

以后写ab两数交换也可换成异或来写：
a=a^b;
b=a^b;//b=(a^b) ^ b = a
a=a^b;//a=(a^b) ^ a = b

五月七日：1486.数组异或操作

简单没啥说的。

题目：https://leetcode-cn.com/problems/xor-operation-in-an-array/

class Solution {
    public int xorOperation(int n, int start) {
        int[] nums = new int[n];
        int res=0;
        for(int i=0;i<n;i++){
            res^=start + 2*i;
        }
        return res;
    }
}

五月八日：1723.完成所有工作的最短时间

困难直接爬了，贴一个宫水姐姐的题解。。。

参考：https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/solution/gong-shui-san-xie-yi-ti-shuang-jie-jian-4epdd/

五月九日：1482.制作m束花所需的最少天数

？？？怎么又难回去了

参考：https://leetcode-cn.com/problems/minimum-number-of-days-to-make-m-bouquets/solution/xiao-ming-chong-hua-by-xiaohu9527-5jf6/

五月十日：872.叶子相似的树

看到题感觉很简单，中序遍历记下叶子结点，然后在判断两个树的叶子结点是否相同即可，结果写好后半天跑不出来。对着三叶大佬改正了一下错误。

题目：https://leetcode-cn.com/problems/leaf-similar-trees/

参考：https://leetcode-cn.com/problems/leaf-similar-trees/solution/gong-shui-san-xie-yi-ti-shuang-jie-di-gu-udfc/

修改前

class Solution {
    List<Integer> list1 = new ArrayList<Integer>();
    List<Integer> list2 = new ArrayList<Integer>();
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        inorder1(root1);
        inorder2(root2);
        //主要是这一步错了，list不能直接判断，需要循环判断，且用equals()方法
        if(list1 == list2)
            return true;
        return false;
    }
    //这里很蠢，可以在inorder方法内多写一个list参数来分别树，结果自己写了两遍中序遍历。。。
    void inorder1(TreeNode root){
        if(root == null) return;
        inorder1(root.left);
        if((root.left == null) && (root.right == null)) list1.add(root.val);
        inorder1(root.right);
    }
    void inorder2(TreeNode root){
        if(root == null) return;
        inorder2(root.left);
        if((root.left == null) && (root.right == null)) list2.add(root.val);
        inorder2(root.right);
    }
}

修改后

class Solution {
    List<Integer> list1 = new ArrayList<>();
    List<Integer> list2 = new ArrayList<>();
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        inorder(root1,list1);
        inorder(root2,list2);
        if(list1.size() == list2.size()){
            for(int i=0;i<list1.size();i++){
                //元素逐个比较，有不相等则false
                if(!list1.get(i).equals(list2.get(i))) return false;
            }
            return true;
        }
        
        return false;
    }
    void inorder(TreeNode root,List<Integer> list){
        if(root == null) return;
        if(root.left == null && root.right == null) {
            list.add(root.val);
            return;
        }
        inorder(root.left,list);
        inorder(root.right,list);
    }
}

今日小结：

• root.left && root.right == null 其中&&不能连接两个树结点。
  正确写法：root.left == null && root.right == null

• inorder方法用于多个表时，可加入list参数，要学会灵活使用语言。

• 两个list判断相等，要用循环判断，不能直接判断。

五月十一日：1734.解码异或后的排序

说实话题意没解释清除，看了一下别人的分析才明白，其实算是一个数学题。

题目：https://leetcode-cn.com/problems/decode-xored-permutation/

//题意是取前n个正整数（1、2、3···n），然后乱序排成perm数组计算出encoded数组。
//重点在于求首位数，算是数学问题。
class Solution {
    public int[] decode(int[] encoded) {
        int n = encoded.length;
        int[] perm = new int[n+1];
        int perm_sum=0,encoded_sum=0;
        //求前n个数的异或和，1^2^3···^n
        for(int i=1;i<=n+1;i++){
            perm_sum^=i;
        }
    /*
    *perm[0]^perm[1]=encode[0];
    *！！！perm[1]^perm[2]=encode[1];！！！
    *perm[2]^perm[3]=encode[2];
    *！！！perm[3]^perm[4]=encode[3];！！！
    *因为n为奇数，encoded数组必有偶数个数
    *其中encoded偶数项的和 = 除去perm[0]后剩下数的和
    *计算出encoded偶数和再与n个数的和异或，即可得到perm首位数
    *然后用之前简单题的方法就能做了
    */
        //计算encoded偶数项的和
        for(int i=1;i<n;i+=2){
            encoded_sum^=encoded[i];
        }

        perm[0] = perm_sum^encoded_sum;
        for(int i=0;i<n;i++){
            perm[i+1] = perm[i] ^ encoded[i];
        }
        return perm;
    }
}

五月十二日：1310.子数组异或查询

简单题，双循环秒了😂。

看了下三叶的题解，有种方法运用了异或的技巧（前缀和），很巧妙的使时间复杂度到了O(n+len)。

使用前缀和直接2ms，双循环700ms左右。

题目：https://leetcode-cn.com/problems/xor-queries-of-a-subarray/

优化参考：https://leetcode-cn.com/problems/xor-queries-of-a-subarray/solution/gong-shui-san-xie-yi-ti-shuang-jie-shu-z-rcgu/

暴力破解：

//我一开始还测试了半天二维数组，用的少，还以为length函数用不了
class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        int len = queries.length;
        int[] ans = new int[len];
       
        for(int i=0;i<len;i++){
            int start = queries[i][0];
            int end = queries[i][1];
            int res = 0;
            for(int k=start;k<=end;k++){
                res ^= arr[k];
            }
            ans[i] = res;
        }
        return ans;
    }
}

优化（前缀和）：

class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        int len = queries.length;
        int n = arr.length;
        int[] sum = new int[n+1];
        int[] ans = new int[len];

/*
 *这里用到了前缀和，因为同一个数异或两次就不见了。
 *所以将0~start-1的和，与0~end和异或，得到start~end的异或
 *后面start、end初值看起来有点怪是为了和sum对应。
 *start-1=i=0就不循环为初值0。
 *只能说前缀和太妙了！！
 */
        for(int i=1;i<=n;i++)
            sum[i] = sum[i-1]^arr[i-1];//n+1位，最后一位没有值，+1是为了辅助计算。毕竟没有初值。
        for(int i=0;i<len;i++){
            int start = queries[i][0]+1;
            int end = queries[i][1]+1;//设置start，end，注意end的值，我们是用来计算前缀和的。要和sum对应，+1后才是正确下标
            ans[i] = sum[start-1] ^ sum[end];
        }
        return ans;
    }
}

五月十三日：1269.停在原地的方案数

动态规划找个时间好好看看，现在遇到dp就倒了。

参考： https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/solution/gong-shui-san-xie-xiang-jie-xian-xing-dp-m9q9/

五月十四日：12.整数转罗马数字

题目：https://leetcode-cn.com/problems/integer-to-roman/

优化参考：https://leetcode-cn.com/problems/integer-to-roman/solution/gong-shui-san-xie-12-zheng-shu-zhuan-luo-b9kw/

普通写法：

class Solution {
    public String intToRoman(int num) {
        int K = num/1000;  num = num%1000;
        int H = num/100;  num = num%100;
        int TEN = num/10;
        int IND = num%10;

        String ans = "";
        for(int i=0;i<K;i++)  ans += "M";
        
        if(H==9)  ans += "CM";
        else if(H<9 && H>=5){
            ans += "D";
            for(int i=0;i<H-5;i++) ans += "C";
        }
        else if(H==4)  ans += "CD";
        else if(H<4)  for(int i=0;i<H;i++) ans += "C";

        if(TEN==9)  ans += "XC";
        else if(TEN<9 && TEN>=5){
            ans += "L";
            for(int i=0;i<TEN-5;i++) ans += "X";
        }
        else if(TEN==4)  ans += "XL";
        else if(TEN<4)  for(int i=0;i<TEN;i++) ans += "X";    

        if(IND==9)  ans += "IX";
        else if(IND<9 && IND>=5){
            ans += "V";
            for(int i=0;i<IND-5;i++) ans += "I";
        }
        else if(IND==4)  ans += "IV";
        else if(IND<4)  for(int i=0;i<IND;i++) ans += "I";
        
        return ans;    
    }
}

五月十五日：13.罗马数字转整数

有思路但数据存放不知道用什么，看了下评论区便学习使用了哈希表。

题目：https://leetcode-cn.com/problems/roman-to-integer/

class Solution {
    public int romanToInt(String s) {
        int sum=0;
        //用哈希表键值对存放数值
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);
        char[] n = s.toCharArray();
        for(int i=0;i<n.length;i++){
            //IV、IX这种，就先减I再加V、X
            //也就是小数在大数前就先减小数，大数顺序排列则累加
            if(i<n.length-1 && map.get(n[i])<map.get(n[i+1]) )
                sum -= map.get(n[i]);
            else sum += map.get(n[i]);
        }
        return sum;
    }
}

五月十六日：421.数组中两个数的最大异或值

暴力破解在超时的边缘摩擦。。。代码太丢人不贴了。

题目：https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/

五月十七日：993.二叉树的堂兄弟结点

这题真的有思路，就是写着写着就来了点小问题，还在那想着用list😭。跟着评论区打了一遍。发现思路没问题，但是使用什么方法出了点岔子。。。

题目：https://leetcode-cn.com/problems/cousins-in-binary-tree/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int x_fa,y_fa,x_dep,y_dep;
    public boolean isCousins(TreeNode root, int x, int y) {
        inorder(root.left,root.val,1,x,y);
        inorder(root.right,root.val,1,x,y);
        return x_fa!=y_fa && x_dep==y_dep;  
    }
    void inorder(TreeNode root, int father, int depth, int x, int y){
        if(root==null) return;
//先判断子结点在更新结点，所以当子结点和数值相等时，现在的结点值便是其父结点。
        if(root.val == x){
            x_fa=father;
            x_dep=depth;
        }else if(root.val == y){
            y_fa=father;
            y_dep=depth;
        }else{
            inorder(root.left,root.val,depth+1,x,y);
            inorder(root.right,root.val,depth+1,x,y);  
        } 
    }
}

五月十八日：1442.形成两个异或相等数组的三元组数目

今天还是有向前缀和的方法靠，然后发现有些细节没想清除。看完题解后发现评论区还有针对异或特性的优化，属实把异或玩明白了。

题目：https://leetcode-cn.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/

参考（评论区有优化）：https://leetcode-cn.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/solution/gong-shui-san-xie-xiang-jie-shi-yong-qia-7gzm/

基础写法：

class Solution {
    public int countTriplets(int[] arr) {
        int n=arr.length;
        int[] sum = new int[n+1];
        for(int i=1;i<=n;i++)
        //方便前缀和计算，就可以直接按题意写。若从i=0开始，则有所改动
            sum[i]=sum[i-1] ^ arr[i-1];
        int ans = 0;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                for(int k=j;k<=n;k++){
                    int a=sum[i-1] ^ sum[j-1];//前缀和计算i~j-1
                    int b=sum[j-1] ^ sum[k];//前缀和计算j~k
                    if(a==b) ans++;
                }
            }
        }
        return ans;
    }
}

异或特性优化：

sum[i-1] ^ sum[j-1]是 i到j-1的异或和；sum[j-1] ^ sum[k]是 j-1到k的异或和

注意前一个都是n-1，因为前缀和的特性想有n的值，要使用n-1的异或和来算，然后又a==b

sum[i-1] ^ sum[j-1]==sum[j-1] ^ sum[k]

sum[i-1] ^ sum[j-1] ^ (sum[j-1] ^ sum[k]) == sum[j-1] ^ sum[k] ^ (sum[j-1] ^ sum[k])

sum[i-1] ^ sum[k] == 0，即i~k的异或和

所以便可转化为求 i到k异或和，然后要注意，每次判定 i到k的异或和==0，而此时的j可以取i<j<=k中的任一个数，所以j有k-i种取法，所以每次循环统计三元组时要+(k-i)，而非+1。

class Solution {
    public int countTriplets(int[] arr) {
        int ans=0;
/*
 *先学习普通前缀和，然后在进行优化
 *普通前缀和可利用异或的特性来优化
 *sum[i-1]^sum[j-1]==sum[j-1]^sum[k]
 *两边同时异或sum[j-1]^sum[k]
 *sum[i-1]^sum[k] == 0，i~k异或和
 *所以就有i~k的异或和=0便是我们要的a==b判定条件
 *然后j可以取i<j<=k,即k-i中的任一个数
 *所以每判定成功一次会有k-i种三元组
 */
        for(int i=0;i<arr.length;i++){
            int sum=0;
            for(int k=i;k<arr.length;k++){
                sum^=arr[k];
                if(sum==0) ans+=(k-i);//j可取i<j<=k,有k-i种取法
            }
        }
        return ans;
    }
}

五月十九日：1738.找出第K大的异或坐标值

看了题解用比较暴力的方法做出来了。这次题解有图讲的很清楚。

题目：https://leetcode-cn.com/problems/find-kth-largest-xor-coordinate-value/

参考：https://leetcode-cn.com/problems/find-kth-largest-xor-coordinate-value/solution/xin-shou-pian-qian-ru-shen-chu-xi-lie-er-uwny/

class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        int n = matrix.length,m=matrix[0].length;
        //计算矩阵横向异或
        for(int i=0;i<n;i++){
            for(int j=1;j<m;j++){
                matrix[i][j] ^= matrix[i][j-1];
            }
        }
        //计算纵向异或，最后矩阵的每个元素都会更新为异或的结果
        for(int j=0;j<m;j++){
            for(int i=1;i<n;i++){
                matrix[i][j] ^= matrix[i-1][j];
            }
        }
        //对所有的异或结果排序，输出第k个
        int[] num = new int[m*n];
        int a=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                num[a]=matrix[i][j];
                a++;
            }
        }
        Arrays.sort(num);
        //sort排序是升序，所以要求倒数第k个数
        int ans = m*n+1-k;//倒数第k个数
        return num[ans-1];//因为是数组从0开始，倒数第k个数还要-1
    }
}

五月二十日：692.前K给高频单词

今天直接g了。。。。。

参考：https://leetcode-cn.com/problems/top-k-frequent-words/solution/qian-kge-gao-pin-dan-ci-by-leetcode-solu-3qk0/

五月二十一日：1035.不相交的线（今日两题）

今天算是给动态规划开荒了，看了题解的建议便先去学了一下最长公共子序列，分析果然是一个类型的，这题甚至都不用改公共子序列的代码。

最长公共子序列我另开一篇经典算法题。

题目：https://leetcode-cn.com/problems/uncrossed-lines/

参考：https://leetcode-cn.com/problems/uncrossed-lines/solution/bu-xiang-jiao-de-xian-by-leetcode-soluti-6tqz/

/*
 *和1143.最长公共子序列不能说相似，只能说是一模一样
 *还是动态规划模拟二维数组来做，因为数组不易插入，这里使用偏移来做。
 */
class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2){
        int n=nums1.length,m=nums2.length;
        int[][] f=new int[n+1][m+1];
        for(int i=1;i<n+1;i++){
            for(int j=1;j<m+1;j++){
                //f[0][0]二维数组的第一行和第一列会默认初始化为0
                //这里i-1、j-1是二维数组对应nums数组的相对值要-1
                if(nums1[i-1] == nums2[j-1]) f[i][j]=f[i-1][j-1]+1;
                else f[i][j]=Math.max(f[i-1][j],f[i][j-1]);
            }
        }
        return f[n][m];
    }
}

五月二十二日：810.黑板异或游戏

妥妥的数学思维题。
解题关键是理解啥情况下A会赢，注意A是先手。

• 1、A是先手，若数组最初异或和=0，A直接赢，此时和奇偶无关。所以后续不再讨论初始异或和=0的情况
• 2、数组为偶数A必赢，也就是先手偶数必赢：
  因为异或特性，两个相同数异或=0，所以当数组为偶数时，必有偶数个数不同（假设有两个不同数x、y），此时A先手拿一个不同数x，数组变为奇数，B若拿y则A赢（下一轮到A时异或和=0），所以B不会拿y而是拿其他成对的相同数，A随后也会拿成对的相同数，相同数会一对对的消失，到最后只会剩下一个y留给B拿。
• 3、数组为奇数，A必输，除非一开局异或和=0。
• 综上：A先手，数组=偶数必赢；数组=奇数必输，除了开局异或和=0。

class Solution {
    public boolean xorGame(int[] nums) {
        int n=nums.length,sum=0;
        if(n%2 == 0) return true;
        for(int x : nums) sum^=x;
        return sum == 0;
    }
}

五月二十三日：1707.与数组中元素的最大异或值

shit，说是要前缀树基础就先去学了前缀树（第208题），回来发现还是不会。。

构造前缀树就写经典算法里面了。早上周赛还忘了，剩9分钟才上去做第一题结果，做完发现已经结束了。。。

参考：https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array/solution/gong-shui-san-xie-jie-zhe-ge-wen-ti-lai-lypqr/

五月二十四日：664.奇怪的打印机

连续三天困难。。。。。不过今天的勉强看懂了。看的官方题解，主要还是动态规划倒推思路。三叶姐姐的题解今天硬是没看懂😥

题目：https://leetcode-cn.com/problems/strange-printer/

参考：https://leetcode-cn.com/problems/strange-printer/solution/qi-guai-de-da-yin-ji-by-leetcode-solutio-ogbu/

class Solution {
    public int strangePrinter(String s) {
        int n=s.length();
        int[][] f=new int[n+1][n+1];
        /*
         *枚举所有结果，区间左端点l从末位最大值取起,区间右端点r则相对l从区间最小值取起。
         *末位取左端点l是为了方便拆分区间时，f[l][k]和f[k+1][r]都是已计算过，
         *因为倒叙计算k在l前面已经先算过了，这就是为什么要从末位取值的原因
         */
        //区间左端点，n-1最后一位一直倒序遍历到0第一位
        for(int l=n-1;l>=0;l--){
            f[l][l]=1;//初始化，单独打印一个字符肯定只打印1次
            //区间右端点，总是相对左端点来取值，原来遍历当前区间，从l+1开始
            for(int r=l+1;r<n;r++){
                //当左端点==右端点，首尾相等，说明首尾可以一起打印，故不用考虑最后一位
                //f[l][r]=f[l][r-1]，例子：aba
                if(s.charAt(l) == s.charAt(r))
                    f[l][r]=f[l][r-1];
                else{
                    //设一个最大值，然后再对比着取min，最后将min赋给f[l][r]
                    int min=Integer.MAX_VALUE;
                    /*
                     *此处是将区间分段，因为区间首尾不等，只能遍历所有区间分段情况来选取其中最小的情
                     *况，注意l<=k<r，k从左端点取起.
                     */
                    for(int k=l;k<r;k++)
                        min=Math.min(min,f[l][k]+f[k+1][r]);
                    f[l][r]=min;
                }
            }
        }
        //返回值便是对应整个字符串，0~n-1。其实就是从最后一位逆推字符串，毕竟分段的k已经先算过了
        return f[0][n-1];
    }
}

五月二十五日：1787.使所有区间的异或结果为零

简单、中等题呢？给人整麻了，高情商：今天不用看算法，可以直接去学自己的东西了。

五月二十六日：1190.反转每对括号间的子串

只能说用栈很好做，就懒得优化了（其实是不会），栈画个过程图然后对着写就行。就是栈的相关方法没怎么用，要查一下，今天做完应该也记住了。

题目：https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses/

class Solution {
    public String reverseParentheses(String s) {
        Stack<Character> stack = new Stack<Character>();
        for(char c : s.toCharArray()){
            if( c == ')' ){
        /*
        *这里使用StringBuilder，因为它添加元素时是改变原本的  
        *值，而String会开辟一个新的空间存放新的值，高下立判
        *当检测到')'时，栈内元素出栈，直到遇见'('
        */
                StringBuilder sb = new StringBuilder();
                while(stack.peek() != '('){
                    sb.append(stack.pop());//出栈，并添加sb
                }
                stack.pop();//左括号'('出栈
                //将刚刚出栈的元素重新入栈，继续外循环
                for(char c1 : sb.toString().toCharArray())
                    stack.push(c1);
            }else
                stack.push(c);
        }
        //循环把全部括号去除后的数据压入栈，我们还要自行出栈
        StringBuilder ans = new StringBuilder();
        while(!stack.empty())
            ans.append(stack.pop());
        //因为遇到最后的一个左括号时顺序已经对了
        //然后入栈会先进后出，最后结果还要自行反转一下
        return ans.reverse().toString();
    }
}

五月二十七日：461.汉明距离

做了这么久的异或，看到二进制相关就想到异或😂

题目：https://leetcode-cn.com/problems/hamming-distance/

/*
 *两个数异或运算，得到的结果与1进行按位与计算，因为异或运算会把同位置的1清0，
 *所以结果中哪一位有1就说明它在原本两个数中是不同位置
 *最后一位按位与得1or0，与ans相加，然后num右移一位，计算二进制数的下一位
 */
class Solution {
    public int hammingDistance(int x, int y) {
        int num = x^y,ans=0;
        while(num!=0){
            ans += num&1;//与1按位与，是最后一位在计算，其余位均与0&=0
            num >>= 1;
        }
        return ans;
    }
}

五月二十八日：477.汉明距离总和

有点巧妙，用二进制对每一位进行统计+组合。

题目：https://leetcode-cn.com/problems/total-hamming-distance/

参考：

(图，好理解)https://leetcode-cn.com/problems/total-hamming-distance/solution/hua-tu-jie-ti-by-cyingenohalt-yy9j/

https://leetcode-cn.com/problems/total-hamming-distance/solution/yi-ming-ju-chi-zong-he-by-leetcode-solut-t0ev/

/*
 *把数组转换为二进制排序，int型是4字节，1字节又是8比特，
 *故有32位，也就是2^32，这是上限。然后这里看题目要求元素
 *上限是10^9小于2^30，所以可以缩短二进制的遍历范围到30
 */
class Solution {
    public int totalHammingDistance(int[] nums) {
        int sum=0,m=nums.length;
        /*
         *这里思想是将数组转化为二进制会统计每一位的1的个数，
         *使用排列组合的思想，数组有m个元素，其中二进制的某一位有n个1，则对应有m-n个0，
         *所以这一位的0与1搭配的总数是0*1的总和也就是n*(m-n)，
         *而我们只需要统计二进制每一位的组合情况并累加，最后得到的就是所有数的汉明距离和。
         *注意求汉明距离就是两个二进制数每一位上是否相同，这里是m个数，所以排列组合来做,
         *我们最后的重点就落在了求n的值
         */
        for(int i=0;i<30;i++){
            int n=0;
            //遍历数组，求每一个元素右移后该位数是否为1，然后排列组合
            for(int num : nums)
                n += (num >> i) & 1;
            sum += n*(m-n);
        }
        return sum;
    }
}

五月二十九日：1074.元素和为目标的子矩阵数量

今天直接跑了。

参考：https://leetcode-cn.com/problems/number-of-submatrices-that-sum-to-target/solution/gong-shui-san-xie-you-hua-mei-ju-de-ji-b-uttw/

五月三十日：231.2的幂

今日简单题。。。进阶做法懒得看了，周赛心累，真的菜啊。。。

参考：https://leetcode-cn.com/problems/power-of-two/solution/gong-shui-san-xie-2-de-mi-by-ac_oier-qm6e/

class Solution {
    public boolean isPowerOfTwo(int n) {
        if(n<=0) return false;
        while(n%2 == 0) n/=2;
        return n==1;
    }
}

五月三十一日：342.4的幂

和昨天做的题差不多，用的常规方法。5月勋章到手😁

题目：https://leetcode-cn.com/problems/power-of-four/

class Solution {
    public boolean isPowerOfFour(int n) {
        if(n<=0) return false;
        while(n%4 == 0) n/=4;
        return n==1;
    }
}

小结

5月完了，6月冲，剑指offer得提上日程了。