秋招突击——算法打卡——6/4——复习{（状态压缩DP）小国王}——新做：{三数之和、最接近的三数之和}

复习

状态压缩DP——小国王

• 这道题已经是第三天看了，今天在看个45分钟，然后自己一个人独立把代码写一遍，把之前看的东西都理一遍。
• 链接奉上
  • 第一天分析链接
    
  • 第二天代码链接
    

思路分析

合法状态和状态转换

注意第一个遍历的边界条件，这里弄错了，应该是小于，不应该是小于等于

// 计算所有的合法状态
// 注意，这里应该是小于，而不是小于等于，最后一个移位的情况完全没有满足
// 写错了： for (int i = 0; i <= 1<< n; ++i) {
  for (int i = 0; i < 1<< n; ++i) {
        if (check(i)){
            state.push_back(i);
            cnt[i] = count(i);
        }
    }

    // 计算所有的合法转移的方程
    for (int i = 0; i < state.size(); ++i) {
        for (int j = 0; j < state.size(); ++j) {
            int a = state[i],b = state[j];
            if((a & b) == 0 && check(a | b) ){
                head[i].push_back(j);
            }
        }
    }

最终实现代码

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 12;// 这里是为了简便运算

const int M = 1<< 10; // 这里是定义了最多的状态数，相当于是2的十次方

const int k = 110;

int n,m;  // n保存棋盘的大小，m是国王的数量

vector<int> state;// 保存所有合法的状态

vector<int> head[M]; // 最多有M种状态，这里是每一个状态的合法转移状态情况
int cnt[M]; // 每一种状态的国王的个数，也就是1的个数

LL f[N][k][M];

bool check(int x){
    // 检查某一个状态是否合法
    for (int i = 0; i < n; ++i) {
        if ((x >> i & 1) && (x >> (i+ 1) & 1)){
            return false;
        }
    }
    return true;
}

int count(int x){
    int r = 0;
    for (int i = 0; i < n; ++i) {
        if(x >> i & 1 ) r++;
    }
    return r;
}

int main(){
    cin>>n>>m;

    // 计算所有的合法状态
    // 因为通过+1进行遍历，所以要从零开始
    for (int i = 0; i < 1<< n; ++i) {
        if (check(i)){
            state.push_back(i);
            cnt[i] = count(i);
        }
    }

    // 计算所有的合法转移的方程
    for (int i = 0; i < state.size(); ++i) {
        for (int j = 0; j < state.size(); ++j) {
            int a = state[i],b = state[j];
            if((a & b) == 0 && check(a | b) ){
                head[i].push_back(j);
            }
        }
    }

    // 实现状态转移的计算，这里是以下标作为直接索引的。
    f[0][0][0] = 1;
    for (int i = 1; i <= (n + 1) ; ++i) {
        for (int j = 0; j <= m; ++j) {
            for (int a = 0; a < state.size(); ++a) {
                for (auto b:head[a]) {
                    int c = cnt[state[a]];
                    if (c <= j){
                        f[i][j][a] += f[i -1][j - c][b];
                    }
                }
            }
        }
    }

    // 正常情况下，应该遍历所有的子状态,但是这里相当于是下一行完全没摆放的状态
    cout<<f[n + 1][m][0]<<endl;
}

• 本来吧，就准备看一个小时的，结果找bug就找了差不多半个小时，看他写差不多又用了半个小时，然后自己写笔记半个小时，一个半小时，不应该，下次自己做。

新作

三数之和

• 题目链接
  

个人实现

• 之前好像做过一个两数只和，那道题要先排序，然后再用双指针进行遍历，那么这道题能不能也转换成双指针？
• 因为相加为特定地和，而且是不能重复的，所以还是要排序解决的。

实现代码

• 这里有点问题了，因为如何使用对应的set集合并不知道，要是用set集合进行去重行。
• 有两个问题
  • 没理解题意，一个元素的值不能重复，而且元素的索引也不能重复,zuizh
  • set使用的不多，忘得差不多了

#include 
#include 
#include 
#include 

using namespace std;


vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(),nums.end(),[](auto a,auto b){
        return a < b;
    });
    vector<vector<int>> res;
    set<vector<int>> reIdx;
    for (int i = 0; i < nums.size(); ++i) {
        int tar = 0 - nums[i];
        int a = 0,b = nums.size() - 1;
        while(a < b){
            if (a == i) a ++ ;
            else if (b == i) b -- ;
            else{
                if (nums[a] + nums[b] > tar) b--;
                else if (nums[a] + nums[b] < tar) a ++;
                else{
                    if(i < a)
                        reIdx.insert({nums[i],nums[a],nums[b]});
                    else if(i < b)
                        reIdx.insert({nums[a],nums[i],nums[b]});
                    else
                        reIdx.insert({nums[a],nums[b],nums[i]});
                    b-- ,a++;
                }
            }
        }
    }

    for (auto temp : reIdx) {
        res.push_back({temp[0],temp[1],temp[2]});
    }
    return res;
}


int main(){
    vector<int> s = {-1,0,1,2,-1,-4};
    vector<vector<int>> res = threeSum(s);
    for (auto & re : res) {
        cout<<re[0]<<re[1]<<re[2]<<endl;
    }
}

参考做法

• 双指真的做法就是有序，所以需要排序。这里有一个细节，就是如果当前的指针是和下一个指针相同，就跳过，这里是满足了咩有重复
• 这里是从左到右三个指针，固定最左边的，然后中间和最右边的一定出现在最左边的指针的右边。这样实现没有重复的问题。

实现代码

• 这里有一个很棒的地方，就是试探，他是计算k-1，不是试探k
  while(j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) k --;

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(),nums.end(),[](auto a,auto b){
        return a < b;
    });
    vector<vector<int>> res;
    for (int i = 0; i < nums.size(); ++i) {
       if(i && nums[i] == nums[i - 1])  continue;
        for (int j = i + 1,k = nums.size() - 1; j < k; ++j) {
            if(j > i + 1 && nums[j] == nums[j - 1])  continue;
            // 这里确实很巧妙,过渡到k不变了,真的蛮厉害的
            while(j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) k --;
            if(nums[i] + nums[j] + nums[k] == 0)
                res.push_back({nums[i], nums[j], nums[k]});
        }
    }

    return res;
}

• 这里还是需要好好整理一下，既然是确定顺序了，不让重复，相当于是确定了一个指针，然后另外两个指针再往后进行遍历

最接近的三数之和

题目链接

个人实现

• 能否和上面一道题一样，使用双指针，完整的遍历一遍，直到左右两边的指针都满足条件，然后在跳出循环。

实现代码

• 不忍卒读，真的，想了半天他的怎么写的，但是就是没想出来，在这里墨迹了差不多二十分钟。不行呀，还是得打一遍他的代码，一遍一遍过一下。

#include 
#include 
#include 
using namespace std;

int threeSumClosest(vector<int>& n, int target) {
    sort(n.begin(),n.end());
    int res = 0,minV = INT_MAX;
    for (int i = 0; i < n.size(); ++i) {
        for (int j = i + 1,k = n.size() - 1; j < n.size(); ++j) {
            if (j + 1 < n.size() && n[j + 1] == n[j]) continue;
//            for (int l = 0; n[j] + n[k - 1] >= target ; ++l) {
//
//            }
            if (k - 1 >= 0 && n[k - 1] == n[k]) {
                k --;
                continue;
            }
            if (minV > (target - n[i] - n[j] - n[k])){
                res = n[i] + n[j] + n[k];
                minV = target - res;
            }
            if( (target - n[i] - n[j] - n[k]) > 0)
                k --;
            else
                j ++;
        }
    }
    return res;
}

int main(){
    int n = 1;
    vector<int> nums = {1,2,3,4};
    int tar = 10;
    cout<<threeSumClosest(nums,tar)<<endl;
}

• 问题在哪里？双指针是知道的，但是写出来就有问题，因为想向着他的方法写的，但是写的很奇怪，写不出来，所以还是要将他的思路和我的思路相结合，重新整合一下代码。
  • 如何处理相同的情况：
  • 如何保证遍历的顺序

参考实现

• 这里的思路就更加明确了，这里是先找到大于等于的情况，然后在缩小一下，就是最小的里面的最大的。
• 这个代码写的很巧妙，得记住，多回忆几遍!!

实现代码

#include 
#include 
#include 
using namespace std;

int threeSumClosest(vector<int>& n, int target) {
   sort(n.begin(),n.end());
   pair<int ,int > res(INT_MAX,INT_MAX); // 这两个数字表示插值和对应的和
   for (int i = 0; i < n.size(); ++i) {
        for (int j = i + 1,k = n.size() - 1; j < k; ++j) {
            while(k - 1 > j && n[i] + n[j] + n[k - 1] >= target) k --;
            int s =  n[i] + n[j] + n[k];
            res = min(res, make_pair(abs(target- s),s));
            if (k - 1 > j){
                s = n[i] + n[j] + n[k - 1];
                res = min(res, make_pair(target- s,s));
            }
        }
    }
   return res.second;
}

int main(){
    int n = 1;
    vector<int> nums = {1,2,3,4};
    int tar = 10;
    cout<<threeSumClosest(nums,tar)<<endl;
}

总结

• 昨天做的两道简单题，今天就该做复杂一点的题目
• 算法复习那道题，浪费了太多时间！！
• 不行呀，算法哪里浪费了太多时间，没有很多时间去学习java，这样不行的！明天开始上午最多一个小时，从十点钟开始学习spring那一套，还有时间，不然没什么时间了。得抓紧。时间控制好。今天中午就花了差不多一个小时，下午还能在学两个小时。
• 明天开始调整了，目前花在算法题的时间太多了，中午和晚上就不写算法题了，每天晚上回来写写。上午复习之前做过的题目，两道题。然后做一道新题，然后晚上回来在做一道题。
• 今天应该是最后一次一天两道新题，两道复习。