LeetCode刷題之路（第一天）

09-21

LeetCode刷題之路（第一天）

來自專欄那些搬磚的日子（計算機視覺與深度學習）1 人贊了文章

1、兩數之和

給定一個整數數組和一個目標值，找出數組中和為目標值的兩個數。

你可以假設每個輸入只對應一種答案，且同樣的元素不能被重複利用。

示例:

給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

C++版：

class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> res; int n = nums.size(); int *a = new int[n]; for(int i = 0;i < n;i++) a[i] = nums[i]; sort(nums.begin(), nums.end()); int lhs = 0, rhs = n -1; //從兩邊開始查找 while(rhs > lhs){ if(nums[rhs] + nums[lhs] > target) rhs--; else if(nums[rhs] + nums[lhs] < target) lhs++; else{ int id1, id2; for(int i = 0;i < n; i++){ if(a[i] == nums[lhs]){ id1 = i+1; break; } } for(int i = n - 1;i >= 0; i--){ if(a[i] == nums[rhs]){ id2 = i+1; break; } } res.push_back(min(id1, id2)); res.push_back(max(id1, id2)); return res; } } }};

這種方法首先把給定的Vector進行排序，然後從Vector的兩端進行查找，其時間複雜度為O(nlogn)，其空間複雜度為O(n)。這種方法相比於暴力求解的演算法性能還是提升了一些。但是有沒有更好的演算法呢？

答案是肯定的，利用哈希表可以用空間換取時間，使得時間複雜度降到O(n)。創建哈希表時要注意，不需要一開始就建立哈希表並掃描全部數據，可以邊創建邊建立哈希表。代碼如下：

class Solution {public: vector<int> twoSum(vector<int> &numbers, int target) { map<int, int> hashmap; vector<int> res; for(int i = 0;i < numbers.size();i++){ if(hashmap.find(target-numbers[i]) != hashmap.end()){ res.push_back(hashmap[target-numbers[i]]+1); res.push_back(i+1); return res; } hashmap[numbers[i]] = i; } return res; }};

Python版：

2. 兩個排序數組的中位數

給定兩個大小為 m 和 n 的有序數組 nums1 和 nums2 。

請找出這兩個有序數組的中位數。要求演算法的時間複雜度為 O(log (m+n)) 。

你可以假設 nums1 和 nums2 不同時為空。

示例 1:

nums1 = [1, 3] nums2 = [2]
中位數是 2.0 示例 2:
nums1 = [1, 2] nums2 = [3, 4]
中位數是 (2 + 3)/2 = 2.5

由於兩個vector是有序的，我們可以是用來類似歸併排序的方法將兩個vector進行結合，注意由於只需要得到中位數，故沒有必要添加所有數據，到達中位數即可。

class Solution {public: double findMedianSortedArrays(int A[], int m, int B[], int n) { vector<int> C; int i, j; int mid = (m+n) / 2 + 1; for(i=0, j=0;i<m && j<n;){ if(A[i] > B[j]){ C.push_back(B[j++]); } else{ C.push_back(A[i++]); } if(C.size() == mid){ break; } } while(C.size() != mid){ if(i < m) C.push_back(A[i++]); if(j < n) C.push_back(B[j++]); } if ((m+n) % 2 == 0) return (C[C.size()-1] + C[C.size()-2]) / 2.0; return *(C.end()-1); }};

3.無重複字元的最長子串

給定一個字元串，找出不含有重複字元的最長子串的長度。

示例 1:
輸入: 「abcabcbb」輸出: 3 解釋: 無重複字元的最長子串是「abc」，其長度為 3。示例 2:
輸入: 「bbbbb」輸出: 1 解釋: 無重複字元的最長子串是「b」，其長度為 1。示例 3:
輸入: 「pwwkew」輸出: 3 解釋: 無重複字元的最長子串是「wke」，其長度為 3。

請注意，答案必須是一個子串，」pwke」是一個子序列而不是子串。

這道題也是建立一個map，然後使用left去儲存當重複字元出現時最左側的索引，並去掉重複元素的重複個數。很簡單有效的思路，map的key值是可以重複出現的。

class Solution {public: int lengthOfLongestSubstring(string s) { int left = 0, maxlen = 0; unordered_map<char, int> charmap; if(s.length() == 0) return 0; for(int i=0; i < s.length();i++){ if(charmap.find(s[i]) != charmap.end()){ left = max(left, charmap[s[i]] + 1); } maxlen = max(maxlen, i-left+1); charmap[s[i]] = i; } return maxlen; }};

4.兩數相加

給定兩個非空鏈表來表示兩個非負整數。位數按照逆序方式存儲，它們的每個節點只存儲單個數字。將兩數相加返回一個新的鏈表。

你可以假設除了數字 0 之外，這兩個數字都不會以零開頭。

示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8 原因：342 + 465 = 807

/** * 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) { //進位 int carry = 0; ListNode* head = new ListNode(0); ListNode* pre = head; while(l1 != NULL || l2 != NULL || carry!=0){ //為null相當於零，但不能同時為null int sum = (l1 == NULL ? 0:l1->val) + (l2 == NULL ? 0:l2->val) + carry; ListNode* cur = new ListNode(sum%10); //當前節點的值為個位數 carry = sum / 10; pre->next = cur; pre = cur; // 把pre從head指向cur l1 = (l1==NULL ? l1 : l1->next); //尋找下一個節點 l2 = (l2==NULL ? l2 : l2->next); } return head->next; }};

聲明

以上代碼均參考於牛客網並在牛客網測試成功。參考了各位大佬的思路整理而成，希望大家一起學習~