7月缺米的来刷题/Mock interview活动

飞猪也是猪 · Screen Shot 2020-07-08 at 11.45.15.png *(322.7 KB, 下载次数: 0)*

今天做了6道

rockwtr

Day 16, solved 6 problems.

Tips:
1. LC 438, use sliding windows;
2. LC 652, Serialize tree first;
3. LC 15, sort first, then ignore repeated numbers; for 2nd and 3rd numbers, use the algorithm "pushing from the two ends of the sorted array to find the given target sum".

NEVERNEVERLAND

本帖最后由 NEVERNEVERLAND 于 2020-7-9 03:45 编辑

82题：删除排序链表中的重复数字
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
      if(!head || !head->next) return head;
      auto dummy = new ListNode(-1);
      dummy->next = head;
      ListNode* p = dummy;
      /**
      -1->1->2->4->4->5
            p  q
      */
      while(p->next) {
         auto q = p->next->next;
         while(q && p->next->val == q->val) q = q->next;
         // p和q质检只间隔了一个数字，且是不同数字，所以 p 向右移动一位
         if(p->next->next == q) p = p->next;
         //否则p的下一个节点指向q:下一个无相同数字的节点
         else p->next = q;
      }

      return dummy->next;
}
}

84题：柱状图中最大矩形面积

class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
stack<int>stk; // 放左边或右边最小的元素的栈,其中最小元素是heigths数组的坐标
vector<int>left(n, 0), right(n, 0);
//从左往右遍历
for(int i = 0;i < n;++i) {
//找到第一个比heights[i]小的数
while(!stk.empty() && heights[stk.top()] >= heights[i]) stk.pop();
//如果不存在，最左为-1
if(stk.empty()) left[i] = -1;
//找到的这个位置为栈顶元素
else left[i] = stk.top();
//将i放进栈中
stk.push(i);
}
//从右往左遍历
stk = stack<int>();
for(int i = n-1;i >= 0;--i) {
//找到第一个比heights[i]小的数
while(!stk.empty() && heights[stk.top()] >= heights[i]) stk.pop();
//如果不存在,则最右为n
if(stk.empty()) right[i] = n;
//找到的这个位置为栈顶元素
else right[i] = stk.top();
//将i放进栈中
stk.push(i);
}
int res = 0;
for(int i = 0; i < n;++i) {
res = max(res, heights[i] * (right[i]-left[i]-1));
}
return res;
}
};[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][i][i][i][i][i][i][i][i][i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i]85.最大矩形面积[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i]class Solution {[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i]public:[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] int func(vector<int>& h) {[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] if(h.empty()) return 0;[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] int n = h.size();[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] vector<int> left(n, 0), right(n, 0);[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] stack<int>stk;[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] for(int i = 0; i < n;++i) {[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] while(!stk.empty() && h[stk.top()] >= h[i]) stk.pop();[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] if(stk.empty()) left[i] = -1;[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] else left[i] = stk.top();[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] stk.push(i);[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] }[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] stk = stack<int>();[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] for(int i = n-1; i >= 0;--i) {[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] while(!stk.empty() && h[stk.top()] >= h[i]) stk.pop();[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] if(stk.empty()) right[i] = n;[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] else right[i] = stk.top();[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] stk.push(i);[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] }[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] int res = 0;[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] for(int i = 0;i<n;++i) {[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] res = max(res, h[i] * (right[i] - left[i] - 1));[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] }[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] return res;[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] }[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] int maximalRectangle(vector<vector<char>>& matrix) {[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] if(matrix.empty() || matrix[0].empty()) return 0;[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] int m = matrix.size(), n = matrix[0].size();[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] //考虑成柱状图中，最大面积的问题[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] //h表示，以第i层，往上看，的柱状图的h一维数组为多少[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] vector<vector<int>>h(m, vector<int>(n, 0));[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] for(int i = 0;i < m;++i) {[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] for(int j = 0;j < n;++j)[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] if(matrix[i][j] == '1') {[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] if(i == 0)[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] h[i][j] = 1;[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] else[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] h[i][j] = h[i-1][j] + 1;[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] }[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] }[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] int res = 0;[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] for(int i = 0; i < m;++i) [/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] res = max(res, func(h[i]));[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] return res;[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i] }[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i]};[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][/i][/i][/i][/i][/i][/i]
[i][i][i][i][i][i][i][i][i][i][i]

复制代码

[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]

一碗栗子

July day5

飞猪也是猪 · Screen Shot 2020-07-08 at 14.37.59.png *(388.89 KB, 下载次数: 0)*

暴走模式

Grace6666 · Screenshot from 2020-07-08 15-56-51.png *(98.75 KB, 下载次数: 0)*

Day 8
"""拓扑排序 topological sort. :
常用于在具有先序关系的任务规划中 e.g. 课程安排的合法性, 课程安排的顺序
BFS method using indegree
DFS

sysuxcc

Day 5
学到的：
填补NULL value 为0的方法：用ROW_NUMBER() 创造一个Master List，最后从Master List中SELECT结果，然后用WHERE限定结果的范围
用Subquery找top n：对每一行，找比他大的数量，如果少于n比他大，说明他是top n

真的不会起名字

本帖最后由真的不会起名字于 2020-7-9 05:13 编辑

DAY 3
问 if there is no such second highest salary since there might be only one record in this table. To overcome this issue, we can take this as a temp table, the solution will be judged as 'Wrong Answer' ; because of the request is ‘If there is no second highest salary, then the query should return null.’
- 其实就是再套一个SELECT()

      Another way to solve the 'NULL' problem is to use IFNULL funtion
- SELECT IFNULL()

      used to specify the number of records to return https://www.w3schools.com/php/php_mysql_select_limit.asp

      from 1 - 30 (inclusive)
      LIMIT 30

      records 16 - 25 (inclusive)
      LIMIT 10 OFFSET 15；

      第N个(M=N-1)
      DESC
      LIMIT 1, OFFSET M
例题：
【Easy】 176. Second Highest Salary https://leetcode.com/problems/second-highest-salary/
【Medium 】177. Nth Highest Salary https://leetcode.com/problems/nth-highest-salary/

saberda

这个活动真的好

刚刷了几道Tree的题

都是用deque进行BFS遍历那种

Maze大猫

7.8 打卡第二天复习了一下昨天做的专题，感觉又有新的体会
背包总结：
1.按照最终要的target weight开辟dp array/matrix(有可能是双重，如0和1的个数)
2.如果可以重复用coins,从前往后填表；反之从后往前填表
3.每次either take it or not take it
Take it： refer to dp[i-coin]

Hashtable/subarray sum问题：

如果全为正数-》sliding window
否则必须prefix+hashmap

[其他] 7月缺米的来刷题/Mock interview活动

评分

评分

评分

评分

评分

评分

评分

评分

评分