bbappyuanyuan
8/13/2018 - 11:56 AM
LeetCode summary
// contained water after rain 2D
// 优先队列，水位慢慢往上涨，低于水位的地方能积水
class Solution {
const int DR[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public:
int trapRainWater(vector<vector<int>>& heightMap) {
int m = heightMap.size();
if (m == 0) return 0;
int n = heightMap[0].size();
priority_queue<tuple<int, int, int>> q;
vector<vector<bool>> v(m, vector<bool>(n, false));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
q.push(make_tuple(-heightMap[i][j], i, j));
v[i][j] = true;
}
int ans = 0;
int level = 0;
while (!q.empty()) {
int h, x, y;
tie(h, x, y) = q.top();
q.pop();
h = -h;
if (level > h)
ans += level - h;
else
level = h;
for (int k = 0, nx, ny; k < 4; ++k) {
nx = x + DR[k][0];
ny = y + DR[k][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !v[nx][ny]) {
q.push(make_tuple(-heightMap[nx][ny], nx, ny));
v[nx][ny] = true;
}
}
}
return ans;
}
};// move to the north, to the west, to the south, to the east... judge if the path crosses itself
// 分相交情况考虑，共三种：4th cross 1st，5th meet 1st，6th cross 1st
class Solution {
public:
bool isSelfCrossing(vector<int>& x) {
int l = x.size();
for (int i = 3; i < l; ++i)
if (x[i - 3] >= x[i - 1] && x[i] >= x[i - 2] || // case 1: 4th cross 1st
i >= 4 && x[i - 3] == x[i - 1] && x[i] + x[i - 4] >= x[i - 2] || // case 2: 5th meet 1st
i >= 5 && x[i - 4] + x[i] >= x[i - 2] && x[i - 5] + x[i - 1] >= x[i - 3] && x[i - 2] >= x[i - 4] && x[i - 3] >= x[i - 1]) // case 3: 6th cross 1st
return true;
return false;
}
};// Given an number array, where exactly 2 elements appear only once, and others appear twice.
// 分组，所有xor以后得到ans1 xor ans2，根据其中一位1分成两组，每组xor结果就是两个答案
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int p = 0;
for (auto a : nums)
p ^= a;
p &= -p;
vector<int> ans{0, 0};
for (auto a : nums)
if (a & p)
ans[0] ^= a;
else
ans[1] ^= a;
return ans;
}
};// maximum gap among sorted array num[] (input is not sorted).
// linear time & space.
// 分成n个桶，分块思想！！！
class Solution {
public:
int maximumGap(vector<int> &num) {
int n = num.size();
if (n < 2) return 0;
int minNum = INT_MAX, maxNum = INT_MIN;
for (int i = 0; i < n; ++i) {
if (num[i] < minNum) minNum = num[i];
if (num[i] > maxNum) maxNum = num[i];
}
if (minNum == maxNum) return 0;
int blockSize = (int)ceil(((double)maxNum - minNum) / (n - 1));
int blockCnt = (maxNum - minNum) / blockSize + 1;
vector<int> minBlock(n, INT_MAX);
vector<int> maxBlock(n, INT_MIN);
for (int i = 0, j; i < n; ++i) {
j = (num[i] - minNum) / blockSize;
if (num[i] < minBlock[j]) minBlock[j] = num[i];
if (num[i] > maxBlock[j]) maxBlock[j] = num[i];
}
int pre = minNum;
int ans = 0;
for (int i = 0; i < blockCnt; ++i)
if (!(minBlock[i] == INT_MAX && maxBlock[i] == INT_MIN)) {
ans = max(ans, minBlock[i] - pre);
pre = maxBlock[i];
}
return ans;
}
};// Recover a BST tree where 2 elements are swapped by mistake.
// constant space
// 顺序遍历树找到两个异常节点。
/**
* 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 {
TreeNode* pre;
TreeNode* p1;
TreeNode* p2;
void go(TreeNode* x) {
if (x->left != NULL) go(x->left);
if (pre != NULL && pre->val > x->val) {
if (p1 == NULL) {
p1 = pre;
p2 = x;
} else
p2 = x;
}
pre = x;
if (x->right != NULL) go(x->right);
}
void swap(int &a, int &b) {
int c = a;
a = b;
b = c;
}
public:
void recoverTree(TreeNode* root) {
pre = p1 = p2 = NULL;
go(root);
swap(p1->val, p2->val);
}
};// Given a collection of numbers that might contain duplicates, return all possible unique permutations.
// 递归枚举，顺序确定第i位的值，与i位后的数进行交换。
// 每轮交换新建set，避免与同一数字交换。
// 如果无重复，可以参考 std::next_permutation(first, last) 函数，源码里面的方法可以从小到大求出排列：从后往前，找出第一个 i 比前一个数 i - 1 大的，然后用后面最小的数（一定是 n - 1）交换 i - 1，然后翻转 [i, n)，即让降序变升序。
class Solution {
int n;
vector<vector<int>> ans;
void dfs(vector<int>& a, int i) {
if (i == n - 1) {
ans.push_back(a);
return;
}
set<int> s;
for (int j = i; j < n; ++j)
if (s.find(a[j]) == s.end()) {
s.insert(a[j]);
swap(a[i], a[j]);
dfs(a, i + 1);
swap(a[i], a[j]);
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
n = nums.size();
dfs(nums, 0);
return ans;
}
};// '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial).
// 动态规划，f[i][j] 表示字符串 s 的前 i 位与字符串 p 的前 j 位的匹配情况。
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
f[0][0] = true;
for (int i = 0; i <= m; ++i)
for (int j = 1; j <= n; ++j)
if (p[j - 1] == '*')
f[i][j] = f[i][j - 1] || (i > 0 && f[i - 1][j]);
else
f[i][j] = i > 0 && f[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?');
return f[m][n];
}
};
// 既然 * 可以匹配任意个字符，只需要记录当前匹配位置的最近的一个 * 的位置即可。
class Solution {
public:
bool isMatch(const char *s, const char *p) {
const char *pre_s = NULL;
const char *pre_p = NULL;
while (*s) {
if (*s == *p || *p == '?') {
++s;
++p;
}
else if (*p == '*') {
pre_s = s;
pre_p = ++p;
}
else {
if (pre_s == NULL)
break;
s = ++pre_s;
p = pre_p;
}
}
while (*p == '*') ++p;
if (*s || *p) return false;
return true;
}
};// 可以使用 O(n) 空间的一位数组作为桶，统计 1～n 的出现情况。由于 O(1) 空间的要求，使用原数组作为桶。
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
int i = 0;
while (i < n)
if (nums[i] == i + 1 || nums[i] <= 0 || nums[i] > n || nums[i] == nums[nums[i] - 1])
++i;
else
swap(nums[i], nums[nums[i] - 1]);
for (i = 0; i < n && nums[i] == i + 1; ++i);
return i + 1;
}
};// Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
// max{min(h[i], h[j]) * (j - i)}，二分答案
class Solution {
int *max0, *max1;
void init(vector<int> &h, const int &n) {
max0 = new int[n];
max0[0] = h[0];
for (int i = 1; i < n; ++i)
max0[i] = max(max0[i - 1], h[i]);
max1 = new int[n];
max1[n - 1] = h[n - 1];
for (int i = n - 2; i >= 0; --i)
max1[i] = max(max1[i + 1], h[i]);
}
bool ok(int area, vector<int> &h, const int &n) {
for (int i = 0, j; i < n; ++i)
if (h[i] > 0) {
int j = (area - 1) / h[i] + 1;
if (i - j >= 0 && max0[i - j] >= h[i] || i + j < n && max1[i + j] >= h[i])
return true;
}
return false;
}
public:
int maxArea(vector<int> &height) {
int n = height.size();
init(height, n);
int ans = 0;
long long l = 1, r = 2147483647, mid;
while (l <= r) {
mid = (l + r) >> 1;
if (ok(mid, height, n)) {
ans = mid;
l = mid + 1;
} else
r = mid - 1;
}
return ans;
}
};
// 从外向内扫描，高度小的向内靠拢以增加高度（宽度肯定减小）
class Solution {
public:
int maxArea(vector<int> &height) {
int n = height.size();
int ans = 0;
int l = 0, r = n - 1;
while (l < r)
if (height[l] <= height[r]) {
ans = max(ans, height[l] * (r - l));
++l;
} else {
ans = max(ans, height[r] * (r - l));
--r;
}
return ans;
}
};// recursion
class Solution {
int findKth(vector<int>& nums1, int m, vector<int>& nums2, int n, int k) {
int h1 = 0, h2 = 0;
while (true) {
if (h1 == m) return nums2[h2 + k - 1];
if (h2 == n) return nums1[h1 + k - 1];
if (k == 1) return min(nums1[h1], nums2[h2]);
int le = h1 + k / 2 - 1 < m ? nums1[h1 + k / 2 - 1] : INT_MAX;
int ri = h2 + k / 2 - 1 < n ? nums2[h2 + k / 2 - 1] : INT_MAX;
if (le <= ri)
h1 += k / 2;
else
h2 += k / 2;
k -= k / 2;
}
}
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
if ((m + n) & 1)
return findKth(nums1, m, nums2, n, (m + n) / 2 + 1);
return (findKth(nums1, m, nums2, n, (m + n) / 2) + findKth(nums1, m, nums2, n, (m + n) / 2 + 1)) * 0.5;
}
};