Leetcode hot 100

双指针

283.移动零

class Solution {
public:void moveZeroes(vector<int>& nums) {int cnt = 0;for(vector<int>::iterator it = nums.begin(); it != nums.end(); ){if(*it == 0) it = nums.erase(it),cnt++;else it++;}while(cnt--){nums.push_back(0);}}
};

11.盛水最多的容器

class Solution {
public:int maxArea(vector<int>& height) {int l = 0, r = height.size()-1;int ans = 0;while(l < r){int t = min(height[l], height[r]) * (r-l) ;ans = max(ans, t);if(height[l] < height[r]) l++;else r--;}return ans;}
};

53. 最大子数组和

class Solution {
public:int maxSubArray(vector<int>& nums) {return  maxx(nums, 0, nums.size() - 1);}int maxx(vector<int>& nums, int l, int r) {if (l > r) return 0;if (l == r) {return nums[l];}int mid = (l + r) / 2;int ret = maxx(nums, l, mid);if(mid + 1 <= r)ret = max(ret, maxx(nums, mid + 1, r));int i = mid-1, j = mid+1;int tmp = nums[mid], maxone = tmp;while ( i >= l ) {tmp += nums[i];if (tmp >= maxone)maxone = max(maxone, tmp);i--;}tmp = maxone;while ( j <= r ) {tmp += nums[j];if ( tmp >= maxone)maxone = max(maxone, tmp);j++;}return max(ret, maxone);}};

56. 合并区间

class Solution {
public:static bool cmp(vector<int> a, vector<int> b){if(a[0] !=  b[0]) return a[0] < b[0];if(a[1] !=  b[1]) return a[1] < b[1];return false; }vector<vector<int>> merge(vector< vector<int> > intervals) {vector<vector<int>> ret ;// vector<int> tmp; sort(intervals.begin(), intervals.end(), cmp);int l = intervals[0][0], r = intervals[0][1];for(int i = 1; i< intervals.size(); i++){// cout<<intervals[i][0]<<' '<<intervals[i][1]<<endl;if(intervals[i][0] <= r) r = max(intervals[i][1], r);else {ret.push_back({l, r});l = intervals[i][0];r = intervals[i][1];}}ret.push_back({l, r});return ret;}};

160. 相交链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* p = headA, *q = NULL;int len1 = 0,len2 = 0;while(p){len1++;p = p->next;}p = headB;while(p){len2 ++;p = p->next;}p = headA;q = headB;if(len1 > len2) {int n = len1 - len2;while(n--) p = p->next;}else{int n = len2 - len1;while(n--) q = q->next;}while(p != q){p = p->next;q = q->next;}return p;}
};

141. 环形链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {set<ListNode *> st;ListNode *p = head;while(p != NULL){if(st.find(p) == st.end()) st.insert(p);else return true;p = p->next;}return false;}
};

142. 环形链表 II

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {map<ListNode *, int> mp;ListNode * ret = head;int idx = 0;while(ret != NULL){cout<<ret<<' ';if(mp.find(ret) != mp.end())return ret;else mp[ret] = idx++ ;ret = ret->next;}return NULL;}
};

2. 两数相加

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* p, *q, *tmp, *tmp2;p = l1;q = l2;int c = 0;tmp2 = p;while(p != NULL && q!=NULL){tmp = p;p->val = p->val + q->val + c;c = p->val / 10;p->val %= 10;p = p->next;q = q->next;}while(p != NULL){tmp = p;p->val += c;c = p->val / 10;p->val %= 10;p = p->next;}if(q!=NULL){tmp->next = q;}while(q != NULL){tmp = q;q->val += c;c = q->val / 10;q->val %= 10;q = q->next;}if(c) {ListNode * x = new ListNode(c, NULL);tmp->next = x;}tmp = reverse(tmp2);tmp2 = reverse(tmp);return tmp2;}ListNode* reverse(ListNode* l1){ListNode* p, *q, *tmp;p = l1 ->next;q = l1;q->next = NULL;while(p != NULL){tmp = p->next;p->next = q;q = p;p = tmp;} return q;}
};