2020-10-05

检查整数及其两倍数是否存在

class Solution { public: bool checkIfExist(vector<int>& arr) { sort(arr.begin(),arr.end()); for(int i = 0; i < arr.size(); i++) { if(arr[i] < 0) { for (int j = arr.size()-1; j >= 0; j--) { if(i!=j&&arr[i]*2 == arr[j]) return true; } } else { arr[i] = arr[i] * 2; for(int j = i+1; j < arr.size(); j++) { if(arr[i] == arr[j]) return true; } } } return false; } };

数组形式的整数加法

class Solution { public: vector<int> addToArrayForm(vector<int>& A, int K) { reverse(A.begin(), A.end()); int index = 0; while (K > 0) { if (index < A.size()) { K += A[index]; A[index] = K % 10; // 未越界, 直接赋值 } else { A.push_back(K % 10); // 越界了, push } K /= 10; ++index; } reverse(A.begin(), A.end()); return A; } };

重复至少 K 次且长度为 M 的模式

class Solution { public: bool containsPattern(vector<int>& arr, int m, int k) { int count = 1; int n = arr.size(); if(n < m * k)return false; for(int i = 0; i+m < n; i++) { vector<int> tmp = vector(arr.begin()+i,arr.begin()+i+m); count = 1; for(int j = i+m; j+m <= n;j+=m) { vector<int> vec = vector<int>(arr.begin()+j,arr.begin()+j+m); if(tmp == vec) { count++; if(count == k) return true; } else { break; } } } return false; } };

第三大的数

class Solution { public: int thirdMax(vector<int>& nums) { int tmp = 1; sort(nums.begin(), nums.end()); reverse(nums.begin(), nums.end()); int tmax = nums[0]; for(int i = 1; i < nums.size(); i++) { if(nums[i] < tmax) {tmp++; tmax = nums[i];} if(tmp == 3) return tmax; } return nums[0]; } };

单调数列

class Solution { public: bool isMonotonic(vector<int>& A) { int n = A.size(); vector<int> nums; nums.assign(A.begin(),A.end()); sort(nums.begin(),nums.end()); for(int i = 0; i < n; i++) { if(nums[i] != A[i]) { for(int j = n-1; j >= 0; j--) { if(nums[j] != A[n-j-1]) return false; } } } return true; } };

特殊数组的特征值

class Solution { public: int specialArray(vector<int>& nums) { int x = nums.size(); int count = 0; while(x) { for(int i = 0; i < nums.size(); i++) { if(nums[i] >= x) count++; } if(count == x) return x; x--; count = 0; } return -1; } };

有效的山脉数组

class Solution { public: bool validMountainArray(vector<int>& A) { int n = A.size(); if(n < 3) return false; int flag = 0; // 当flag = 1时开始递减 int head=0,tail=n-1; for(;head<n-1&&A[head]<A[head+1];++head); for(;tail>0&&A[tail]<A[tail-1];--tail); if(head==tail&&head!=0&&tail!=n-1) return true; return false; } };

子数组最大平均数 I

class Solution { public: double findMaxAverage(vector<int>& nums, int k) { double sum = 0; double max = 0; for(int j = 0; j < k; j++) { sum += nums[j]; } max = sum; for(int i = k; i < nums.size(); i++) { sum = sum - nums[i-k]+nums[i]; if(sum > max) max = sum; } return max/k; } };

珠玑妙算

class Solution { public: vector<int> masterMind(string solution, string guess) { vector<int> num(2,0); int i = 0,j = 0; map<char,int> map; for(auto s:solution) { map[s]++;; } for(int i = 0; i < solution.size(); i++) { if(solution[i] == guess[i]) num[0]++; if(map[guess[i]]){ cout << guess[i] << endl; map[guess[i]]--; num[1]++; } } num[1] -= num[0]; return num; } };

2020-10-06

旋转数组

class Solution { public: void rotate(vector<int>& nums, int k) { vector<int> arr(nums.size(),0); int n = nums.size(); for(int i = 0; i < n; i++) { arr[(i+k)%n] = nums[i]; } nums.assign(arr.begin(),arr.end()); } };

1比特与2比特字符

class Solution { public: bool isOneBitCharacter(vector<int>& bits) { int n = bits.size(); int t; vector<int> vec1 = {1,0}; vector<int> vec2 = {1,1}; for(int i = 0; i+2 <= n; ) { vector<int> tmp = vector(bits.begin()+i,bits.begin()+i+2); if(tmp == vec1 || tmp == vec2) { t = i+2; i+=2; }else { i++; } } if(t == n) return false; return true; } };

顺时针打印矩阵

class Solution { public: vector<int> spiralOrder(vector<vector<int>>& matrix) { if(matrix.size() == 0) return {}; int n = matrix.size()-1; int m = matrix[0].size()-1; vector<int> arr; int k = 0, l = 0; while(true) { for(int i = k; i <= m; i++) { arr.push_back(matrix[l][i]); } if(++l > n) break; for(int i = l; i <= n; i++){ arr.push_back(matrix[i][m]); } if(k > --m) break; for(int i = m; i >= k; i--) { arr.push_back(matrix[n][i]); } if(l>--n) break; for(int i = n; i >= l; i--) { arr.push_back(matrix[i][k]); } if(++k > m) break; } return arr; } };

总持续时间可被 60 整除的歌曲

class Solution { public: int numPairsDivisibleBy60(vector<int>& time) { int count = 0; int n = time.size(); map<int,int> map; for(int i = 0; i < n; i++) { map[time[i]`]++; } for(int i = 0; i < n; i++) { map[time[i]`]--; int tmp = time[i]` == 0? 0:(60-time[i]`); count+=map[tmp]; } return count; } };

数组的度

class Solution { public: int findShortestSubArray(vector<int>& nums) { int numsSize = nums.size(), res = INT_MAX, degree = 0; map<int, int> numsCnt;//记录各个数字出现的次数 map<int, pair<int, int>> pos;//记录各个数字第一次、最后一次出现的下标 for (int i = 0; i < numsSize; ++i) { if (++numsCnt[nums[i]] == 1) { //元素第一次出现 pos[nums[i]] = {i, i}; } else { //更新最后出现的下标 pos[nums[i]].second = i; } //更新出现次数最多的元素次数 degree = max(degree, numsCnt[nums[i]]); } for (auto &item : numsCnt) { if (degree == item.second) {//此元素出现的次数等于数组的度 res = min(res, pos[item.first].second - pos[item.first].first + 1); } } return res; } };

较大分组的位置

class Solution { public: vector<vector<int>> largeGroupPositions(string s) { vector<vector<int>> res; int start = 0; // 开始位置 int N = s.size(); for(int i = 1;i<N;i++){ if(s[i] != s[i-1]){ if(i-start>=3){ res.push_back({start,i-1}); } start = i; } } if(N - start >= 3) res.push_back({start,N-1}); return res; } };

等价多米诺骨牌对的数量

class Solution { public: int numEquivDominoPairs(vector<vector<int>>& dominoes) { // step 1: 调整次序 for(int i=0;i<dominoes.size();i++){ if(dominoes[i][0] > dominoes[i][1]){ int tmp = dominoes[i][0]; dominoes[i][0] = dominoes[i][1]; dominoes[i][1] = tmp; } } // step 2: 统计次数 map<vector<int>,int> count; for(auto d : dominoes){ count[d]++; } // step 3: 计算等价数量（全排列=n*(n-1)/2） int res = 0; for(auto d : count){ int n = count[d.first]; res += (n*(n-1)/2); } return res; } };

可被 5 整除的二进制前缀

class Solution { public: vector<bool> prefixesDivBy5(vector<int>& A) { int n = A.size(); vector<bool> answer(n,true); int pre = 0; for(int i = 0; i < n; i++) { pre = pre << 1; pre += A[i]; if(pre%5 != 0) answer[i] = false; pre = pre%5; } return answer; } };

将数组分成和相等的三个部分

class Solution { public: bool canThreePartsEqualSum(vector<int>& A) { int sum = 0; int n = A.size(); int left = 0; int count = 0; for(int i = 0; i < n; i++) { sum+=A[i]; } if(sum%3 != 0) return false; sum /= 3; for(int i = 0; i < n; i++) { left+=A[i]; if(left == sum) { count++; left = 0; } if(count == 3) return true; } return false; } };

字符串

2020-10-07 #434 字符串中的单词数 #917 仅仅反转字母 #859 亲密字符串 #1374 生成每种字符都是奇数个的字符串 #面试题 01.06 字符串压缩 #1370 上升下降字符 #1576 替换所有的问号 2020-10-08 旅行终点站 反转字符串 赎金信 旋转数字 数组中的字符串匹配 唯一摩尔斯密码词 连续字符 反转字符串 II 左旋转字符串 比较字符串最小字母出现频次 转换成小写字母 字符串相加 2020-10-09 URL化 验证回文字符串 Ⅱ 字符串轮转 分割字符串的最大得分 IP 地址无效化 字符串的最大公因子 转变日期格式 特殊等价字符串组 检测大写字母 机器人能否返回原点 解码字母到整数映射

2020-10-10

最常见的单词

class Solution { public: string mostCommonWord(string paragraph, vector<string>& banned) { unordered_map<string, int> cnt; unordered_set<string> ban; for (auto& w : banned) { ban.insert(w); } int maxcnt = 0; string ans; for (auto& c : paragraph) { c = isalpha(c) ? c : ' '; } stringstream ss(paragraph); string temp; while (ss >> temp) { for (auto& c : temp) { c = tolower(c); } if (ban.count(temp) != 0) continue; cnt[temp]++; if (cnt[temp] > maxcnt) { maxcnt = cnt[temp]; ans = temp; } } return ans; } };

重新格式化字符串

class Solution { public: string reformat(string s) { string Snumber = ""; string Schar = ""; string result = ""; for(auto ss:s) { if(ss>='a'&&ss<='z') Schar+=ss; if(ss>='0'&&ss<='9') Snumber+=ss; } if(Schar.size()-Snumber.size() <= 1){ for(int i = 0; i < Schar.size(); i++) { result += Schar[i]; if(i<Snumber.size()) result += Snumber[i]; } return result; }else if(Snumber.size()-Schar.size() <= 1){ for(int i = 0; i < Snumber.size(); i++) { result += Snumber[i]; if(i<Schar.size()) result += Schar[i]; } } return result; } };

千位分隔数

class Solution { public: string thousandSeparator(int n) { if(n == 0) return "0"; string result = ""; int num = 0; while(n) { result+=n+'0'; num++; if(num == 3) { result +="."; num = 0; } n/=10; } if(result[result.size()-1] == '.') result.pop_back(); reverse(result.begin(),result.end()); return result; } };

山羊拉丁文

class Solution { public: string toGoatLatin(string S) { string ans = ""; string ex = "a"; istringstream ww(S); string w; while(ww>>w) { char ch = tolower(w[0]); if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') { ans += w +"ma" +ex; }else { ans += string(w.begin()+1,w.end()) + w[0] +"ma"+ex; } ans+=" "; ex +="a"; } ans.pop_back(); return ans; } };

学生出勤记录 I

class Solution { public: bool checkRecord(string s) { int countA = 0; for(int i = 0; i < s.size(); i++) { if(s[i] == 'A') countA++; if(countA>1) return false; if(s[i] == 'L') { if(i+1<s.size()&&s[i+1] == 'L') { if(i+2<s.size()&&s[i+2] == 'L') return false; } } } return true; } };

判断路径是否相交

class Solution { public: bool isPathCrossing(string path) { set<pair<int,int>> set; int x = 0; int y = 0; set.insert({0,0}); for(auto p:path) { switch(p) { case 'N':y++;break; case 'S':y--;break; case 'E':x++;break; case 'W':x--;break; } if(set.count({x,y})) return true; set.insert({x,y}); } return false; } };

删除回文子序列

class Solution { public: int removePalindromeSub(string s) { if(s.size() == 0) return 0; for(int i = 0; i < s.size()/2; i++) { if(s[i]!=s[s.size()-1-i]) return 2; } return 1; } };

独特的电子邮件地址

class Solution { public: int numUniqueEmails(vector<string>& emails) { map<string,int> map; for(int i = 0; i < emails.size(); i++) { map[Judg(emails[i])]++; } return map.size(); } string Judg(string email) { string res = ""; for(auto ss: email) { if(ss == '.') continue; if(ss == '+') break; if(ss == '@') break; res += ss; } int index = email.find('@'); res += email.substr(index,email.size()); return res; } };

检查单词是否为句中其他单词的前缀

class Solution { public: int isPrefixOfWord(string sentence, string searchWord) { int num = 0; string tmp = ""; for(auto s: sentence) { if(s == ' ') { num++; int index = tmp.find(searchWord); if(index == 0) return num; tmp = ""; } else { tmp += s; } } if(tmp != "" && tmp.find(searchWord)==0) return num+1; return -1; } };

翻转单词顺序

class Solution { public: string reverseWords(string s) { vector<string> S; string tmp = ""; for(auto ss:s) { if(ss == ' ') { if(tmp != "") { S.push_back(tmp); tmp = ""; } continue; } tmp += ss; } if(tmp != "") S.push_back(tmp); tmp = ""; for(int i = S.size()-1; i >= 0; i--) { tmp += S[i]; if(i!=0) tmp += " "; } return tmp; } };

重新排列单词间的空格

class Solution { public: string reorderSpaces(string text) { int num = 0;//统计空格的个数 vector<string> S; string res = ""; for(auto s:text) { if(s == ' ') { num++; if(res != "") { S.push_back(res); res = ""; } continue; } res += s; } if(res != "") S.push_back(res); res = ""; if(S.size() == 1) { res += S[0]; for(int i = 0; i < num; i++) { res += " "; } return res; } int pre = num/(S.size()-1);// 相邻单词之间的空格数 int last = num%(S.size()-1); // 尾部空格数 for(int i = 0 ; i < S.size(); i++) { res += S[i]; if(i != S.size()-1) { for(int i = 0; i < pre; i++) res +=" "; } } for(int i = 0; i < last; i++) res += " "; return res; } };

判定是否互为字符重排

class Solution { public: bool CheckPermutation(string s1, string s2) { sort(s1.begin(),s1.end()); sort(s2.begin(),s2.end()); if(s1 == s2) return true; return false; } };

2020-10-11

重新排列日志文件

public: static bool cmp(const string &a, const string &b){ int i = 0, j = 0; while(a[i] != ' ') i ++; while(b[j] != ' ') j ++; string a_content = a.substr(i), b_content = b.substr(j); if (a_content != b_content) return a_content < b_content; else return a < b; } vector<string> reorderLogFiles(vector<string>& logs) { vector<string> res, alp; for(int i = 0, j = 0; i < logs.size(); i ++){ j = logs[i].find(' '); if(logs[i][j + 1] >= '0' && logs[i][j + 1] <= '9') res.push_back(logs[i]); else alp.push_back(logs[i]); } sort(alp.begin(),alp.end(),cmp); res.insert(res.begin(),alp.begin(),alp.end()); return res; } };

哈希表

有多少小于当前数字的数字

class Solution { public: vector<int> smallerNumbersThanCurrent(vector<int>& nums) { vector<int> hash(106); vector<int> res; for(int num: nums) hash[num]++; int count = 0; int tmp; for(int i = 0; i < 106; i++) { if(hash[i]) { tmp = hash[i]; hash[i] = count; count += tmp; } } for(int num:nums) { res.push_back(hash[num]); } return res; } };

岛屿的周长

class Solution { public: int islandPerimeter(vector<vector<int>>& grid) { //.....没有用到hash。。。。 int n = grid.size(); int m = grid[0].size(); int ans = 0; for(int i = 0; i < n;i++){ for(int j = 0; j < m; j++){ if(grid[i][j] ==1){ ans += 4; if(i > 0 && grid[i-1][j] == 1) ans--; if(i < n-1 && grid[i+1][j] == 1) ans --; if(j > 0 && grid[i][j-1] == 1) ans --; if(j < m-1 && grid[i][j+1] == 1) ans --; } } } return ans; } };

只出现一次的数字

class Solution { public: int singleNumber(vector<int>& nums) { // // 方法一: // sort(nums.begin(),nums.end()); // for(int i = 0; i+2 < nums.size(); i+=2) { // if(nums[i] != nums[i+1]) return nums[i]; // } // return nums[nums.size()-1]; // // 方法二： // map<int, int> m; // for(auto n: nums) { // m[n]++; // } // for(auto mm: m) { // if(mm.second == 1) return mm.first; // } // return -1; //位运算 int ans = 0; for(int i = 0; i < nums.size(); i++) { ans ^= nums[i]; } return ans; } };

两句话中的不常见单词

class Solution { public: vector<string> uncommonFromSentences(string A, string B) { map<string,int> hash; A = A + " " + B; istringstream str(A); string word; while (str >> word){ hash[word]++; } vector<string> res; for(auto m:hash) { if(m.second == 1) res.push_back(m.first); } return res; } };

宝石与石头

class Solution { public: int numJewelsInStones(string J, string S) { map<char,int> Smap; for(auto ss: S) { Smap[ss]++; } int res = 0; for(auto j:J) { if(Smap[j]) { res += Smap[j]; } } return res; } };

键盘行

class Solution { public: vector<string> findWords(vector<string>& words) { map<char,int> map={{'q',0},{'w',0},{'e',0},{'r',0},{'t',0},{'y',0},{'u',0},{'i',0},{'o',0},{'p',0},{'a',1},{'s',1},{'d',1},{'f',1},{'g',1},{'h',1},{'j',1},{'k',1},{'l',1},{'z',2},{'x',2},{'c',2},{'v',2},{'b',2},{'n',2},{'m',2},{'Q',0},{'W',0},{'E',0},{'R',0},{'T',0},{'Y',0},{'U',0},{'I',0},{'O',0},{'P',0},{'A',1},{'S',1},{'D',1},{'F',1},{'G',1},{'H',1},{'J',1},{'K',1},{'L',1},{'Z',2},{'X',2},{'C',2},{'V',2},{'B',2},{'N',2},{'M',2}}; int tmp; vector<string> res; int flag = 0; for(int i = 0; i < words.size(); i++) { tmp = map[words[i][0]]; flag = 0; if(words[i].size() == 1) {res.push_back(words[i]);continue;} for(int j = 1; j < words[i].size(); j++) { if(map[words[i][j]] != tmp) { flag = 1; break; } } if(flag == 0) res.push_back(words[i]); } return res; } };

独一无二的出现次数

class Solution { public: bool uniqueOccurrences(vector<int>& arr) { map<int,int> m; map<int, int> map; for(int item : arr) { m[item]++; } for(auto item: m) { map[item.second]++; if(map[item.second] >= 2) return false; } return true; } };

重复 N 次的元素

class Solution { public: int repeatedNTimes(vector<int>& A) { int num = A.size()/2; map<int,int> m; for(int a: A) { m[a]++; if(m[a] == num) return a; } return 0; } };

回旋镖的数量

class Solution { public: int numberOfBoomerangs(vector<vector<int>>& points) { int ans = 0; for(int i = 0; i < points.size(); i ++){ map<int,int> map; for(int j = 0; j < points.size(); j ++){ int x = points[i][0] - points[j][0]; int y = points[i][1] - points[j][1]; map[x * x + y * y]++; } for(auto x:map){ ans += x.second * (x.second - 1); } } return ans; } };