常见算法题

class Solution {

public:

    void inorder(TreeNode* root, vector<int>& res) {

        if (!root) {

            return;

        }

        inorder(root->left, res);

        res.push_back(root->val);

        inorder(root->right, res);

    }

    vector<int> inorderTraversal(TreeNode* root) {

        vector<int> res;

        inorder(root, res);

        return res;

    }

};

class Solution {

public:

    vector<vector<int>> levelOrder(TreeNode* root) {

        vector <vector <int>> ret;

        if (!root) {

            return ret;

        }

        queue <TreeNode*> q;

        q.push(root);

        while (!q.empty()) {

            int currentLevelSize = q.size();

            ret.push_back(vector <int> ());

            for (int i = 1; i <= currentLevelSize; ++i) {

                auto node = q.front(); q.pop();

                ret.back().push_back(node->val);

                if (node->left) q.push(node->left);

                if (node->right) q.push(node->right);

            }

        }

        return ret;

    }

};

class Solution {

public:

    TreeNode* invertTree(TreeNode* root) {

        if (root == nullptr) {

            return nullptr;

        }

        TreeNode* left = invertTree(root->left);

        TreeNode* right = invertTree(root->right);

        root->left = right;

        root->right = left;

        return root;

    }

};

class Solution {

private:

    void dfs(vector<vector<char>>& grid, int r, int c) {

        int nr = grid.size();

        int nc = grid[0].size();

        grid[r][c] = '0';

        if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);

        if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);

        if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);

        if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);

    }

public:

    int numIslands(vector<vector<char>>& grid) {

        int nr = grid.size();

        if (!nr) return 0;

        int nc = grid[0].size();

        int num_islands = 0;

        for (int r = 0; r < nr; ++r) {

            for (int c = 0; c < nc; ++c) {

                if (grid[r][c] == '1') {

                    ++num_islands;

                    dfs(grid, r, c);

                }

            }

        }

        return num_islands;

    }

};

class Solution {

public:

    void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){

        // 所有数都填完了

        if (first == len) {

            res.emplace_back(output);

            return;

        }

        for (int i = first; i < len; ++i) {

            // 动态维护数组

            swap(output[i], output[first]);

            // 继续递归填下一个数

            backtrack(res, output, first + 1, len);

            // 撤销操作

            swap(output[i], output[first]);

        }

    }

    vector<vector<int>> permute(vector<int>& nums) {

        vector<vector<int> > res;

        backtrack(res, nums, 0, (int)nums.size());

        return res;

    }

};

class Solution:

    def compareVersion(self, version1: str, version2: str) -> int:

        ver1 = version1.split('.')

        ver2 = version2.split('.')

        # 用int可以去除前导零

        len1 = len(ver1)

        len2 = len(ver2)

        if len1 > len2:

            ver2.extend(['0'] * (len1 - len2))

        if len2 > len1:

            ver1.extend(['0'] * (len2 - len1))

        for i in range(max(len1, len2)):

            if int(ver1[i]) > int(ver2[i]):

                return 1

            elif int(ver1[i]) < int(ver2[i]):

                return - 1

        return 0

print(Solution().compareVersion(version1 = "1", version2 = "1.1"))

class Solution {

public:

    int findTargetSumWays(vector<int>& nums, int S) {

        int sum = 0;

        for (int i = 0; i < nums.size(); i++) sum += nums[i];

        if (S > sum) return 0; // 此时没有方案

        if ((S + sum) % 2 == 1) return 0; // 此时没有方案

        int bagSize = (S + sum) / 2;

        vector<int> dp(bagSize + 1, 0);

        dp[0] = 1;

        for (int i = 0; i < nums.size(); i++) {

            for (int j = bagSize; j >= nums[i]; j--) {

                dp[j] += dp[j - nums[i]];

            }

        }

        return dp[bagSize];

    }

};

class Solution {

public:

    int findTargetSumWays(vector<int>& nums, int S) {

        long sum = 0;

        for (const int &it : nums) sum += it;

        if ((S + sum) % 2 == 1 || S > sum) return 0;

        S = (S + sum) / 2;

        int *dp = new int[S + 1];

        memset(dp, 0, (S + 1) * sizeof(int));

        dp[0] = 1;

        for (const int &it : nums) {

            for (int j = S; j >= it; j--)

                dp[j] += dp[j - it];

        }

        int ans = dp[S];

        delete[] dp;

        return ans;

    }

};

class Solution {

public:

    int findTargetSumWays(vector<int>& nums, int S) {

        return dfs(nums, S, 0);

    }

    int dfs(vector<int> &nums, uint target, int left) {

        if (target == 0 && left == nums.size()) return 1;

        if (left >= nums.size()) return 0;

        int ans = 0;

        ans += dfs(nums, target - nums[left], left + 1);

        ans += dfs(nums, target + nums[left], left + 1);

        return ans;

    }

};

struct Nagato {

    int x, y;

    int rest;

    Nagato(int _x, int _y, int _r): x(_x), y(_y), rest(_r) {}

};

class Solution {

private:

    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public:

    int shortestPath(vector<vector<int>>& grid, int k) {

        int m = grid.size(), n = grid[0].size();

        if (m == 1 && n == 1) {

            return 0;

        }

        k = min(k, m + n - 3);

        bool visited[m][n][k + 1];

        memset(visited, false, sizeof(visited));

        queue<Nagato> q;

        q.emplace(0, 0, k);

        visited[0][0][k] = true;

        for (int step = 1; q.size() > 0; ++step) {

            int cnt = q.size();

            for (int _ = 0; _ < cnt; ++_) {

                Nagato cur = q.front();

                q.pop();

                for (int i = 0; i < 4; ++i) {

                    int nx = cur.x + dirs[i][0];

                    int ny = cur.y + dirs[i][1];

                    if (nx >= 0 && nx < m && ny >= 0 && ny < n) {

                        if (grid[nx][ny] == 0 && !visited[nx][ny][cur.rest]) {

                            if (nx == m - 1 && ny == n - 1) {

                                return step;

                            }

                            q.emplace(nx, ny, cur.rest);

                            visited[nx][ny][cur.rest] = true;

                        }

                        else if (grid[nx][ny] == 1 && cur.rest > 0 && !visited[nx][ny][cur.rest - 1]) {

                            q.emplace(nx, ny, cur.rest - 1);

                            visited[nx][ny][cur.rest - 1] = true;

                        }

                    }

                }

            }

        }

        return -1;

    }

};