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