2021年3月28日，星期日
前一天刚刚完成和实验室同学一起参加的华为软挑，虽然无缘决赛，但是还是收获了比赛的快乐，接着今天就迎来了力扣单周赛，又是望着大佬们流口水的一天......
这次的全国排名是
值得高兴的是我把四道题都做出来了！虽然是“手速场”，但我还是要夸夸自己。
第一题是
给你一个字符串，让你把字符串中的数字挑出来，看看有多少个不同的数字。
诶，我一拍脑袋，这不就是遍历的过程中把int存在一个集合里就可以了嘛，注意到题目里面说前导0不算，我还在暗自庆幸转化成数字前导0根本不受影响，考虑到大数int没法存，我还抖机灵的换成了long，然后下面的代码就没法应对 "035985750011523523129774573439111590559325" 这种离谱的数字
class Solution { public: bool isnum(char c){ return c >= ‘0‘ && c <= ‘9‘; } int numDifferentIntegers(string word) { word += ‘y‘; set<long> ss; long sum = 0; for(int i = 0; i < word.length(); i++){ if(!isnum(word[i])){ if(i > 0 && isnum(word[i - 1]))ss.insert(sum); sum = 0; continue; } sum = sum * 10 + word[i] - ‘0‘; } return ss.size(); } };
我都做到这份上了，干脆换成string存不好吗，于是换成下面的代码通过了
class Solution { public: bool isnum(char c){ return c >= ‘0‘ && c <= ‘9‘; } int numDifferentIntegers(string word) { word += ‘y‘; set<string> ss; string sum = ""; for(int i = 0; i < word.length(); i++){ if(!isnum(word[i])){ if(i > 0 && isnum(word[i - 1])){ int j = 0; while(j < sum.length() - 1 && sum[j] == ‘0‘)++j; ss.insert(sum.substr(j, (sum.length() - j))); } sum = ""; continue; } sum += word[i]; } return ss.size(); } };
第二题
听我同学们说按照规律只用判断1什么时候回原位值就可以了，我当时直接暴力模拟做的，因为它数据量实在太小了 n < 1000
如果 i % 2 == 0 ，那么 arr[i] = perm[i / 2]
如果 i % 2 == 1 ，那么 arr[i] = perm[n / 2 + (i - 1) / 2]
按照这个规律，当 n = 6的时候,
[0, 1, 2, 3, 4, 5]
[0, 3, 1, 4, 2, 5]
[0, 4, 3, 2, 1, 5]
[0, 2, 4, 1, 3, 5]
[0, 1, 2, 3, 4, 5]
方法一 ： 暴力模拟
class Solution { public: bool isEqual(vector<int>& a, int n){ for(int i = 0; i < n; i++){ if(a[i] != i) return false; } return true; } int reinitializePermutation(int n) { vector<int> a(n, 0); vector<int> b(n, 0); for(int i = 0; i < n; i++){ a[i] = i; } int ans = 0; do{ for(int i = 0; i < n; i++){ if(i % 2 == 1){ b[i] = a[n / 2 + (i - 1) / 2]; }else{ b[i] = a[i / 2]; } } a = b; ans++; }while(!isEqual(a, n)); return ans; } };
方法二 ： 因为每个数字最周都会回到原来的位置，所以每个数字都有它的循环路径，我们以下标 pos = 1 为追踪位置，当数字1重新回到位置1时，数组恢复原样
class Solution { public: int reinitializePermutation(int n) { int pos = 1, ans = 0; do{ //pos = pos & 1 ? n / 2 + (pos - 1) / 2 : pos / 2; if(pos % 2 == 1){ pos = n / 2 + (pos - 1) / 2; }else{ pos = pos / 2; } ++ans; }while(pos != 1); return ans++; } };
第三题
我觉得这个题目没有什么技巧也没有什么坑，用一个map保存一下映射就好了
class Solution { public: string evaluate(string s, vector<vector<string>>& k) { unordered_map<string, string> mp; for(auto& v : k){ mp[v[0]] = v[1]; } string ans = ""; int i = 0; while(i < s.length()){ if(s[i] == ‘(‘){ string cur = "";i++; while(i < s.length() && s[i] != ‘)‘){ cur += s[i]; i++; } i++; if(mp.find(cur) != mp.end()){ ans += mp[cur]; }else{ ans += ‘?‘; } continue; } if(i < s.length()) ans += s[i]; i++; } return ans; } };
第四题
很高兴这次的hard是一道数学题，和leetcode上剪绳子是类似的题目
其实是看primFactors分解成若干个数的和之后，这些数的最大乘积是多少，理论上，能分解成3尽量分解成3，变成3的幂次和2的幂次
这道题如果用pow(x, n)会大数溢出，并且会超时，选择用快速幂解决就好啦
class Solution { public: int mm = 1e9 + 7; long powt(int t, int n){ if(n == 0)return 1; if(n == 1){ return t; } long tmp = powt(t, n / 2) % mm; if(n & 1) return tmp * tmp % mm * t % mm; return tmp * tmp % mm; } int maxNiceDivisors(int p) { long ans = 1; int two = 0, three = 0; if(p == 1)return 1; if(p % 3 == 2){ three = p / 3; two = 1; }else if(p % 3 == 1){ three = p / 3 - 1; two = 2; }else{ three = p / 3; } ans = powt(2, two) * powt(3, three) % mm; return (ans + mm) % mm; } };
原文：https://www.cnblogs.com/Dancing-Fairy/p/14589525.html