📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 329| 回复: 4
跳转到指定楼层
上一主题 下一主题
收起左侧

DAY2 刷题打卡

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
继续记录一下自己的刷题进度。今天还是继续刷array和hash table相关的题

上一篇:记录刷题
下一篇:DAY3 刷题打卡
💯 1
全局:
加油加油。
回复

使用道具 举报

全局:
我刚刚复习了这个题目: 752. Open the Lock
按照bfs 的框架写就行,triky 的地方是有写小细节、corner case 可能会忘记处理。
从current state 走向下一个state 的时候,原本对每个数字进行加一或者减一就行,但是这里有个特殊情况是 0 - 1 之后是9, 9 + 1 之后是0. 这个循环的部分需要特殊处理一下。第一遍写的时候因为没有处理这个特殊情况导致访问范围特别大,超时了。
问了一下chatgpt, 给出的办法是加10 再对10取余。
int next_digit = (digit + 10 + change[j]) % 10;

还有就是corner case: 如果target 就是起始点直接返回0,如果deadends 里有起始点,直接返回不能打开。

class Solution {
    int change[2] = {1, -1};
public:
    int openLock(vector<string>& deadends, string target) {
        if (target == "0000") return 0;
        unordered_set<string> dead_set;
        for (int i = 0; i < deadends.size(); i++) {
            dead_set.insert(deadends[i]);
        }
        if (dead_set.count("0000")) return -1;

        // we need an unordered_set to record visited state of the 4 wheels.
        unordered_set<string> visited;
        visited.insert("0000");

        queue<string> q;
        q.push("0000");
        int steps = 0;

        while(!q.empty()) {
            int len = q.size();
            for (int k = 0; k < len; k++) {
                string cur = q.front();
                q.pop();

                // visit all neighbors of the current state.
                for (int i = 0; i < 4; i++) {
                    int digit = cur[i] - '0';
                    for (int j = 0; j < 2; j++) {
                        int next_digit = (digit + 10 + change[j]) % 10;
                        char next = next_digit + '0';
                        string str = cur;
                        str[i] = next;
                        // skip if found dead ends or visited before.
                        if (dead_set.count(str) || visited.count(str)) continue;
                        // if found the target, return the steps.
                        if (target == str) return ++steps;

                        // if not found the target, mark visited, enque the neighbor.
                        visited.insert(str);
                        q.push(str);
                    }
                }
            }
            steps++;
        }
        return -1;
    }
};
回复

使用道具 举报

🔗
 楼主| NikoCheng 2026-9-25 09:30:59 | 只看该作者
全局:
一起加油!!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表