成功人士從不刷Leetcode(3)

01-29

1. Two sum(https://leetcode.com/problems/two-sum/)

要求：求一個數組的數，返回數組的兩個元素的index，使這兩個元素之和等於目標值。

思路：使用hash map存儲第N個元素AN，以值為key，以index為value。讀到第N＋1個元素A(N+1)時，先在map中尋找key為target-A(N+1)，如果沒有，則繼續把第N＋1個元素存儲進map，否則返回N+1和查找到的map中元素的value（即對應元素的index）。

提示：用unordered_map代替map。

class Solution {npublic:n vector<int> twoSum(vector<int>& nums, int target) {n unordered_map<int,int> h;n vector<int> ret;n for (int i=0;i<nums.size();i++){n if (h.find(target - nums[i]) == h.end() ) h[nums[i]] = i;n else {n ret.push_back(h[target - nums[i]]);n ret.push_back(i);n }n }n return ret;n }n};n

2. Add Two Numbers (https://leetcode.com/problems/add-two-numbers/)

要求：將兩個LinkedList的各個元素相加，組成一個新的LinkedList。

提示：走遍兩個LinkedList，把value相加即可。注意兩點：1. 當兩個LinkedList長度不一樣時，應該考慮在末尾再補上長出的List；2. 注意設置進位位，每一次添加新的Node時都應該考慮加前一個進位位和新的進位位，並且注意處理在所有List加完之後最後進位位是否還有剩餘，如果還有，則再添加一個ListNode(1)（例如999999 + 1 = 1000000）

/**n * Definition for singly-linked list.n * struct ListNode {n * int val;n * ListNode *next;n * ListNode(int x) : val(x), next(NULL) {}n * };n */nclass Solution {npublic:n ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {n ListNode* newhead = new ListNode(0);n ListNode* cur = newhead;n int mark = 0;n while (l1 && l2) {n cur->next = new ListNode( (l1->val + l2->val + mark) % 10 );n mark = ( (l1->val + l2->val + mark) >= 10)?1:0;n l1 = l1->next;n l2 = l2->next;n cur = cur->next;n }n n while (l1) {n cur->next = new ListNode ((l1->val + mark) % 10);n mark = (l1->val + mark >= 10)?1:0;n cur = cur->next;n l1 = l1->next;n }n n while (l2) {n cur->next = new ListNode( (l2->val + mark) % 10 );n mark = (l2->val + mark >= 10)?1:0;n cur = cur->next;n l2 = l2->next;n }n n if (mark) cur->next = new ListNode(1);n return newhead->next;n }nn};n

104. Maximum Depth of Binary Tree(https://leetcode.com/problems/maximum-depth-of-binary-tree/)

要求：求一個Binary Tree的最大的深度。

提示：recursive解法。

class Solution {npublic:n int maxDepth(TreeNode* root) {n if (!root) return 0;n else return max(maxDepth(root->left), maxDepth(root->right)) + 1;n }n};n

155. Min Stack (https://leetcode.com/problems/min-stack/)

要求：實現一個stack，使其不僅有stack的方法，還有getmin（）的方法，以O（1）的時間讀取stack所有元素的最小值。

提示：另設一個st_min的stack，使得該stack的頂端值，為當前stack的最小值。如果新push進來的元素小於st_min的top，則把該元素也push到st_min中。當從stack中pop一個元素時，如果該元素剛好等於st_min的top，則同樣pop出st_min的元素。

class MinStack {npublic:n /** initialize your data structure here. */n stack<int> st;n stack<int> st_min;n MinStack() {n }n void push(int x) {n st.push(x);n if (st_min.size() == 0 || st_min.top() >= x) st_min.push(x);n }n void pop() {n if (st_min.top() == st.top()) st_min.pop();n st.pop();n }n int top() {n return st.top();n }n int getMin() {n return st_min.top();n }nnn};n

7. Reverse Integer(https://leetcode.com/problems/reverse-integer/)

要求：將一個整數的各位數字顛倒過來。

提示：要判斷顛倒過來的數字是否在INT_MIN~INT_MAX範圍內，否則返回0。

class Solution {npublic:n int reverse(int x) {n int neg_mark = x>0?1:0;n long y = 0;n x = abs(x);n while (x) {n y = y * 10 + x % 10;n x /= 10;n }n if (y > INT_MAX || y < INT_MIN) return 0;n return neg_mark? y:(y*-1);n }n};n

206. Reverse Linked List(https://leetcode.com/problems/reverse-linked-list/)

提示：使用Recursive method，當head->next之後的所有List都反轉後，head->next指向的是該list的最後一個，而之前函數返回的是該List的第一個，因此只要把head放在head->next最後，並把返回的head_next給返回了即可。

class Solution {npublic:n ListNode* reverseList(ListNode* head) {n if (!head || !head->next) return head;n ListNode* head_next = reverseList(head->next);n head->next->next = head;n head->next = NULL;n return head_next;n }n};n

再給一個Iterative的寫法。

class Solution {npublic:n ListNode* reverseList(ListNode* head) {n ListNode* newhead = new ListNode(0);n if (!head) return NULL;n ListNode* temp = head->next;n if (!temp) return head;n while (temp) {n temp = head->next;n head->next = newhead->next;n newhead->next = head;n head = temp;n }n return newhead->next;n }n};n

141. Linked List Cycle (https://leetcode.com/problems/linked-list-cycle/)

提示：使用快慢指針，注意判斷快指針next的有效性。

class Solution {npublic:n bool hasCycle(ListNode *head) {n ListNode* f; //fastn ListNode* s; //slown if (!head || !head->next) return false;n f = s = head;n while (f) {n if (f->next) f = f->next->next;n else return false;n s = s->next;n if (f==s) return true;n }n return false;n }n};n

我發現每天晚上碼的「成功人士從不刷Leetcode」系列已經成為知乎書館最受歡迎的連載內容，臨睡前寫一點，寫起來不費勁，還有好多人愛看。如果您對某道題目有更好的解法，或者有錯誤指出，歡迎直接投稿到本專欄。有人說我第一期就那麼敷衍，後來為什麼越來越敷衍了呢，於是從明天起只講medium和hard的題目。

另外英國成功脫離歐洲，曾老師將於近期在本專欄直播裸奔，敬請關注。