0%

leetcode题解(一)

最近在刷leetcode,topcoder上的题目,决定写一些笔记,加深一下印象吧。顺序就是从简单的开始。

Nim Game

1
2
3
4
5
6
7
8
class Solution {
public:
bool canWinNim(int n) {
if (n % 4 == 0)
return false;
return true;
}
};

在n=1,2,3时会赢,n=4时会输。 但n>4时,都可以转化为n<=4的情况,所以取模即可。

Add Digits

1
2
3
4
5
6
7
8
9
class Solution {
public:
int addDigits(int num) {
if (num == 0)
return 0;
int r = num % 9;
return r == 0 ? 9 : r ;
}
};

从1开始观察下就可发现,其实最后结果就是对9取模.

Maximum Depth of Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL)
return 0;
int num = 1;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
int add = left > right ? left : right;
return add + num;
}
};
```
用递归即可

[Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)

递归版本
``` cpp
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL)
return NULL;
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
};

非递归版本,其实递归程序都可以用stack来改成非递归版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL)
return NULL;
stack<TreeNode* > st;
st.push(root);
TreeNode* node;
while (!st.empty()) {
node = st.top();
st.pop();
TreeNode* tmp = node->left;
node->left = node->right;
node->right = tmp;
if (node->left)
st.push(node->left);
if (node->right)
st.push(node->right);

}

return root;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
int size = nums.size();
if (size < 2) return false;
vector<int> aux(nums);

return sort(nums, aux, 0, size - 1);

}
bool sort(vector<int>& nums, vector<int>& aux, int lo, int hi) {
if (lo >= hi)
return false;
int mid = lo + (hi - lo) / 2;
if (sort(nums, aux, lo, mid) || sort(nums, aux, mid + 1, hi)) {
return true;
}
return merge(nums, aux, lo, mid, hi);
}
bool merge(vector<int>& nums, vector<int>& aux, int lo, int mid, int hi) {

for (int i = lo; i <= hi; ++i) {
aux[i] = nums[i];
}
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; ++k) {
if (i > mid) nums[k] = aux[j++];
else if (j > hi) nums[k] = aux[i++];
else if (aux[i] == aux[j]) return true;
else if (aux[i] < aux[j]) nums[k] = aux[i++];
else nums[k] = aux[j++];
}
return false;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
int size = nums.size();
//if (size < 2) return false;
vector<int> aux(nums);

for (int sz = 1; sz < size; sz = 2*sz)
for (int lo = 0; lo < size - sz; lo += sz + sz)
if (merge(nums, aux, lo, lo + sz - 1, min(lo + sz + sz -1, size - 1))) return true;
return false;
}

bool merge(vector<int>& nums, vector<int>& aux, int lo, int mid, int hi) {

for (int i = lo; i <= hi; ++i) {
aux[i] = nums[i];
}
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; ++k) {
if (i > mid) nums[k] = aux[j++];
else if (j > hi) nums[k] = aux[i++];
else if (aux[i] == aux[j]) return true;
else if (aux[i] < aux[j]) nums[k] = aux[i++];
else nums[k] = aux[j++];
}
return false;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *pre = NULL;
ListNode *next;

while(head) {
next = head->next;
head->next = pre;
pre = head;
head = next;
}
return pre;
}
};