leetCode进阶算法题+解析（五十三）

国庆+年假一共十几天，我是一点没碰电脑，这次放假忙了好多事，现在要把刷题补回来了。而且最近发现了个b站比较不错的up主，叫狂神，最近在看他的视频，有兴趣的也可以自己看看，用一种讲故事的方式传输思维和知识，推荐一波。
开始刷题啦（ps：今天发现ac的题目数超过500了，从一开始的简单难度的题都能卡两三天，到现在形成了一定的逻辑思维能力，会了很多小技巧，各种排序，查找方法，简单的dp，回溯，拓扑等，坚持刷题快一年了，感谢自己，只要学不死，就要往死学。）

一和零

题目：在计算机界中，我们总是追求用有限的资源获取最大的收益。现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。

示例 1:
输入: strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。
示例 2:
输入: strs = ["10", "0", "1"], m = 1, n = 1
输出: 2
解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。
提示：
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

思路：这个题怎么说呢，我审了好几遍题才理解，感觉是个很明显的最优解的题目，我暂时第一反应是从字符串短的开使拼，莫名其妙的觉得最优解都可以用dp实现。我先去试试看。
我感觉我的思路还是不错的，写了一个排序，根据1的个数/根据0的个数排序，然后两个数组看哪个能走的结果长，就选择哪个结果。最开始排序是字符串排序，但是真正做了发现转化成二维数组更好，每一个元素用一个数组表示，数组第一个数字是需要的0的个数，第二个数字是需要的1的个数。等ac了再过来分享。
好吧，上面的思路完美的失败了，果然还是要dp。我去专心研究怎么套模板吧。
直接贴代码:

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if(strs.length == 0) return 0;
        //字符串数组转成二维数组
        int[][] arr = new int[strs.length][];
        for(int i = 0;i<arr.length;i++){
            arr[i] = new int[2];
            for(char c:strs[i].toCharArray()) {
                arr[i][c-'0']++;
            }
        }
        //动态规划，用数组记录中间过程的递归
        int[][][] dp = new int[strs.length+1][m+1][n+1];
        for(int k = 1;k<=strs.length;k++){
            int[] temp = arr[k-1];
            for(int i = 0;i<=m;i++){
                for(int j = 0;j<=n;j++){
                    if(temp[0]<=i && temp[1]<=j){
                        dp[k][i][j] = Math.max(dp[k-1][i][j],1+dp[k-1][i-temp[0]][j-temp[1]]);
                    }else{
                        dp[k][i][j] = dp[k-1][i][j];
                    }
                }
            }
        }
        return dp[strs.length][m][n];
    }

}

需要注意下，上面代码的主要逻辑在于三层for循环里面的if-else中。else中很好理解，就是当前的数值已经凑不出来了，那么直接凑出来的最大数就是上一个元素能凑出来的最大数，所以没啥好说的。问题就是当前元素能凑出来，那么减去当前用掉的0和1，然后存入凑成的个数。
因为这个是个三维数组，我在画草图方便理解的时候把自己都绕懵了。其实这个性能也不咋地，三层for循环，mnl的时间复杂度。这里说是dp还不如说就是记录中间过程的暴力破解。
看了官方题解中的另一种写法。感觉比我的要明了多了，我直接贴出来：

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if(strs.length == 0) return 0;
        //字符串数组转成二维数组
        int[][] arr = new int[strs.length][];
        for(int i = 0;i<arr.length;i++){
            arr[i] = new int[2];
            for(char c:strs[i].toCharArray()) {
                arr[i][c-'0']++;
            }
        }
        //动态规划，用数组记录中间过程的递归
        int[][] dp = new int[m+1][n+1];
        for(int k = 1;k<=strs.length;k++){
            int[] count = arr[k-1];
            for (int zeroes = m; zeroes >= count[0]; zeroes--)
                for (int ones = n; ones >= count[1]; ones--)
                    dp[zeroes][ones] = Math.max(1 + dp[zeroes - count[0]][ones - count[1]], dp[zeroes][ones]);

        }
        return dp[m][n];
    }

这种方式怎么说呢，二维维数组看着更简单了，简单来说就是每一个元素选择/不选择都作为一条线走下去。然后求最优解。我一般遇到这种问题都是按照思路模板套的：

1. 判断是不是可以用选/不选 来解决这道题。（本题是可以的，每一个字符串选/不选去拆）
2. 确定是dp。那么状态转移方程是什么？（这个元素选了的当前最优解和不选这个元素的当前最优解。因为虽说是1和0，但是本质是一个串。）
3. 带入到这个题，因为他本身要考虑0和1两个因素。所以用传统的一维数组是记录不了的，所以这里一定是二维dp确定下来了。

4. 二维数组怎么记录呢？到了关键是时候了，到这里我一般都是用最笨的方法：带入法来理解这个中题目（我dp不行，所以这里用最笨的方法，其实很多大佬都能看出状态转移方程，我反正不行）。随便写五个元素，然后从第一个开始一点点判断。如下图。

   
   我的思路
   

   其实比较low，不夸张的说这个题我推演了三四个小时。确实dp这里稍微难一点就贼费劲。不过好歹是做出来了，这个题就这样了。下一道题了。

汉明距离总和

题目：两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。计算一个数组中，任意两个数之间汉明距离的总和。

示例:
输入: 4, 14, 2
输出: 6
解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
注意:
数组中元素的范围为从 0到 10^9。
数组的长度不超过 10^4。

思路：这个题的难度，我不知道是不是在超时上，反正我个人感觉单纯的实现不是很难。首先两两比较获得结果。其次双层for循环第一层0-数组长。第二层第一层下一个到最后一一判断相加。我去实现下试试。我预感告诉我会超时。哈哈。

暴力法超时
怎么说呢，一点不遗憾，意料之中的结果。毕竟中等难度的题不至于这么简单。剩下的就该是优化了。其实我是有个大胆的想法的。本质上某一位数上比如3个1,4个0。那么是可以算出这位数中不同的个数是多少的。每个1和其余四个0都是四种不同。所以这个位数上不同数目是3*4=12.
然后所有数字一共就12位。我去试试这种方式能不能ac。
居然acl，随着时间的执行我这个心都在颤抖，虽然是低空略过，只超过百分之五的人，我先把代码贴上：

class Solution {
    public int totalHammingDistance(int[] nums) {
        int res = 0;
        //第一个32是位数。每一位分0，1两种情况。所以是二维数组。
        int[][] d = new int[32][2];
        for(int i : nums){
            int j = 0;
            //因为最大是10的九次方，也就是30位
            while(j<30){
                if((i&1)==0){
                    d[j][0]++;
                } else{
                    d[j][1]++;
                }
                i /= 2;
                j++;
            }
        }
        for(int[] i : d) {
            res += i[0]*i[1];
        }
        return res;
    }

}

起码说明思路是没问题的。我觉得其实还有优化的空间，比如说这个前置0要赋值为1的这个问题。我再想想。第二版本代码：

class Solution {
    public int totalHammingDistance(int[] nums) {
        int res = 0;
        int len = nums.length;
        //第一个32是位数。每一位分0，1两种情况。所以是二维数组。
        int[][] d = new int[32][2];
        for(int i : nums){
            int j = 0;
            while(i!=0){
                if((i&1)==0){
                    d[j][0]++;
                } else{
                    d[j][1]++;
                }
                i /= 2;
                j++;
            }
        }
        for(int[] i : d) {
            if(i[0]+i[1] == len) {
                res += i[0]*i[1];
            }else{//走到这说明出现了某位数只有1.0是前置位0所以没计数
                res += i[1]*(len-i[1]);
            }
        }
        return res;
    }
}

通过这个变化，我又有了新思路。其实不用统计1的个数0的个数。只统计一个就行了。毕竟不是1就是0.我再去改下。
最终版代码：

class Solution {
    public int totalHammingDistance(int[] nums) {
        int res = 0;
        int len = nums.length;
        //计算二进制每一位1的个数。
        int[] d = new int[32];
        for(int i : nums){
            int j = 0;
            while(i!=0){
                //当结果是1则计数
                if((i&1)==1) d[j]++;
                j++;
                i /= 2;
            }
        }
        for(int i : d) {
            if(i!=0)res += i*(len-i);
        }
        return res;
    }
}

说一个很悲哀的故事：这么多版本，就没有一个性能是好的。哭了。我去看看性能排行第一的代码吧。

超过百分之五的用户

！！！！说实话，除了是用二进制计算，其余的思路是一样一样的，人家是性能第一，我是性能惨不忍睹。。附上代码下一题：

class Solution {
    public int totalHammingDistance(int[] nums) {
        int res = 0, n = nums.length;
        for (int i = 0; i < 32; i++) {
            int cnt = 0;
            for (int num : nums) {
                cnt += (num >>> i) & 1;
            }
            res += cnt * (n - cnt);
        }
        return res;
    }
}

在圆内随机生成点

题目：给定圆的半径和圆心的 x、y 坐标，写一个在圆中产生均匀随机点的函数 randPoint 。

说明:

输入值和输出值都将是浮点数。

圆的半径和圆心的 x、y 坐标将作为参数传递给类的构造函数。

圆周上的点也认为是在圆中。

randPoint 返回一个包含随机点的x坐标和y坐标的大小为2的数组。

示例 1：
输入:
["Solution","randPoint","randPoint","randPoint"]
[[1,0,0],[],[],[]]
输出: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]
示例 2：
输入:
["Solution","randPoint","randPoint","randPoint"]
[[10,5,-7.5],[],[],[]]
输出: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]
输入语法说明：
输入是两个列表：调用成员函数名和调用的参数。Solution 的构造函数有三个参数，圆的半径、圆心的 x 坐标、圆心的 y 坐标。randPoint 没有参数。输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。

思路：简单来说，是保证给定的横纵坐标是圆范围内的。其实我觉得这个比较难的是随机圆的范围吧。如果是正方形长方形等是很容易算出边框的。在这区间random就好，但是因为是圆，所以还是挺不好实现的。我去画图理理思路。
这个题着实是我的知识盲区。毕竟我数学基础一直是渣渣。看了一种题解觉得很适合我（微积分的那个属于看都不想看）。就是半径形成正方形。正方形内取点。如果点在圆上则返回。否则重新取点。我是觉得这种方式我能理解也能做出来，去写代码试试了。
我直接贴代码：

class Solution {
    double rad, xc, yc;
    public Solution(double radius, double x_center, double y_center) {
        rad = radius;
        xc = x_center;
        yc = y_center;
    }

    public double[] randPoint() {
        double x0 = xc - rad;
        double y0 = yc - rad;

        while(true) {
            double xg = x0 + Math.random() * rad * 2;
            double yg = y0 + Math.random() * rad * 2;
            if (Math.sqrt(Math.pow((xg - xc) , 2) + Math.pow((yg - yc), 2)) <= rad)
                return new double[]{xg, yg};
        }
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(radius, x_center, y_center);
 * double[] param_1 = obj.randPoint();
 */

怎么说呢，感觉对我这种数学渣很不友好啊。而且get不到考点是什么。反正现在对付实现了（看到题解有的思路）。也不多bb，下一题。

神奇字符串

题目：神奇的字符串 S 只包含 '1' 和 '2'，并遵守以下规则：字符串 S 是神奇的，因为串联字符 '1' 和 '2' 的连续出现次数会生成字符串 S 本身。字符串 S 的前几个元素如下：S = “1221121221221121122 ......”如果我们将 S 中连续的 1 和 2 进行分组，它将变成：

1 22 11 2 1 22 1 22 11 2 11 22 ......

并且每个组中 '1' 或 '2' 的出现次数分别是：

1 2 2 1 1 2 1 2 2 1 2 2 ......

你可以看到上面的出现次数就是 S 本身。给定一个整数 N 作为输入，返回神奇字符串 S 中前 N 个数字中的 '1' 的数目。注意：N 不会超过 100,000。

示例：
输入：6
输出：3
解释：神奇字符串 S 的前 6 个元素是 “12211”，它包含三个 1，因此返回 3。

思路：怎么说呢，这个串确实是挺神奇的，毕竟我看了好几遍才看懂。我暂时的想法就是前19位是确定的。其实根据这19位是可以继续往下无线顺延的。我去试试代码。
三次过的。第一次是截取字符串的时候用的n-1.最近学redis学多了，redis的截取就是闭区间。但是java中是含前不含后的，所以这里错了。第二次是我没想到n还能等于0.所以补了下第一句代码。第三次ac，虽然性能差点。

class Solution {
    public int magicalString(int n) {
        if(n==0) return 0;
        if(n<=3) return 1;
        StringBuffer sb = new StringBuffer("122");
        int idx = 2;//从下标为2的开始遍历
        int flag = 2;//当前是1还是2
        int realIdx = 2;//从下标为2的开始算。
        while(realIdx<n) {
            char c = sb.charAt(idx);         
            if(flag == 1) {
                //如果上一个是1这个续2
                sb.append(c=='1'?"2":"22");
                flag = 2;
            }else {//上一个是2，这个续1
                sb.append(c=='1'?"1":"11");
                flag = 1;
            }
            idx++;
            realIdx += (c=='1'?1:2);
        }
        //有可能最后是两个数，sb长度大于n
        String res = sb.toString().substring(0, n).replace("2", "");
        return res.length();
    }
}

整体来说其实这个题给了前两个数就可以自己往下编了，我这里是把所有的数追加了下，再判断这个字符串的1的个数。这样也是让思路更清晰的。至于性能问题不知道是不是因为我选择stringbuffer这种方式才这样的。可能用队列会更好？我去试一下。

class Solution {
    public int magicalString(int n) {
        if(n == 0) return 0;
        int res = 1;
        if(n<=3) return res;
        boolean flag = true;
        int num = 3;
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(2);
        while(num<n) {
            queue.add(flag==true?1:2);
            if(flag) res++;//说明插入的是1，计数+1
            num++;
            if(queue.poll()==2 && num<n) {//如果num=n了后面的不用计算了
                queue.add(flag==true?1:2);
                if(flag) res++;//说明插入的是1，计数+1
                num++;
            }
            flag = !flag;           
        }
        return res;
    }
}

说真的这个改动差不多是新做了一次，不过性能没好多少，贴上个截图我去看性能排行第一的代码了：

提交记录

看了性能排行第一的代码，只能说可能是越简单的越美好。人家的简单的多了，就是数组操作，但是性能好。贴出来大家一起看看：

class Solution {
    public int magicalString(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 3) {
            return 1;
        }
        boolean[] nums = new boolean[n];
        nums[1] = true;
        int i1 = 1, i2 = 1;
        boolean cur = true;
        while(i2 < n) {
            nums[i2++] = cur;
            if (i2 == n) {
                break;
            }
            if (nums[i1]) {
                nums[i2++] = cur;
            }
            i1++;
            cur = !cur;
        }
        int res = 0;
        for (boolean b : nums) {
            if (!b) {
                res++;
            }
        }
        return res;
    }
}

好了，下一题吧。

预测赢家

题目：给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1：
输入：[1, 5, 2]
输出：False
解释：一开始，玩家1可以从1和2中进行选择。
如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。
所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
因此，玩家 1 永远不会成为赢家，返回 False 。
示例 2：
输入：[1, 5, 233, 7]
输出：True
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。
提示：
1 <= 给定的数组长度 <= 20.
数组里所有分数都为非负数且不会大于 10000000 。
如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。

思路：我不知道为啥leetcode里的人这么爱玩游戏，还他妈都是高智商的游戏。太扎心了。反正这个题目总而言之应该可以用暴力法破解吧。其实每个人都选择最大的结果，那么另一个人就是最小的结果，这个是一个四重选择的操作。也可以说是递归操作。思路是有的，我去实现下试试。
直接贴代码：

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int sum = 0;
        for(int i : nums){
            sum += i;
        }
        return dfs1(nums,0,nums.length-1)*2>=sum;
    }
    public int dfs1(int[] nums,int l,int r) {
        //说明只有一个元素了那么下一手的人没得选.所以一个是元素值，一个是0
        if(l==r) return nums[l];
        //剩两个元素，选择大的那个
        if(l==r-1) return Math.max(nums[l],nums[r]);
        //其实这是四个选择。 我可以选左/右，下一个人可以选左/右
        //假如我选择了左，下一个人要么选左2.要么选右。我只能获取较小的那个
        int left = Math.min(dfs1(nums, l+1, r-1), dfs1(nums, l+2, r))+nums[l];
        //假如我选了右，下一个人要么左1，要么右2
        int right = Math.min(dfs1(nums, l, r-2), dfs1(nums, l+1, r-1))+nums[r];
        //聪明人选择结果大的那个
        return Math.max(left, right);
    }
}

我觉得我备注写的很清楚了，毕竟自己一点点理出来的思路。总体来说没超时我就觉得很惊喜了，但是这种暴力遍历绝对是可以用dp实现的，但是怎么实现我只有正着写出来了反着去看才有可能分析出来，太扎心了。我去试试了。

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int length = nums.length;
        int[] dp = new int[length];
        for (int i = 0; i < length; i++) {
            dp[i] = nums[i];
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
            }
        }
        return dp[length - 1] >= 0;
    }
}

直接看的题解，放弃这么复杂的思路了，年纪大了，没追求了，哎。
这篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利!java技术交流群130031711，欢迎各位踊跃加入！