leetcode解题思路分析（八十九）781 - 788 题

Love The Way You Lie 2022-09-08 10:30 163阅读 0赞

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

**如果有 x 只兔子都回答 y，则至少有 x / (y + 1) 取上界种不同的颜色，且每种颜色有 y+1只兔子**

class Solution { 
    public:
        int numRabbits(vector<int> &answers) { 
            unordered_map<int, int> count;
            for (int y : answers) { 
                ++count[y];
            }
            int ans = 0;
            for (auto &[y, x] : count) { 
                ans += (x + y) / (y + 1) * (y + 1);
            }
            return ans;
        }
    };

1.  变为棋盘  
    一个 N x N的 board 仅由 0 和 1 组成 。每次移动，你能任意交换两列或是两行的位置。输出将这个矩阵变为 “棋盘” 所需的最小移动次数。“棋盘” 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。如果不存在可行的变换，输出 -1。

class Solution { 
    private:
        // 记录列数和列数（因为方阵是相等的）
        int n;
    
        // 计算时候最大的范围，避免引入不再考虑范围的计算值
        int mask;
    
        // 计算bit为1的数量
        int CntOneBit(int num)
        { 
            int cnt = 0;
            while (num > 0)
            { 
                if ((num & 1) == 1)
                { 
                    ++cnt;
                }
                num >>= 1;
            }
    
            return cnt;
        }
    
        // 计算最小步数的函数
        // codex,numx对应的就是排列类型和对应的数量
        int CalculateSteps(unordered_map<int, int>& code2num)
        { 
            int codes[2];
            int nums[2];
            int cnt = 0;
            // 从map获得num和code,这里正好2个（之前已经判断了）
            for (auto iter = code2num.begin(); iter != code2num.end(); ++iter)
            { 
                codes[cnt] = iter->first;
                nums[cnt] = iter->second;
                ++cnt;
            }
            // cout << "CalculateSteps " << codes[0] << "," << codes[1] << " " << nums[0] << "," << nums[1] << endl;
    
            // 判断数量是否符合预期: 默认第一个计数更大
            if (nums[0] < nums[1])
            { 
                swap(nums[0], nums[1]);
                swap(codes[0], codes[1]);
            }
            if (nums[0] != (n+1)/2 || nums[1] != n/2)
            { 
                // cout << "wrong n" << endl;
                return -1;
            }
    
            // 正好需要异或互补：长度为n的数量
            if ((codes[0] ^ codes[1]) != mask)
            { 
                // cout << "wrong xor " << (codes[0] ^ codes[1]) << endl;
                return -1;
            }
            // 开始计算最小步数，考虑两种情况 0x55555555 或 0xaaaaaaaa
            // 最小步数即计算异或后的1的位数/2（记得即考虑mask范围内的1）
            // 
            if (n % 2 == 0)
            { 
                return min(CntOneBit((codes[0] ^ 0x55555555) & mask), CntOneBit((codes[0] ^ 0xaaaaaaaa) & mask)) >> 1;
            }
            else
            { 
                int code = CntOneBit(codes[0]) > (n/2) ? codes[0] : codes[1];
                return CntOneBit((code ^ 0x55555555) & mask) / 2;
            }
        }
    public:
        int movesToChessboard(vector<vector<int>>& board) { 
            n = board.size();
            mask = (1 << n)-1;
    
            // 两种排列类型
            unordered_map<int, int> code2num;
    
            // 先计算行的情况
            for (int i = 0; i < n; ++i)
            { 
                // 当前的排列类型
                int curr = 0;
                for (int j = 0; j < n; ++j)
                { 
                    curr = (curr << 1) + board[i][j];
                }
                // 排除出现第三种排列情况，直接返回失败 -1
                ++code2num[curr];
                if (code2num.size() > 2)
                { 
                    return -1;
                }
            }
            int stepsRow = CalculateSteps(code2num);
            if (stepsRow == -1)
            { 
                return -1;
            }
    
            code2num.clear();
            // 按照列的情况
            for (int j = 0; j < n; ++j)
            { 
                // 当前的排列类型
                int curr = 0;
                for (int i = 0; i < n; ++i)
                { 
                    curr = (curr << 1) + board[i][j];
                }
                // 排除出现第三种排列情况，直接返回失败 -1
                ++code2num[curr];
                if (code2num.size() > 2)
                { 
                    return -1;
                }
            }
    
            int stepsCol = CalculateSteps(code2num);
            if (stepsCol == -1)
            { 
                return -1;
            }
    
            return stepsRow + stepsCol;
        }
    };

1.  字母大小写全排列  
    给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

**位运算的使用：n位每一位0、1表示大小写，遍历一遍然后按位处理即可**

class Solution { 
    public:
        vector<string> letterCasePermutation(string s) { 
            int n=s.size();
            vector<int> v;              //记录下标
            for(int i=0;i<n;i++){ 
                if(isalpha(s[i]))v.push_back(i);
            }
            n=v.size();
            vector<string> ans;
            for(int i=0;i<1<<n;i++){     //二进制枚举
                string res(s);
                for(int j=0;j<n;j++){ 
                    if(i&1<<j){          //判断对应位置是否为1
                        if(islower(res[v[j]])){ 
                            res[v[j]]=toupper(res[v[j]]); 
                        }
                        else{ 
                            res[v[j]]=tolower(res[v[j]]);
                        }
                    }
                }
                ans.push_back(res);
            }
            return ans;
        }
    };

1.  判断二分图  
    存在一个 无向图 ，图中有 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 。

**根据题意，我们可以转化为图着色问题：相邻节点需要有不同颜色。由此使用DFS或者BFS遍历即可。**

class Solution { 
    private:
        static constexpr int UNCOLORED = 0;
        static constexpr int RED = 1;
        static constexpr int GREEN = 2;
        vector<int> color;
        bool valid;
    
    public:
        void dfs(int node, int c, const vector<vector<int>>& graph) { 
            color[node] = c;
            int cNei = (c == RED ? GREEN : RED);
            for (int neighbor: graph[node]) { 
                if (color[neighbor] == UNCOLORED) { 
                    dfs(neighbor, cNei, graph);
                    if (!valid) { 
                        return;
                    }
                }
                else if (color[neighbor] != cNei) { 
                    valid = false;
                    return;
                }
            }
        }
    
        bool isBipartite(vector<vector<int>>& graph) { 
            int n = graph.size();
            valid = true;
            color.assign(n, UNCOLORED);
            for (int i = 0; i < n && valid; ++i) { 
                if (color[i] == UNCOLORED) { 
                    dfs(i, RED, graph);
                }
            }
            return valid;
        }
    };

1.  第K个最小的素数分数  
    给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数 组成，且其中所有整数互不相同。对于每对满足 0 < i < j < arr.length 的 i 和 j ，可以得到分数 arr\[i\] / arr\[j\] 。那么第 k 个最小的分数是多少呢? 以长度为 2 的整数数组返回你的答案, 这里 answer\[0\] == arr\[i\] 且 answer\[1\] == arr\[j\]

class Solution { 
    public:
        vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) { 
            auto cmp = [&arr](int a, int b)
            { 
                return arr[a>>10]*arr[b&0x3ff] - arr[a&0x3ff]*arr[b>>10] > 0;
            };
    
            priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
    
            for (int i = 1; i < arr.size(); ++i)
            { 
                q.push(i);
            }
    
            // 这里取掉k-1个小的分数
            --k;
            while (k > 0)
            { 
                int curr = q.top();
                q.pop();
                int n = curr >> 10;
                int m = curr & 0x3ff;
                if (n < m)
                { 
                    n++;
                    q.push((n<<10) + m);
                }
                --k;
            }
            // cout << q.size() << endl;
            // 这就是第k个小的分数
            auto curr = q.top();
            return { arr[curr>>10], arr[curr&0x3ff]};
        }
    };

1.  K站中转内最便宜的航班  
    有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights\[i\] = \[fromi, toi, pricei\] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

**动态规划**

class Solution { 
    private:
        static constexpr int INF = 10000 * 101 + 1;
    
    public:
        int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) { 
            vector<int> f(n, INF);
            f[src] = 0;
            int ans = INF;
            for (int t = 1; t <= k + 1; ++t) { 
                vector<int> g(n, INF);
                for (auto&& flight: flights) { 
                    int j = flight[0], i = flight[1], cost = flight[2];
                    g[i] = min(g[i], f[j] + cost);
                }
                f = move(g);
                ans = min(ans, f[dst]);
            }
            return (ans == INF ? -1 : ans);
        }
    };

1.  旋转数字

**暴力或者动态规划均可**

class Solution { 
    private:
        bool isGood(int n)
        { 
            // 记录2,5,6,9个数
            int diff = 0;
            int curr = 0;
            while (n > 0)
            { 
                curr = n % 10;
                n /= 10;
                if (curr == 3 || curr == 4 || curr == 7)
                { 
                    return false;
                }
                else
                { 
                    diff += (curr == 2 || curr == 5 || curr == 6 || curr == 9);
                }
            }
    
            return diff > 0;
        }
    public:
        int rotatedDigits(int n) { 
            int res = 0;
            for (int i = 1; i <= n; ++i)
            { 
                res += isGood(i);
            }
            return res;
        }
    };