LeetCode 506. Relative Ranks

Feb 13, 2017

题目描述：

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: “Gold Medal”, “Silver Medal” and “Bronze Medal”.

Example 1:

1
2
3
4
5
Input: [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal". 
For the left two athletes, you just need to output their relative ranks according to their scores.

Note:

  1. N is a positive integer and won’t exceed 10,000.
  2. All the scores of athletes are guaranteed to be unique.

用排序+哈希表来建立得分与排名的对应关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    vector<string> medals = {"Gold Medal", "Silver Medal", "Bronze Medal"};
public:
    vector<string> findRelativeRanks(vector<int>& nums) {
        vector<string> ans;
        unordered_map<int, int> ranks;
        vector<int> sortNums = nums;
        sort(sortNums.begin(), sortNums.end(), greater<int>());
        for (int i = 0; i < sortNums.size(); i++) {
            ranks[sortNums[i]] = i + 1;
        }
        for (auto i : nums) {
            int rank = ranks[i];
            if (rank <= 3) {
                ans.push_back(medals[rank - 1]);
            }
            else {
                ans.push_back(to_string(rank));
            }
        }
        return ans;
    }
};

LeetCode 504. Base 7

Feb 13, 2017

题目描述：

Given an integer, return its base 7 string representation.

Example 1:

1
2
3
Input: 100
Output: "202"

Example 2:

1
2
3
Input: -7
Output: "-10"

Note: The input will be in range of [-1e7, 1e7].

使用除法来进行进制转换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string convertToBase7(int num) {
        int sign = num >= 0 ? 1 : -1;
        string ans;
        num = abs(num);
        if (num == 0) return string("0");
        while (num > 0) {
            ans.insert(ans.begin(), (num % 7) + '0');
            num /= 7;
        }
        if (sign > 0) return ans;
        else return string("-") + ans;
    }
};

LeetCode 500. Keyboard Row

Feb 13, 2017

题目描述：

Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.

American keyboard

Example 1:

1
2
3
Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]

Note:

  1. You may use one character in the keyboard more than once.
  2. You may assume the input string will only contain letters of alphabet.

判断每个字母在键盘上位于哪一行，可以用Hash表来保存每个字母所对应的行，也可以每次都搜索一次，因为数据量都很小所以性能差距很小。

Hash表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    vector<int> keymap = {2,3,3,2,1,2,2,2,1,2,2,2,3,3,1,1,1,1,2,1,1,3,1,3,1,3};
public:
    vector<string> findWords(vector<string>& words) {
        vector<string> ans;
        for (auto str : words) {
            int row = keymap[tolower(str[0]) - 'a'], i;
            for (i = 1; i < str.length(); i++) {
                if (keymap[tolower(str[i]) - 'a'] != row) break;
            }
            if (i == str.length()) ans.push_back(str);
        }
        return ans;
    }
};

搜索：

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 {
    vector<string> keyboard = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
public:
    vector<string> findWords(vector<string>& words) {
        vector<string> ans;
        for (auto str : words) {
            int row = findRow(str[0]), i;
            for (i = 1; i < str.length(); i++) {
                if (findRow(str[i]) != row) break;
            }
            if (i == str.length()) ans.push_back(str);
        }
        return ans;
    }
    
    int findRow(char c) {
        c = tolower(c);
        for (int i = 0; i < keyboard.size(); i++) {
            if (keyboard[i].find(c) != string::npos) 
                return i;
        }
        return -1;
    }
};

LeetCode 496. Next Greater Element I

Feb 13, 2017

题目描述：

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:

1
2
3
4
5
6
7
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Example 2:

1
2
3
4
5
6
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
    For number 2 in the first array, the next greater number for it in the second array is 3.
    For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

Note:

  1. All elements in nums1 and nums2 are unique.
  2. The length of both nums1 and nums2 would not exceed 1000.

使用双重循环即可。先搜索数值，再向后搜索比它大的第一个值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
        vector<int> ans;
        for (auto toFind : findNums) {
            for (int i = 0; i < nums.size(); i++) {
                if (nums[i] == toFind) {
                    int j;
                    for (j = i + 1; j < nums.size() && nums[j] <= toFind; j++) ;
                    if (j < nums.size()) ans.push_back(nums[j]);
                    else ans.push_back(-1);
                }
            }
        }
        return ans;
    }
};

LeetCode 492. Construct the Rectangle

Feb 4, 2017

题目描述：

For a web developer, it is very important to know how to design a web page’s size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:

1
2
3
4
5
6
1. The area of the rectangular web page you designed must equal to the given target area.

2. The width W should not be larger than the length L, which means L >= W.

3. The difference between length L and width W should be as small as possible.

You need to output the length L and the width W of the web page you designed in sequence.

Example:

1
2
3
4
5
Input: 4
Output: [2, 2]
Explanation: The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1]. 
But according to requirement 2, [1,4] is illegal; according to requirement 3,  [4,1] is not optimal compared to [2,2]. So the length L is 2, and the width W is 2.

Note:

  1. The given area won’t exceed 10,000,000 and is a positive integer
  2. The web page’s width and length you designed must be positive integers.

找到最接近的两个因数，使之乘积等于特定值。从给定的area的平方根向两边搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> constructRectangle(int area) {
        vector<int> ans(2);
        int t = sqrt(area);
        if (t * t == area) {
            ans[0] = ans[1] = t;
            return ans;
        }
        while (area % t != 0) {
            t--;
        }
        ans[0] = area / t;
        ans[1] = t;
        return ans;
    }
};

LeetCode 494. Target Sum

Feb 3, 2017

题目描述：

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

  1. The length of the given array is positive and will not exceed 20.
  2. The sum of elements in the given array will not exceed 1000.
  3. Your output answer is guaranteed to be fitted in a 32-bit integer.

暴力的DFS可以AC，但是Runtime不理想.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int ans = 0;
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        DFS(nums, 0, 0, S);
        return ans;
    }
    
    void DFS(vector<int>& nums, int i, int path, int S) {
        if (i == nums.size() - 1) {
            if (path + nums[i] == S) ans++;
            if (path - nums[i] == S) ans++;
            return ;
        }
        DFS(nums, i + 1, path + nums[i], S);
        DFS(nums, i + 1, path - nums[i], S);
    }
};

使用DP是比较好的选择。dp[i][j]表示前i+1个元素中和为j的情况数，由于和可能为负，所以为了确保下标非负，所有的j减去所有元素的和sum后才是真正的和。

要注意在初始化时，第一个元素如果为0，那么和0所对应的下标sum应该初始化为2而不是1。

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:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (auto i : nums) sum += i;
        
        int dp[nums.size()][sum * 2 + 1];
        memset(dp, 0, sizeof(dp));
        if (S > sum || S < -sum) return 0;
        dp[0][nums[0] + sum]++;
        dp[0][-nums[0] + sum]++;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j <= sum * 2; j++) {
                if (dp[i - 1][j]) {
                    int index = j + nums[i];
                    if (index >= 0 && index <= sum * 2) dp[i][index] += dp[i - 1][j];
                    index = j - nums[i];
                    if (index >= 0 && index <= sum * 2) dp[i][index] += dp[i - 1][j];
                }
            }
        }
        return dp[nums.size() - 1][S + sum];
    }
};

LeetCode 495. Teemo Attacking

Feb 3, 2017

题目描述：

In LLP world, there is a hero called Teemo and his attacking can make his enemy Ashe be in poisoned condition. Now, given the Teemo’s attacking ascending time series towards Ashe and the poisoning time duration per Teemo’s attacking, you need to output the total time that Ashe is in poisoned condition.

You may assume that Teemo attacks at the very beginning of a specific time point, and makes Ashe be in poisoned condition immediately.

Example 1:

1
2
3
4
5
6
7
Input: [1,4], 2
Output: 4
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned immediately. 
This poisoned status will last 2 seconds until the end of time point 2. 
And at time point 4, Teemo attacks Ashe again, and causes Ashe to be in poisoned status for another 2 seconds. 
So you finally need to output 4.

Example 2:

1
2
3
4
5
6
7
8
Input: [1,2], 2
Output: 3
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned. 
This poisoned status will last 2 seconds until the end of time point 2. 
However, at the beginning of time point 2, Teemo attacks Ashe again who is already in poisoned status. 
Since the poisoned status won't add up together, though the second poisoning attack will still work at time point 2, it will stop at the end of time point 3. 
So you finally need to output 3.

Note:

  1. You may assume the length of given time series array won’t exceed 10000.
  2. You may assume the numbers in the Teemo’s attacking time series and his poisoning time duration per attacking are non-negative integers, which won’t exceed 10,000,000.

提莫队长，正在送命！

题目比较简单，就是debuff状态时间不会叠加，每次击中目标后重新开始计时，要求返回总的debuff时间。只要每次判断与上一次攻击后的生效时间是否有重合，有的话就减去重合部分即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int ans = 0;
        if (timeSeries.empty()) return ans;
        ans = duration;
        for (int i = 1; i < timeSeries.size(); i++) {
            if (timeSeries[i] >= timeSeries[i - 1] + duration) {
                ans += duration;
            }
            else {
                ans += (timeSeries[i] - timeSeries[i - 1]);
            }
        }
        return ans;
    }
};

LeetCode 501. Find Mode in Binary Search Tree

Feb 3, 2017

题目描述：

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
  • Both the left and right subtrees must also be binary search trees.

For example: Given BST [1,null,2,2],

1
2
3
4
5
6
1
 \
  2
 /
2

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

使用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
/**
 * 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 {
    vector<int> ans;
    unordered_map<int, int> val;
    int maxOccur = 0;
public:
    vector<int> findMode(TreeNode* root) {
        inOrder(root);
        for (auto i : val) {
            if (i.second == maxOccur) 
                ans.push_back(i.first);
        }
        return ans;
    }
    
    void inOrder(TreeNode *node) {
        if(!node) return ;
        inOrder(node->left);
        maxOccur = max(maxOccur, ++val[node->val]);
        inOrder(node->right);
    }
};

在要求不使用额外存储空间的情况下，因为这是一棵BST，所以中序遍历结果是一个有序序列，问题就转化为在一个有序序列中连续出现次数最多的元素有哪些。除了维护结果集以外，还要维护结果集中元素的出现次数，上一个元素的值和当前元素的出现次数。当前元素的出现次数超过结果集中元素的出现次数后就清空结果集，然后增加当前元素。

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
/**
 * 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 {
    vector<int> ans;
    int lastElem = INT_MAX;
    int lastElemOccurTimes;
    int valInAnsOccurTimes = 0;
public:
    vector<int> findMode(TreeNode* root) {
        inOrder(root);
        return ans;
    }
    
    void inOrder(TreeNode *node) {
        if(!node) return ;
        inOrder(node->left);
        if (lastElem == node->val) {
            lastElemOccurTimes++;
        }
        else {
            lastElemOccurTimes = 1;
            lastElem = node->val;
        }
        
        if (lastElemOccurTimes == valInAnsOccurTimes) {
            ans.push_back(node->val);
        }
        else if (lastElemOccurTimes > valInAnsOccurTimes) {
            valInAnsOccurTimes = lastElemOccurTimes;
            ans.clear();
            ans.push_back(node->val);
        }
            
        inOrder(node->right);
    }
};

LeetCode 215. Kth Largest Element in an Array

Jan 21, 2017

题目描述：

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example, Given [3,2,1,5,6,4] and k = 2, return 5.

**Note: ** You may assume k is always valid, 1 ≤ k ≤ array’s length.

堆排序，我直接用STL了……

1
2
3
4
5
6
7
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        partial_sort(nums.begin(), nums.begin() + k, nums.end(), greater<int>());
        return nums[k - 1];
    }
};

LeetCode 214. Shortest Palindrome

Jan 21, 2017

题目描述：

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

这道题用直接的双重循环可能会超时，但是也不一定，比如我下面的代码就可以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
class Solution {
public:
    string shortestPalindrome(string s) {
        if(s.empty()) return s;
        int max_r = INT_MIN;
        for (int i = s.length() / 2; i >= 0; i--) {
            if ((max_r = palindromeBeside(s, i)) != -1) {
                break;
            }
        }
        string t = s.substr(max_r);
        reverse(t.begin(), t.end());
        return t + s;
    }
    
    int palindromeBeside(string &s, int axis) {
        int l = axis, r = axis;
        for (; l >= 0 && r < s.length(); l--, r++) {
            if(s[l] != s[r]) 
                break;
        }
        if (l < 0) {
            return r;
        }
        l = axis - 1, r = axis;
        for (; l >= 0 && r < s.length(); l--, r++) {
            if(s[l] != s[r]) 
                break;
        }
        if (l < 0) {
            return r;
        }
        return -1;
    }
};

但是这肯定不是一道Hard题的解法。这道题的本质在于寻找一个字符串S的最长回文前缀子串k，回文串的一个特征就是翻转之后保持不变，如果我们把S整个翻转之后接到S的后面得到的是以k开头，以k结尾的字符串。可以使用KMP算法中计算字符串自我覆盖情况的算法来进行计算，这个算法有点DP的意思，但是理解起来还是有点困难的，具体介绍可以Google关键字KMP。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string shortestPalindrome(string s) {
        if(s.empty()) return s;
        string ts = s;
        reverse(ts.begin(), ts.end());
        ts = s + "|" + ts;
        vector<int> v(ts.length(), 0);
        for (int i = 1; i < ts.length(); i++) {
            int index = i - 1;
            while (index >= 0 && ts[v[index]] != ts[i]) {
                index = v[index] - 1;
            }
            if (index >= 0) {
                v[i] = v[index] + 1;
            }
        }
        
        ts = s.substr(v.back());
        reverse(ts.begin(), ts.end());
        return ts + s;
    }
};