leetcode-7-hashTable
解题思路:
这道题需要注意的是s和t长度相等,但都为空的情况。只需要扫描一遍s建立字典(char, count),然后扫描t,如果有
未出现的字母,或者键值小于0,就可以返回false了。
bool isAnagram(string s, string t) { if (s.length() != t.length()) return false; if (s.length() == 0 && t.length() == 0) return true; map<char,int> dict; for (int i = 0; i < s.length(); i++) { if (dict.find(s[i]) == dict.end()) { dict.insert(dict.end(), make_pair(s[i],1)); } else dict.find(s[i])->second++; } for (int i = 0; i < t.length(); i++) { if (dict.find(t[i]) == dict.end()) return false; else { dict.find(t[i])->second--; if (dict.find(t[i])->second < 0) return false; } } return true; }
但是,因为题目中说是小写字母,所以可以用数组来做。思路类似,相比使用map插入更简单。
bool isAnagram(string s, string t) { if (s.length() != t.length()) return false; int n = s.length(); int counts[26] = {0}; for (int i = 0; i < n; i++) { counts[s[i] - 'a']++; counts[t[i] - 'a']--; } for (int i = 0; i < 26; i++) if (counts[i]) return false; return true; }
与这道题类似的是这个:
解题思路:
使用数组计数。
bool canConstruct(string ransomNote, string magazine) { int i; int arr[26] = {0}; for (i = 0; i < magazine.length(); i++) { arr[magazine[i]-'a']++; } for (i = 0; i < ransomNote.length(); i++) { arr[ransomNote[i]-'a']--; if (arr[ransomNote[i]-'a'] < 0) return false; } return true; }
相同思路的还有这道题:
解题思路:
因为数字是1~n的,所以考虑直接利用下标。将nums[i]-1取绝对值后作为新的索引,将此处的数组值添加负号。
如果再次索引到此处,则可以将此索引值+1加入到result中。
vector<int> findDuplicates(vector<int>& nums) { vector<int> result; int i; for (i = 0; i < nums.size(); i++) { if (nums[abs(nums[i])-1] < 0) result.push_back(abs(nums[i])); else nums[abs(nums[i])-1] *= -1; } return result; }
相同的还有这道题:
438. Find All Anagrams in a String
解题思路:
同样用数组存p内字母的情况,然后扫s检查就好。需要注意的是memcpy函数的使用,分配空间时,不要用数字。。。
之前我写memcpy(temp, pArr, 26);实际上:
简直呵呵哒。
vector<int> findAnagrams(string s, string p) { vector<int> result; if (p.length() > s.length()) return result; int pArr[26] = {0}; for (int i = 0; i < p.length(); i++) { pArr[p[i] - 'a'] ++; } int i,j,k; bool flag; for (i = 0; i <= s.length() - p.length() ; i++) { int temp[26]; memcpy(temp, pArr, sizeof(pArr)); flag = true; for (j = i; j < i + p.length(); j++) { if (temp[s[j] - 'a'] == 0) { flag = false; break; } else temp[s[j] - 'a'] --; } if (flag == true) { for (k = 0; k < 26; k++) { if (temp[k] != 0) break; } if (k == 26) { result.push_back(i); } } } return result; }
解题思路:
本来是用遍历两次数组来算的,外层0~n-1,内层i+1~n-1,找到即跳出。但是如果数组很大,这样无疑很耗时。
由于数组是升序,所以考虑从左右两端开始查找。如果numbers[left]+numbers[right]==target,就找到了;
大于的话right左移,小于的话left右移。当left>=right时,终止。
vector<int> twoSum(vector<int>& numbers, int target) { vector<int> result; int left = 0; int right = numbers.size() - 1; while(left < right) { if (numbers[left] + numbers[right] == target) { result.push_back(left + 1); result.push_back(right + 1); break; } else if (numbers[left] + numbers[right] > target) { right --; } else { left ++; } } return result; }