LeetCode刷題筆記 （1-3）

解答記錄

1. Two Sum

一遍hash法的解答程序

class Solution {public: //一遍hash法求解 vector<int> twoSum(vector<int>& nums, int target) { int size = nums.size(); map <int,int> hash;//利用map構建hash表，內容為<number,index> vector<int> ans; for(int i=0;i<size;i++) { int ans_num = target-nums[i]; //每次加入新元素時就查找map，檢查有無答案 if(hash.find(ans_num)!=hash.end())//find the answer number { ans.push_back(hash[ans_num]); ans.push_back(i); return ans; } else //not find the answer number hash.insert(pair<int,int>(nums[i],i)); } return ans; } };

暴力法過於簡單，此處不寫。

如果將 建立hash表-查找答案 這兩個步驟分開進行，就是本題答案中的 二次hash解法。

2. Add Two Numbers

本題沒有特別之處，在多項式加和中只需要考慮進位即可。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *iter = new ListNode(0); ListNode *ans = iter; //initialize the ans list iter->val = l1->val + l2->val; int carry = iter->val / 10; iter->val %= 10; while(l1!=NULL || l2!=NULL) { int x = l1?l1->val:0; int y = l2?l2->val:0; iter->next = new ListNode(0); iter = iter->next;//next node iter->val = x + y + carry; carry = iter->val / 10; iter->val %= 10; l1 = l1?l1->next:NULL; l2 = l2?l2->next:NULL; } if(carry != 0) { iter->next = new ListNode(0); iter = iter->next; iter->val = carry; } return ans; }};

3.Longest Substring Without Repeating Characters

查找給定字元串的最長不重複子串

3.1 簡單優化暴力法

使用set存放字元來確定子串是否重複，然後i的每次遍歷從i+len直到末尾

class Solution {public: int notRepeat(string s,int begin,int end) { int i; set<char> chs; for(i=begin;i<=end;i++) { if(chs.find(s[i])==chs.end())//沒有重複字元 { chs.insert(s[i]);//將字元加入chs } else//發現重複字元 return 0; } return 1; } int lengthOfLongestSubstring(string s) { int len = 1;//default 1 int size = s.size(); if(s == "") return 0;//if s is empty for(int i=0;i<size-1;i++) for(int j=i+len;j<size;j++) { if(notRepeat(s,i,j)) len = max((j-i+1),len); else break; } return len; }};

3.2 滑動窗口法

首先建立[i, j)的一個窗口，此處使用[i, j-1]的一個set來實現

如果沒有重複，則擴大窗口 [i, j)-》[i, j+1)

如果發現j與[i, j)內第i_c號元素重複，則縮小窗口 [i, j)-》[i_c+1, j)

每次更新窗口後，檢查最大長度是否需要更新。

class Solution {public: //簡單優化 滑動窗口法 int lengthOfLongestSubstring(string s) { int i,j,len = 1; int size = s.size(); set<int> win; win.insert(s[i]);//建立窗口[0,1) if(s=="") return 0; //利用窗口進行遍歷 for(i=0,j=1;j<size;) { if(win.find(s[j])==win.end())//win中不包含j號元素 { win.insert(s[j]); j++;//窗口右端移動1個單位:[i,j)->[i,j+1) len = max(j-i,len);//確認最大長度 } else//出現重複元素 i_c和j 時 { //[i,j)->[i_c+1,j) do { win.erase(s[i]);//刪除i i++;//窗口左端移動1個單位:[i,j)->[i+1,j) }while(s[i-1]!=s[j]); } } return len; }};

顯而易見的效率提升

總結

本次主要學習了兩種方法

利用map構建的hash表（在需要實現<index,element>的快速查找時）

利用set實現的滑動窗口（在需要遍曆數組的非重複子串時）