头像

南街戏子




离线:1小时前


最近来访(133)
用户头像
马马奇马
用户头像
Cold_heartless
用户头像
NULL_
用户头像
AcWing2AK
用户头像
一万小时定律
用户头像
V1
用户头像
Daisies
用户头像
Resurgence1001
用户头像
4444486
用户头像
V1CI-_-
用户头像
Fivk
用户头像
xmgck2022
用户头像
WangJY
用户头像
Anwma
用户头像
椒盐土豆
用户头像
冰之韵
用户头像
Cyzh
用户头像
a阿哲啊
用户头像
RyanMoriarty
用户头像
我要出去乱说


南街戏子
21小时前
class Solution {
public:
    int maximum69Number (int num) {
        vector<int> a;
        while(num){
            a.push_back(num % 10);
            num /= 10;
        }

        int res = 0;
        bool flag = false;
        for(int i = a.size() - 1;i >=0 ;i --)
            if(a[i] == 6 && !flag){
                res = res * 10 + 9;
                flag = true;
            }else res = res * 10 + a[i];

        return res;
    }
};



南街戏子
21小时前
class Solution {
public:
    int minFlips(int a, int b, int c) {
        int res = 0;
        for(int i = 31;i >= 0; i--){
            int x1 = a >> i & 1;
            int x2 = b >> i & 1;
            int x3 = c >> i & 1;
            if(x3 == 1 && (x1 == 1 || x2 ==1))continue;
            else if(x3 == 1 && x1 ==0 && x2 == 0)res++;
            else if(x3 == 0 && x1 == 1 && x2 == 1)res += 2;
            else if(x3 == 0 && (x1 == 1 || x2 == 1))res++;
        }

        return res;
    }
};



南街戏子
21小时前
class Solution {
public:
    bool check(int x){
        while(x){
            int t = x % 10;
            x /= 10;
            if(t == 0)return false;
        }

        return true;
    }
    vector<int> getNoZeroIntegers(int n) {
        for(int i = 1;;i ++)
            if(check(i) && check(n - i)){
                return {i , n - i};
            }
    }
};


活动打卡代码 LeetCode 70. 爬楼梯

class Solution {
public:

    int climbStairs(int n) {
        int a = 1, b = 1;
        for(int i = 2;i <= n; i ++){
            int c = a + b;
            int d = b;
            b = c;
            a = d;
        }
        return b;
    }
};


活动打卡代码 LeetCode 46. 全排列

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    bool st[20];

    void dfs(vector<int> & nums,int u,vector<int> &path){
        if(u == nums.size()){
            res.push_back(path);
            return ;
        }

        for(int i = 0; i < nums.size(); i ++){
            if(!st[i]){
                st[i] = true;
                path.push_back(nums[i]);
                dfs(nums,u + 1,path);
                st[i] = false;
                path.pop_back();
            }
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums,0,path);
        return res;
    }
};



更好的阅读体验

题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。 

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

样例

输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。

算法1

(剪枝)

C++ 代码

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    void dfs(vector<int>& candidates,int & target,int s,int u){
        if(s > target)return ;
        if(s == target){
            res.push_back(path);
            return ;
        }

        for(int i = u; i < candidates.size() ; i ++){ 
        //如果当前这个数可以选的话,那么便一直选,否则的话直接进入下一个枝头即可
                path.push_back(candidates[i]);
                dfs(candidates,target,candidates[i] + s,i);
                path.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates,target,0,0);
        return res;
    }
};

算法2

(爆搜)

类似于完全背包,用这种方式可以解决下一题,不过在这里有个数的限制,类似于多重背包

C++ 代码

class Solution {
public:

    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> combinationSum(vector<int>& c, int target) {
        dfs(c, 0, target);
        return ans;
    }

    void dfs(vector<int>& c, int u, int target) {
        if (target == 0) {
            ans.push_back(path);
            return;
        }
        if (u == c.size()) return;

        for (int i = 0; c[u] * i <= target; i ++ ) { //枚举当前数可以选多少个,不超过target即可
            dfs(c, u + 1, target - c[u] * i);
            path.push_back(c[u]);
        }

        for (int i = 0; c[u] * i <= target; i ++ ) { //恢复现场
            path.pop_back();
        }
    }
};


活动打卡代码 LeetCode 40. 组合总和 II

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    vector<vector<int>> combinationSum2(vector<int>& c, int target) {
        sort(c.begin(),c.end());
        dfs(c,0,target);
        return res;
    }


    void dfs(vector<int>& c,int u,int target){
        if(target == 0){
            res.push_back(path);
            return ;
        }

        if(u == c.size())return ;

        int k = u + 1;
        while(k < c.size() && c[k] == c[u]) k ++;
        int count = k - u;

        for(int i = 0 ; i <= count && i * c[u] <= target; i ++){
            dfs(c,k,target - i * c[u]);
            path.push_back(c[u]);
        }

        for(int i = 0 ; i <= count && i * c[u] <= target; i ++){
            path.pop_back();
        }

    }
};


活动打卡代码 LeetCode 39. 组合总和

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    void dfs(vector<int>& candidates,int & target,int s,int u){
        if(s > target)return ;
        if(s == target){
            res.push_back(path);
            return ;
        }

        for(int i = u; i < candidates.size() ; i ++){
                path.push_back(candidates[i]);
                dfs(candidates,target,candidates[i] + s,i);
                path.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates,target,0,0);
        return res;
    }
};


活动打卡代码 LeetCode 38. 外观数列

class Solution {
public:
string dfs(int n){
        string res;
        if(n == 1){
            res = "1";
            return res;
        }
        else {
            auto c = dfs(n - 1);
            res = "";
            for(int i = 0 ; i < c.size(); i ++){
                int j = i + 1;
                int count = 0;
                while(j < c.size() && c[i] == c[j])j ++;
                count = j - i;
                res = res + char (count + '0') + c[i];
                i = j - 1;
            }

            return res;
        }
    }  

    string countAndSay(int n) {
        return dfs(n);
    }
};


活动打卡代码 LeetCode 37. 解数独

class Solution {
public:
    bool row[9][9]={false};
    bool col[9][9]={false};
    bool cell[3][3][9]={false};

    void solveSudoku(vector<vector<char>>& board) {
        for(int i = 0 ; i < 9 ; i ++){
            for(int j = 0; j < 9; j ++)
                if(board[i][j] != '.'){
                    int t = board[i][j] - '1';
                    row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
                }
        }    

        dfs(board,0,0);
    }

    bool dfs(vector<vector<char>> & board, int x, int y){
        if(y == 9) x ++ ,y = 0;
        if(x == 9)return true;

        if(board[x][y] != '.')return dfs(board,x, y + 1);

        for(int i = 0 ; i < 9 ; i ++ )
            if(!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]){
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
                board[x][y] = i + '1';
                if(dfs(board,x,y + 1))return true;
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
                board[x][y] = '.';
            }

        return false;
    }
};