打印零与奇偶数

问题描述

假设有这么一个类：
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];
    }
};

二叉树的锯齿形层次遍历

问题描述

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal

思路

• 首先，将二叉树进行普通的层次遍历，并将结果存在vector<vector> ret中。
  详情见 https://www.irene.ink/admin/write-post.php?cid=77
• 如果i是奇数，将ret[i]进行反转，然后就可以得到最终结果。

题解

class Solution {
public:
    vector<vector<int>> ret;
    vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
        dfs(root, 0);
        int n=ret.size();
        for(int i=0;i<n;i++){
            if(i%2!=0){
                reverse(ret[i].begin(),ret[i].end());
            }
        }
           return ret; 
    }
    void dfs(TreeNode *node, int level) {
        if (node == nullptr) return;
        if (level + 1 > ret.size()) ret.push_back(vector<int>());
        ret[level].push_back(node->val);
        if (node->left != nullptr)dfs(node->left, level + 1);
        if (node->right != nullptr) dfs(node->right, level + 1);
    }
};