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];
    }

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

判断是不是可以用选/不选 来解决这道题。（本题是可以的，每一个字符串选/不选去拆）
确定是dp。那么状态转移方程是什么？（这个元素选了的当前最优解和不选这个元素的当前最优解。因为虽说是1和0，但是本质是一个串。）
带入到这个题，因为他本身要考虑0和1两个因素。所以用传统的一维数组是记录不了的，所以这里一定是二维dp确定下来了。
二维数组怎么记录呢？到了关键是时候了，到这里我一般都是用最笨的方法：带入法来理解这个中题目（我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，欢迎各位踊跃加入！