Skip to content

Commit aba8f02

Browse files
MrFreezingMrFreezing
committed
First Week In GeekSchool : Algorithm 10
1 parent 0fd6bbe commit aba8f02

10 files changed

Lines changed: 213 additions & 1 deletion

‎Week01/LeetCodes/189_Rotate_Array.cpp‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
class Solution {
2+
public:
3+
// void rotate(vector<int>& nums, int k) {
4+
// int len = nums.size();
5+
// k = k % len;
6+
// if (k != 0) {
7+
// reserve(nums, 0, len - 1 - k);
8+
// reserve(nums, len - k, len - 1);
9+
// reserve(nums, 0, len -1);
10+
// }
11+
// }
12+
13+
// void reserve(vector<int>& nums, int begin, int end) {
14+
// while (begin < end) {
15+
// int temp = nums[begin];
16+
// nums[begin++] = nums[end];
17+
// nums[end--] = temp;
18+
// }
19+
// }
20+
21+
void rotate(vector<int>& nums, int k) {
22+
int len = nums.size();
23+
k = k % len;
24+
25+
if ( k != 0) {
26+
for (int i = 0, start = 0; i < len; start++) {
27+
int next = start;
28+
int prev = nums[start];
29+
30+
do {
31+
next = (next + k) % len;
32+
int temp = nums[next];
33+
nums[next] = prev;
34+
prev = temp;
35+
i++;
36+
} while (next != start);
37+
}
38+
}
39+
}
40+
};

‎Week01/LeetCodes/1_Two_Sum.cpp‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
class Solution {
2+
public:
3+
vector<int> twoSum(vector<int>& nums, int target) {
4+
vector<int> ret;
5+
int len = nums.size();
6+
7+
if (len > 1) {
8+
map<int,int> hash;
9+
for (int i = 0; i < len; i++) {
10+
if (hash.find(nums[i]) != hash.end()) {
11+
ret.push_back(hash[nums[i]]);
12+
ret.push_back(i);
13+
return ret;
14+
}
15+
hash[target - nums[i]] = i;
16+
}
17+
}
18+
19+
return ret;
20+
}
21+
};

‎Week01/LeetCodes/21_Merge_Two_Sorted_Lists.cpp‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* struct ListNode {
4+
* int val;
5+
* ListNode *next;
6+
* ListNode() : val(0), next(nullptr) {}
7+
* ListNode(int x) : val(x), next(nullptr) {}
8+
* ListNode(int x, ListNode *next) : val(x), next(next) {}
9+
* };
10+
*/
11+
class Solution {
12+
public:
13+
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
14+
if (!l1 || !l2) return l1 ? l1 : l2;
15+
16+
ListNode * p1 = l1;
17+
ListNode * p2 = l2;
18+
ListNode * head = p1->val < p2->val ? (p1 = p1->next, l1) : (p2 = p2->next, l2);
19+
ListNode * p = head;
20+
21+
while(p1 && p2) {
22+
if (p1->val < p2->val) {
23+
p->next = p1;
24+
p1 = p1->next;
25+
} else {
26+
p->next = p2;
27+
p2 = p2->next;
28+
}
29+
p = p->next;
30+
}
31+
32+
p->next = p1 ? p1 : p2;
33+
return head;
34+
}
35+
};

‎Week01/LeetCodes/26_Remove_Duplicates_from_Sorted_Array.cpp‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
class Solution {
2+
public:
3+
int removeDuplicates(vector<int>& nums) {
4+
if (nums.size() == 0) return 0;
5+
6+
int j = 0;
7+
for (int i = 1; i < nums.size(); i++) {
8+
if (nums[i] != nums[j]) nums[++j] = nums[i];
9+
}
10+
return j+1;
11+
//nums.erase(nums.begin()+j, nums.end());
12+
}
13+
};

‎Week01/LeetCodes/283_Move_Zeroes.cpp‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
class Solution {
2+
public:
3+
void moveZeroes(vector<int>& nums) {
4+
int j = 0;
5+
int len = nums.size();
6+
for (int i=0; i < len; i++) {
7+
if (nums[i] == 0)
8+
continue;
9+
nums[j++] = nums[i];
10+
}
11+
12+
for (; j < len; j++) {
13+
nums[j] = 0;
14+
}
15+
}
16+
};

‎Week01/LeetCodes/42_Trapping_Rain_Water.cpp‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
class Solution {
2+
public:
3+
int trap(vector<int>& height) {
4+
int len = height.size();
5+
if (len < 2) return 0;
6+
7+
stack<int> idx;//位置栈
8+
stack<int> hi;//高度向量栈
9+
int area = 0;//雨水总面积
10+
11+
for (int i = 1; i < len; i++) {
12+
int t_hi = height[i] - height[i-1];
13+
if ( t_hi > 0 ) area += pop(idx, hi, i, t_hi);
14+
else if (t_hi < 0 ) {
15+
idx.push(i);
16+
hi.push(-t_hi);
17+
} else {
18+
//do nothing
19+
}
20+
}
21+
22+
return area;
23+
}
24+
25+
int pop (stack<int> &idx, stack<int>& hi, int index, int height ) {
26+
if (idx.size() == 0 ) return 0;
27+
28+
int s_hi = hi.top(); hi.pop();
29+
int s_idx = idx.top(); idx.pop();
30+
31+
if (height > s_hi) {
32+
return s_hi * (index - s_idx) + pop(idx, hi, index, height - s_hi);
33+
} else if (height == s_hi) {
34+
return s_hi * (index - s_idx);
35+
} else {
36+
idx.push(s_idx);
37+
hi.push(s_hi - height);
38+
return height * (index - s_idx);
39+
}
40+
}
41+
};
42+

‎Week01/LeetCodes/66_Plus_One.cpp‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
class Solution {
2+
public:
3+
vector<int> plusOne(vector<int>& digits) {
4+
int i = digits.size();
5+
do {
6+
digits[i-1] = digits[i-1] == 9 ? 0 : digits[i-1]+1;
7+
} while (!digits[--i] && i);
8+
9+
if (!i && !digits[i]) {
10+
digits[0] = 1;
11+
digits.push_back(0);
12+
}
13+
14+
return digits;
15+
}
16+
};

‎Week01/LeetCodes/88_Merge_Sorted_Array.cpp‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
class Solution {
2+
public:
3+
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
4+
for (int i = m+n-1; i>=0 && n >0; i--)
5+
nums1[i] = m < 1 ? nums2[--n] : nums1[m-1] > nums2[n-1] ? nums1[--m] : nums2[--n];
6+
7+
}
8+
};

‎Week01/NOTE.md‎

Lines changed: 22 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,22 @@
1-
学习笔记
1+
学习笔记
2+
3+
周末才有空开始学习，课程内容比想象得多
4+
重中之重还是要多练, 练的同时也要掌握方法和效率。
5+
忍不住硬啃了一题接雨水，提交通过一瞬间还是挺开心的，但是一晃眼大把的时间过去了，还是不建议硬啃。
6+
7+
8+
写力扣代码时，有些陷进去运行时间，
9+
另外代码行数也很难做到最精简，感觉在力扣上，会不知不常见牺牲掉可读性，去追求更少的代码行数，这与实际工作中的规范可能是相违背的。
10+
11+
不过有些代码也是真的精妙，忍不住贴一下这个妖怪的代码, 这个for循环写得我目瞪口呆：
12+
13+
vector<int> plusOne(vector<int>& digits) {
14+
for (int i=digits.size(); i--; digits[i] = 0)
15+
if (digits[i]++ < 9)
16+
return digits;
17+
digits[0]++;
18+
digits.push_back(0);
19+
return digits;
20+
}
21+
22+
https://leetcode.com/problems/plus-one/discuss/24084/Is-it-a-simple-code(C++)

‎Week01/数据结构.pdf‎

383 KB
Binary file not shown.

0 commit comments

Comments
 (0)