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

打卡 day 12

今天写了linked list 有关问题 [141] & [142] Linked List Cycle II & [1290]
龟兔赛跑（网上说是Floyd's algo） 我觉得其实只要理解了快，慢两个指针就好了。
当你需要找到一个Linked List里面是否有循环的时候，你就需要用两个指针来找，一个走得快，一个走的慢，快的走两步，慢的走一步。然后当他们相遇的时候，证明这个Linked List有循环（否则快的指针会先走到Null pointer上面）。所以这也是判断条件之一，这个题前面一道就是判断是否有循环。这道题是那道题的进阶版，要你返回进入循环的node。要做到这点，你需要明白当快指针第一次与慢指针相遇的时候，快指针走了a+2b+c，慢指针走了a+b。而快指针的速度是慢指针的两倍，你也可以用a+2b+c == 2(a+b) 来表示，这样你就得到了a==c的结论（也就是说你能通过新开启一个头部指针，然后他走的距离和两个指针走到loop开始的距离一样，当他们相遇的时候，确保这个是loop的起点）
leetcode上面这个人解释的很好，我把截图放在这里了。

Day 6, 3道题

按类别做了下跟加和有关的问题

2. 两数相加
链表逐个节点向后遍历,空节点值0,直到两个链表都走完
需要记住 两数x, y相加后:
(x + y) % 10 取到个位数
(x + y) / 10  获取进位 carry


1. 两数之和
  a. 暴力, 两个循环 复杂度 O(N^2)
  b. 利用set, 一个数不用两边, 根据 x + y = target==>
     对于每一个x, 找y = target -x 即可 O(N)
      

15. 三数之和
    1. for i,j,k O(N^3)
    2. a + b = -c, 枚举 a+b, 在剩下的数据找-c, 用Set Hash 的办法,将复杂度从O(N)下降到O(1)
    3. sort, find: 整个数据排序 O(NlogN):
        a. loop a, 在剩下的数组里找 b,c
        b. 两遍夹逼的办法,枚举b,c, b从0, c从最后开始
        c. a+b+c > 0, 右边界--, a+b+c < 0 左边界++

day7 #sql 3题
1. pivot并组内排序-- case when reshape + rank() over(partition by) -- 按排序分组取最值
2. 同时求最大值和最小值-- rank() over

06.12 刷题第二天打卡第二天
String

1. Remove Adjacent Repeated Characters IV
use two pointers
fast linear scan from left to right, and in terms of the slow if we meet the same as array[fast], slow--;

2. Determine if a small string is a substring of another large string.

Handle the corner case if small.isEmpty() just return 0,
if small.length() > large.length() return -1;
one pointer linear scan(0, large.length() - small.length()]
use helper function to determine if the index could be found.

3.ABCD1234 -> A1B2C3D4 (do it in-place)
handle the odd and even cases use same helper function with different parameters
reverse the middle two and reverse it back("I love google" helper function is here)
do the reOrder process recursively

4. Given a string, replace adjacent, repeated characters with the character
followed by the number of repeated occurrences.
Mindset
1.because it could be longer or shorter, but I really have no idea yet
so just utilize a newLength and set up a new array
2.use "begin" trick to detect the length either longer or shorter

Note:
1. Handle the "cast" operation
2. Use Character.isDigit to check if the current char is a digit
3. The updated fast pointer should depend on the pos of slow but not the original array;

5. Given a string, replace adjacent, repeated characters with the character followed by the number of repeated occurrences.

Assumptions

The string is not null

The characters used in the original string are guaranteed to be ‘a’ - ‘z’

Mindset:
1. Assume the number only between 1-9;
2. handle the shorter and longer cases differently
3. create a new Array and seperater (0-2] and (2 - 9]

Day12 四道题打卡 今天打的有点晚了

Day 7
0612
7 道题

String compression 挺考验耐性的。。。 其中一个出去找边界的while循环单写的话会简单很多。
Design HashMap 写了个linkedlist，练一下手
Climbing Stairs 过于简单的dp。。。
Find Minimum in Rotated sorted Array 也非常基础。。。
Robot Return 太简单了。。。一个数数的过程
Minimum Size subarray Sum，一开始忘了sliding window。。。 题目那个非要你写nlogn的很意外，prefix sum arr 然后binary search
Jump Game 2， 分析了半天发现是个greedy。。。

今日 4 题

06/13/2020 打卡第13天。

今天三道题。
#134 gas station 我的暴力方法可以通过，但官方答案的greedy算法好的多。用暴力法不符合题目考察的本意。
#93 Restore IP Addresses 一个非常经典的backtracking。非常能够体现backtrack其中要把“00” “01”排除掉这一步很容易被忽略掉。
#138 Copy List with Random Pointer 和克隆图那道题很类似。

All My SubmissionsTime Submitted        Question        Status        Runtime        Language
0 minutes ago        Copy List with Random Pointer        Accepted        0 ms        java
15 minutes ago        Restore IP Addresses        Accepted        1 ms        java
9 hours, 30 minutes ago        Gas Station        Accepted        20 ms        java

day7_coding.rar (11.32 KB, 下载次数: 0)

2020-6-13 15:51 上传

点击文件名下载附件
day7
下载积分: 大米 -1 颗

Day 7

1. Word Search II.
2. Word Search.
3. Implement Stack by Two Queues.