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

# leetcode28 KMP模板

#### 思路

KMP 模板
https://www.zhihu.com/question/21923021
– 首先理解 PMT，以及根据 PMT 如何进行回溯；其与 next 不同
– next 数组指的是 pattern 当前位匹配不上时，应该回溯到哪一位继续匹配
– p[j] == t[k] 时更新 next[j+1]==k+1，思路时 j+1 匹配不上时回溯要考虑前一位的匹配情况

#### 源码

``````//
//  leetcode28.cpp
//  test
//
//  Created by sgxm on 2020/8/5.
//

#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>
using namespace std;

vector<int> calNext(string p){
vector<int> next(p.length());
next[0] = -1;
int j = 0,k = -1;
while(j<p.length()-1){
if(k==-1||p[j]==p[k]){
j++;k++;
next[j]=k;
}else{
k = next[k];
}
}
return next;
}
int main(){
string p =      "ababca";
string target = "abcababca";
vector<int> next = calNext(p);
int j = 0,i = 0;
while((j<(int)p.length())&&(i<(int)target.length())){
if(j==-1||p[j]==target[i]){
i++;j++;
}else{
j = next[j];
}
//        if((j<p.length())&&(i<target.length()))
//            cout <<i<<" < "<<target.length()<<","<<j<<" < "<<p.length()<<endl;
}
// cout << j;
if(j == p.length()){
cout <<i-j<<endl;
}else{
cout <<-1<<endl;
}
return 0;
}

``````

# 4.5算法之动态规划 193:棋盘分割 区间dp

#### 题目

http://noi.openjudge.cn/ch0405/193/

#### 思路

https://blog.csdn.net/nnnnnnnnnnnny/article/details/51592665

#### 源码

``````//
//  193.cpp
//  test
//
//  Created by sgxm on 2020/8/3.
//

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <memory.h>
#include <iomanip>
#include <string.h>
#define maxn 15
using namespace std;

int dp[15][8][8][8][8];
int s[8][8][8][8];
int tb[8][8];
int n;
int calSum(int x1,int y1,int x2,int y2){
int sum = 0;
for(int i = x1;i<=x2;++i){
for(int j = y1;j <= y2;++j){
sum+=tb[i][j];
}
}
return sum*sum;
}
int calDp(int k,int x1,int y1,int x2,int y2){
int MIN = 99999999;

if(dp[k][x1][y1][x2][y2]!=-1){
return dp[k][x1][y1][x2][y2];
}
if(k == 1){
return dp[k][x1][y1][x2][y2]=s[x1][y1][x2][y2];
}
dp[k][x1][y1][x2][y2]=MIN;
//横向划分
for(int x = x1;x<x2;++x){
int t1 = calDp(k-1, x1, y1, x, y2);
int t2 = calDp(k-1,x+1,y1,x2,y2);
int t = min(t1+s[x+1][y1][x2][y2],t2+s[x1][y1][x][y2]);
MIN = min(MIN,t);
}
for(int y = y1;y<y2;++y){
int t1 = calDp(k-1,x1,y1,x2,y);
int t2 = calDp(k-1,x1,y+1, x2, y2);
int t = min(t1+s[x1][y+1][x2][y2],t2+s[x1][y1][x2][y]);
MIN = min(MIN,t);
}
MIN=min(MIN,dp[k][x1][y1][x2][y2]);
//cout<<k<< " "<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" = "<<MIN<<endl;
return  dp[k][x1][y1][x2][y2]=MIN;

}
int main(){
cin >> n;
for(int i = 0;i < 8;++i){
for(int j = 0;j < 8;++j){
cin >> tb[i][j];
}
}
memset(dp, -1,sizeof(dp));
//init Sum
for(int x1 = 0;x1 < 8;++x1){
for(int y1 = 0;y1 < 8;++y1){
for(int x2 = x1;x2<8;++x2){
for(int y2 = y1;y2<8;++y2){
s[x1][y1][x2][y2]=calSum(x1,y1,x2,y2);
}
}
}
}
//calDp(2,5,5,6,7);
int sum2 = calDp(n, 0, 0, 7, 7);
double res = 1.0*n*calDp(n, 0, 0, 7, 7)-s[0][0][7][7];
cout<<setiosflags(ios::fixed)<<setprecision(3)<<sqrt(res/(n*n))<<endl;
return 0;
}

``````

# 4.5算法之动态规划 191:钉子和小球 概率

#### 题目

http://noi.openjudge.cn/ch0405/191/

#### 思路

n = 2 时，第 0 层为钉子的上一层，初始小球

– 其上方钉子空则上两层对应小球数量直接累加
– 左侧钉子不空则左侧钉子上方小球数量一半累加到该位置
– 右侧同理

#### 源码

``````//
//  191.cpp
//  test
//
//  Created by bytedance on 2020/7/30.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
vector<vector<long long>> dp;
vector<vector<char>> cnt;
long long gcd(long long x,long long y){
return y?gcd(y,x%y):x;
}
int main(){
long long n,m;
cin >> n >> m;
cnt.resize(n+1,vector<char>(n+1));
dp.resize(n+1,vector<long long>(n+1,0));
for(long long i = 1;i <= n; ++i){
for(long long j = 1;j <= i; ++j){
char c;
cin >> c;
cnt[i][j]=c;
}
}
//
dp[0][0] = pow(2,n);
for(long long i = 1;i <= n;++i){
for(long long j = 0;j <= i; ++j){
//处理左右边界
if(j == 0){
if(cnt[i][j+1]=='*'){
dp[i][j]=dp[i-1][j]/2;
}else{
dp[i][j]=0;
}
}else if(j == i){
if(cnt[i][j]=='*'){
dp[i][j]=dp[i-1][j-1]/2;
}else{
dp[i][j]=0;
}
}else{
if(cnt[i-1][j]=='.'){
dp[i][j]+=dp[i-2][j-1];
}
if(cnt[i][j]=='*'){
dp[i][j]+=dp[i-1][j-1]/2;
}
if(cnt[i][j+1]=='*'){
dp[i][j]+=dp[i-1][j]/2;
}
}
}
}

long long a = dp[n][m],b = dp[0][0];
long long gc=gcd(b,a);
a/=gc;
b/=gc;
cout << a<<"/"<<b;

return 0;
}

``````