本周心得

1. vector中，字符串的sort()排序问题（按顺序以字母表比较，前一位优先级高：abc < acb < bca）
2. 数组中的排序sort问题：（sort函数作用范围为 [begin, end) ，不包含最后一位 ）
   静态数组：int a[10] = { 9, 0, 1, 2, 3, 7, 4, 5, 8, 6 }; sort(a, a +10);
   （注意加的是长度，加到数组末尾的下一位）
   vector： sort(heights.begin(), heights.end());
   （vector中的end（）代表的是最后一位数的下一位）
3. string.substr(int start_index, int length)的用法：
   两个参数时，第一个是起始位置，第二个是子串长度 eg: substr(0,5)获得字符串s中 从第0位开始的长度为5的字符串
   一个参数时默认从指定开始位置到尾 eg: substr(1) ) 获得字符串s中 从第1位开始的到结尾的字符串
4. char字符串数组是以 ‘\0’ 为结尾的，但是string 是一个类，结尾没有字符’\0’
5. C++删除string最后一个字符的几种方法：
   - str.pop_back();
   - str.erase(str.end() - 1);
   - str = str.substr(0, str.length() - 1)；
6. string.erase()的用法
   （1）erase(pos,n); 删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符
   （2）erase(first, last);删除从first到 last之间的字符（first和last都是迭代器）
   （3）erase(pos);删除pos处的一个字符(pos必须是个string类型的迭代器 string::iterator pos)
7. 寻找质数的算法：厄拉多塞筛法（精简高效寻找每个数字的倍数的算法）
8. 关于字符的转码问题：
   char to int : 一般使用 char - ‘0’
   int to cha : 一般使用 int + ‘0’
   (注意： char(4) : 将4转变为’\4’而不是 字符 ‘4’，int(‘a’): 将字符串转换为对应的ASCII码
   因此涉及int/char转换问题最好使用 ±’0’，其中 (char) 绝对不要使用！）
9. 判断vector中有无某值：（STL）find
   vector<int>::iterator it = find(arr.begin(),arr.end(),res);
if( it != arr.end() ) //值在数组中
if( it == arr.end() ) //值不在数组中
10. 弗洛伊德循环查找算法 (快慢指针法/龟兔指针法)
    原理：兔子每走一步就向乌龟靠近一个节点（在它们的移动方向上）。若有则必相遇
    用于判断一个链表是否有循环

594，最长和谐子序列

class Solution {
public:int findLHS(vector<int>& nums) {unordered_map<int, int> hash;for(auto num:nums)hash[num]++;int res = 0;for(auto i : hash)//if(hash[i.first+1] != 0)if(hash.count(i.first+1))res = max(res, i.second + hash[i.first + 1]);return res;}
};

1160, 拼写单词

class Solution {
public:int countCharacters(vector<string>& words, string chars) {int res=0;int ch[26]={0};for(char c:chars)ch[c-'a']++;for(string word:words){int wd[26]={0};for(char c:word)wd[c-'a']++;res+=word.size();for(char c:word){if(ch[c-'a']<wd[c-'a']){res-=word.size();break;}    }}return res;}
};

572, 分糖果

class Solution {
public:int distributeCandies(vector<int>& candies) {int nums = candies.size();vector<int> hash(10000);for(int i = 0; i < nums; i++){hash[candies[i]]++;}int res = 0;for(int i = 0; i < 10000; i++){if(hash[i] >= 2) res++;else if(hash[i] == 1 && res < (nums/2) ) res++;}return min(nums/2, res);}
};

599 两个列表共同元素的最小索引总和

class Solution {
public:vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {unordered_map<string, int> hash;//unordered_map<string, unordered_map> hash;int i = 0;for(auto r1 : list1){i++;hash[r1] += i;}int j = 0;for(auto r2 : list2){j++;if(hash[r2] != 0){int tmp = -hash[r2];hash[r2] = tmp;hash[r2] -= j;} }int min_res = INT_MAX;for(auto h:hash){if(h.second < 0)min_res = min(min_res, -h.second);}vector<string> arr_res;for(auto h:hash){if(-h.second == min_res)arr_res.push_back(h.first);}return arr_res;}
};

1078. Bigram分词

这题有很多小细节：

1. char字符串数组是以 ‘\0’ 为结尾的，但是string 是一个类，结尾没有字符’\0’（string 是以字符串长度，来判断结束的），故所以在这题的string里加了一个’\0’来作为结束判断符
2. string 中的常用操作：
   删除：earse(Iterator，Iterator)；
   末尾添加字符 append(个数，char)；

class Solution {
public:vector<string> findOcurrences(string text, string first, string second) {vector<string> str_arr;string str;text.append(1,'\0');for(auto c : text){if(c == ' ' || c == '\0'){str_arr.push_back(str);str.erase (str.begin(), str.end());}else   str.append(1, c);}vector<string> res;for(int i = 1; i<str_arr.size(); i++){if(str_arr[i - 1] == first && str_arr[i] == second && i != str_arr.size() - 1)res.push_back(str_arr[i + 1]);} return res;}
};

645.错误的集合

注意：在这里hash表的 初始化 和 指定操作 分开进行，达到目的

class Solution {
public:vector<int> findErrorNums(vector<int>& nums) {unordered_map<int, int> hash;for(int i = 0; i < nums.size();i++){hash[i] = 0;}for(auto num:nums){hash[num-1]++;}vector<int> res;for(auto h:hash){if(h.second == 2)res.push_back(h.first+1);}for(auto h:hash){if(h.second == 0)res.push_back(h.first+1);}return res;}
};

720，词典中最长的单词

const int MAX_NODE = 1000000 + 10;
const int CHARSET = 26;
int trie[MAX_NODE][CHARSET] = {0};
int ending[MAX_NODE] = {0};int k = 1; // k为节点标记
void insert(string w){ //在Trie树中插入一个单词int len = w.size();int p = 0; // p为动态节点标记for(int i=0; i<len; i++){int c = w[i] - 'a';if(!trie[p][c]){trie[p][c] = k;k++;}p = trie[p][c];}ending[p] = 1;  //ending数组是个hash表，记录为终止节点的节点标记k
}int search(string s){int len = s.size();int p = 0;for(int i=0; i<len; i++){int c = s[i] - 'a';if(!trie[p][c]) return 0;p = trie[p][c];}return ending[p] == 1;
}class Solution {
public:string longestWord(vector<string>& words) {for(auto word:words){insert(word);}vector<string> res_arr;for(auto word:words){int length = word.size();bool flag = 1;while(length){if(!search(word.substr(0,length--))){flag = 0;break;      }}if(flag)res_arr.push_back(word);}int max_len = 0;for(auto s:res_arr){int s_len = s.size();max_len = max(max_len, s_len);}vector<string> res;for(auto s:res_arr){if(s.size() == max_len)res.push_back(s);}sort(res.begin(), res.end());return res[0];}
};

204 寻找质数

厄拉多塞筛法: 高效for循环创建hash表

class Solution {
public:int countPrimes(int n) {int count = 0;//初始默认所有数为质数vector<bool> signs(n, true);for (int i = 2; i < n; i++) {if (signs[i]) {count++;for (int j = i + i; j < n; j += i) {//排除不是质数的数signs[j] = false;}}}return count;}
};

202 快乐数

快乐数：各个位数平方和为1，非1和可继续循环，最终为1即可）
tips：为了防止无限循环，可以用数组记忆已出现的值，再次出现说明死循环

class Solution {
public:bool isHappy(int n) {unordered_map<char, int> hash;for(int i =0; i<10;i++){hash[i+'0'] = i*i;  //hash[char(i)] 错误 ---(char)将4转变为'\4'而不是'4';}int tacket = n;vector<int> arr;while(1){string num = to_string(tacket);int res = 0;for(auto c:num){res += hash[c];}if(res == 1) return 1;vector<int>::iterator it=find(arr.begin(),arr.end(),res);if(it != arr.end()) return 0; else arr.push_back(res);tacket = res;}     return 0;}
};