Leetcode每天兩題8-第18題和第19題

03-06

這是上午學習的兩個題，中午吃飯的時候看了集變形記，沒有任何準備的被感動到了。一對雲南的中年夫妻帶著兩個孩子，農村人，很土。某天男人精心策劃後帶著女人進了一間影樓，補拍婚紗照！圓了女人十幾年來的一個願望，然後帶著女人和孩子去吃甜品，為女人帶上新買的項鏈。男人全程很自信，女人很幸福滿足。

其實爛漫不分貴賤，愛情就該這樣，你崇拜我像英雄，我寵你像孩子。

18. 4Sum

從數組中找和等於給定值的四個數，並返回。

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:

[

[-1, 0, 0, 1],

[-2, -1, 1, 2],

[-2, 0, 0, 2]

]

代碼+注釋

class Solution {public: vector<vector<int>> fourSum(vector<int>& nums, int target) { //用set來避免重複問題 //排序 //每次先取兩個相鄰的數 //然後用左右兩個索引向中間逼近，判斷四個數的和是否等於target set<vector<int>> res; int n = nums.size(); sort(nums.begin(), nums.end()); int left = 0; for (int i = 0; i<n - 1; i++) { for (int j = i + 1; j<n - 2; j++) { left = j + 1; int right = n - 1; while (left<right) { int sum = nums[i] + nums[j] + nums[left] + nums[right]; if (sum == target) { res.insert({ nums[i],nums[j],nums[left],nums[right] }); left++; right--; } else if (sum<target) left++; else right--; } } } //這樣的返回有意思 return vector<vector<int>>(res.begin(), res.end()); }};

19. Remove Nth Node From End of List

移除鏈表倒數第N個節點，限定n一定是有效的，即n不會大於鏈表中的元素總數。還有題目要求我們一次遍歷解決問題。

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Try to do this in one pass.

代碼+注釋

class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { //傳入的鏈表不能為空 //準備兩個指針，保證兩個指針直接的距離為n //先兩個指針都指向首地址，將其中一個指針往後移動n //同時移動兩個指針，當位置靠前的指針的下個位置為空時 //靠後的指針就是要刪的節點 if (!head->next) return NULL; ListNode *pre = head, *curr = head; for (int i = 0; i<n; i++) curr = curr->next; if (!curr) return head->next; while (curr->next) { curr = curr->next; pre = pre->next; } pre->next = pre->next->next; return head; }};