LeetCode 164. Maximum Gap

Oct 12, 2016

题目描述:

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

这道题就是一个排序问题, 但是要求O(n)时间复杂度, 可用的办法有桶排序(bucket sort)和基数排序(radix sort), 但是虽然说这两种算法有近似O(n)的复杂度, 但是它们并不一定真的比快排之类的算法快, 因为虽然快排, 堆排的时间复杂度是O(nlogn), 但即使n达到232, logn也只有32而已, 实际中要排序的数据达到这个数量级时我觉得应该考虑外部排序了, 因为很可能数据已经无法完全装入内存了. 而桶排序和基数排序的O(n)算法系数也并不小, 所以这道题直接用快排或者STL的sort函数也是能过的.

更进一步来说, 基于比较的排序算法时间复杂度下界是O(nlogn), 而能到达O(n)复杂度的算法是非比较的排序算法(计数排序, 基数排序, 桶排序).(http://blog.csdn.net/zouliping123/article/details/8934856)

桶排序:

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
class Solution {
public:
    int maximumGap(vector<int> &nums) {
        int length = nums.size();
        if (length < 2) return 0;
        int max_item = nums[0], min_item = nums[0];

        for(int i = 1; i < length; i++){
            max_item = max(max_item, nums[i]);
            min_item = min(min_item, nums[i]);
        }

        int bucket_gap = ( max_item - min_item ) / length >= 1 ? ( max_item - min_item ) / length : 1;
        int bucket_size = ( max_item - min_item ) / bucket_gap + 1;

        vector<vector<int>> bucket(bucket_size);

        for(int i = 0; i < length; i++){
            bucket[(nums[i] - min_item) / bucket_gap].push_back(nums[i]);
        }

        int max_gap = 0;

        for(int i = 0; i < bucket_size; i++){
            sort(bucket[i].begin(), bucket[i].end());
        }
        
        int lastNoneEmptyIndex = -1;
        for(int i = 0; i < bucket.size(); i++){
            if(!bucket[i].empty() && i != 0 && lastNoneEmptyIndex != -1){
                max_gap =max(max_gap, bucket[i][0] - bucket[lastNoneEmptyIndex].back());
            }
            
            if(!bucket[i].empty()){
                lastNoneEmptyIndex = i;
                for(int j = 1; j < bucket[i].size() && max_gap < bucket_gap; j++){
                    max_gap = max(max_gap, bucket[i][j] - bucket[i][j - 1]);
                }
            }
        }

        return max_gap;
    }
};

基数排序:

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 maximumGap(vector<int> &nums) {
        int length = nums.size();
        if (length < 2) return 0;
        int max_gap = 0;
        vector<int> radix(10, 0);
        vector<int> tmp(length);
        int i = 0, r = 1;
        while(i < 10){
            for(int j = 0; j < 10; j++){
                radix[j] = 0;
            }
            for(auto j : nums){
                radix[(j / r) % 10]++;
            }
            for(int j = 1; j < 10; j++){
                radix[j] += radix[j - 1];
            }
            for(int j = length - 1; j >= 0; j--){
                int k = (nums[j] / r) % 10;
                tmp[--radix[k]] = nums[j];
            }
            i++;
            r *= 10;
            nums = tmp;
        }
        
        for(int i = 0; i < length - 1; i++){
            max_gap = max(max_gap, nums[i + 1] - nums[i]);
        }

        return max_gap;
    }
};

LeetCode 162. Find Peak Element

Oct 12, 2016

题目描述:

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

**Note:**Your solution should be in logarithmic complexity.

二分搜索，每次比较找到的nums[mid]与邻居的大小来决定向哪边搜索,注意对于边界的处理,下标不能越界.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if(nums.size() == 1) return 0;
        if(nums.size() == 2) return nums[0] > nums[1] ? 0 : 1;
        int start = 0, end = nums.size(), mid, len = nums.size();
        while(start < end){
            mid = (start + end) / 2;
            if(mid == 0) return nums[0] > nums[1] ? 0 : 1;
            if(mid == nums.size() - 1) return nums[len - 2] > nums[len - 1] ? len - 2 : len - 1;
            if(nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]){
                return mid;
            }else if(nums[mid] > nums[mid - 1] && nums[mid + 1] > nums[mid]){
                start = mid + 1;
            }else{
                end = mid;
            }
        }
        return start;
    }
};

LeetCode 160. Intersection of Two Linked Lists

Oct 12, 2016

题目描述:

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

1
2
3
4
5
6
A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

这是一道我遇到过的面试题. 解题方法就是先遍历得到两个链表的长度, 然后再跳过较长的链表的前面几个节点, 直到两个链表剩下的部分长度相等, 再同步移动指针来找到相交的节点.

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = 0, lenB = 0;
        ListNode *pa = headA, *pb = headB;
        while(pa){
            lenA++;
            pa = pa->next;
        }
        while(pb){
            lenB++;
            pb = pb->next;
        }
        pa = headA, pb = headB;
        if(lenA > lenB){
            for(int i = 0; i < lenA - lenB; i++) pa = pa->next;
        }
        else if(lenA < lenB){
            for(int i = 0; i < lenB - lenA; i++) pb = pb->next;
        }
        while(pa && pb){
            if(pa == pb && pa != nullptr) return pa;
            pa = pa->next;
            pb = pb->next;
        }
        return nullptr;
    }
};

LeetCode 155. Min Stack

Oct 11, 2016

题目描述:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • getMin() – Retrieve the minimum element in the stack.

Example:

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

实现一个栈的同时能在常数时间内取得栈内的最小值. 使用两个栈即可, 一个栈用来保存元素, 另一个栈用来保存对应元素时栈内的最小值.

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 MinStack {
public:
    vector<int> stack;
    vector<int> min;
    void push(int x) {
        stack.push_back(x);
        if(min.empty() || min.back() > x) min.push_back(x);
        else min.push_back(min.back());
    }

    void pop() {
        stack.pop_back();
        min.pop_back();
    }

    int top() {
        if(stack.empty()) return -1;
        return stack.back();
    }

    int getMin() {
        return min.back();
    }
};

LeetCode 154. Find Minimum in Rotated Sorted Array II

Oct 11, 2016

题目描述:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

与上一题类似, 但是有重复元素, 所以要用遍历的方法跳过这些元素.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1, mid = (right + left) / 2;
        while(left < right){
            if(nums[mid] > nums[right]) left = mid + 1;
            else if(nums[mid] == nums[right]) right--;
            else right = mid;
            mid = (right + left) / 2;
        }
        return nums[left];
    }
};

LeetCode 153. Find Minimum in Rotated Sorted Array

Oct 11, 2016

题目描述:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

这道题虽然使用线性遍历的方法也能过, 但是是可以使用二分搜索的.

一个经过了循环左移的有序数组相当于被分成了两部分, 我们要找的是这两部分的分界点, 判断一个点是在哪一部分是看它与两端的元素的大小关系, 如果比两端的元素大, 那么它是在左半部分; 如果比两端的元素小, 那么它是在右半部分; 如果它比左端元素小比右边元素大, 那么从左端到右端整体是有序的, 在这种情况下最左端元素就是最小值; 不可能出现比左端元素大而比右端元素小的情况.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1, mid = (left + right) / 2;
        while(true){
            if(nums[mid] < nums[left] && nums[mid] < nums[right]){
                right = mid;
            }
            else if(nums[mid] >= nums[left] && nums[mid] > nums[right]){
                left = mid + 1;
            }
            else{
                return nums[left];
            }
            mid = (left + right) / 2;
        }
    }
};

LeetCode 152. Maximum Product Subarray

Oct 10, 2016

题目描述:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

DP问题, 主要问题在于数组中可能会出现负数, 所以要在维护最大值的同时维护一个最小值, 因为如果一个元素为负, 那么最小值也有可能变为最大值.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxPrevP = nums[0], minPrevP = nums[0], maxP = nums[0];
        for(int i = 1; i < nums.size(); i++){
            int maxCurP = max(maxPrevP * nums[i], max(nums[i], minPrevP * nums[i]));
            int minCurP = min(maxPrevP * nums[i], min(nums[i], minPrevP * nums[i]));
            if(maxP < maxCurP) maxP = maxCurP;
            maxPrevP = maxCurP, minPrevP = minCurP;
        }
        return maxP;
    }
};

LeetCode 151. Reverse Words in a String

Oct 10, 2016

题目描述:

Given an input string, reverse the string word by word.

For example, Given s = “the sky is blue”, return “blue is sky the”.

Clarification:

  • What constitutes a word? A sequence of non-space characters constitutes a word.
  • Could the input string contain leading or trailing spaces? Yes. However, your reversed string should not contain leading or trailing spaces.
  • How about multiple spaces between two words? Reduce them to a single space in the reversed string.

翻转一个字符串中的单词, 先翻转整个字符串然后再把每一个单词都翻转一次即可. 但是要考虑输入字符串前后的空格和单词间多余空格.

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:
    void reverseWords(string &s) {
        trimString(s);
        reverse(s.begin(), s.end());
        for(int i = 0; i < s.size(); i++){
            int j;
            for(j = i + 1; j < s.size() && s[j] != ' '; j++);
            reverse(s.begin() + i, s.begin() + j);
            if(j == s.size()){
                break;
            }
            else{
                while(j + 1 < s.size() && s[j + 1] == ' ') s.erase(j + 1, 1);
                i = j;
            }
        }
    }
    
    void trimString(string &s){
        while(s.front() == ' ') s.erase(s.begin());
        while(s.back() == ' ') s.pop_back();
    }
};

LeetCode 417. Pacific Atlantic Water Flow

Oct 10, 2016

题目描述:

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

  1. The order of returned grid coordinates does not matter.
  2. Both m and n are less than 150.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

比较直接的搜索题, 用BFS或者DFS分别找出所有与Pacific连接的位置和与Atlantic连接的位置, 然后求它们的交集.

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
56
57
58
59
60
61
62
class Solution {
    int col, row;
public:
    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
        vector<pair<int, int>> ans;
        if(matrix.empty()) return ans;
        if(matrix[0].empty()) return ans;
        row = matrix.size(), col = matrix[0].size();
        vector<vector<int>> pacificVisited(row, vector<int>(col, 0)), atlanticVisited(row, vector<int>(col, 0));
        unordered_set<long long> pacific, atlantic;
        for(int i = 0; i < col; i++){
            BFS(matrix, 0, i, pacificVisited, pacific);
            BFS(matrix, row - 1, i, atlanticVisited, atlantic);
        }
        for(int i = 0; i < row; i++){
            BFS(matrix, i, 0, pacificVisited, pacific);
            BFS(matrix, i, col - 1, atlanticVisited, atlantic);
        }

        for(auto i : pacific){
            if(atlantic.count(i))
                ans.push_back(pair<int, int>(i >> 32, i & -1));
        }
        return ans;
    }
    
    void BFS(vector<vector<int>>& matrix, int x, int y, vector<vector<int>> &visited, unordered_set<long long> &ocean){
        if(visited[x][y]) return;
        queue<pair<int, int>> q;
        q.push(pair<int, int>(x, y));
        ocean.insert((long long)x << 32 | (long long)y);
        visited[x][y] = 1;
        while(!q.empty()){
            pair<int, int> p = q.front();
            if(p.first > 0 && !visited[p.first - 1][p.second] && matrix[p.first][p.second] <= matrix[p.first - 1][p.second]){
                visited[p.first - 1][p.second] = 1;
                pair<int, int> nextP = pair<int, int>(p.first - 1, p.second);
                ocean.insert((long long)nextP.first << 32 | (long long)nextP.second);
                q.push(nextP);
            }
            if(p.first < row - 1 && !visited[p.first + 1][p.second] && matrix[p.first][p.second] <= matrix[p.first + 1][p.second]){
                visited[p.first + 1][p.second] = 1;
                pair<int, int> nextP = pair<int, int>(p.first + 1, p.second);
                ocean.insert((long long)nextP.first << 32 | (long long)nextP.second);
                q.push(nextP);
            }
            if(p.second > 0 && !visited[p.first][p.second - 1] && matrix[p.first][p.second] <= matrix[p.first][p.second - 1]){
                visited[p.first][p.second - 1] = 1;
                pair<int, int> nextP = pair<int, int>(p.first, p.second - 1);
                ocean.insert((long long)nextP.first << 32 | (long long)nextP.second);
                q.push(nextP);
            }
            if(p.second < col - 1 && !visited[p.first][p.second + 1] && matrix[p.first][p.second] <= matrix[p.first][p.second + 1]){
                visited[p.first][p.second + 1] = 1;
                pair<int, int> nextP = pair<int, int>(p.first, p.second + 1);
                ocean.insert((long long)nextP.first << 32 | (long long)nextP.second);
                q.push(nextP);
            }
            q.pop();
        }
    }
};

LeetCode 416. Partition Equal Subset Sum

Oct 9, 2016

题目描述:

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note: Both the array size and each of the array element will not exceed 100.

Example 1:

1
2
3
4
5
6
Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

1
2
3
4
5
Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

动态规划问题, 比较容易看出如果用dp[i][j]表示前i+1个数字能否找出和为j的子集的话, dp[i][j]=dp[i-1][j] || dp[i-1][j-nums[i]]. 但是用二维数组来进行dp的话, 数组的列数是不知道的, 我一开始用hash表来存储行, 但是运行速度很慢, 后来注意到总的元素数目最多只有100个, 每个最多只有100, 而我们要找的目标是和的一半, 也就是最多5000, 完全可以把数组的列数设置为和的一半, 然后从下往上dp.

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
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int i = 0; i < nums.size(); i++){
            sum += nums[i];
        }
        if(sum % 2) return false;
        
        sum /= 2;
        vector<int> dp(sum + 1), tmpDp(sum + 1);
        dp[0] = 1;
        dp[nums[0]] = 1;
        
        for(int i = 1; i < nums.size(); i++){
            tmpDp = dp;
            for(int j = 0; j < dp.size(); j++){
                if(tmpDp[j] == 0) continue;
                int t = j + nums[i];
                if(t == sum) return true;
                if(t < sum) dp[t] = 1;
            }
        }
        return false;
    }
};