每日题目-1.1：每日一题+39+40

1. 每日一题2022：将一维数组转变成二维数组

题目

给你一个下标从 0 开始的一维整数数组 nums 和两个整数 m 和 n 。你需要使用 original 中 所有 元素创建一个 m 行 n 列的二维数组。
nums 中下标从 0 到 n - 1 （都包含）的元素构成二维数组的第一行，下标从 n 到 2 * n - 1 （都 包含 ）的元素构成二维数组的第二行，依此类推。
请你根据上述过程返回一个 m x n 的二维数组。如果无法构成这样的二维数组，请你返回一个空的二维数组。

输入：original = [1,2,3,4], m = 2, n = 2
输出：[[1,2],[3,4]]

输入：original = [3], m = 1, n = 2
输出：[]

输入：original = [1,2,3], m = 1, n = 3
输出：[[1,2,3]]

思路

水题。如果n * m不等于nums.size()直接返回空，否则遍历nums存储到答案数组中。

代码

class Solution {
public:
    vector<vector<int>> construct2DArray(vector<int>& nums, int m, int n) {
        vector<vector<int>> ans(m, vector(n, 0));
        if(n * m != nums.size() || nums.empty()) return {};
        for(int i = 0; i < nums.size(); i++){
            int x = i / n, y = i % n;
            ans[x][y] = nums[i];
        }
        return ans;
    }
};

2. 39: 组合总和

题目

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]] 

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

输入: candidates = [2], target = 1
输出: []

1 <= nums.length <= 30
1 <= nums[i] <= 200
nums 中的每个元素都 互不相同
1 <= target <= 500

思路

因为要输出所有方案，因此没法优化只能暴搜，考虑的是搜索顺序。因此从小往大依次看每个数选多少个。
搜索终止的条件为nums[x]的个数和大于target或下标x大于等于nums.size()。

代码

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> tem;
    vector<vector<int>> combinationSum(vector<int>& nums, int target) {
        // 下标从0开始
        dfs(nums, 0, target);
        return ans;
    }
    void dfs(vector<int>& nums, int x, int target){
        // 满足条件更新答案
        if(target == 0){
            ans.push_back(tem);
            return ;
        }
        // 不可能实现
        if(x >= nums.size()) return ;
        // 从0开始，表示可以选0个
        for(int i = 0; i * nums[x] <= target; i++){
            // 这里已经决定了numsx选了i个的情况，在这基础上进行下一层的搜索
            dfs(nums, x + 1, target - nums[x] * i);
            // 这里实现了重复插入
            tem.push_back(nums[x]);
        }
        // 恢复现场
        for(int i = 0; i * nums[x] <= target; i++){
            tem.pop_back();
        }
    }
};

3. 40: 组合总和2

题目

给定一个数组 nums 和一个目标数 target ，找出 nums 中所有可以使数字和为 target 的组合。
nums 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

1 <= nums.length <= 100
1 <= nums[i] <= 50
1 <= target <= 30

思路

和上题思路相同，不同点在于数字不能无限选，因此只需在判定条件前多加一个次数cnt判定即可。

代码

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> tem;
    vector<vector<int>> combinationSum2(vector<int>& nums, int target) {
        // 先排序
        sort(nums.begin(), nums.end());
        dfs(nums, 0, target);
        return ans;
    }
    void dfs(vector<int> &nums, int x, int target){
        if(target == 0){
            ans.push_back(tem);
            return ;
        }
        if(x >= nums.size()) return ;
        // 记录numx的出现次数
        int k = x + 1;
        while(k < nums.size() && nums[k] == nums[x]) k++;
        int cnt = k - x;
        for(int i = 0; nums[x] * i <= target && i <= cnt; i++){
            // 转入到不同的数字的下标即为k
            dfs(nums, k, target - nums[x] * i);
            tem.push_back(nums[x]);
        }
        for(int i = 0; nums[x] * i <= target && i <= cnt; i++){
            tem.pop_back();
        }
    }
};