Showing posts with label array. Show all posts
Showing posts with label array. Show all posts

Thursday, November 27, 2014

[LeetCode] First Missing Positive

Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.

思路：

无序数组的题目如果要O(n)解法往往要用到hash table，但这题要求constant space。所以可以用数组本身作为一个"hash table"：A[0] = 1, A[1] = 2, .... A[n-1] = n。目标是尽可能将数字i放到数组第i-1个位置。

扫描数组中每个数：
1. 如果A[i]<1或者A[i]>n。说明A[i]一定不是first missing positive。跳过
2. 如果A[i] = i+1，说明A[i]已经在正确的位置，跳过
3. 如果A[i]!=i+1，且0<A[i]<=n，应当将A[i]放到A[A[i]-1]的位置，所以可以交换两数。
这里注意，当A[i] = A[A[i]-1]时会陷入死循环。这种情况下直接跳过。



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        int i=0;
        while(i<n) {
            if(A[i]!=i+1 && A[i]>0 && A[i]<=n && A[i]!=A[A[i]-1])
                swap(A[i],A[A[i]-1]);
            else
                i++;
        }
        for(int i=0; i<n; i++) {
            if(A[i]!=i+1) return i+1;
        }
        return n+1;
    }
};
Posted by at 2 comments:
Labels: , ,

Wednesday, November 26, 2014

[LeetCode] Merge Intervals

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

思路：

从Insert Interval那题的解法，我们知道了如何判断两个interval是否重合，如果不重合，如何判断先后顺序。那么这题就很简单了，首先按照start的大小来给所有interval排序，start小的在前。然后扫描逐个插入结果。如果发现当前interval a和结果中最后一个插入的interval b不重合，则插入a到b的后面；反之如果重合，则将a合并到b中。注意要给object排序需要定义一个compare structure作为sort函数的额外参数。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    struct compInterval {
        bool operator()(const Interval &a, const Interval &b) const {
            return a.start<b.start;
        }
    };

    vector<Interval> merge(vector<Interval> &intervals) {
        sort(intervals.begin(),intervals.end(),compInterval());
        vector<Interval> ret;
        for(int i=0; i<intervals.size(); i++) {
            if(ret.empty() || ret.back().end < intervals[i].start)  // no overlap
                ret.push_back(intervals[i]);
            else   // overlap
                ret.back().end = max(ret.back().end, intervals[i].end);
        }
        return ret;
    }
};
Posted by at No comments:
Labels: , , ,

[LeetCode] Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

思路：

题目涉及两个问题：
1. 如何判断两个interval有重合。
2. 如果重合，如何合并。
3. 如何判断[s1, e1]是否在[s2, e2]前面

A1. 两个interval有重合有很多种可能性，但判断它们不重合则比较简单直观。无非两种情况：

(1) [s1, e1]  [s2, e2]：即s2>e1 
(2) [s2, e2]  [s1, e1]：即s1>e2

不重合的条件为：s2>e1 || s1>e2，反之则重合。

A2. 对于两个有重合的interval： [s1, e1]，[s2, e2]。合并后变为[min(s1,s2), max(e1,e2)]。

A3. [s1, e1]在[s2, e2]前面的条件：e1<s2

所以插入interval a的算法为：扫描队列中每个interval I[i]：
如果a已经被插入了，则只要插入I(i)就行。
如果a在I(i)前，则先插入a再插入I(i)到结果。
如果a和I(i)有重合，则将I(i)合并入a，但并不插入结果。
如果a在I(i)后，则插入I(i)到结果。


 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:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> ret;
        bool isInsert = false;
        for(int i=0; i<intervals.size(); i++) {
            // already insert newInterval
            if(isInsert) {  
                ret.push_back(intervals[i]);
                continue;
            }
            
            // insert newInterval before current interval
            if(newInterval.end < intervals[i].start) {  
                ret.push_back(newInterval);
                ret.push_back(intervals[i]);
                isInsert = true;
                continue;
            }
            
            // combine newInterval with current interval
            if(newInterval.start<=intervals[i].end && intervals[i].start<=newInterval.end) {
                newInterval.start = min(newInterval.start, intervals[i].start);
                newInterval.end = max(newInterval.end, intervals[i].end);
                continue;
            }
            
            // newInterval after current interval
            ret.push_back(intervals[i]);
        }
        
        if(!isInsert) ret.push_back(newInterval);
        return ret;
    }
};
Posted by at 2 comments:
Labels: , ,

[LeetCode] Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10.

思路1：Brute Force

对每个bar i，求它能构成的最大面积。用左右指针向两边扫，直到遇到比bar i矮的或遇到边界则停止，然后根据左右指针距离得到宽度和面积。但是这个解法过不了大集合，因为最坏情况：当整个histogram是递增或递减时，算法复杂度是O(n^2)。



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int maxArea = 0;
        for(int i=0; i<height.size(); i++) 
            maxArea = max(maxArea, calRecArea(height,i));
        return maxArea;
    }
    
    int calRecArea(vector<int> &height, int index) {
        int left = index-1, right = index+1;
        while(left>=0 && height[left]>=height[index]) 
            left--;
        while(right<height.size() && height[right]>=height[index])
            right++;
            
        return (right-left-1)*height[index];
    }
};


思路2：Stack

仔细考察Brute Force算法，发现问题在于指针重复扫描。以递增序列为例：

0 1 2 3 4 5 6

在计算s[0]的时候扫描了右边6个数，计算s[1]时继续扫描右边5个数，依次类推。而没能利用到这个序列的递增性质。当序列从i递增到j时，bar i~j的面积一定都能扩展到j。而一旦在j+1递减了，那么表示bar i~j中的部分bar k无法继续扩展，条件是h[k]>h[j+1]。

1. 利用这个性质，可以将递增序列cache在一个stack中，一旦遇到递减，则根据h[j+1]来依次从stack里pop出那些无法继续扩展的bar k，并计算面积。

2. 由于面积的计算需要同时知道高度和宽度，所以在stack中存储的是序列的坐标而不是高度。因为知道坐标后很容易就能知道高度，而反之则不行。



 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 largestRectangleArea(vector<int> &height) {
        if(height.empty()) return 0;
        height.push_back(-1);
        height.insert(height.begin(),-1);
        stack<int> s;
        int maxArea = 0;
        
        for(int i=0; i<height.size(); i++) {
            while(!s.empty() && height[i]<=height[s.top()]) {
                int h = height[s.top()];
                s.pop();
                if(height[i]<h) maxArea = max(maxArea, (i-s.top()-1)*h);
            }
            s.push(i);
        }
        
        // reset height
        height.erase(height.begin());
        height.pop_back();
        return maxArea;
    }
};
Posted by at 1 comment:
Labels: , , , ,

Tuesday, November 25, 2014

[LeetCode] Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.

思路：

既然要O(n)算法，排序显然不行，所以自然想到用hash table。将序列中的所有数存到一个unordered_set中。对于序列里任意一个数A[i]，我们可以通过set马上能知道A[i]+1和A[i]-1是否也在序列中。如果在，继续找A[i]+2和A[i]-2，以此类推，直到将整个连续序列找到。为了避免在扫描到A[i]-1时再次重复搜索该序列，在从每次搜索的同时将搜索到的数从set中删除。直到set中为空时，所有连续序列搜索结束。

复杂度：由于每个数字只被插入set一次，并删除一次，所以算法是O(n)的。


 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
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        if(num.empty()) return 0;
        unordered_set<int> ht;
        for(int i=0; i<num.size(); i++)
            ht.insert(num[i]);
            
        int maxLen = 1;
        for(int i=0; i<num.size(); i++) {
            if(ht.empty()) break;
            int curLen = 0;
            int curNum = num[i];
            
            while(ht.count(curNum)) {
                ht.erase(curNum);
                curLen++;
                curNum++;
            }
            
            curNum = num[i]-1;
            while(ht.count(curNum)) {
                ht.erase(curNum);
                curLen++;
                curNum--;
            }
            
            maxLen = max(maxLen, curLen);
        }
        
        return maxLen;
    }
};
Posted by at 5 comments:
Labels: , , ,

[LeetCode] Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

思路：

遇到这类概念比较抽象的题目，写几个例子通常会帮助理解问题的规律：

7 2 5 2 3 1
7 2 5 3 1 2
7 2 5 3 2 1
7 3 1 2 2 5

其中红色的数字表示next permutation改变原数字的最高位。比如对于725321来说，由于5321由于从最低位到最高位是升序排列，已经达到该四位数字permutation的最大值。这时不得不改变第5位的2来增加数值。如何改变？为了使增量最小，在前4位中比第5位大的数(5, 3)中找一个最小的数，即数字3。用3替换2，而剩下5, 2, 2, 1四个数字要组成最低4位。由于第5位已经从2增加到3，同样为了使增量最小，我们希望剩下的4位数尽可能小。所以将他们从低到高位降序排列即可。总结上面的思考：

1. 从低位向高位（从右向左）找第一个递减的数：s[i]<s[i+1]。如果不存在，则表明该permutation已经最大，next permutation为当前序列的逆序。
2. 在s[i+1:n-1]中找一个j，使s[j]>s[i]>=s[j+1]，swap(s[i], s[j])
3. 将s[i+1:n-1]排序，从低位到高位单调递减。



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if(num.size()<2) return;
        int n = num.size(), j = n-2;
        while(j>=0 && num[j]>=num[j+1]) j--;
        
        if(j<0) {
            sort(num.begin(),num.end());
            return;
        } 
        
        int i=j+1;
        while(i<n && num[i]>num[j]) i++;
        i--;
        
        swap(num[i],num[j]);
        sort(num.begin()+j+1, num.end());
    }
};
Posted by at 5 comments:
Labels: , ,

Monday, November 24, 2014

[LeetCode] Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X



思路：

这题题意也略显含糊，实际上就是要将所有以O组成、但不连通到网格边缘的区域变为X。所以我们可以先在四边上寻找连通到边缘的区域，将它们的O都变成Y。剩余的所有O一定无法连通到边缘，所以可以全部变为X。最后再将所有Y变回O。

这题的测试比较tricky，上来没多想就用递归的DFS实现flood fill，结果发现run time error，栈溢出了：


 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 Solution {
public:
    void solve(vector<vector<char>> &board) {
        if(board.size()<3 || board[0].size()<3) return;
        fillBorders(board, 'O', 'Y');
        replace(board, 'O', 'X');
        fillBorders(board, 'Y', 'O');
    }
    
    void fill(vector<vector<char>> &board, int i, int j, char target, char c) {
        int m = board.size(), n = board[0].size();
        if(i<0 || j<0 || i>=m || j>=n || board[i][j]!=target) return;
        board[i][j] = c;
        fill(board, i-1, j, target, c);
        fill(board, i+1, j, target, c);
        fill(board, i, j-1, target, c);
        fill(board, i, j+1, target, c);
    }
    
    void fillBorders(vector<vector<char>> &board, char target, char c) {
        int m = board.size(), n = board[0].size();
        for(int i=0; i<m; i++) {
            if(board[i][0]==target) fill(board, i, 0, target, c);
            if(board[i][n-1]==target) fill(board, i, n-1, target, c);
        }
        
        for(int j=1; j<n-1; j++) {
            if(board[0][j]==target) fill(board, 0, j, target, c);
            if(board[m-1][j]==target) fill(board, m-1, j, target, c);
        }
    }
    
    
    void replace(vector<vector<char>> &board, char target, char c) {
        int m = board.size(), n = board[0].size();
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(board[i][j]==target)
                    board[i][j] = c;
            }
        }
    }
};


于是些了个迭代版的DFS，果然过了大数据测试。当然这里也可以用BFS实现flood fill。

 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
class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if(board.size()<3 || board[0].size()<3) return;
        fillBorders(board, 'O', 'Y');
        replace(board, 'O', 'X');
        fillBorders(board, 'Y', 'O');
    }
    
    void fill(vector<vector<char>> &board, int i, int j, char target, char c) {
        int m = board.size(), n = board[0].size();
        if(i<0 || j<0 || i>=m || j>=n || board[i][j]!=target) return;
        stack<pair<int,int>> s;
        s.push(make_pair(i,j));
        
        while(!s.empty()) {
            i = s.top().first;
            j = s.top().second;
            s.pop();
            board[i][j] = c;
            if(i>0 && board[i-1][j]==target) s.push(make_pair(i-1,j));
            if(i<m-1 && board[i+1][j]==target) s.push(make_pair(i+1,j));
            if(j>0 && board[i][j-1]==target) s.push(make_pair(i,j-1));
            if(j<n-1 && board[i][j+1]==target) s.push(make_pair(i,j+1));
        }
    }
    
    void fillBorders(vector<vector<char>> &board, char target, char c) {
        int m = board.size(), n = board[0].size();
        for(int i=0; i<m; i++) {
            if(board[i][0]==target) fill(board, i, 0, target, c);
            if(board[i][n-1]==target) fill(board, i, n-1, target, c);
        }
        
        for(int j=1; j<n-1; j++) {
            if(board[0][j]==target) fill(board, 0, j, target, c);
            if(board[m-1][j]==target) fill(board, m-1, j, target, c);
        }
    }
    
    
    void replace(vector<vector<char>> &board, char target, char c) {
        int m = board.size(), n = board[0].size();
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(board[i][j]==target)
                    board[i][j] = c;
            }
        }
    }
};



Posted by at 6 comments:
Labels: , , , ,

[LeetCode] Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

思路：

这题题意不是很清楚。很容易让人觉得置0是“连锁反应”，造成最后每个元素都为0。而实际题目的意思是，只有在原始矩阵中为0的数字才能将相应行列置0。而原本非0的数字，即使由于同行或同列的0元素而被置0了，也不能将它相关的行列置0。即这种置0的操作没有传递性，

1. O(mn)解法：克隆原来的matrix，然后扫描原来的matrix，遇到0，则在克隆版本中将对应的行列置0。
2. O(m+n)解法：用两个bool数组O(n)和O(m)，分别记录每行和每列的是否需要被置0。最后根据这两个数组来置0整个矩阵。
3. O(1)解法：用第0行和第0列来记录第1 ~ m-1行和第1 ~ n-1列是否需要置0。而用两个变量记录第0行和第0列是否需要置0。

O(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
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
class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        if(matrix.empty() || matrix[0].empty()) return;
        int m = matrix.size(), n = matrix[0].size();
        
        // find if the 1st row/col needs to be set as zero
        bool isFirstRowZero = false;
        bool isFirstColZero = false;
        for(int j=0; j<n; j++) {
            if(matrix[0][j]==0) {
                isFirstRowZero = true;
                break;
            }
        }
        for(int i=0; i<m; i++) {
            if(matrix[i][0]==0) {
                isFirstColZero = true;
                break;
            }
        }
        
        // use 1st row/col to record whether to set each col/row as zero
        for(int i=1; i<m; i++) {
            for(int j=1; j<n; j++) {
                if(matrix[i][j]==0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        
        // set rows & cols
        for(int i=1; i<m; i++) {
            if(matrix[i][0]==0) setRowCol(matrix, i, true);
        }
        for(int j=1; j<n; j++) {
            if(matrix[0][j]==0) setRowCol(matrix, j, false);
        }
        
        // set first row & col
        if(isFirstRowZero) setRowCol(matrix, 0, true);
        if(isFirstColZero) setRowCol(matrix, 0, false);
    }
    
    void setRowCol(vector<vector<int>> &matrix, int index, bool isSetRow) {
        if(matrix.empty() || matrix[0].empty() || index<0) return;
        int m = matrix.size(), n = matrix[0].size();
        if((isSetRow && index>=m) || (!isSetRow && index>=n)) return;
        
        if(isSetRow) {
            for(int j=0; j<n; j++)
                matrix[index][j] = 0;
        }
        else {
            for(int i=0; i<m; i++)
                matrix[i][index] = 0;
        }
    }
};
Posted by at 6 comments:
Labels: ,

[LeetCode] Unique Paths I, II

Unique Paths I

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.


Unique Paths II

Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
The total number of unique paths is 2.
Note: m and n will be at most 100.

思路：Unique Paths I

Climbing Stairs二维版。计算解个数的题多半是用DP。而这两题状态也非常显然，dp[i][j]表示从起点到位置(i, j)的路径总数。DP题目定义好状态后，接下去有两个任务：找通项公式，以及确定计算的方向。

1. 由于只能向右和左走，所以对于(i, j)来说，只能从左边或上边的格子走下来：
dp[i][j] = dp[i-1][j] + dp[i][j-1]

2. 对于网格最上边和最左边，则只能从起点出发直线走到，dp[0][j] = dp[i][0] = 1

3. 计算方向从上到下，从左到右即可。可以用滚动数组实现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m<1 || n<1) return 0;
        vector<int> dp(n, 1);
        for(int i=1; i<m; i++) {
            for(int j=1; j<n; j++) {
                dp[j] += dp[j-1];
            }
        }
        return dp[n-1];
    }
};


思路：Unique Paths II

与I有两点不同：

1. 当(i, j)有障碍时dp[i][j] = 0
2. dp[0][j]和dp[i][0]未必为1.
dp[0][j] = obstacleGrid[0][j] ? 0 : dp[0][j-1]
dp[i][0] = obstacleGrid[i][0] ? 0 : dp[i-1][0]
3. 当obstacleGrid [0][0] = 1时，return 0


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        if(obstacleGrid.empty() || obstacleGrid[0].empty() || obstacleGrid[0][0]==1) return 0;
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<int> dp(n,1);
        for(int j=1; j<n; j++) {
            if(obstacleGrid[0][j]==1)
                dp[j] = 0;
            else
                dp[j] = dp[j-1];
        }
        
        for(int i=1; i<m; i++) {
            dp[0] = obstacleGrid[i][0]==1 ? 0 : dp[0];
            for(int j=1; j<n; j++) {
                dp[j] = obstacleGrid[i][j]==1 ? 0 : dp[j-1] + dp[j];
            }
        }
        return dp[n-1];
    }
};
Posted by at 2 comments:
Labels: , , ,

[LeetCode] Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

思路：

这题用到了一点DP的思路，即存储每一层的结果，来计算下一层。关键点在于要用O(n) space。用两个数组prePath和curPath分别存储上一层和本层的每个坐标的min path sum。如果已知prePath，则可以计算curPath：

1. 对第j层 (j = 0 ~ n-1)，一共有j+1个数：0:j。而上一层有j个数：0:j-1
2. 除去头尾两个数外，curPath[i] = min(prePath[i-1], prePath[i]) + triangle[j][i]
3. 头尾的特殊情况：curPath[0] = prePath[0] + triangle[j][0]；curPath[j] = prePath[j-1] + triangle[j][j]
4. 在计算下一层前，需要交换curPath和prePath。
5. 在最后一层curPath计算结束后，在其中找一个最小值即为整个树的min path sum。

额外存储空间是2n。尽管通过滚动数组也可以事先n，但代码要复杂很多，面试短时间内容易出错。


 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 minimumTotal(vector<vector<int> > &triangle) {
        if(triangle.empty()) return 0;
        int n = triangle.size();
        vector<int> curPath(n,INT_MAX);
        vector<int> prePath(n,INT_MAX);
        curPath[0] = triangle[0][0];
        
        for(int lvl=1; lvl<n; lvl++) {
            prePath = curPath;
            curPath[0] = prePath[0] + triangle[lvl][0];
            curPath[lvl] = prePath[lvl-1] + triangle[lvl][lvl];
            for(int i=1; i<lvl; i++)
                curPath[i] = min(prePath[i-1], prePath[i]) + triangle[lvl][i];
        }
        
        int minPath = INT_MAX;
        for(int i=0; i<n; i++) 
            minPath = min(minPath, curPath[i]);
        
        return minPath;
    }
};
Posted by at 1 comment:
Labels: , ,

[LeetCode] Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.

思路：

这题要想清楚不容易，尽管想清楚后代码写起来很简单。

I.  显然当gas[i]<cost[i]时，i不能作为起点。

II. 当对所有加油站求和：sum(gas[i] - cost[i]) <0时，无法环绕一圈。反之，则一定能环绕一圈。

问题是如果可以环绕一圈，如何找起点？

性质1. 对于任意一个加油站i，假如从i出发可以环绕一圈，则i一定可以到达任何一个加油站。显而易见。

性质2. 如果这样的i是唯一的，则必然不存在j!=i， 从j出发可以到达i。

反证法：如果存在这样的j，则必然存在j->i->i的路径，而这个路径会覆盖j->j一周的路径。那么j也将是一个符合条件的起点。与唯一解的限制条件矛盾。

性质3. 假如i是最后的解，则由1可知，从0 ~ i-1出发无法达到i。而从i出发可以到达i+1 ~ n-1。

结合以上三条性质，得出解决的思路：

0. 如果对所有加油站的sum(gas[i] - cost[i])<0，则无解。否则进入1。

1. 从0开始计算sum(gas[i] - cost[i])，当遇到i1使sum<0时，说明从0出发无法到达i1。根据性质1，0不是起始点。而由于从0出发已经到达了1 ~ i1-1。根据性质2，1 ~ i1-1一定不是正确的起始点。此时i1为起始点的候选。

2. 将sum清0，并从i1出发，假如又遇到i2使sum(gas[i] - cost[i]) < 0 时，说明i1出发无法绕一圈，更具性质1，排除i1。又因为i1+1 ~ i2-1都能从i1出发到达,。根据性质2，它们也必然不是起始点。此时i2为起始点的候选。

3. 以此类推，直到遇到ik，使从ik出发可以到达ik+1 ~ n-1。

其中步骤0可以合并到1~3的扫描中，一个pass来得到解。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int start = 0, netGasSum = 0, curGasSum = 0;
        for(int i=0; i<cost.size(); i++) {
            netGasSum += gas[i] - cost[i];
            curGasSum += gas[i] - cost[i];
            if(curGasSum<0) {
                start = i+1;
                curGasSum = 0;
            }
        } 
        if(netGasSum < 0) return -1;
        return start;
    }
};
Posted by at 7 comments:
Labels: , , ,
Subscribe to: Posts (Atom)