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

题目

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

思路

双维度 01 背包问题,m,n是容量,value 都是1,遍历个数,遍历容量,对容量进行状态压缩

源码

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/

思路

直接计算即可,使用 vector 模拟优先级队列,计算当前位置应该是第几大的数 k– 后直接对应下标,不需要考虑向上或向下取整问题

源码

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/

思路

与运算特性,只会递减,其中只会出现 1 变成 0
所以,以 r 为边界的 func 最多只会有 32 种结果,即从全1开始每次只少一个1,在此基础上遍历 r in [1,n]

源码

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.
//  Copyright © 2020 sgxm. All rights reserved.
//

#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/
描述
将一个8*8的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了(n-1)次后,连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)

原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘,并使各矩形棋盘总分的均方差最小。
均方差,其中平均值,xi为第i块矩形棋盘的总分。
请编程对给出的棋盘及n,求出O’的最小值。
输入
第1行为一个整数n(1 < n < 15)。
第2行至第9行每行为8个小于100的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。
输出
仅一个数,为O’(四舍五入精确到小数点后三位)。

思路

区间 dp, dp[k][x1][y1][x2][y2] 表示将,(x1,y1):(x2,y2)区间内的矩形分成 k 块,均方误差的最小值
该问题是一个一对多问题,即两个子矩形的最优解拼接为一个大矩形后不一定为最优解,但是一个大矩形的最优解一定可以由两个子矩形的解拼接而成,所以针对子矩形遍历其横向划分和纵向划分。

其中要最小化平方和即可,具体推导过程参考该博客
https://blog.csdn.net/nnnnnnnnnnnny/article/details/51592665

源码

//
//  193.cpp
//  test
//
//  Created by sgxm on 2020/8/3.
//  Copyright © 2020 sgxm. All rights reserved.
//

#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(n+1)/2颗钉子,还有(n+1)个格子(当n=5时如图1)。每颗钉子和周围的钉子的距离都等于d,每个格子的宽度也都等于d,且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。
让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落,小球每碰到一个钉子都可能落向左边或右边(概率各1/2),且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。
我们知道小球落在第i个格子中的概率pi=,其中i为格子的编号,从左至右依次为0,1,…,n。
现在的问题是计算拔掉某些钉子后,小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。

输入
第1行为整数n(2 <= n <= 50)和m(0 <= m <= n)。以下n行依次为木板上从上至下n行钉子的信息,每行中’*’表示钉子还在,’.’表示钉子被拔去,注意在这n行中空格符可能出现在任何位置。
输出
仅一行,是一个既约分数(0写成0/1),为小球落在编号为m的格子中的概pm。既约分数的定义:A/B是既约分数,当且仅当A、B为正整数且A和B没有大于1的公因子。

思路

n = 2 时,第 0 层为钉子的上一层,初始小球 2^n
从第 0 层开始,第一个钉子编号为 1,第一个坑位编号为 0,对于每一个坑位考虑
– 其上方钉子空则上两层对应小球数量直接累加
– 左侧钉子不空则左侧钉子上方小球数量一半累加到该位置
– 右侧同理

最后辗转相除法求最大公约数,约分

源码

//
//  191.cpp
//  test
//
//  Created by bytedance on 2020/7/30.
//  Copyright © 2020 bytedance. All rights reserved.
//

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