Leetcode第234场周赛

Leetcode第234场周赛

Louis 1450 2021-04-09

本文是临时紧急事项清单的规定产出，第234次周赛的题解。

文章中会出现该周赛的题目&我的解法&大佬的解法。

周赛连接： 第 234 场周赛

字符串中不同整数的数目

题目连接：字符串中不同整数的数目

我的解法：

第一个思路：

  1. for循环遍历，遇到一个数字，将其转换为int，加入temp中

  2. 遇到字母时保存到哈希表中，最后输出哈希表的大小。

这个思路失败的原因：temp必须有个初值，程序会将这个初值放进哈希表，影响结果

第二个思路：

  1. 遇到一个数字，直接用while循环找到最后一个数字，转换成int（这样就避免了temp值引起的问题），然后存入哈希表
  2. 最后输出哈希表的大小

这个思路失败的原因：测试集中居然有8273949821782379471897491279163791843812这么长的数据……

第三个思路：

  1. 直接用string存，但是这样会引起一个问题：有前置0的数字无法去重
  2. 于是干脆，给所有数字都补一个前置0，然后忽略它们自带的前置0，实现去重
class Solution {
public:
    int numDifferentIntegers(string word) {
        string temp;
        unordered_set<string> set;
        int index = 0;
        while (index < word.size()) {
            if (word[index] >= '0' && word[index] <= '9') {
                temp = "0";
                while (index < word.size() && word[index] >= '0' && word[index] <= '9') {
                    //想办法把前面的0去掉
                    if(temp == "0" &&  word[index] == '0'){
                        index ++;
                        continue;
                    }
                    temp += word[index];
                    index++;
                }
                set.insert(temp);
            } else {
                index++;
            }
        }
        return set.size();
    }
};

这道题的提交起码错了10遍……

别人的答案：

class Solution {
public:
    int numDifferentIntegers(string word) {
        word += "-";
        unordered_set<string> ans;
        string val = "-";
        for (auto c : word) {
            if (!isdigit(c)) {
                if (val == "-") continue;
                ans.insert(val);
                val = "-";
            }
            else {
                val = (val == "-") ? "0" : val;
                val = (val == "0") ? "" : val;
                val += c;
            }
        }
        return ans.size();
    }
};

作者：ikaruga
链接：https://leetcode-cn.com/problems/number-of-different-integers-in-a-string/solution/number-of-different-integers-by-ikaruga-qmh2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

还原排列的最少操作步数

题目连接：还原排列的最少操作步数

后面看题解的时候很多人连题目都没有看懂……

我的思考过程：

  1. 按照题解操作一遍，直到改变回原来的顺序。但是，每次操作都要对比数组中的每个值，虽然我没试过，但是感觉会超时
  2. 画图，发现数字位移的规律，只要一个数字到了原来的位置，其他必须也位于之前的位置，所以只需要判断其中一个数字就行了
  3. 但是又不能选num[0]，因为这一位一直都是不动的。
  4. 一看size>=2. 很明显就是放水嘛。选num[1]

我的解法：

class Solution {
public:
    int reinitializePermutation(int n) {
        int ret = 0;
        int i = 1;
        do {
            if(i % 2 == 0){
                i = i/2;
            } else {
                i = n / 2 + (i - 1) / 2;
            }
            ret++;
        } while (i != 1);
        return ret;
    }
};

优雅，完美。完全不给它作为中等题的尊严。哈哈哈。

替换字符串中的括号内容

题目链接：替换字符串中的括号内容

我的解法：

  1. 遍历一遍knowledge建立键值对字典
  2. 遍历一遍字符串找括号，然后替换
class Solution {
public:
    string evaluate(string s, vector<vector<string>> &knowledge) {
        //build a map
        unordered_map<string, string> k;
        string ret = "";
        for (auto item : knowledge) {
            k[item[0]] = item[1];
        }
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                int front = i;
                while (i < s.size() && s[i] != ')') {
                    i++;
                }
                front ++;
                string key = s.substr(front, i - front);
                if (k.find(key) != k.end()) {
                    ret += k[key];
                } else {
                    ret += "?";
                }
            }else{
                ret.push_back(s[i]);
            }
        }
        return ret;
    }
};

优化点使用unordered_map，然后是寻找key匹配可以使用count() 就不用每次从头找。

题解中暂时没有特别好玩的方法。

尾声

这次是模拟周赛，大概60分钟左右前3道题，做题时候的专注还是挺爽的，模拟周赛的排名是1200左右。

冲鸭！！！

Leetcode