头像

小雪菜本大菜




离线:2小时前


最近来访(38)
用户头像
重生带我走
用户头像
太雪菜
用户头像
种花家的兔兔
用户头像
鄭Y
用户头像
ZPOP
用户头像
目标今年刷基础课2遍和提高课1遍
用户头像
布克波波
用户头像
acwing_7777
用户头像
OI
用户头像
绝壁芭蕾
用户头像
富贵
用户头像
你好闹啊
用户头像
khalil
用户头像
一塌糊涂
用户头像
wangyc
用户头像
我要出去乱说
用户头像
liberty..
用户头像
CyanFishhh
用户头像
徐朝九
用户头像
冷丁Hacker

问题 dp

想问下动态规划问题一般什么时候需要在输出前枚举一遍所有方案呢,有没有类似的题目可以参考一下,(除了最大上升子序列



问题 算法书

xdm 有什么推荐的算法书吗




题目链接 LeetCode XXX

我遇到了blablabla问题。

代码:

class Solution {
public:
    //记录答案
    vector<vector<int>> ans;
    //记录当前方案
    vector<int> path;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        //先把整个数组排序 把所有相同的数排在一起
        sort(nums.begin(),nums.end());
        //dfs一遍 从第 0 段开始枚举
        dfs(nums, 0);
        return ans;
    }
    void dfs(vector<int>& nums,int u) {
        //如果已经枚举了最后一个数的话就说明找到了一种方案
        if(u == nums.size()) {
            //把方案加到答案里面
            ans.push_back(path);
            return;
        }
        //求当前这一段有多少个
        int k = u + 1;
        while(k < nums.size() && nums[k] == nums[u]) k ++ ;
        //最终这一段的个数就会有0 ~ k - i 一共 k - i + 1 种情况
        //接下来枚举所有情况 枚举当前这个数选多少个 第一次选 0 个、第二个选 1 个...一直到选 k - i 个都可以枚举到
        for(int i = 0; i <= k - u; i++ ) {
            dfs(nums,k);

            path.push_back(nums[u]);
        }
        //恢复现场 已经在当前数组里面添加了 k - i + 1 个数 需要把这 k - i + 1 个数去掉
        for(int i = 0;i <= k - u; i ++ ) {
            path.pop_back();
        }
    }
};


分享 lc题解

有刷lc的小伙伴吗?推荐一下我的题解: https://blog.csdn.net/weixin_60569662/category_11843861.html?spm=1001.2014.3001.5482



活动打卡代码 LeetCode 5. 最长回文子串

class Solution {
public:
    string longestPalindrome(string s) {
        //结果数组
        string res;
        //枚举中心点
        for(int i = 0;i < s.size();i++) {
            //枚举长度是奇数的情况
            int l = i - 1,r = i + 1;
            //两个指针分别往两边走 当两个指针没有越界的时候,并且两个指针指向的数值相同 
            //左指针就往左走一格右指针就往右走一格
            while(l >= 0 && r < s.size() && s[l] == s[r]) l --,r ++;
            //停下来的时候 [l + 1,r - 1]就是最长的回文串
            if(res.size() < r - l -1) res = s.substr(l + 1,r - l -1);
            l = i,r = i + 1;
            while(l >= 0 && r < s.size() && s[l] == s[r]) l --,r ++;
            //停下来的时候 [l + 1,r - 1]就是最长的回文串
            if(res.size() < r - l -1) res = s.substr(l + 1,r - l -1);
        }
        return res;
    }
};



class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //定义一个哈希表 统计每个字符出现的次数
        unordered_map<char,int> heap;
        //定义一个最大值
        int res = 0;
        //从前往后枚举 i 是后面的指针 j 是前面的指针
        for(int i = 0,j = 0;i < s.size();i++) {
            //每次把当前新的字符加到哈希表中去
            heap[s[i]] ++;
            //如果有重复 必然是 s[i] 重复 
            //当 s[i] 大于 1 的时候,每一次将 s[j] 删除并把 j 往后移动一位 
            while(heap[s[i]] > 1) heap[s[j++]]--;
            //退出循环之后 从 j 到 i 就是以 i 结尾的不包含重复字符最长的一段
            //用这一段更新答案
            res = max(res,i - j + 1);
        }
        return res;
    }
};


活动打卡代码 LeetCode 1. 两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //定义哈希表把每个数值映射到它的下标
        unordered_map<int,int> heap;
        //从前往后去遍历每个数
        for(int i = 0;i < nums.size();i++) {
            int r = target - nums[i];
            if(heap.count(r)) return {heap[r],i};
            //把当前这个数插到哈希表里面
            heap[nums[i]] = i;
        }
        return{};
    }
};


活动打卡代码 AcWing 116. 飞行员兄弟

#include <iostream>
#include <cstring>
#include <algorithm>
//用于存储方案
#include <vector>
using namespace std;
//PII 等价于 pair<int,int>
typedef pair<int,int> PII;

//x 等价于 first
#define x first
#define y second


//字符串最后有一个'\0'长度是 4 的字符串要开 5 个位置否则会越界
const int N = 5;

//备份数组
char g[N][N],backup[N][N];

//输入一个 i,j 返回映射关系 返回第 x 行第 y 列这个位置上的数是多少
int get(int x,int y)
{
    return x * 4 + y; 
}

void turn_one(int x,int y)
{
    //如果原来是'+'就变成'-' 如果原来是'-'就变成'+'
    if(g[x][y] == '+') g[x][y] = '-';
    //否则把 g[x][y]变成 '+'
    else g[x][y] = '+';
} 

//一整行一整列改变
void turn_all(int x,int y)
{
    for(int i = 0;i < 4;i++)
    {
        //整列
        turn_one(x,i);
        //整行
        turn_one(i,y);
    }
    //x,y这个位置 turn 两遍被抵消 因此还需要 turn 一遍
    turn_one(x,y);
}

int main()
{
    //读入所有灯泡的状态
    for(int i = 0;i < 4;i++) cin >> g[i];

    //结果数组
    vector<PII> res;
    //枚举所有操作:从 0 枚举到 2^16 -1,1 << 16 就是 2^16 
    for(int op = 0;op < 1 << 16;op++)
    {
        //需要存储方案:用 pair 存储两维坐标 把当前位置存储到 temp 中
        vector<PII> temp;
        //需要对原数组进行操作 需要备份原数组以进行下一次操作
        memcpy(backup,g,sizeof g);

        //按照该方案对所有灯泡进行操作 枚举 16 个位置
        for(int i = 0;i < 4;i++)
            for(int j = 0;j < 4;j++)
                //需要计算i,j这个格子上的编号是多少 如果当前位置上是 1 的话,就需要按下开关
                if(op >> get(i,j) & 1)
                {
                    temp.push_back({i,j});
                    //摁一下开关 一整行一整列改变
                    turn_all(i,j);
                }
        //判断所有灯泡是否全亮 定义变量表示是不是有灯泡灭着
        bool has_closed = false;
        //一开始是没有的
        //枚举所有灯泡
        for(int i = 0;i < 4;i++)
            for(int j  = 0;j < 4;j++)
                //如果当前灯泡是灭着的
                if(g[i][j] == '+')
                    has_closed = true;
        //所有灯泡都是亮着的:记录方案
        if(has_closed == false)
        {
            if(res.empty() || res.size() > temp.size()) res = temp; 

        }
        //还原原来的数组
        memcpy(g,backup,sizeof g);
    }
    cout << res.size() << endl;
    //题目下标从 1 开始,代码下标从 0 开始 需要 + 1 做转换
    for(auto op :res) cout << op.x + 1 <<' ' << op.y + 1<< endl;
    return 0;
}



活动打卡代码 AcWing 1208. 翻硬币

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 110;

int n;
//字符串开始和结尾两个状态
char start[N],ending[N];

//翻转第 i 个字符
void turn(int i)
{
    if(start[i] == '*') start[i] = 'o';
    //否则把 start[i] 变成 '*'
    else start[i] = '*';
}
int main()
{
    //读入两个字符串
    cin >> start >> ending;
    //计算两个字符串的长度:由于保证两个字符串一定有解,所以两个字符串一定长度相同
    n = strlen(start);
    //记录最终答案
    int res = 0;
    //从前往后扫描每一个字符:只要扫描到 n - 1 就可以了
    //由于保证两个字符串一定有解,因此最后一个字符一定相等,否则无解
    //如果当前位置的开始字符和结束字符是不一样的就需要翻转两个字符
    for(int i = 0;i < n - 1;i++)
    {
        if(start[i] != ending[i])
        {
            turn(i),turn(i + 1);
            //答案总数加 1
            res++;
        }
    }
    //输出最终答案
    cout << res << endl;
}


活动打卡代码 AcWing 95. 费解的开关

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 6;

char g[N][N], backup[N][N];
int dx[5] = {-1, 0, 1, 0, 0}, dy[5] = {0, 1, 0, -1, 0};

void turn(int x, int y)
{
    for (int i = 0; i < 5; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;   // 在边界外,直接忽略即可
        g[a][b] ^= 1;
    }
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        for (int i = 0; i < 5; i ++ ) cin >> g[i];

        int res = 10;
        for (int op = 0; op < 32; op ++ )
        {
            memcpy(backup, g, sizeof g);
            int step = 0;
            for (int i = 0; i < 5; i ++ )
                if (op >> i & 1)
                {
                    step ++ ;
                    turn(0, i);
                }

            for (int i = 0; i < 4; i ++ )
                for (int j = 0; j < 5; j ++ )
                    if (g[i][j] == '0')
                    {
                        step ++ ;
                        turn(i + 1, j);
                    }

            bool dark = false;
            for (int i = 0; i < 5; i ++ )
                if (g[4][i] == '0')
                {
                    dark = true;
                    break;
                }

            if (!dark) res = min(res, step);
            memcpy(g, backup, sizeof g);
        }

        if (res > 6) res = -1;

        cout << res << endl;
    }

    return 0;
}