刷题leetcode 打卡战拖 保持积极

这里开自己第一个帖子
战胜拖延
有兴趣的小伙伴来一起努力 互相监督

之前leetcode刷题会做的题目 面试现场还是会出现脑子空白 自己思路不去开动的现象

这里重新开一个leetcode session
希望能熟悉这些方法 并且真的把这些方法转化为自己内在的解题思路 形成思考和解决问题的肌肉记忆
勇敢一点
最近几天情绪比较低落
希望在这里一步一步 也能慢慢走出低潮期吧

20201014:
55 Jump Game:
第一个思路 从前往后数组每一个元素遍历，记录从该index是否可以到达最后一个, greedy去做(recursive call helper)，TLE，spaceO(2n),time O(n^2)
换第二个思路，从后往前，不断刷新所需到达的最后一个index的位置，只要改元素的值+index> laststop index，既可以成功，一次遍历数组，AC， spaceO(n),timeO(N)

20201015

61 rotate list to k
914 x of a kind in a deck of cards -> smallest common divisor

lynnnaive16 发表于 2020-10-15 18:11
20201015

61 rotate list to k

20201016
Partition list

20201017
142 detect cycle in linked list and return the start of circle
2*(F+a) = F + n*c + a

20201018
92. Reverse Linked List II
1626: dp
1624: hash table

lynnnaive16 发表于 2020-10-18 23:43
20201018
92. Reverse Linked List II
1626: dp

20201019
1622 fancy number
这道题真的我完全没有头绪
是一道design的题目

看了很久才发现
为了降低在addall, multiall操作的时间复杂度到O(1)，以O(N)的空间换取
最优解法
1)用了 拆解连续的 + 和 *的 运算的时候 多开了2列数组，以cumsum的形式，记录当数组里有N个数的时候，最后一个元素记录了到N目前为止，所有做过的+和乘的total amount
2) 读取数组中id处的元素，则有原数组的该出元素和对应的add,multi数组里的元素退出最终的数字

20201020
1621 #of ways to select k segments on a length of n axis(0-n points)-> segment non-overlap, allow endpoint overlap
1) combination number: -> n+k-1 number, choose 2k out of it
2) dp -> transition function
             -> dp[n][k] = dp[n-1][k] + dsumovern[n-1][k-1]
             -> dsumovern[n][k] = dsumovern[n-1][k] + dp[n][k]
             initiation state dp[i][0] = 1, dsumovern[i][0] = dsumovern[i-1][0] + dp[i][0]   ,   dp[0][k] = 0
             time complexity O(nk), space complexity O(nk)

20201021
1625 Lexicographically Smallest String After Applying Operations
greedy 题目 拿到不用慌 ，没啥特别解法而需要用greedy的题目，按照顺序有条理的brute force下去就好
BFS(breadth就是两个operation, rotate和add)
Space complexity: at most O(10*10*len(s)) 因为str是even长度，导致可能的组合数目缩小了很多

20201022
1626 best team with no conflicts
dp -> sort by age, dp[idx] 表示加入当前sidx处core，从0-idx元素考虑进来之后，得到的最大分数-》O(n**2)，无法保证往后update不重复不漏，就以dix为界限往前update

20201023
1546 max # of non-over lapping subarrays with sum equals target
presum + dp
dp -> keep record of till index n, the largest # of subarrays
-> find equal to target. use two-sum dictionary keep record of already went through elements
-> non-overlapping, used elements cannot be used 2nd time, so use visited to keep record, after one pair is recorded, reset visited
-> corner case, dictionary add key =0, ele(index=-1) -> key is the presum value, ele is index
-> corner case, keep updating dictionary as the loop goes, to get the most updated dp value, even if the presum is same(key duplicated)