Leetcode_14 天数据结构入门_day2

Posted on | Edited on | In ,
| 3.3k | 28 mins.

这两天的主题都是数组，感觉叫线性表更合适。

1. Two Sum

Analysis

好吧，这是 leetcode 第一题，估计没人没做过吧。做法很多，用散列做一下得了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
  vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> ht;
        vector<int> ret(2);
        for(int i = 0; i < nums.size(); i++) {
            if(ht.find(target - nums[i]) != ht.end()) {
                ret[0] = ht[target - nums[i]], ret[1] = i;
            break;
          }
            ht[nums[i]] = i;
        }
        return ret;
    }
};

88. Merge Sorted Array

Analysis

这个题跟合并链表好像是一个类型的题。

Code

method 1

先按照常规做法做一下。题目要求没有返回值，所以最后的结果只能存储在 nums1 中，那就只能想办法把 nums2 的数插到 nums1 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* method 1 */
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i = 0; i < n; i++) {
            int tmp = nums2[i], pos = 0;
            while(pos < m && tmp > nums1[pos]) pos++;
            if(pos != m) {
                int index = m;
                while(index > pos) {
                    nums1[index] = nums1[index - 1];
                    index--;
                }
            }
            nums1[pos] = tmp;
            m++;
        }
    }
};

从上面的解法中也可以看出链表与线性表在插入元素上的效率差异。

method 2

下面换一种解法。

1
2
3
4
5
6
7
8
9
10
11
/* method 2 */
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int index = 0;
        for(int i = m; i < m + n; i++) {
            nums1[i] = nums2[index++];
        }
        sort(nums1.begin(), nums1.end());
    }
};

直接拷贝到后面，排序完事。

method 3

别忘记了，题目还有一个条件，那就是 nums1 和 nums2 本身是有序的，那么就可以按照队列的思路来做了。让 nums1和 nums2 的元素按大小依次入队，最后结果就是所求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* method 3 */
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> queue(m + n);
        int pos1 = 0, pos2 = 0, index = 0;
        while(pos1 < m && pos2 < n) {
            if(nums1[pos1] < nums2[pos2]) {
                queue[index] = nums1[pos1];
                pos1++;
            } else {
                queue[index] = nums2[pos2];
                pos2++;
            }
            index++;
        }
        while(pos1 < m) queue[index++] = nums1[pos1++];
        while(pos2 < n) queue[index++] = nums2[pos2++];
        nums1 = queue;
    }
};

上面的解法其实是双指针的用法，但是额外消耗了空间。之所以要消耗空间，是因为先选出小的元素，后面的元素如果不后移就会被覆盖了。那么，先选大的元素，就不用担心这个问题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* method 4 */
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int pos1 = m - 1, pos2 = n - 1, index = m + n - 1;
        while(pos1 >= 0 && pos2 >= 0) {
            if(nums1[pos1] > nums2[pos2]) {
                nums1[index] = nums1[pos1];
                pos1--;
            } else {
                nums1[index] = nums2[pos2];
                pos2--;
            }
            index--;
        }
        while(pos1 >= 0) nums1[index--] = nums1[pos1--];
        while(pos2 >= 0) nums1[index--] = nums2[pos2--];
    }
};

Summary

今天的两个题比较简单，但是第二个题的解法很多，特别是双指针的解法，很灵活。

Buy me a coffee ? :)
0%