LeetCode 419. Battleships in a Board

题目描述:

Given an 2D board, count how many different battleships are in it. The battleships are represented with 'X's, empty slots are represented with '.'s. You may assume the following rules:

  • You receive a valid board, made of only battleships or empty slots.
  • Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) orNx1 (N rows, 1 column), where N can be of any size.
  • At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.

Example:

1
2
3
4
X..X
...X
...X

In the above board there are 2 battleships.

Invalid Example:

1
2
3
4
...X
XXXX
...X

This is an invalid board that you will not receive - as battleships will always have a cell separating between them.

Follow up: Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?

这道题题目中举的invalid的例子是不会作为输入数据的, 所以不需要对它进行判断. 最直接的方法就是遍历数组, 然后~~找舰娘(雾)/老婆(大雾)~~在遇到一个X的时候计数器加1, 并把与它相邻接的所有X清除以防止重复计算.

但是Follow up中是要求不修改原数组的. 对于横向的战舰只要直接跳过就可以了, 因为一般都是按行=>列的方式来遍历. 而对于纵向的战舰, 则要判断它上方是否有X, 如果有的话说明这艘战舰已经计算过了, 不应该重复计算.

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 countBattleships(vector<vector<char>>& board) {
int ans = 0;
int row = board.size();
if(board.empty()) return ans;
int col = board[0].size();
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(board[i][j] == 'X'){
if(i > 0 && board[i - 1][j] == 'X'){
continue;
}
ans++;
if(j < col - 1 && board[i][j + 1] == 'X'){
for(; j < col && board[i][j] == 'X'; j++) board[i][j] = '.';
j--;
}
}
}
}
return ans;
}
};

LeetCode 436. Find Right Interval

题目描述:

Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the “right” of i.

For any interval i, you need to store the minimum interval j’s index, which means that the interval j has the minimum start point to build the “right” relationship for interval i. If the interval j doesn’t exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Note:

  1. You may assume the interval’s end point is always bigger than its start point.
  2. You may assume none of these intervals have the same start point.

Example 1:

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

Output: [-1]

Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

1
2
3
4
5
6
7
8
Input: [ [3,4], [2,3], [1,2] ]

Output: [-1, 0, 1]

Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.

Example 3:

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

Output: [-1, 2, -1]

Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.

使用排序+二分搜索. 要注意记录排序之前每个interval的下标.

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
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<int> findRightInterval(vector<Interval>& intervals) {
vector<pair<int, int>> maps(intervals.size());
for(int i = 0; i < intervals.size(); i++){
maps[i].first = intervals[i].start;
maps[i].second = i;
}

sort(maps.begin(), maps.end(), [&](pair<int, int> &a, pair<int, int> &b){
return a.first < b.first;
});

vector<int> ans(intervals.size());
for(int i = 0; i < intervals.size(); i++){
int target = intervals[i].end;
ans[i] = binSearch(maps, 0, target);
}
return ans;
}

int binSearch(vector<pair<int, int>> &m, int begin, int target){
int left = begin, right = m.size(), mid = (left + right) / 2;
while(left < right){
if(m[mid].first == target){
return m[mid].second;
}
else if(m[mid].first < target){
left = mid + 1;
}
else{
right = mid;
}
mid = (left + right) / 2;
}
return -1;
}
};

或者可以使用hash表.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<int> findRightInterval(vector<Interval>& intervals) {
unordered_map<int, int> maps;
for(int i = 0; i < intervals.size(); i++){
maps[intervals[i].start] = i;
}
vector<int> ans(intervals.size());
for(int i = 0; i < intervals.size(); i++){
ans[i] = maps.count(intervals[i].end) ? maps[intervals[i].end] : -1;
}
return ans;
}
};

LeetCode 435. Non-overlapping Intervals

题目描述:

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

  1. You may assume the interval’s end point is always bigger than its start point.
  2. Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

Example 1:

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

Output: 1

Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

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

Output: 2

Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

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

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

先对区间按照左端点值, 右端点值的优先级从小到大排序, 然后从前到后依次处理. 对于前后两个区间a和b(它们并不一定相邻)来说, 有两种可能的情况:

  1. 两个区间没有重叠. 这样的话b之后的区间也不可能与a有重叠, 不需要做处理.
  2. 两个区间有重叠. 这又分两种情况: 1. a完全"盖住"了b; 2. a没有完全"盖住"b. 对于前者, 应该移除的是a区间, 因为a比b要"大", 之后的区间如果与b有重叠则一定与a有重叠, 但是与a有重叠不一定与b有重叠. 对于后者, 应该移除区间b, 因为与a有重叠则必然与b有重叠, 但是与b有重叠不一定与a有重叠.

a应该始终保存上一个没有被移除的区间.

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
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
int eraseOverlapIntervals(vector<Interval>& intervals) {
int ans = 0;
if(intervals.empty()) return 0;
sort(intervals.begin(), intervals.end(), [&](Interval &a, Interval &b){
if(a.start == b.start){
return a.end < b.end;
}
return a.start < b.start;
});
int p = 0;
for(int i = 1; i < intervals.size(); i++){
if(overlap(intervals[p], intervals[i])){
if(intervals[i].end < intervals[p].end){
p = i;
}
ans++;
}
else{
p = i;
}
}
return ans;
}

bool overlap(Interval &a, Interval &b){
return !(a.start >= b.end || a.end <= b.start);
}
};

LeetCode 179. Largest Number

题目描述:

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

这是一个排序问题, 只要能判断两个数的先后顺序, 那就可以通过比较排序得到最后的有序序列. 对于两个int数据a, b, 把它们以abba两种形式存储在long long中, 就可以通过直接的比较大小来判断顺序.

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
class Solution {
public:
string largestNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), [=](int a, int b){
long long ab = func(a, b), ba = func(b, a);
return ab > ba;
});
string re;
for(int i = 0; i < nums.size(); i++){
re += to_string(nums[i]);
}
auto iter = re.begin();
for(; iter != re.end() && (*iter) == '0'; iter++);
if(iter == re.end()) return string("0");
else return string(iter, re.end());
}

long long func(int a, int b){
if(b == 0) return a * 10;
long long re = a;
int t = b;
while(t > 0) {
re *= 10;
t /= 10;
}
return re + b;
}
};

LeetCode 174. Dungeon Game

题目描述:

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

img

Notes:

  • The knight’s health has no upper bound.
  • Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

使用二分搜索+DP. 单纯的二维DP是不行的, 因为这道题要求从起点到终点的路径中每个格子的值都不能小于1. 有可能出现终点时生命值大于0但是每一条路径实际上都无法抵达.

但是我们可以使用DP来判断一个特定初始生命值的knight能否救到princess. 然后在外层使用二分搜索来找到最小的初始生命值. 虽然可以用0~INT_MAX作为搜索范围, 但是先找出初始生命值为0时每一条路径中出现的最小的生命值可以大大缩小这个范围, 实际上如果初始生命值为0时, 所有的格子中生命值都是大于1的, 可以直接返回1; 否则搜索范围的最大值就是最小生命值的绝对值加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
60
61
62
63
64
65
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
if (dungeon.empty()) return 0;
if (dungeon[0].empty()) return 0;
int tmp = minInPath(dungeon);
if(tmp > 0) return 1;
int left = 0, right = -tmp + 1, mid = (right + left) / 2;
while (left < right) {
int h = canArrive(dungeon, mid);
if(h == 1){
break;
}
else if (h < 1) {
left = mid + 1;
}
else {
right = mid;
}
mid = (right + left) / 2;
}
return mid ? mid : 1;
}

int canArrive(vector<vector<int>>& dungeon, int target) {
int row = dungeon.size(), col = dungeon[0].size();
vector<vector<int>> dp(row, vector<int>(col, 0));
dp[0][0] = target + dungeon[0][0];
for (int i = 1; i < col; i++) {
if (dp[0][i - 1] > 0) dp[0][i] = dp[0][i - 1] + dungeon[0][i];
}
for (int i = 1; i < row; i++) {
if (dp[i - 1][0] > 0) dp[i][0] = dp[i - 1][0] + dungeon[i][0];
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if(dp[i - 1][j] > 0 || dp[i][j - 1] > 0)
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + dungeon[i][j];
}
}
return dp[row - 1][col - 1];
}

int minInPath(vector<vector<int>>& dungeon){
int row = dungeon.size(), col = dungeon[0].size(), minInPath = INT_MAX;
vector<vector<int>> dp(row, vector<int>(col, 0));
dp[0][0] = dungeon[0][0];
minInPath = min(minInPath, dp[0][0]);
for (int i = 1; i < col; i++) {
dp[0][i] = dp[0][i - 1] + dungeon[0][i];
minInPath = min(minInPath, dp[0][i]);
}
for (int i = 1; i < row; i++) {
dp[i][0] = dp[i - 1][0] + dungeon[i][0];
minInPath = min(minInPath, dp[i][0]);
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + dungeon[i][j];
minInPath = min(minInPath, dp[i][j]);
}
}
return minInPath;
}
};

LeetCode 173. Binary Search Tree Iterator

题目描述:

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

**Note: **next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

二叉树的非递归中序遍历, 只不过不是放在循环中, 而是通过next来触发每一步的进行.

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
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
TreeNode *BST, *curNode;
vector<TreeNode*> path;
public:
BSTIterator(TreeNode *root) {
BST = root;
mostLeft(root);
curNode = nullptr;
}

TreeNode* mostLeft(TreeNode *root){
TreeNode *node = root;
while(node) {
path.push_back(node);
node = node->left;
}
return node;
}

/** @return whether we have a next smallest number */
bool hasNext() {
if(path.empty() && !curNode) return false;
else return true;
}

/** @return the next smallest number */
int next() {
//curNode = path.back();
int ans;
if(!curNode){
ans = path.back()->val;
curNode = path.back()->right;
path.pop_back();
}
else{
mostLeft(curNode);
ans = path.back()->val;
curNode = path.back()->right;
path.pop_back();
}
//cout<<ans<<endl;
return ans;
}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/

LeetCode 441. Arranging Coins

题目描述:

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

1
2
3
4
5
6
7
8
9
n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2:

1
2
3
4
5
6
7
8
9
n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

等差数列的问题, 前m行共有 $$ \frac{m(m+1)}{2} $$ 个硬币, 共有n个硬币, 那么应该找出最大的m满足 $$ \frac{m(m+1)}{2} \le n \rightarrow m^2+m-2n \le 0 $$ 因为m是正整数, 所以 $$ m \le \frac{-1+\sqrt{1+8n}}{2} $$

1
2
3
4
5
6
class Solution {
public:
int arrangeCoins(int n) {
return (sqrt((long long)n * 8 + 1) - 1.0) / 2;
}
};

LeetCode 438. Find All Anagrams in a String

题目描述:

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

1
2
3
4
5
6
7
8
9
Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

1
2
3
4
5
6
7
8
9
10
Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

使用哈希表和双指针, 可以在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:
vector<int> findAnagrams(string s, string p) {
vector<int> letters(26, 0);
vector<int> ans;
if(s.empty() || p.empty() || s.length() < p.length()) return ans;
for(auto c : p){
letters[c - 'a']++;
}
int i = 0, j;
vector<int> tmp = letters;
for(j = 0; j < p.length(); j++){
tmp[s[j] - 'a']--;
}
while(j <= s.length()){
bool match = true;
for(auto k : tmp){
if(k != 0){
match = false;
break;
}
}
if(match) ans.push_back(i);
if(j == s.length()) break;
tmp[s[i] - 'a']++;
tmp[s[j] - 'a']--;
i++;
j++;
}

return ans;
}
};

LeetCode 414. Third Maximum Number

题目描述:

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

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

Output: 1

Explanation: The third maximum is 1.

Example 2:

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

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

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

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

只要求保存前三个最大的数(不重复), 所以可以在遍历过程中维护已经遍历过的元素中最大的三个值. 由于有可能不重复的数值不足三个, 所以还要记录已经保存的最大元素的个数.

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
class Solution {
public:
int thirdMax(vector<int>& nums) {
int max1, max2, max3;
max1 = max2 = max3 = INT_MIN;
int num = 0;
for(auto i : nums){
if((i == max1 && num > 0) ||
(i == max2 && num > 1) ||
(i == max3 && num > 2))
continue;
if(num == 0 || i > max1){
max3 = max2;
max2 = max1;
max1 = i;
}
else if(num == 1 || i > max2){
max3 = max2;
max2 = i;
}
else if(num == 2 || i > max3){
max3 = i;
}
num = min(num + 1, 3);
}
if(num == 3) return max3;
return max1;
}
};

LeetCode 413. Arithmetic Slices

题目描述:

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1
2
3
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1
1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence: A[P], A[p + 1], …, A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

1
2
3
A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

这道题我首先用双指针找到所有的尽量长的连续等差数列. 对于每个数列, 假设长度为n, 那么它所包含的所有可能长度的等差数列(长度>=3)有$1+2+3+\dots+(n-2)=(n-2)(n-1)/2=(n^2-3n+2)/2$个.

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 numberOfArithmeticSlices(vector<int>& A) {
if(A.size() < 3) return 0;
int p = 0, q = 2;
int ans = 0;
while(q < A.size()) {
if(A[p + 1] - A[p] != A[q] - A[p + 1]) {
p++, q++;
continue;
}
int diff = A[p + 1] - A[p];
while(q + 1 < A.size() && A[q + 1] - A[q] == diff) q++;
int seqLength = q - p + 1;
ans += (seqLength * seqLength - 3 * seqLength + 2) / 2;
p = q;
q = p + 2;
}
return ans;
}
};