LeetCode 415. Add Strings

Oct 9, 2016

题目描述:

Given two non-negative numbers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

  1. The length of both num1 and num2 is < 5100.
  2. Both num1 and num2 contains only digits 0-9.
  3. Both num1 and num2 does not contain any leading zero.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

简单的模拟加法.

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
36
class Solution {
public:
    string addStrings(string num1, string num2) {
        if(num2.length() > num1.length()) swap(num1, num2);
        int maxLen = num1.length(), minLen = num2.length(), inc = 0;
        string ans(maxLen, '0');
        int i;
        for(i = 0; i < minLen; i++){
            char a = num1[maxLen - i - 1] - '0', b = num2[minLen - i - 1] - '0';
            char r = a + b + inc;
            if(r >= 10){
                inc = 1;
            }
            else{
                inc = 0;
            }
            ans[maxLen - i - 1] = r % 10 + '0';
        }
        if(i < maxLen){
            for(; i < maxLen; i++){
                char r = num1[maxLen - i - 1] - '0' + inc;
                if(r >= 10){
                    inc = 1;
                }
                else{
                    inc = 0;
                }
                ans[maxLen - i - 1] = r % 10 + '0';
            }
        }
        if(inc){
            ans.insert(ans.begin(), '1');
        }
        return ans;
    }
};

LeetCode 150. Evaluate Reverse Polish Notation

Oct 8, 2016

题目描述:

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

1
2
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

逆波兰表达式的意思就是运算符后缀, 这种方式就是为栈设计的. 当读入数字的时候就将其入栈, 读入运算符的时候就将栈顶的两个元素取出运算后再压入栈.

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:
    int evalRPN(vector<string>& tokens) {
        vector<int> nums;
        for(int i = 0; i < tokens.size(); i++){
            string s = tokens[i];
            if(s.size() == 1 && (s == "+" || s == "-" || s == "*" || s == "/")){
                int a = nums.back();
                nums.pop_back();
                int b = nums.back();
                nums.pop_back();
                int re;
                switch(s[0]){
                    case '+':
                        re = a + b;
                        break;
                    case '-':
                        re = b - a;
                        break;
                    case '*':
                        re = b * a;
                        break;
                    case '/':
                        re = b / a;
                        break;
                }
                nums.push_back(re);
            }
            else{
                nums.push_back(stoi(s));
            }
        }
        return nums[0];
    }
};

LeetCode 149. Max Points on a Line

Oct 8, 2016

题目描述:

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

寻找一个平面上最多有多少个点共线. 首先应该复杂度应该是O(n2)的, 因为要判断每一个点与其他点的关系(或者说判断是否在之前的点所连成的线上). 对每一个点, 计算与其他点的连线的斜率, 找出出现次数最多的斜率, 它的出现次数就是共线的点的个数(但是这里没有包括改点自己, 再加上重复点的问题, 所以最后要加上该点自己的出现次数). 使用一个hash表来保存斜率的出现次数即可.

还要注意对于连线斜率为无穷大的点来说(横坐标相同), 要单独处理.

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
36
37
/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point>& points) {
        if(points.size() < 2) return points.size();
        
        int maxNum = 2;
        for(int i = 0; i < points.size(); i++){
            unordered_map<double, int> slope;
            int num = 1, mmax = 0, infiniteSlope = 0;
            for(int j = 0; j < i; j++){
                if(points[i].x == points[j].x){
                    if(points[i].y == points[j].y){
                        num++;
                    }
                    else{
                        mmax = max(mmax, ++infiniteSlope);
                    }
                }
                else{
                    double k = (double)(points[i].y - points[j].y) / (points[i].x - points[j].x);
                    mmax = max(mmax, ++slope[k]);
                }
            }
            maxNum = max(maxNum, mmax + num);
        }
        return maxNum;
    }
};

LeetCode 148. Sort List

Oct 7, 2016

题目描述:

Sort a linked list in O(n log n) time using constant space complexity.

不使用额外空间对单向链表进行排序, 要求时间复杂度为O(nlogn). 可以使用归并排序, 使用快慢指针把链表分为两部分, 分别进行递归地归并排序后再合并为一个链表.

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next) return head;
        if(head->next->next == nullptr){
            if(head->val > head->next->val){
                head->next->next = head;
                ListNode *t = head->next;
                head->next = nullptr;
                return t;
            }
            else return head;
        }
        ListNode *fast = head, *slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode *right = slow->next;
        slow->next = nullptr;
        head = sortList(head);
        right = sortList(right);
        return merge(head, right);
    }
    
    ListNode* merge(ListNode *left, ListNode *right){
        ListNode *head = new ListNode(0), *p1 = left, *p2 = right, *p = head;
        while(p1 && p2){
            if(p1->val < p2->val){
                p->next = p1;
                p1 = p1->next;
            }
            else{
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        if(p && !p1){
            p->next = p2;
        }
        else if(p && !p2){
            p->next = p1;
        }
        return head->next;
    }
};S

LeetCode 147. Insertion Sort List

Oct 7, 2016

题目描述:

Sort a linked list using insertion sort.

使用插入排序对一个链表进行排序. 对于原来链表中的每一个节点搜索在新链表中应该插入的位置.

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
36
37
38
39
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        return insertion(head);
    }
    
    ListNode* insertion(ListNode* head){
        if(!head) return nullptr;
        ListNode *h = new ListNode(head->val), *p = head->next;
        while(p){
            ListNode *tp = h, *prev = nullptr;
            while(tp && tp->val < p->val) {
                prev = tp;
                tp = tp->next;
            }
            if(prev){
                ListNode *newNode = new ListNode(p->val);
                newNode->next = prev->next;
                prev->next = newNode;
            }
            else{
                ListNode *newHead = new ListNode(p->val);
                newHead->next = h;
                h = newHead;
            }
            
            p = p->next;
        }
        return h;
    }
};

LeetCode 146. LRU Cache

Oct 6, 2016

题目描述:

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

实现一个LRU数据结构, 就是说在元素容量到达上限时要删除最长时间没有访问的元素. 要注意set和get都属于访问了元素.

主要问题在于如何保存所有访问元素的顺序并且能够高效地进行查找和删除. 我一开始想的方法是使用两个map, 分别保存上一次使用时间=>key和key=>上一次使用时间两个映射. 其中第一个map需要有序而第二个不需要, 所以第二个可以采用unordered_map. 第一个map用于保存每一个key的上一次访问时间并且按照访问时间从远到近排序. 但是这个办法虽然可以AC但是效率不高, 而且并不实用. 因为访问时间的表示范围毕竟是有限的, 实际中的访问次数是完全有可能超过它的取值范围的.

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
36
37
38
39
40
41
42
43
44
45
46
class LRUCache{
    unordered_map<int, int> data;
    map<int, int> lastTimeAndKey;
    unordered_map<int, int> keyAndLastTime;
    int capacity, useTime;
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        useTime = 0;
    }
    
    int get(int key) {
        if(data.count(key)) {
            int lastUseTime = keyAndLastTime[key];
            keyAndLastTime[key] = useTime;
            lastTimeAndKey.erase(lastUseTime);
            lastTimeAndKey[useTime] = key;
            useTime++;
            return data[key];
        }
        else return -1;
    }
    
    void set(int key, int value) {
        if(data.count(key)){
            int lastUseTime = keyAndLastTime[key];
            keyAndLastTime[key] = useTime;
            lastTimeAndKey.erase(lastUseTime);
            lastTimeAndKey[useTime] = key;
        } 
        else if(data.size() < capacity){
            lastTimeAndKey[useTime] = key;
            keyAndLastTime[key] = useTime;
        }
        else{
            int eraseKey = lastTimeAndKey.begin()->second;
            keyAndLastTime.erase(eraseKey);
            lastTimeAndKey.erase(lastTimeAndKey.begin());
            data.erase(eraseKey);
            lastTimeAndKey[useTime] = key;
            keyAndLastTime[key] = useTime;
        }
        useTime++;
        data[key] = value;
    }
};

所以后来我采用一个双向链表作为队列, 然后使用一个unordered_map来维护key=>链表节点指针(迭代器)的映射, 而链表中保存相应的key值. 当要更新队列时, 就通过key来找到节点, 删除节点并在最后增加节点, 更新key对应的迭代器. 当要删除队列中的第一个元素时, 可以通过头结点保存的key值同时删除data中的数据和key=>链表节点指针(迭代器)中的数据. 这样的话每次set和get的处理时间都是常数的.

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
36
37
38
39
40
41
42
43
class LRUCache{
    unordered_map<int, int> data;
    list<int> q;
    unordered_map<int, list<int>::iterator> keyToPointer;
    int capacity;
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if(data.count(key)) {
            list<int>::iterator iter = keyToPointer[key];
            q.erase(iter);
            q.push_back(key);
            keyToPointer[key] = --q.end();
            return data[key];
        }
        else return -1;
    }
    
    void set(int key, int value) {
        if(data.count(key)){
            list<int>::iterator iter = keyToPointer[key];
            q.erase(iter);
            q.push_back(key);
            keyToPointer[key] = --q.end();
        } 
        else if(data.size() < capacity){
            q.push_back(key);
            keyToPointer[key] = --q.end();
        }
        else{
            int keyToErase = q.front();
            data.erase(keyToErase);
            keyToPointer.erase(keyToErase);
            q.pop_front();
            q.push_back(key);
            keyToPointer[key] = --q.end();
        }
        data[key] = value;
    }
};

LeetCode 145. Binary Tree Postorder Traversal

Oct 6, 2016

题目描述:

Given a binary tree, return the postorder traversal of its nodes’ values.

For example: Given binary tree {1,#,2,3},

1
2
3
4
5
6
1
 \
  2
 /
3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

非递归后序遍历.

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(!root) return ans;
        vector<TreeNode*> stack = {root};
        
        while(!stack.empty()){
            TreeNode* n = stack.back();
            stack.pop_back();
            ans.push_back(n->val);
            if(n->left) stack.push_back(n->left);
            if(n->right) stack.push_back(n->right);
        }
        reverse(ans.begin(), ans.end());
        
        return ans;
    }
};

LeetCode 410. Split Array Largest Sum

Oct 5, 2016

题目描述:

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note: Given m satisfies the following constraint: 1 ≤ m ≤ length(nums) ≤ 14,000.

Examples:

1
2
3
4
5
6
7
8
9
10
11
Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

这道题我是采用二分搜索的方法解的. 虽然要想到对整个int型范围进行二分搜索还是不太容易, 但是只要想到这一点, 问题就基本解决了, 剩下的就可以通过贪心来判断数组能不能被分成m个并且保证最大的和不超过一个给定的值. 二分搜索上界是INT_MAX, 而下界是数组中的最大值.

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
36
37
38
39
40
41
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int len = nums.size();
        int maxElement = 0;
        for(auto i : nums){
            maxElement = max(maxElement, i);
        }
        long long left = maxElement, right = INT_MAX, mid = (left + right) / 2;
        while(left < right){
            if(canSplit(nums, mid, m)){
                right = mid;
            }
            else{
                left = mid + 1;
            }
            mid = (left + right) / 2;
        }
        return left;
    }
    
    bool canSplit(vector<int> &nums, long long target, int m){
        long long sum = 0;
        int splitArrs = 0;
        for(int i = 0; i < nums.size() && splitArrs <= m; i++){
            if(sum + nums[i] > target){
                sum = nums[i];
                splitArrs++;
            }
            else if(sum + nums[i] == target){
                sum = 0;
                splitArrs++;
            }
            else{
                sum += nums[i];
            }
        }
        if(sum > 0) splitArrs++;
        return splitArrs <= m;
    }
};

LeetCode 144. Binary Tree Preorder Traversal

Oct 5, 2016

题目描述:

Given a binary tree, return the preorder traversal of its nodes’ values.

For example: Given binary tree {1,#,2,3},

1
2
3
4
5
6
1
 \
  2
 /
3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

二叉树非递归前序遍历. 需要背下来的代码了…

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
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<TreeNode*> path;
        vector<int> ret;
        if(root == NULL) return ret;
        TreeNode *node = root;

        while(node || !path.empty()){
            if(node){
                ret.push_back(node->val);
                path.push_back(node);
                node = node->left;
            }
            else{
                node = path.back();
                path.pop_back();
                node = node->right;
            }
        }

        return ret;
    }
};

LeetCode 143. Reorder List

Oct 5, 2016

题目描述:

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.

这道题如果不用辅助空间的话分成三步: 1. 分割链表; 2. 颠倒第二个链表; 3. 合并链表. 其中分割链表通过快慢指针来找到链表的中间节点.

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode *fast = head, *low = head, *preLow = nullptr;;
        if(!head || !head->next) return;
        while(fast && fast->next){
            fast = fast->next->next;
            preLow = low;
            low = low->next;
        }
        preLow->next = nullptr;
        ListNode *h1 = head, *h2 = low;
        h2 = reverseList(h2);
        while(h1){
            if(!h1->next){
                h1->next = h2;
                break;
            }
            else{
                ListNode *h2next = h2->next;
                h2->next = h1->next;
                h1->next = h2;
                h1 = h1->next->next;
                h2 = h2next;
            }
        }
    }
    
    ListNode* reverseList(ListNode* head){
        if(!head) return head;
        ListNode *p1 = nullptr, *p2;
        p2 = head;
        while(p2){
            ListNode *next = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = next;
        }
        return p1;
    }
};