數(shù)組
要求
實(shí)現(xiàn)一個支持動態(tài)擴(kuò)容的數(shù)組
實(shí)現(xiàn)一個大小固定的有序數(shù)組，支持動態(tài)增刪改操作
實(shí)現(xiàn)兩個有序數(shù)組合并為一個有序數(shù)組
學(xué)習(xí)哈希表思想傍菇，并完成leetcode上的兩數(shù)之和(1)及Happy? Number(202)！(要求全部用哈希思想實(shí)現(xiàn)！)
哈希表 ： 散列表（Hash table舱沧，也叫哈希表）馋劈，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)攻锰。也就是說晾嘶，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度娶吞。這個映射函數(shù)叫做散列函數(shù)垒迂，存放記錄的數(shù)組叫做散列表。
散列函數(shù)設(shè)計(jì)原則：
計(jì)算簡單：散列函數(shù)的計(jì)算時間不應(yīng)該超過其他查找技術(shù)與關(guān)鍵字比較的時間妒蛇。
散列地址分布均勻：盡量讓散列地址均勻地分布在存儲空間中机断，這樣可以保證存儲空間的有效利用，并減少為處理沖突而耗費(fèi)的時間
1.Three?Sum（求三數(shù)之和）
英文版：https://leetcode.com/problems/3sum/
中文版：https://leetcode-cn.com/problems/3sum/
```
class Solution {
public:
? ? vector<vector<int>> threeSum(vector<int>& nums) {? ? ? ?
? ? ? ? map<int,int> temp;
? ? ? ? vector<vector<int>> ans;
? ? ? ? set<set<int>> anss;
? ? ? ? int len = nums.size();
? ? ? ? int n = 0;
? ? ? ? sort(nums.begin(), nums.end());
? ? ? ? for (int i = 0; i < len; i++)
? ? ? ? {
? ? ? ? ? ? temp[nums[i]] = i;
? ? ? ? }
? ? ? ? for (int i = 0; i < len; i++){
? ? ? ? ? ? for (int j = i+1; j < len; j++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? int num = -nums[i] - nums[j];
? ? ? ? ? ? ? ? if (num>0) continue;
? ? ? ? ? ? ? ? map<int, int> ::iterator add = temp.find(num);
? ? ? ? ? ? ? ? if (add == temp.end() || add->second <= j) continue;
? ? ? ? ? ? ? ? set<int> t;
? ? ? ? ? ? ? ? t.insert(nums[i]);
? ? ? ? ? ? ? ? t.insert(nums[j]);
? ? ? ? ? ? ? ? t.insert(add->first);
? ? ? ? ? ? ? ? //cout << nums[i] << nums[j] << add->first << endl;
? ? ? ? ? ? ? ? if (anss.count(t) == 0)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? anss.insert(t);
? ? ? ? ? ? ? ? ? ? vector<int> t;
? ? ? ? ? ? ? ? ? ? t.push_back(nums[i]);
? ? ? ? ? ? ? ? ? ? t.push_back(nums[j]);
? ? ? ? ? ? ? ? ? ? t.push_back(add->first);
? ? ? ? ? ? ? ? ? ? ans.push_back(t);
? ? ? ? ? ? ? ? ? ? cout << nums[i] << nums[j] << add->first << endl;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return ans;
? ? }
};
```
2.Majority?Element（求眾數(shù)）
英文版：https://leetcode.com/problems/majority-element/
中文版：https://leetcode-cn.com/problems/majority-element/
剛開始理解C++绣夺，先用個簡單方法吧吏奸，時間倉倉倉倉促。將數(shù)組給定區(qū)間的所有元素進(jìn)行排序之后返回?cái)?shù)量大于n/2的元素陶耍。（排序后還出現(xiàn)在中點(diǎn)苦丁，那一定是有很多個了）
```
class Solution {
public:
? ? int majorityElement(vector<int>& nums) {
? ? ? ? sort(nums.begin(), nums.end());
? ? ? ? return nums[nums.size()/2];
? ? ? ? }
};
```
https://leetcode-cn.com/problems/majority-element/
3.Missing?Positive（求缺失的第一個正數(shù)）
英文版：https://leetcode.com/problems/first-missing-positive/
中文版：https://leetcode-cn.com/problems/first-missing-positive/
```
class Solution {public:
? ? intfirstMissingPositive(vector& nums) {
? ? ? ? intn = nums.size();
? ? ? ? for(inti =0; i < n; ++i) {
? ? ? ? ? ? while(nums[i] >0&& nums[i] <= n && nums[nums[i] -1] != nums[i]) {
? ? ? ? ? ? ? ? swap(nums[i], nums[nums[i] -1]);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? for(inti =0; i < n; ++i) {
? ? ? ? ? ? if(nums[i] != i +1)returni +1;
? ? ? ? }
? ? ? ? returnn +1;
? ? }
};
```
https://leetcode-cn.com/problems/first-missing-positive/
字符串
實(shí)現(xiàn)一個字符集，只包含?a～z?這?26?個英文字母的?Trie?樹
實(shí)現(xiàn)樸素的字符串匹配算法
1.Reverse?String?（反轉(zhuǎn)字符串）
英文版：https://leetcode.com/problems/reverse-string/
中文版：https://leetcode-cn.com/problems/reverse-string/
```
class Solution {
public:
? ? void reverseString(vector<char>& s) {
? ? ? ? int length=s.size();
? ? ? ? if(length<2)
? ? ? ? ? ? return;
? ???????//reverse()會將區(qū)間[beg,end)內(nèi)的元素全部逆序物臂；
? ? ? ? reverse(s.begin(),s.end());
? ? }
};
```
https://leetcode-cn.com/problems/reverse-string/
2.Reverse?Words?in?a?String（翻轉(zhuǎn)字符串里的單詞）
英文版：https://leetcode.com/problems/reverse-words-in-a-string/
中文版：https://leetcode-cn.com/problems/reverse-words-in-a-string/
將字符串中的每個單詞反轉(zhuǎn)一下旺拉。對C++比C友好太多了！棵磷！
```
class Solution {
public:
? ? string reverseWords(string s) {
? ? ? ? int last = 0, now = 0;
? ? ? ? //翻轉(zhuǎn)每個單詞蛾狗，同時翻轉(zhuǎn)整個字符串，則對應(yīng)單詞拼寫正確
? ? ? ? while (s[now])
? ? ? ? {
? ? ? ? ? ? while (s[now] == ' ') now++;
? ? ? ? ? ? last = now;
? ? ? ? ? ? while (s[now] != ' ' && s[now] != '\0') now++;
? ? ? ? ? ? reverse(s[now], s[now-1]);
? ? ? ? }
? ? ? ? reverse(s[0], s[now-1]);
? ? ? ? last = 0;
? ? ? ? //刪除多余的空格
? ? ? ? for (int i = 0; i < now; i++)
? ? ? ? {
? ? ? ? ? ? if (!isblank(s[i]) || (last && s[last - 1] != s[i]))
? ? ? ? ? ? s[last++] = s[i];
? ? ? ? }
? ? ? ? s[last] = 0;
? ? ? ? if (last && s[last - 1] == ' ')
? ? ? ? ? ? s[last - 1] = 0;
? ? }
};
```
3.String?to?Integer?(atoi)（字符串轉(zhuǎn)換整數(shù)?(atoi)）
英文版：https://leetcode.com/problems/string-to-integer-atoi/
中文版：https://leetcode-cn.com/problems/string-to-integer-atoi/
```
class Solution {
public:
? ? int myAtoi(string str) {
? ? ? ? const int maxint=0x7fffffff;
? ? ? ? const int minint=0x80000000;
? ? ? ? const long long max=0x100000000;
? ? ? ? long long ans=0;
? ? ? ? bool flag=false;
? ? ? ? int st=0;
? ? ? ? while(st<str.length()&&str[st]==' '){
? ? ? ? ? ? st++;
? ? ? ? }
? ? ? ? if(st<str.length()&&str[st]=='+'){
? ? ? ? ? ? st++;
? ? ? ? }else{
? ? ? ? ? ? if(st<str.length()&&str[st]=='-'){
? ? ? ? ? ? ? ? flag=true;
? ? ? ? ? ? ? ? st++;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? for(int i=st;i<str.length();i++){
? ? ? ? ? ? if(str[i]<='9'&&str[i]>='0'){
? ? ? ? ? ? ? ? ans=ans*10+str[i]-'0';
? ? ? ? ? ? ? ? if(ans>maxint) ans=max;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if(flag) ans=-ans;
? ? ? ? if(ans>maxint) ans=maxint;
? ? ? ? if(ans<minint) ans=minint;
? ? ? ? return ans;
? ? }
};
```
