缺大米的请参加这个刷题/Mock interview活动

Day 11 (6/25)

leetcode 刷题3道

谢谢楼主

6.25 day26
304 medium 部分和2D版，容斥原理解题
349 easy 虽然是easy，但仔细研究有多解法，二分、set都可以
350 easy 又是一hashmap应用

打卡第24天， 刷了3道题

11. Container With Most Water
动态编程，用到左右两指针，每次从小的那边往里缩进。

27. Remove Element
用2个指针，一个指针指向不含该元素的前端，往前推进，一旦遇到the element, copy另一个指针指向的数，然后更新指针。

69. Sqrt(x)
用了牛顿法，和二分法。二分法边界老搞错。

6.25 连续第五天 打卡三题

LC375. Guess Number Higher or Lower II，DP，需要二维DP数组，无法压缩到一维，注意区间[m+1...m+n]的cost无法通过区间[1...n]的cost来表示
LC593. Valid Square，通过点之间的距离判断 ，计算不同点之间的距离（共6个），在所有距离中，如果最大的2个距离相同（构成对角线），其余的也相同（4条边），则可构成正方形
LC287. Find the Duplicate Number，binary search可实现O(nlog n)，fast-slow pointer可实现O(n)

菜鸡第二十六天

今天还是五道题
1. contiguous array: 找0和1数量相等的最长的subarary，如果遇到0就把sum-1，把presum存成map的key，index是对应的value，
    如果map已经有当前的presum，就说明这一段subarray 0 1数量相等，看看需不需要 update，不然就把sum-index放进map里
2. subaray sum equals k: 这个也是用一个map存presum，如果map有sum和sum-k，就说明subarray的sum是k，count就加上map
    里sum-k对应的count，不存在的话就把当前sum存到map里，可以用getOrDefault(sum, 0)+1
3. find pivot index: 这个就先找总的sum，再存presum，如果当前index的时候presum = sum - presum - nums[index]，就说明两面
    的和相等，index就是pivot
4. partition array into three parts with equal sum: 这个和前一个差不多，可以存sum，也可以用two pointer做，如果left, right 两边
    的和等于total sum的三分之一，就是equal partition，不然的话根据presum的情况把指针向中间移
5. binary tree inorder traversal: 复习一下之前的，已经忘掉怎么做了，用一个stack，每次node!=null，就把node push到stack里面，
    node = node.left, 如果node是null了，就从stack里面pop一个加到result里，同时node = node.right

978. Longest Turbulent Subarray
1313. Decompress Run-Length Encoded List
1365. How Many Numbers Are Smaller Than the Current Number

打卡第15天。347. Top K Frequent Elements; 49. Group Anagrams; 380. Insert Delete GetRandom O(1); 560. Subarray Sum Equals K; 438. Find All Anagrams in a String; 138. Copy List with Random Pointer； 截图放在截图链接

补充内容 (2020-6-27 12:08):
写错了 第16天

第十天 6道题
257 Binary Tree Paths
- dfs
- post order traversal
707 Design Linked List
- list operations
207 Course Schedule
- backtracking → cycle detection
- topological sort
210 Course Schedule II
- backtracking → dfs
- topological sort
802 Find Eventual Safe States
- backtracking → dfs → O(N+E)
- topological sort → O(N+E)
240 Search a 2D Matrix II
- binary search O(nlogn)
- search from left bottom O(m+n)

慕容清 发表于 2020-06-24 01:58:10
打卡15天

8.atoi, 主要就是各种case需要进行判断。str.trim().toCharArray(); .trim()可以直接去掉string前后的所有空格。转化成char之后比较好操作。

补卡打卡16天

79.word search: 还是用的dfs+回溯的方式进行。还是要注意回溯操作完之后需要复原已经visited 的值，如果可以一条路走到黑，这条路上的值可以依次逐个恢复，如果这个节点不是想要的值，路径在这里卡住，直接就可以回溯改值，并不影响可能出现的下一次访问这个节点数值。

169.majority element：找众数，直接能够想到的方法有hashmap存储数字以及出现的次数，找最大次数即可，或者是排序，中位数一定是众数。最节省复杂度的是投票法，就是从头开始进行遍历，计数count == 1，以首位元素为众数开始遍历，首先如果count == 0, 则以当前元素为众数，count++，如果下一个元素和众数相同，则count++，如果不同则count—。背后的原理：假设真实的众数为x，进行正负两两相抵使得count = 0，有两种情况，一种是其中一个数为众数，另一种就是都不是众数，这两种方式进行相抵，都会使得最后的结果剩下的是众数。

65.valid number. 是一道corner cases非常多的题。s.charAt() 可以直接用指标的，不一定得转化成char[]。 然后里面进行条件判断的时候，可以直接判断不符合条件的直接return false；如果符合条件不会进入循环，就可以直接跑，可以节省代码。

今天10题，继续加油！ 加深了对two pointer的理解