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
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

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
};