组合总和 II

问题描述

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。

说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。 

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii

思路

本题分为两步

简单的回溯算法
对未完全剪枝的ret进行去重。

去重的方法有两种，效率都比较低

• sort(ret.begin(), ret.end());ret.erase(unique(ret.begin(), ret.end()), ret.end())
• set<vector<int>> sets(ret.begin(), ret.end());ret=vector<vector<int>>(sets.begin(),sets.end())

题解

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ret;
    int n;

    vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
        n = candidates.size();
        sort(candidates.begin(), candidates.end());
        dfs(candidates, 0, 0, target);
        sort(ret.begin(), ret.end());
        ret.erase(unique(ret.begin(), ret.end()), ret.end());
        return ret;
    }

    void dfs(vector<int> vec, int sum, int location, int target) {
        if (sum >= target || location == n) {
            if (sum == target) {
                ret.push_back(tmp);
            }
            return;
        }
        for (int i = location; i < n; i++) {
            tmp.push_back(vec[i]);
            sum += vec[i];
            dfs(vec, sum, i + 1, target);
            sum = sum - vec[i];
            tmp.pop_back();
        }
    }
};

打印零与奇偶数

问题描述

假设有这么一个类：
class ZeroEvenOdd {
  public ZeroEvenOdd(int n) { ... }  // 构造函数
public void zero(printNumber) { ... } // 仅打印出 0
public void even(printNumber) { ... } // 仅打印出 偶数
public void odd(printNumber) { ... } // 仅打印出 奇数
}
相同的一个 ZeroEvenOdd 类实例将会传递给三个不同的线程：

线程 A 将调用 zero()，它只输出 0 。
线程 B 将调用 even()，它只输出偶数。
线程 C 将调用 odd()，它只输出奇数。
每个线程都有一个 printNumber 方法来输出一个整数。请修改给出的代码以输出整数序列 010203040506... ，其中序列的长度必须为 2n。

示例 1：
输入：n = 2
输出："0102"
说明：三条线程异步执行，其中一个调用 zero()，另一个线程调用 even()，最后一个线程调用odd()。正确的输出为 "0102"。

示例 2：
输入：n = 5
输出："0102030405"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/print-zero-even-odd

还没有学会，学会了再写叭，嘻嘻

跳跃游戏

问题描述

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。

示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game

思路

range是能够跳跃的最远距离，从0开始遍历range范围内的数，如果第i位能走的步数nums[i]+i大于range，则将range增大到nums[i]+i。
如果在range范围内走不到最后一个，那么将永远到达不了最后一个。

来源：https://leetcode-cn.com/problems/jump-game/solution/fan-fu-xiu-gai-ke-yi-dao-da-de-zui-da-shang-xian-b/
作者：肖克莱

题解

class Solution {
public:
    bool canJump(vector<int> &nums) {
        int range = nums[0];
        for (int i = 0; i <= range; i++) {
            if (range < i + nums[i]) { range = i + nums[i]; }
            if (range >= nums.size() - 1) return true;
        }
        return false;
    }
};

岛屿数量

问题描述

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:
输入:
11110
11010
11000
00000

输出: 1

示例 2:
输入:
11000
11000
00100
00011

输出: 3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands

思路

最开始的时候，将所有的小岛的 访问位 置为0；
i从0到grid.size(),j从0到grid[0].size()遍历，如果vis[i][j] && grid[i][j] == '1' 将visi置为true;将其邻接位置的1的 访问位 置为0；
返回结果ans++；
最后返回ans即可。

题解

class Solution {
public:
    int next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, n, m, ans = 0;
    vector<vector<bool>> vis;
    bool check(int x, int y, const vector<vector<char>> &grid) {
        return x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == '1' && !vis[x][y];
    }
    void dfs(int x, int y, const vector<vector<char>> &grid) {
        vis[x][y] = true;
        for (int k = 0; k < 4; k++) {
            if (check(x + next[k][0], y + next[k][1], grid)) dfs(x + next[k][0], y + next[k][1], grid);
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        n = grid.size(), m = grid[0].size();
        vis.resize(n);
        for (int i = 0; i < n; i++) vis[i].resize(m, false);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!vis[i][j] && grid[i][j] == '1') {
                    dfs(i, j, grid);
                    ans++;
                }
            }
        }
        return ans;
    }
};

不同路径

问题描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。

示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:
输入: m = 7, n = 3
输出: 28

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths

思路

动态规划
当i==0或者j==0时，dp[i][j]=1;
当i>1或者j>1时，dp[i][j]=dp[i][j-1]+dp[i+1][j];
最后返回dp[m-1][n-1]即可。

题解

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp;
        dp.resize(m);
        for(int i=0;i<m;i++){
            dp[i].resize(n);
            dp[i][0]=1;
        }
        for(int i=0;i<n;i++){
            dp[0][i]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }
};