# leetcode 474 Ones and Zeroes 双维度01背包问题

#### 题目

https://leetcode.com/problems/ones-and-zeroes/submissions/

#### 源码

``````class Solution {
public:
vector<int> ones;
vector<int> zeros;
vector<vector<int>> mn;
int findMaxForm(vector<string>& strs, int m, int n) {
if(strs.size()==0)return 0;
if(m==0&&n==0)return 0;
ones.resize(strs.size());
zeros.resize(strs.size());
mn.resize(m+1,vector<int>(n+1,0));
for(int i = 0;i < strs.size();++i){
int o = 0;
for(int k = 0;k < strs[i].size();++k){
if(strs[i][k]=='1')o++;
}
ones[i]=o;
zeros[i]=strs[i].length()-o;
}
//bag
for(int i = 0;i < strs.size();++i){
//cout<<endl <<i<<endl;
for(int m1 = m;m1>=zeros[i];--m1){
for(int n1 = n;n1>=ones[i];--n1){
mn[m1][n1]=max(mn[m1][n1],mn[m1-zeros[i]][n1-ones[i]]+1);
//cout <<m1<<","<<n1<<" = "<<mn[m1][n1]<<endl;
}
}
}
return mn[m][n];
}
};
``````

# leetcode 322 Coin Change 完全背包

#### 题目

https://leetcode.com/problems/coin-change/submissions/

#### 思路

https://zhuanlan.zhihu.com/p/141627678?from_voters_page=true
min 类型的完全背包问题，和零一背包的唯一区别在于 j 从 coins 开始，这样可以复用之间 的结果，该写法是状态压缩的写法

#### 源码

``````class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int>dp(amount+1,INT_MAX-10);
dp[0] = 0;
for(int i = 0;i < coins.size();++i){
for(int j = coins[i];j <=amount;++j){
if(dp[j] != INT_MAX)
dp[j] = min(dp[j],dp[j-coins[i]]+1);
}
}
return dp[amount]==INT_MAX-10?-1:dp[amount];
}
};
``````

# leetcode 46. Permutations DFS

#### 题目

https://leetcode.com/problems/permutations/

dfs遍历 去重看上一个

#### 源码

``````class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> vis(nums.size(),false);
vector<int>path;
dfs(nums,path,vis);
return res;
}
void dfs(vector<int>& nums,vector<int>& path,vector<bool> vis){
if(path.size()==nums.size()){
res.push_back(path);
return;
}
for(int i = 0;i < nums.size();++i){
if(vis[i])continue;
path.push_back(nums[i]);
vis[i]=true;
dfs(nums,path,vis);
vis[i]=false;
path.pop_back();
}
}
};
``````

# leetcode 60 Permutation Sequence

#### 题目

https://leetcode.com/problems/permutation-sequence/submissions/

#### 源码

``````class Solution {
public:
string getPermutation(int n, int k) {
vector<int> q;
for(int i = 1;i <= n; ++i){
q.push_back(i);
}
k--;
string res;
for(int i = n-1;i >= 0 ;--i){
int idx = k/cal(i);
res+=q[idx]+'0';
k%=cal(i);
q.erase(q.begin()+idx);
}
return res;
}
int cal(int n){
return n==0?1:n*cal(n-1);
}
};
``````

# leetcode 31 Next Permutation

#### 题目

https://leetcode.com/problems/next-permutation/

#### 源码

``````class Solution {
public:
void nextPermutation(vector<int>& nums) {
int i = nums.size()-2;
for(;i >= 0;--i){
if(nums[i]<nums[i+1]){
for(int j = nums.size()-1;j > i;--j){
if(nums[j]>nums[i]){
cout << j;
int t = nums[j];
nums[j]=nums[i];
nums[i]=t;
sort(nums.begin()+i+1,nums.end());
i=-1;
break;
}
}
}

}
if(i!=-2){
// sort(nums.begin(),nums.end());
reverse(nums.begin(),nums.end());
}
}
};
``````

``````class Solution {
public:
void nextPermutation(vector<int>& nums) {
//倒着扫描递增序列怎么改都是会变小，找到非递增的数，用后面的最接近它的数交换，sort
//插入排序？

//我的想法时，改变最小数量级的位置，即替换十位，替换百位，替换千位。。。
//那么从十位开始考虑是否该位为非递增位，是则为替换位一共考虑n-1位
//每次考虑时，从最低位开始找比该位大的，因为后面是递增的一定要从低位最小的数找起才能保证变化最小
int n = nums.size();
int end;
bool can=false;
for(int i = 1;i <= n - 1; ++i){
int j = n-1;
int step = i;
while(step--){
if(nums[j]>nums[n-i-1]){
int temp = nums[j];
nums[j]=nums[n-i-1];
nums[n-i-1]=temp;
can = true;
end = n-i-1;
break;
}
j--;
}
if(can)break;

}
cout << end <<endl;
if(can)
sort(nums.begin()+end+1,nums.end());
else
sort(nums.begin(),nums.end());

}
};
``````

# leetcode 43 字符串乘法模板

#### 题目

https://leetcode.com/problems/multiply-strings/submissions/

#### 源码

``````class Solution {
public:
//不要只有一个循环，直接两个循环，计算任意两个数的乘法，然后结果对应的位置可以直接计算，落下去迭代更新
string multiply(string num1, string num2) {
int m = num1.size(),n = num2.size();
if(m == 0||n == 0)return "0";
int pos[m+n]={0};
for(int i = m-1;i >= 0; i--){
for(int j = n-1; j >= 0; j--){
//pos从大存从小存都可以
int mul = (num1[i]-'0')*(num2[j]-'0');
int pl = i+j+1;
int ph = i+j;
int sum = pos[pl]+mul;//这一步也很妙
pos[pl]=sum%10;
pos[ph]+=sum/10;
}
}
string res = "";
for(int i = 0;i < m+n;++i){
//排除开头的0
if(res.length()==0&&pos[i]==0)continue;
res+=('0'+pos[i]);
}
return res.length()==0?"0":res;
}
};
``````

# leetcode 1521 Find a Value of a Mysterious Function Closest to Target 与运算

#### 题目

https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/

#### 源码

``````class Solution {
public:
int closestToTarget(vector<int>& arr, int target) {
set<int> s;
int mn = INT_MAX;
s.insert(arr[0]);
for(int i = 1;i < arr.size();++i){
set<int> t;
for(auto p:s){
t.insert(p&arr[i]);
}
t.insert(arr[i]);
s = t;
for(auto p:s){
//cout << p<<endl;
mn = min(abs(p-target),mn);
}
//cout <<endl;
}
return mn;
}
};
``````