leetcode

leetcode-245. Shortest Word Distance III

2016-08-11

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

word1 and word2 may be the same and they represent two individual words in the list.

For example,
Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Given word1 = “makes”, word2 = “coding”, return 1.
Given word1 = “makes”, word2 = “makes”, return 3.

Note:
You may assume word1 and word2 are both in the list.
原题地址

比Shortest Word Distance的第三种解法多一个判断。

1
2
3
4
5
6
7
8
9
10
11
int shortestWordDistance(vector<string>& words, string word1, string word2) {
    int idx = -1, dist = INT_MAX;
    for (int i = 0; i < words.size(); i++) {
        if (words[i] == word1 || words[i] == word2) {
            if (idx != -1 && (word1 == word2 || words[i] != words[idx]))
                dist = min(dist, i - idx);
            idx = i;
        }
    }
    return dist;
}

leetcode-244. Shortest Word Distance II

2016-08-11

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = “makes”, word2 = “coding”, return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
原题地址

哈哈哈，人生的大喜大悲不过如此。刚刚还在吐槽zz的解法正中这道题下怀，直接贴上代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class WordDistance {
    unordered_map<string, vector<int>> hash;
public:
    WordDistance(vector<string>& words) {
        for (int i = 0; i < words.size(); i++)
            hash[words[i]].push_back(i);
    }
    int shortest(string word1, string word2) {
        int diff = INT_MAX, i1 = 0, i2 = 0;
        vector<int> vec1 = hash[word1];
        vector<int> vec2 = hash[word2];
        while (i1 < vec1.size() && i2 < vec2.size()) {
            if (vec1[i1] < vec2[i2])
                diff = min(diff, vec2[i2] - vec1[i1++]);
            else
                diff = min(diff, vec1[i1] - vec2[i2++]);
        }
        return diff;
    }
};

leetcode-243. Shortest Word Distance

2016-08-11

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example,
Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = “makes”, word2 = “coding”, return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
原题地址

感觉自己就跟zz一样。

首先扔出自己的2b解法。O(n) time, and O(n) space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int shortestDistance(vector<string>& words, string word1, string word2) {
    unordered_map<string, vector<int>> hash;
    for (int i = 0; i < words.size(); i++)
        hash[words[i]].push_back(i);
    vector<int> vec1 = hash[word1];
    vector<int> vec2 = hash[word2];
    int diff = INT_MAX, i1 = 0, i2 = 0;
    while (i1 < vec1.size() && i2 < vec2.size()) {
        if (vec1[i1] < vec2[i2]) {
            diff = min(diff, vec2[i2] - vec1[i1]);
            i1++;
        }
        else {
            diff = min(diff, vec1[i1] - vec2[i2]);
            i2++;
        }
    }
    return diff;

然后在网上看到比较标准的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int shortestDistance(vector<string>& words, string word1, string word2) {
    int i1 = -1, i2 = -1, diff = INT_MAX;
    for (int i = 0; i < words.size(); i++) {
        if (words[i] == word1) {
            i1 = i;
            if (i2 != -1)   diff = min(diff, i1 - i2);
        }
        if (words[i] == word2) {
            i2 = i;
            if (i1 != -1)   diff = min(diff, i2 - i1);
        }            
    }
    return diff;
}

然后又看到了更为简洁的写法。

1
2
3
4
5
6
7
8
9
10
11
int shortestDistance(vector<string>& words, string word1, string word2) {
    int idx = -1, diff = INT_MAX;
    for (int i = 0; i < words.size(); i++) {
        if (words[i] == word1 || words[i] == word2) {
            if (idx != -1 && words[i] != words[idx])
                diff = min(diff, i - idx);
            idx = i;
        }
    }
    return diff;
}

精益求精。

leetcode 167. Two Sum II - Input array is sorted

2016-08-10

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
原题地址

思路：Two pointers，从两边向中间找。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> twoSum(vector<int>& numbers, int target) {
    int begin = 0, end = numbers.size() - 1;
    while (end > begin) {
        int sum = numbers[begin] + numbers[end];
        if (sum < target)
            begin++;
        else if (sum > target)
            end--;
        else
            break;
    }
    vector<int> re = {begin + 1, end + 1};
    return re;

leetcode 370. Range Addition

2016-08-10

Assume you have an array of length n initialized with all 0’s and are given k update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex … endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.
原题地址

Google OA题。思路就是先把每一步的操作加、减到开始、结束位，最后累积求和。
不知道为什么速度不是很快，代码如下：

1
2
3
4
5
6
7
8
9
10
11
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
    vector<int> re(length + 1, 0);
    for (vector<int> & vec: updates) {
        re[vec[0]] += vec[2];
        re[vec[1] + 1] -= vec[2];
    }
    re.pop_back();
    for (int i = 1; i < length; i++)
        re[i] += re[i - 1];
    return re;        
}

leetcode 280. Wiggle Sort

2016-08-10

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]….
For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
原题地址

原理很简单，如果发现有违反规则的就跟前一个交换。一开始理解这道题认为就是一大一小交替排列，跑了一遍发现第一个必须是小。代码如下：

1
2
3
4
5
6
7
8
9
10
void wiggleSort(vector<int>& nums) {
    int diff = -1;
    for (int i = 1; i < nums.size(); i++) {
        int temp = nums[i] - nums[i - 1];
        if (diff * temp > 0)
            swap(nums[i - 1], nums[i]);
        diff = -diff;
    }
    return;
}

看了网上的答案，发现我的脑回路果然跟主流的不一样XD。正常的思路应该是，奇数位的要比前面大，偶数位的要比前面小。代码如下：

1
2
3
4
5
6
void wiggleSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 1; i < n; i++)
        if (((i & 1) && nums[i] < nums[i - 1]) || (!(i & 1) && nums[i] > nums[i - 1]))
            swap(nums[i], nums[i - 1]);
}

leetcode三刷

2016-08-10

之前断断续续刷了两波leetcode，最近面试发现又忘了差不多了。今天借到了一个会员账号，开始三刷之旅。借鉴一下其他博主的经验，这里把做过的题的思路都整理下来，方便以后回顾。我们优先从上锁题开始吧！

© 2016 Trivia - Powered by Hexo - Theme Chan