leetCode进阶算法题+解析（七十二）

哎，不知不觉这个进阶算法的文集也到了第72篇。虽然leetcode中的未刷题目越刷越多（我当年入坑一共一千一百多道题。现在一共两千道题，真.越刷越多.系列）。不过也算是从一个算法小白到了一个略有了解，运气好还能搞定困难题目的地步了。对于快排，归并，二分，贪心，dp，回溯也可以说的头头是道。
今天又一个同事提了离职。虽然现在还在我旁边坐着但是距离离岗也只差几天。总而言之，也坚持刷题一年半左右了。真的是岁月匆匆，时光荏苒。身边的同事换了一波一波，经手的项目一个一个。不出意外的话，大概等这个系列到了九十九篇，就这么结束了吧，至于说刷题的话，这是爱好，不能断。以后的日子会是什么样谁知道呢！
可能是连续阴雨两周久违了的阳光让我颇有感触，也可能是今天的风太过温柔。我觉得我还是喜欢这个行业，一行行代码在手中敲出，演变成一个个或实用，或神奇的作品。无论是办公用的erp；还是功能性很强的众筹抽奖；哪怕是自己搭服务器，延迟几秒的多人视频，都让我觉得充满了干劲和满足。我确实喜欢这个行业，现在，依然，永远。
好了，伤春悲秋到此结束，开始刷题吧！

基本计算器

题目：实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。

示例 1：
输入：s = "1 + 1"
输出：2
示例 2：
输入：s = " 2-1 + 2 "
输出：3
示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23
提示：
1 <= s.length <= 3 * 105
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式

思路：这个题挺简单的。虽然是困难难度，但是类似的我做过，就是各种字符串分情况处理。用一个flag记录+还是-。然后括号里的先计算。大概思路就这样，我直接去敲代码试试了。
第一版代码：

class Solution {
    public int calculate(String s) {
        boolean flag = true;//true是加，false是减
        int first = 0;//第一个加数
        int temp = 0;
        for(int i = 0;i<s.length();i++){
            while (i<s.length() && Character.isDigit(s.charAt(i))){
                temp = temp*10+(s.charAt(i)-'0');
                i++;
            }
            if(i == s.length()) break;
            //当前到了+-，那么要把之前的都计算清楚了
            if(s.charAt(i) == '+' || s.charAt(i) == '-'){
                if(flag){
                    first += temp;
                }else {
                    first -= temp;
                }
                temp = 0;
                flag = s.charAt(i) == '+'?true:false;
            }else if(s.charAt(i) == '('){
                StringBuffer sb = new StringBuffer();
                int z = 1;//遇到左括号了，所以左括号数量+1
                while (z != 0){
                    i++;
                    char c = s.charAt(i);
                    sb.append(c);
                    if(c == '('){
                        z++;
                    }else if(c == ')'){
                        z--;
                    }
                }
                //到这里说明z为0，也就是说是一个完整的括号中的内容了。直接计算
                if(flag){
                    first += calculate(sb.substring(0,sb.length()-1).toString());
                }else {
                    first -= calculate(sb.substring(0,sb.length()-1).toString());
                }
            }
        }
        return flag?first+temp:first-temp;
    }
}

说真的，我觉得性能应该还好，优化点的话应该是StringBuffer这块吧？改下去试试。
emmmm...从百分之五到百分之七，也算是进步了？修改版代码：

class Solution {
    public int calculate(String s) {
        boolean flag = true;//true是加，false是减
        int first = 0;//第一个加数
        int temp = 0;
        for(int i = 0;i<s.length();i++){
            while (i<s.length() && Character.isDigit(s.charAt(i))){
                temp = temp*10+(s.charAt(i)-'0');
                i++;
            }
            if(i == s.length()) break;
            //当前到了+-，那么要把之前的都计算清楚了
            if(s.charAt(i) == '+' || s.charAt(i) == '-'){
                if(flag){
                    first += temp;
                }else {
                    first -= temp;
                }
                temp = 0;
                flag = s.charAt(i) == '+'?true:false;
            }else if(s.charAt(i) == '('){
                int start = i+1;
                int z = 1;//遇到左括号了，所以左括号数量+1
                while (z != 0){
                    i++;
                    char c = s.charAt(i);
                    if(c == '('){
                        z++;
                    }else if(c == ')'){
                        z--;
                    }
                }
                //到这里说明z为0，也就是说是一个完整的括号中的内容了。直接计算
                if(flag){
                    first += calculate(s.substring(start,i));
                }else {
                    first -= calculate(s.substring(start,i));
                }
            }
        }
        return flag?first+temp:first-temp;
    }
}

怎么说呢，我不知道是不是因为我递归的原因，反正是性能还是不咋地。。。直接去看看性能第一的代码吧：

class Solution {
    int index = 0;
    public int calculate(String s) {
        int sign = 1;
        int res = 0;
        int num = 0;
        while (index < s.length()) {
            char c = s.charAt(index);
            if (c >= '0' && c <= '9') {
                num = num*10 + c - '0';
            } else if (c == '+' || c == '-') {
                res += sign * num;
                num = 0;
                sign = c == '+'?1:-1;
            } else if (c == '(') {
                index++;
                res += sign*calculate(s);
                sign = 1;
            } else if (c == ')') {
                res += sign*num;
                return res;
            }
            index++;
        }
        return res+num*sign;
    }
}

我觉得吧，思路是大同小异的，你看前几步代码都差不多，但是为什么写出来差别这么大呢！！！其实这里也用到了递归。只不过没有多余遍历。而是每一次（括号进递归，）括号退出。
看完人家写的恍然大悟，自己当时没想到。这个题其实麻烦为主，不算很难，下一题了。

森林中的兔子

题目：森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。返回森林中兔子的最少数量。

示例:
输入: answers = [1, 1, 2]
输出: 5
解释:
两只回答了 "1" 的兔子可能有相同的颜色，设为红色。
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。
输入: answers = [10, 10, 10]
输出: 11
输入: answers = []
输出: 0
说明:
answers 的长度最大为1000。
answers[i] 是在 [0, 999] 范围内的整数。

思路：这个题有个小技巧：回答一样的可能是同一个颜色。但是这里有个坑：回答人数不能超过总数。所以说这里要判断两次。比如说第一个例子：1 1 2是这个答案。但是如果1 1 1 2的话，那么要多加两个兔子了，三个回答1的，可能两个颜色相同。剩下的我们最大可能看成颜色相同，比如1 1 1 1 2的话可以和1 1 1 2一样、差不多就这个思路，我去实现下试试。
附上第一版代码：

class Solution {
    public int numRabbits(int[] answers) {
        int[] d = new int[1000];
        for(int i : answers) d[i]++;
        int ans = 0;
        for(int i = 0;i<d.length;i++){
            if(d[i] == 0) continue;
            //有种情况是这些人虽然是一样的但是也不能都是一个颜色，不然颜色超了，所以这里用num判断颜色数
            int n = d[i];
            int num = n/(i+1);
            if(n%(i+1) != 0){
                ans += (num+1)*(i+1);
            }else {//如果等于0的话则正好划分这么多阵营
                ans += n;
            }
        }
        return ans;
    }
}

总而言之这个题没什么坑，按照我上面的思路代码性能也还好。所以这个题就这么过了。最近这几道题做的很顺啊。

判断二分图

题目：存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：

不存在自环（graph[u] 不包含 u）。
不存在平行边（graph[u] 不包含重复值）。
如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。

二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。如果图是二分图，返回 true ；否则，返回 false 。

思路：这个题感觉有点类似之前的分圈子的游戏。本身每一条线都要一头在一边。所以下标本身代表的值和下标对应的数组中元素的值一定是在两个圈子里。同时有可能分多个圈子，所以这里不能从第一个元素开始一直往下扒。而且其实每一个元素在计算时有三种状态：0 无划分， 1划分到第一个分组，2划分到第二个分组。其实我们在遍历中可以很容易判断：如果某一个集合中（一个集合中元素应该在一个分组。并且与下标所在分组正好不同）存在和下标相同的分组则说明分不了，直接false。否则继续往下判断，看能不能都走一遍。如果所有元素都可以分好，那么就是true，否则false。思路比较清晰，我去实现下试试。
第一版代码：

class Solution {
    int[] c;
    boolean flag;
    public boolean isBipartite(int[][] graph) {
        flag = true;
        c = new int[graph.length];
        for(int i = 0;i<graph.length&&flag;i++){
            if(c[i] == 0) isOk(i,1,graph);
        }
        return flag;
    }
    public void isOk(int temp,int red,int[][] graph){
        c[temp] = red;
        int cur = c[temp]==1?2:1;//因为一条无向边两端要在不同阵营，所以下标是1的话，这里的值都是2
        for(int i:graph[temp]){
            if(c[i] == 0){
                //把当前节点看做是2，看能不能跑通
                isOk(i,cur,graph);
                if(!flag) return;
            }else if(c[i] == red){
                flag = false;
                return;
            }
        }
    }
}

其实这个题我前不久才做过类似的，所以这里占了便宜。简单来说就是用染色的方式实现的。我记得之前做个题目是给花染色。有点类似这个题目。都是下标值本身和其对应数组的值一定要相反。这个dfs的规律就是一次1.一次2这样循环来的。多看看代码debug跑跑就行了。继续下一题了。

K站中转内最便宜的航班

题目：有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。

提示：
n 范围是 [1, 100]，城市标签从 0 到 n - 1
航班数量范围是 [0, n * (n - 1) / 2]
每个航班的格式 (src, dst, price)
每个航班的价格范围是 [1, 10000]
k 范围是 [0, n - 1]
航班没有重复，且不存在自环

思路：其实这个题我觉得深搜就可以了，每一个可选项都顺着往下走，遇到超过k次的就减枝。然后在k次内从s到e的费用记下来，取最小值，over~我想的还是挺美的。然后至于所有的起始点，我个人打算用map构单项图。反正思路是有了，我去实现下试试。
第一版代码：

class Solution {
    int ans = Integer.MAX_VALUE;
    int k;
    int end;
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        Map<Integer,Map<Integer,Integer>> map = new HashMap<>();
        for(int [] i :flights){
            Map<Integer,Integer> sub = map.get(i[0]);
            if(sub == null) sub = new HashMap<>();
            sub.put(i[1],i[2]);
            map.put(i[0],sub);
        }
        k = K;
        end = dst;
        dfs(map,new HashSet<Integer>(),0,src);
        return ans == Integer.MAX_VALUE?-1:ans;
    }
    public void dfs(Map<Integer,Map<Integer,Integer>> map,Set<Integer> s,Integer money,Integer src){
        if(src == end) {//src等于end说明到了终点，判断最小花费
            ans = Math.min(ans,money);
            return;
        }
        //最多经过k个中转站，起始站不算。所以中间最多只能经过起始点个数-1个站点。否则就不能往下走了。
        if(s.size()>=k+1) return;
        Map<Integer,Integer> sub = map.get(src);
        if(sub == null) return;//这条路走不通了。
        for(Integer key:sub.keySet()){
            //去重：这条路线已经走过这个节点了，不能回去了
            if(s.contains(key)) continue;
            //剪枝：当前的花费已经大于已有最小值，直接pass
            if(money+sub.get(key)>=ans) continue;
            Set<Integer> set = new HashSet<>();
            set.addAll(s);
            set.add(key);
            dfs(map,set,money+sub.get(key),key);
        }
    }
}

可能，我没超时就已经是上天保佑了吧。。。感觉性能应该还是卡在了set这块了。因为n最大99。我感觉这里用数组都比用set强，也有可能是这里可以用回溯吧。反正我感觉是我写的有问题了。。我去看看性能第一的代码：

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        // dp[i][k]是经过k个中转站后到达站 i 的最小费用
        int[][] dp = new int[n][K + 1];

        // 循环初始化整个二维数组。
        for(int i = 0; i < n; ++i) Arrays.fill(dp[i], Integer.MAX_VALUE);

        // 利用flights中的信息初始化src可直达的班次
        for(int[] flight : flights) {
            if(flight[0] == src){
                dp[flight[1]][0] = flight[2];
            }
        }

        // 循环初始化数组中dst == src的行
        for(int i = 0; i <= K; i++){
            dp[src][i] = 0;
        }

        //动态规划状态转移方程，开始填表
        //直达的已经初始化了（即k = 0的情况），现在从k = 1 的开始，即只有一个中转站开始
        for(int k = 1; k <= K; k++){
            for(int[] flight : flights){
                //结合题目理解
                if(dp[flight[0]][k - 1] != Integer.MAX_VALUE){
                    dp[flight[1]][k] = Math.min(dp[flight[1]][k], dp[flight[0]][k - 1] + flight[2]);
                }
            }
        }
        return dp[dst][K] == Integer.MAX_VALUE? -1: dp[dst][K];
    }
}

这个题原来可以用dp啊。。看了人家写的才发现这个题用dp确实挺合适。。而且我特意挑了一个注释写的很全的代码贴出来的。dp其实也是一步一步往下走，但是因为记住了每一步，所以有一些重复数据是不用来回来去计算的了。比如我上文中： 1,2,4 1,4 1,5,4这种情况下，三种方式走到了4这个节点，然后要重复计算三次4往下走的路。
但是用dp的话就可以省略了。dp——记录中间过程的递归。
其实看了人家的代码我就又又又恍然大悟了，但是自己下意识的想法就是递归，哎，我差不多是没救了，下一题吧。

多米诺和托米诺平铺

题目：有两种形状的瓷砖：一种是 2x1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。

XX <- 多米诺

XX <- "L" 托米诺

X

给定 N 的值，有多少种方法可以平铺 2 x N 的面板？返回值 mod 10^9 + 7。（平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。）

示例:
输入: 3
输出: 5
解释:
下面列出了五种不同的方法，不同字母代表不同瓷砖：
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY
提示：
N 的范围是 [1, 1000]

思路：这个题乍一看有点蒙，但是稍微一看示例其实就能发现是个典型的dp题目了。首先我觉得这个示例3用的很有用。因为正好按照两个砖的摆放，3应该是个比较大的可能了。比如再往下输入是4.也就是在3的基础上多加一个竖条，只有多米诺可以实现，往前后者往后竖着贴一层。也就是结果是3的结果2（因为每一种可能都可以往前或者往后加一个竖着的多米诺。）另外如果每多两个，都会有一种的相比于之前多一种可能：。*
不得不说我在推导递推公式的时候直接发现规律了。虽然为什么不懂。。下面是计算过程：

结果是前一个数*2 + 前三个数。从4开始有规律的。我去试试这个规律是不是对的。
!!!!!就这么ac了，而且性能超好，这里一定要截图纪念一下！

然后附上代码：

class Solution {
    public int numTilings(int N) {
        if(N<3) return N;
        long[] dp = new long[N+1];
        dp[0] = 0l;
        dp[1] = 1l;
        dp[2] = 2l;
        dp[3] = 5l;
        for(int i = 4;i<=N;i++){
            dp[i] = (dp[i-1]*2 + dp[i-3])%1000000007;
        }
        return (int)dp[N];
    }
}

感觉逆推为什么的话可能更容易一些吧。。。我去琢磨琢磨为什么是上一个*2+上上上一个。
好吧，我果断没琢磨出来，所以这里看了题解，并且看题解都找了好几个才懂，大概的思路下面一点点说：
我们求dp[n]时

1. 考虑从dp[n-1]基础上补2×1列图案，只有用1个多米诺的1种方案；
2. 考虑从dp[n-2]基础上补2×2列图案，只有用2个多米诺的1种方案；（注意，补的部分一定要不可从某列中间断开，否则会重复！比如两个竖着放的多米诺这种补法一定会和上面的一个竖着的方案重复）

3. 考虑从dp[n-x]基础上补2×2列图案，只有用2个托米诺+y个多米诺拼的2种方案；(x为2，3,4，……，n)

   
   
   图解

所以递推公式为

• dp[n]=dp[n-1]+dp[n-2]+(dp[0]+dp[1]+...+dp[n-3])*2
• 再结合dp[n-1]=dp[n-2]+dp[n-3]+(dp[0]+dp[1]+...+dp[n-4])*2
• 可得dp[n]=dp[n-1]*2+dp[n-3]

然後这样才算是勉强反推回来了。。。

本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利吧！我现在觉得工作顺顺利利简直是最好的祝福了~~~