LeetCode---2021/7/17

灰太狼 2022-08-29 15:50 123阅读 0赞

### 目录 ###

*  颠倒二进制位
 *  只出现一次的数
 *  位1的个数
 *  2的幂
 *  组合
 *  全排列
 *  字母大小写全排列
 *  打家劫舍
 *  三角形最小路径和
 *  填充每个节点的下一个右侧节点指针

# 颠倒二进制位 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]  
分析：  
  c++的bitset中封装了对二进制的操作：构造函数可以直接将整型转为其二进制表示，to\_string()可将其二进制转为字符串形式，to\_ulong()转为整数形式。  
代码：

class Solution { 
    public:
        uint32_t reverseBits(uint32_t n) { 
            bitset<32> x(n);
            string s = x.to_string();
            reverse(s.begin(), s.end());
    		bitset<32> y(s);
            uint32_t res = y.to_ulong();
            return res;
        }
    };

# 只出现一次的数 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]  
分析：  
  两个相同的数异或为0，任何数与0异或为本身，所以数组中所有数的异或即为只出现一次的数。  
代码：

class Solution { 
    public:
        int singleNumber(vector<int>& nums) { 
            int ret = 0;
            for (auto e: nums) ret ^= e;
            return ret;
        }
    };

# 位1的个数 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]  
方法一：  
  同样利用bitset，将其二进制表示转为字符串形式，然后统计其中1的个数。  
代码：

class Solution { 
    public:
        int hammingWeight(uint32_t n) { 
            bitset<32> x(n);
            int res = 0;
            string s = x.to_string();
            for(int i = 0; i < 32; i++) { 
                if(s[i] == '1') { 
                    res++;
                }
            }
            return res;
        }
    };

方法二：  
  n & (n - 1)其运算结果恰为把n的二进制位中的最低位的1变为0之后的结果，所以依次将n的最低位的1变为0，在这个过程中计数，直到n为0即可。  
代码：

class Solution { 
    public:
        int hammingWeight(uint32_t n) { 
            int ret = 0;
            while (n) { 
                n &= n - 1;
                ret++;
            }
            return ret;
        }
    };

# 2的幂 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]  
分析：  
  这里直接参考官方的题解，核心是：n如果是2的幂，则n是正整数并且n的二进制表示中只有1个1。第一个方法采用了前面提到的n & (n - 1)，该式可以将n最低位的1变成0，如果最低位变成0后n为0，则n满足要求。第二个方法采用了n & -n，该式可以直接获取到最低位的1，实际上就是n的最高位，如果n & -n后n不变，则n满足要求。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 5]  
代码：

class Solution { 
    public:
        bool isPowerOfTwo(int n) { 
            return n > 0 && (n & (n - 1)) == 0;
        }
    };

class Solution { 
    public:
        bool isPowerOfTwo(int n) { 
            return n > 0 && (n & -n) == n;
        }
    };

# 组合 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 6]  
分析：  
  典型的dfs例题。  
代码：

class Solution { 
    public:
        vector<int> temp;
        vector<vector<int>> ans;
        void dfs(int cur, int n, int k) { 
            if(temp.size() + (n - cur + 1) < k) { 
                return;
            }
            if(temp.size() == k) { 
                ans.push_back(temp);
                return;
            }
            temp.push_back(cur);
            dfs(cur + 1, n, k);
            temp.pop_back();
            dfs(cur + 1, n, k);
        }
        vector<vector<int>> combine(int n, int k) { 
            dfs(1, n, k);
            return ans;
        }
    };

# 全排列 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 7]  
方法一：  
  c++的next\_permutation()封装了全排列的实现，注意使用前先排序。  
代码：

class Solution { 
    public:
        vector<vector<int>> permute(vector<int>& nums) { 
            vector<vector<int>> res;
            sort(nums.begin(), nums.end());
            do { 
                res.push_back(nums);
            }while(next_permutation(nums.begin(), nums.end()));
            return res;
        }
    };

方法二：  
  采用dfs。  
代码：

class Solution { 
    public:
        void dfs(int cur, vector<int>& temp, vector<vector<int>>& res, vector<int>& used, vector<int>& nums) { 
            if(cur == nums.size()) { 
                res.push_back(temp);
                return;
            }
            for(int i = 0; i < nums.size(); i++) { 
                if(used[i] == 0) { 
                    used[i] = 1;
                    temp.push_back(nums[i]);
                    dfs(cur + 1, temp, res, used, nums);
                    temp.pop_back();
                    used[i] = 0;
                }
            }
        }
        
        vector<vector<int>> permute(vector<int>& nums) { 
            int n = nums.size();
            vector<int> temp;
            vector<vector<int>> res;
            if(n == 0) { 
                return res;
            }
            vector<int> used(n, 0);
            dfs(0, temp, res, used, nums);
            return res;
        }
    };

# 字母大小写全排列 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 8]  
分析：  
  简单的模拟题。  
代码：

class Solution { 
    public:
        
        vector<string> letterCasePermutation(string s) { 
            vector<string> res;
            for(int i = 0; i < s.size(); i++) { 
                if(s[i] >= '0' && s[i] <= '9') { 
                    if(res.empty()) { 
                        string temp = "";
                        temp += s[i];
                        res.push_back(temp);
                    }else { 
                        for(int j = 0; j < res.size(); j++) { 
                            res[j].push_back(s[i]);
                        }
                    }
                }else { 
                    //复制两份
                    int n = res.size();
                    char s1 = tolower(s[i]), s2 = toupper(s[i]);
                    if(n == 0) { 
                        string temp = "";
                        res.push_back(temp + s1);
                        res.push_back(temp + s2);
                        continue;
                    }
                    vector<string> test;
                    for(int j = 0; j < n; j++) { 
                        string temp = res[j];
                        test.push_back(temp + s1);
                        test.push_back(temp + s2);
                    }
                    res = test;
                }
            }
            return res;
        }
    };

# 打家劫舍 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 9]  
分析：  
  动态规划，设dp\[i\]表示房间数为i时的最优解。边界条件：如果只有一个房间，则只能选择偷窃此房间，即dp\[0\] = nums\[0\]；如果有两个房间，由于不能偷窃连续房间，则dp\[1\]为max(nums\[0\], nums\[1\])；如果房间数大于2，对于第i个房间，可以选择不偷窃，即dp\[i\] = dp\[i-1\]，也可以选择偷窃，由于不能偷窃连续房间，则dp\[i\] = dp\[i - 2\] + nums\[i\]。  
代码：

class Solution { 
    public:
        int rob(vector<int>& nums) { 
            if (nums.empty()) { 
                return 0;
            }
            int size = nums.size();
            if (size == 1) { 
                return nums[0];
            }
            vector<int> dp = vector<int>(size, 0);
            dp[0] = nums[0];
            dp[1] = max(nums[0], nums[1]);
            for (int i = 2; i < size; i++) { 
                dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
            }
            return dp[size - 1];
        }
    };

# 三角形最小路径和 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 10]  
分析：  
  动态规划，比较简单，不再分析。  
代码：

class Solution { 
    public:
        int minimumTotal(vector<vector<int>>& triangle) { 
            int m = triangle.size();
            vector<vector<int>> f(m, vector<int>(m, 0));
            f[0][0] = triangle[0][0];
            for(int i = 1; i < m; i++) { 
                f[i][0] = f[i - 1][0] + triangle[i][0];
                f[i][i] = f[i - 1][i - 1] + triangle[i][i];
            }
            for(int i = 0; i < m; i++) { 
                for(int j = 0; j < i; j++) { 
                    if(j == 0 || i == j) { 
                        continue;
                    }else { 
                        f[i][j] = min(f[i - 1][j], f[i - 1][j - 1]) + triangle[i][j];
                    }
                }
            }
            return *min_element(f[m - 1].begin(), f[m - 1].end());
        }
    };

# 填充每个节点的下一个右侧节点指针 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 11]  
分析：  
  层序遍历（与层次遍历不同）：采用bfs，每次将同一层中的所有节点取出，然后进行链接。  
代码：

/* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node* next; Node() : val(0), left(NULL), right(NULL), next(NULL) {} Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {} Node(int _val, Node* _left, Node* _right, Node* _next) : val(_val), left(_left), right(_right), next(_next) {} }; */
    
    class Solution { 
    public:
        Node* connect(Node* root) { 
            if (root == nullptr) { 
                return root;
            }
            queue<Node*> Q;
            Q.push(root);
            while (!Q.empty()) { 
                // 记录当前队列大小
                int size = Q.size();
                // 遍历这一层的所有节点
                for(int i = 0; i < size; i++) { 
                    Node* node = Q.front();
                    Q.pop();
                    // 连接
                    if (i < size - 1) { 
                        node->next = Q.front();
                    }
                    if (node->left != nullptr) { 
                        Q.push(node->left);
                    }
                    if (node->right != nullptr) { 
                        Q.push(node->right);
                    }
                }
            }
            return root;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]: /images/20220829/b4f9015c7fb44f24a578ad6c13a6876d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]: /images/20220829/c8dc45979f6049a79f1bfd2c11f1aa54.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]: /images/20220829/cc124ebdacac4d8ca46a2e86dd281935.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]: /images/20220829/9056e672b6f44f4094b66384dffee064.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]: /images/20220829/1d0f8a2c3f71454ab520b9fd0151293e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 5]: /images/20220829/dd4b06601d154bdba2e7c46447364c58.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 6]: /images/20220829/ce41c6fa4bcb4701bc0670b05e5c0f50.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 7]: /images/20220829/25aefe3433a7401b9d623842ebb15863.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 8]: /images/20220829/e57c9911e680440090b41d8c0bcb9b99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 9]: /images/20220829/b863d0ea58f449fda523abb9a3256b7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 10]: /images/20220829/347b33d27de34a399f4f5ac0c033152c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 11]: /images/20220829/553b939bf3c54e8388f9b939c2ff880d.png