乘积最大子序列

问题描述

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray

思路

• 首先对特殊情况，num.size()==0||num.size()==1进行处理。如果nums为空，返回0；如果只有一个数，返回那个唯一的数即可。
• 当num.size()>=2时，初始化max=-∞，i从2开始，递增到n结束，j从i开始，递增到n结束。如此循环可以得出以nums[i]为开始的所有子序列的乘积。当子序列的乘积大于最大值时，令最大值等于子序列的乘积即可。

题解

class Solution {
public:
    int maxProduct(vector<int> &nums) {
        int n = nums.size();
        if (n == 0)
            return 0;
        else if(n==1){
            return nums[0];
        }
        int max = INT_MIN;
        int tmp;
        for (int i  = 0; i < n; i++) {
            tmp=1;
            for (int j =i; j < n; j++) {
                tmp = nums[j] * tmp;
                if (max < tmp) {
                    max = tmp;
                }
            }
        }
        return max;
    }
};

有效的数独

问题描述

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1:
输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: true

示例 2:
输入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 '.' 。
给定数独永远是 9x9 形式的。

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

思路

• vector<vector<int>> rows(9, vector<int>(9, 0)); 每行的数字1-9未出现过
• vector<vector<int>> cols(9, vector<int>(9, 0)); 每列的数字1-9未出现过
• vector<vector<int>> cell(9, vector<int>(9, 0)); 每个3x3 宫格内数字1-9未出现过
  在遍历的过程中，i行的数字num（char）第一次出现时，将rows[i]中第num-'1'+1列的值即rowsi置为1，如果在i行第二次出现即rowsi==1，则不是有效的数独，返回false;
  其他两种，同理。

其中非常有意思的一点是，将9*9的宫格转化为9个3*3的宫格时，每个3*3的宫格占cell中的一行，在遍历i、j时，用(i/3)*3+j/3的值即可计算出board[i][j]在第几个宫格。

题解

class Solution {
public:
    bool isValidSudoku(vector<vector<char>> &board) {
        vector<vector<int>> rows(9, vector<int>(9, 0));
        vector<vector<int>> cols(9, vector<int>(9, 0));
        vector<vector<int>> cell(9, vector<int>(9, 0));
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                int e = board[i][j] - '1';
                if (rows[i][e] == 0) rows[i][e] = 1;
                else return false;
                if (cols[j][e] == 0) cols[j][e] = 1;
                else return false;
                if(cell[(i/3)*3+j/3][e]==0) cell[(i/3)*3+j/3][e]=1;
                else return false;
            }
        }
        return true;
    }
};

组合总和 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();
        }
    }
};

跳跃游戏

问题描述

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

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