Warm-up Challenges
Counting Valleys
数海拔从0变为负数的次数即为山谷的个数。
Sales by Match
按颜色统计袜子的个数，然后算双数。
int sockMerchant(int n, vector<int> ar) {
vector<int> colors(100+1, 0);
for (auto &x : ar) {
++colors[x];
}
int res = 0;
for (auto &x : colors) {
res += x/2;
}
return res;
}Jumping on the Clouds
因为每次只能往前走1步或者2步，因此不会存在2片连续的雷雨云。遇到雷雨云需要往前走2步跳过雷雨云，而对于一片连续的积雨云，假设其长度为k，则需要走k/2步从这片积雨云的左端点走到右端点，因此最终解法就是数数组中1的个数和每个连续0区间的长度。
int jumpingOnClouds(vector<int> c) {
int res = 0;
int last_1_pos = -1;
int len = c.size();
for (int i = 0; i < len; i++) {
if (c[i] == 1) {
res += 1;
res += (i - last_1_pos - 1) / 2;
last_1_pos = i;
}
}
res += (len - last_1_pos - 1) / 2;
return res;
}数组
Minimal Swaps 2
思路：找出输入排列中的循环，对一个有k个元素的循环需要最少k – 1次swap来使得循环里的各个元素回到其本来的位置上．
数学证明：如何证明有k个元素的循环需要最少k – 1次swap可以回到其本来的位置上？
排序
滑动窗口计算中位数
长度为n的数组，一个长度为k的滑动窗口在这个数组上滑动，求滑动窗口的中位数．
思路１：窗口开始滑动时，对窗口内的数组排一次序，之后每次往前滑动一个元素时，用二分查找找到要删除的元素，将其替换为要加入滑动窗口的元素，此时除了这个新加入的元素，其他元素都是有序的，新加入元素只要按照冒泡排序的方式，不停向左或者向右交换，即可到达使整个窗口有序的位置．
不过这种思路在测试时遇到了超时的问题，原因在于测试case中k很大，和n相当，那么这就退化成为一个n*n级别的算法．
思路２：由于题目限制了元素大小范围为0-200，因此可以用计数排序的方式统计滑动窗口内的数，每次滑动时，只需要将对应元素的频率统计值减１和加１即可，然后遍历频率统计的数组求滑动窗口的中位数即可．这是一个200*n级别的算法．
统计数组中有序三元组k,k*r,k*r*r的个数
直接枚举所有的三元组，来判断其是否满足r倍数关系的话，有多少个三元组就需要枚举多少次，即使是满足条件的三元组个数，也都是有1个满足条件的三元组就枚举了一次，时间复杂度很高．
可以依次枚举数组中的元素a[i]，并且用一个哈系表记录到目前为止a[i]作为k*r*r出现了多少次，a[i]作为k*r出现了多少次，最后更新a[i]作为k出现了多少次．那么题目要求的有序三元组个数就是所有a[i]作为k*r*r出现次数之和．这枚举和更新的顺序隐式地保证了k,k*r,k*r*r三个数的索引也是递增的．
字符串
最多删除一个字符使得字符串中字符出现频率相等
3种情况是有效的字符串：
- 字符串中所有字符频率相等；
- 字符串中有1个字符出现的频率为1次，其他字符都出现了k(k > 1)次；
- 字符串中有除了一个字符出现了k+1次，其他字符都出现了k次；
求除中心字符可以不同外其他字符都必须相同的子字符串的个数
思路就是统计连续相同字符串构成的区间，再分别求所有字符都相同的子串的个数和中心字符不同但是其他字符都相同的子串的个数．
链表
反转双向链表
思路一：依次移除head后面的节点并将其放到链表头；
DoublyLinkedListNode* reverse(DoublyLinkedListNode* llist) {
if (!llist) {
return llist;
}
DoublyLinkedListNode *head = llist;
while (llist->next) {
DoublyLinkedListNode *tmp = llist->next;
llist->next = llist->next->next;
if (llist->next) {
llist->next->prev = llist;
}
tmp->prev = nullptr;
tmp->next = head;
head = tmp;
}
return head;
}
思路二：由于是双向链表，因此只要将每个节点的next和prev交换即可；
Node* Reverse(Node* head)
{
Node *temp = NULL;
Node *current = head;
while (current != NULL)
{
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
if(temp != NULL )
head = temp->prev;
return head;
}思路三：递归；
插入节点到有序链表
思路：找到最后一个小于插入节点数据的节点，然后分情况处理；
DoublyLinkedListNode* sortedInsert(DoublyLinkedListNode* llist, int data) {
DoublyLinkedListNode *inserted = new DoublyLinkedListNode(data);
DoublyLinkedListNode *tmp = llist;
while (tmp != nullptr && tmp->data < data && tmp->next != nullptr) {
tmp = tmp->next;
}
if (tmp == nullptr) {
llist = inserted;
} else if (tmp->data < data) {
inserted->next = tmp->next;
inserted->prev = tmp;
tmp->next = inserted;
if (inserted->next) {
inserted->next->prev = inserted;
}
} else {
if (tmp == llist) {
llist = inserted;
}
inserted->next = tmp;
inserted->prev = tmp->prev;
tmp->prev = inserted;
if (inserted->prev) {
inserted->prev->next = inserted;
}
}
return llist;
}找到两个链表的公共节点
思路一：先确定两个链表的长度，如果两个链表存在公共节点，那么他们的最后一段是相同的，因此从两个链表的头节点开始遍历，并且让长度更长的链表先往前走k步(k为长度更长的链表多出来的节点个数)，然后两个链表依次比较节点是否相同，直到找到相同的节点或者到达链表末尾．
思路二：对于已知的两个链表A和B，可以把A分解为listX+listC，B分解为listY+listC，listC为两个链表公共的部分(listC可能是空的)．那么同时用两个指针来遍历listX+listC+listY和listY+listC+listX，
如果两个链表A,B长度相同：如果listC非空，那么这两个指针会同时遍历到同一个节点；如果listC为空，那么这两个指针会同时变为空；
如果两个链表A,B长度不相同：如果listC非空，那么两个指针会各自在遍历完一遍listX+listC+listY和listY+listC+listX后，开始接着遍历listC，这个时候两个指针就遍历到了同一个节点；如果listC为空，那么两个指针会各自在遍历完一遍listX+listC+listY和listY+listC+listX后同时变为空；
判断链表是否有环
用两个指针从头开始遍历，一个每次前进１步，一个每次前进２步，如果两个指针走到同一个节点则有环，否则走２步的会先走到链表的末尾．
递归与回溯
十字填字游戏
思路：递归找到第一个’-‘的格子，依次尝试用每一个单词去填这个格子，并且填的方式也需要枚举，一是枚举横着填还是竖着填，二是这个格子可能需要用这个单词的第几个字母来填。
multiset<string> split(string words, char sep) {
vector<int> seps;
seps.push_back(-1);
for (int i = 0; i < words.size(); i++) {
if (words[i] == sep) {
seps.push_back(i);
}
}
seps.push_back(words.size());
multiset<string> res;
for (int i = 1; i < seps.size(); i++) {
string word;
word.assign(words.substr(seps[i - 1] + 1, seps[i] - seps[i - 1] - 1));
res.insert(word);
}
return res;
}
bool match(vector<string> &crossword, vector<vector<int>> &state, string str, int dir, int offset, int x, int y) {
if (dir == 0) {
if (x - offset < 0 || x - offset + str.size() > crossword.size()) {
return false;
}
for (int i = x - offset; i < x - offset + str.size(); i++) {
if (crossword[i][y] == '+'
|| (crossword[i][y] != '-' && crossword[i][y] != str[i - (x - offset)])) {
return false;
}
}
} else {
if (y - offset < 0 || y - offset + str.size() > crossword[0].size()) {
return false;
}
for (int i = y - offset; i < y - offset + str.size(); i++) {
if (crossword[x][i] == '+'
|| (crossword[x][i] != '-' && crossword[x][i] != str[i - (y - offset)])) {
return false;
}
}
}
return true;
}
void apply(vector<string> &crossword, vector<vector<int>> &state, string str, int dir, int offset, int x, int y) {
if (dir == 0) {
for (int i = x - offset; i < x - offset + str.size(); i++) {
crossword[i][y] = str[i - (x - offset)];
++state[i][y];
}
} else {
for (int i = y - offset; i < y - offset + str.size(); i++) {
crossword[x][i] = str[i - (y - offset)];
++state[x][i];
}
}
}
void fallback(vector<string> &crossword, vector<vector<int>> &state, string str, int dir, int offset, int x, int y) {
if (dir == 0) {
for (int i = x - offset; i < x - offset + str.size(); i++) {
state[i][y] -= 1;
if (state[i][y] == 0) {
crossword[i][y] = '-';
}
}
} else {
for (int i = y - offset; i < y - offset + str.size(); i++) {
state[x][i] -= 1;
if (state[x][i] == 0) {
crossword[x][i] = '-';
}
}
}
}
bool solve(vector<string> &crossword, multiset<string> &words, vector<vector<int>> &state) {
bool find = false;
int i = 0, j = 0;
for (i = 0; i < crossword.size(); i++) {
for (j = 0; j < crossword.size(); j++) {
if (crossword[i][j] == '-') {
find = true;
break;
}
}
if (find) {
break;
}
}
if (!find && words.empty()) {
return true;
} else {
auto wordSet = words;
for (auto &str : wordSet) {
for (auto dir = 0; dir < 2; dir++) {
for (int k = 0; k < str.size(); k++) {
if (match(crossword, state, str, dir, k, i, j)) {
apply(crossword, state, str, dir, k, i, j);
words.erase(str);
if (solve(crossword, words, state)) {
return true;
} else {
words.insert(str);
fallback(crossword, state, str, dir, k, i, j);
}
}
}
}
}
}
return false;
}
/*
* Complete the 'crosswordPuzzle' function below.
*
* The function is expected to return a STRING_ARRAY.
* The function accepts following parameters:
* 1. STRING_ARRAY crossword
* 2. STRING words
*/
vector<string> crosswordPuzzle(vector<string> crossword, string words) {
int m = crossword.size();
int n = crossword[0].size();
vector<vector<int>> state;
for (int i = 0; i < m; i++) {
state.push_back(vector<int>(n, 0));
}
multiset<string> wordSet = split(words, ';');
solve(crossword, wordSet, state);
return crossword;
}
树
判断是否是二叉搜索树
思路：递归判断。
动态规划
Abbreviation
容易坑的地方就是递推的时候，当string a的字串为空而b的子串不为空的时候，这个两个子串是不能算匹配的。
string abbreviation(string a, string b) {
int lena = a.size();
int lenb = b.size();
if (lena < lenb) {
return "NO";
}
bool res[lena + 1];
bool tmp[lena + 1];
bool findUpper = false;
res[0] = true;
for (int i = 0; i < lena; i++) {
if (isupper(a[i])) {
findUpper = true;
}
res[i + 1] = !findUpper;
}
for (int i = 1; i <= lenb; i++) {
memcpy(tmp, res, sizeof(bool) * (lena + 1));
res[0] = false; //这句话很关键
for (int j = 1; j <= lena; j++) {
if (isupper(a[j - 1])) {
res[j] = (a[j - 1] == b[i - 1]) && tmp[j - 1];
} else {
res[j] = res[j - 1] || (tmp[j - 1] && (toupper(a[j - 1]) == b[i - 1]));
}
}
}
if (res[lena]) {
return "YES";
} else {
return "NO";
}
}Candies
思路：从两个方向分别找以每个元素结尾的最长连续上升子序列的长度，取较高者作为candy数。
贪心
Reverse Shuffle Merge
求最小的A，其实就是将字符串反转后，按照字符串现有顺序取一个最小的A。方法就是每次贪心地取一个最小的合法的字符。
int getMin(string &s, int index, vector<int> discard_freq, vector<int> target_freq) {
int min_index = index;
while (discard_freq[s[index] - 'a'] > 0 && index + 1 < s.size()) {
--discard_freq[s[index] - 'a'];
++index;
if (target_freq[s[index] - 'a'] > 0
&& (s[index] < s[min_index] || target_freq[s[min_index] - 'a'] <= 0)) {
min_index = index;
}
}
return min_index;
}
/*
* Complete the 'reverseShuffleMerge' function below.
*
* The function is expected to return a STRING.
* The function accepts STRING s as parameter.
*/
string reverseShuffleMerge(string s) {
vector<int> target_freq(26, 0);
for (auto ch : s) {
++target_freq[ch - 'a'];
}
for (auto &f : target_freq) {
f /= 2;
}
vector<int> discard_freq = target_freq;
std::reverse(s.begin(), s.end());
//cout << "reversed:" << s << endl;
string res;
int index = -1;
while (res.size() < s.size() / 2) {
int pick = getMin(s, index + 1, discard_freq, target_freq);
//cout << "pick: " << pick << " " << s[pick] << endl;
--target_freq[s[pick] - 'a'];
res.push_back(s[pick]);
for (int i = index + 1; i < pick; i++) {
--discard_freq[s[i] - 'a'];
}
index = pick;
}
return res;
}栈与队列
Min Max Riddle
思路：计算出每个数作为最小值的区间长度(分别从顺序和逆序两个方向遍历数组，并用单调递减的栈算出每个数左边连续比它大的数的个数和右边连续比它大的数的个数)，这个区间长度不包括自己，因此其最小值为0。在计算每个数arr[i]作为最小值的区间长度len[i]时，每算出一个len[i]，需要去更新结果数组res[len[i]] = max(res[len[i]], arr[i])。需要注意一点，如果两个数arr[i]，arr[j]满足：arr[i] > arr[j]，len[i] > len[j]，那么res[len[j]]也是要考虑arr[i]的，因为arr[i]作为一个更长区间的最小值，也是可以作为len[j]这种长度区间的最小值的。所以在计算最终的结果数组时我们需要倒序进行更新：
for i = n - 2; i >= 0; i--
res[i] = max(res[i], res[i + 1]);Solution：
vector<long> riddle(vector<long> arr) {
vector<long> range(arr.size());
stack<long> descend_stack;
vector<long> res(arr.size(), 0);
// left side
for (int i = 0; i < arr.size(); i++) {
while (!descend_stack.empty() && arr[descend_stack.top()] >= arr[i]) {
descend_stack.pop();
}
if (descend_stack.empty()) {
range[i] = i;
} else {
range[i] = i - descend_stack.top() - 1;
}
descend_stack.push(i);
}
while (!descend_stack.empty()) {
descend_stack.pop();
}
// plus right side
for (int i = arr.size() - 1; i >= 0; i--) {
while (!descend_stack.empty() && arr[descend_stack.top()] >= arr[i]) {
descend_stack.pop();
}
if (descend_stack.empty()) {
range[i] += arr.size() - 1 - i;
} else {
range[i] += descend_stack.top() - 1 - i;
}
res[range[i]] = res[range[i]] > arr[i] ? res[range[i]] : arr[i];
descend_stack.push(i);
}
for (int i = arr.size() - 2; i >= 0; i--) {
res[i] = res[i + 1] > res[i] ? res[i + 1] : res[i];
}
return res;
}用栈模拟队列
一个栈用于获取队列头，一个栈用于获取队列尾，只有在必要的时候才移动这两个栈中的一个。
class MyQueue {
public:
stack<int> stack_newest_on_top, stack_oldest_on_top;
void push(int x) {
stack_newest_on_top.push(x);
}
void pop() {
if (stack_oldest_on_top.empty()) {
while (!stack_newest_on_top.empty()) {
stack_oldest_on_top.push(stack_newest_on_top.top());
stack_newest_on_top.pop();
}
}
stack_oldest_on_top.pop();
}
int front() {
if (stack_oldest_on_top.empty()) {
while (!stack_newest_on_top.empty()) {
stack_oldest_on_top.push(stack_newest_on_top.top());
stack_newest_on_top.pop();
}
}
return stack_oldest_on_top.top();
}
};搜索
Maximum Subarray Sum
计算连续子数组和对指定数字m取模的最大值。
思路计算从索引0开始的序列和(对m取了模的)prefix[0]，prefix[1]，prefix[n-1]。则所有的连续子数组和都可以通过prefix[i]，i = 0，1，…，n – 1以及prefix[j] – prefix[i]，j > i表示出来。在枚举(prefix[j] – prefix[i])%m的最大值时，可以先枚举j，固定住j，在枚举i，i取0，1，…，j – 1。这种枚举的复杂度是n平方的，因此需要优化。优化的方式就是避免不必要的枚举：
- 对于prefix[i]比prefix[j]小的i，有prefix[j] – prefix[i] <= prefix[j]， 所以这些prefix[i]也是不必枚举的；
- 对于prefix[i]比prefix[j]大的i，我们只需要枚举这些prefix[i]中最小的一个，因为prefix[j] – prefix[i]减出来是负数，对m取模需要再加上m，因此负得越少，取模的结果越大。
所以终上两个优化点，算法思路就是依次计算prefix[j]，并找到之前计算出的prefix[0]，prefix[1]，prefix[2]，…，prefix[j – 1]中大于prefix[j]的最小那一个(假设索引是k)，用max(prefix[j]，(prefix[j] – prefix[k] + m) % m)去更新我们要求的最大值即可。
Making Candies
思路：
- 如果要增加worker或者machine，那么就应该在一开始就增加，因为相同数量的worker和machine，增加的越早生产的candy越多；
- 增加worker和machine时，应该按照尽量让两者数量一致的方式来增加，这样才可以让machine和worker的乘积尽量大；
- 按照增加的worker和machine的总数来枚举，当发现增加worker和machine反而使得生产指定数量candy的时间增加时，就不用继续枚举了；
- 按照第3点尝试一个一个的增加worker和machine的总数来枚举会导致需要枚举的case很多，运行超时，所以需要优化。优化的方式是，如果每次决定要增加worker和machine的数量，那就要把剩余的candy花完，不要让剩余的candy超过p。
a proof that we must only buy-all or buy-none, buy-some is not optimal
At a certain pass, assume that current machine number and worker number is m and w, and m <= w, assume r for (n-remain), if buy-one is better than buy-none means that (r/(m * w))>=((r+p)/(m * w+w)), this equals to r/p >= m
On this basis, prove buying i+1 is better than buying i is to prove that (r + ip)/(mi * wi ) – (r+ip+p)/(mi * wi + wi) >= 0 where mi, wi is machine number and worker number after investing i times
(r + ip)/(mi * wi ) – (r+ip+p)/(mi * wi + wi) >= 0 equals r/p >= mi – i, because of r/p >= m, we only need to prove m >= mi – i, since i is split into wi and mi, m + i >= mi is obvious.
优化之前的代码：
/*
* Complete the 'minimumPasses' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts following parameters:
* 1. LONG_INTEGER m
* 2. LONG_INTEGER w
* 3. LONG_INTEGER p
* 4. LONG_INTEGER n
*/
long minimumPasses(long m, long w, long p, long n) {
if ((double)m * (double)w >= n) {
return 1;
}
long min_passes = ceil((double)n / (m * w));
long passes = 0;
long candies = 0; // candies remained in the last pass
if (p >= n) {
return min_passes;
}
while (true) {
if (candies < p) {
long added_passes = ceil((double) (p - candies) / (m * w));
candies += added_passes * (m * w);
passes += added_passes;
}
if (m < w) {
++m;
} else {
++w;
}
candies -= p;
long passes_needed = min_passes;
if (candies >= n) {
passes_needed = passes;
} else {
passes_needed = passes + ceil((double) (n - candies) / (m * w));
}
if (passes_needed > min_passes || passes >= min_passes) {
break;
} else if (passes_needed < min_passes) {
min_passes = passes_needed;
}
}
return min_passes;
}优化之后的代码：
/*
* Complete the 'minimumPasses' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts following parameters:
* 1. LONG_INTEGER m
* 2. LONG_INTEGER w
* 3. LONG_INTEGER p
* 4. LONG_INTEGER n
*/
long minimumPasses(long m, long w, long p, long n) {
long min_passes = ceil((double)n / ((double)m * w));
long passes = 0;
long candies = 0; // candies remained in the last pass
if (p >= n || min_passes == 1) {
return min_passes;
}
int index = 0;
while (true) {
if (candies < p) {
long added_passes = ceil((double) (p - candies) / ((double)m * w));
candies += added_passes * (m * w);
passes += added_passes;
}
long added_m_or_w = candies / p;
if (m + added_m_or_w <= w) {
m += added_m_or_w;
} else if (w + added_m_or_w <= m) {
w += added_m_or_w;
} else {
long sum = m + w + added_m_or_w;
m = sum / 2;
w = sum - m;
}
candies = candies % p;
long passes_needed = passes + ceil((double) (n - candies) / ((double)m * w));
if (passes_needed > min_passes || passes >= min_passes) {
break;
} else if (passes_needed <= min_passes) {
min_passes = passes_needed;
cout << "min_passes:" << passes_needed
<< " m:" << m
<< " w:" << w
<< " passes:" << passes
<< " candies:" << candies
<< " index:" << index++
<< endl;
}
}
return min_passes;
}
图论
寻找相同颜色节点之间的最短路径
对指定颜色的节点同时进行宽度优先搜索即可。
修建道路和图书馆的最小费用
图书馆的费用低于道路费用时就直接每个城市修建一座图书馆，否则有多少个联通分量就修建多少个图书馆。
其他
Maximum Xor
对于给定的一个数和一个集合，判断这个数和集合中的哪个数做异或运算得到的结果最大。
思路：将这个集合里的数组织成trie。
Friend Circle Queries
朋友的朋友还是朋友，问每当得知两个人是朋友，所有人中最大的朋友圈的人数是多少？
思路：并查集，每当得知两人是朋友关系后，将人数较小的圈子里的人加入到人数教大的圈子里去。
近期评论