6405

hhhhhhhhhy

Cold_heartless
NULL_
AcWing2AK

V1
Daisies
WA声闹彻明
4444486
V1CI-_-
Fivk
xmgck2022
WangJY
Anwma

Cyzh
a阿哲啊
RyanMoriarty

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


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


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


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


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 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

#### 样例

输入：candidates = [2,3,6,7], target = 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();
}
}
};


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();
}

}
};


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


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);
}
};


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