提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

LeetCode刷题系列(3)

LeetCode 系列 刷题
2023-06-13 09:12:50 时间

1 全排列

方法一：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;
    }
};

‍

2 字母大小写全排列

分析：简单的模拟题。

代码：

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

3 打家劫舍

分析：动态规划，设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];
    }
};

4 三角形最小路径和

分析：动态规划，比较简单，不再分析。

代码：

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());
    }
};

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

分析：层序遍历（与层次遍历不同）：采用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;
    }
};

相关文章