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

加油加油！今天又是五题。
其中有个308. Range Sum Query 2D 总结了一下心得。
Matrix计算presum：
        for i in range(row):
            for j in range(col):
                if j == 0:
                    self.presum[i][j] = matrix[i][j]
                else:
                    self.presum[i][j] = self.presum[i][j-1]+matrix[i][j]
        for i in range(1,row):
            for j in range(col):
                self.presum[i][j] = self.presum[i-1][j]+self.presum[i][j]

然后算region sum的时候就是用大的region减去左边的角，再减去上边的角，因为左上的小角被减了两次，再把左上的小角加一次回去。
row1col2 = self.presum[row1-1][col2] if row1>0 else 0
row2col1 = self.presum[row2][col1-1] if col1>0 else 0
row1col1 = 0 if row1==0 or col1==0 else self.presum[row1-1][col1-1]
return self.presum[row2][col2]-row1col2-row2col1+row1col1

day 23

mock 很tricky的题目，但又很简单。。。呜呜呜，多练习
对面朋友的猫咪一直窜上电脑太可爱了

Jul 29 打卡第26天，4道题
583. Delete Operation for Two Strings, LCS; 也可以直接dp进行delete操作；
712. Minimum ASCII Delete Sum for Two Strings, 将最长长度换成ascii值的和；也可以像583直接计算delete的值而不是保留；

今天刷了5题：
Predict the Winner
Implement Rand10() Using Rand7()
Unique Substrings in Wraparound String
Patients With a Condition
Best Time to Buy and Sell Stock with Cooldown

菜鸡七月第三十天

1. best time to buy and sell stock with cooldown: july challange, 一共有三个states，s0是可以买，s1是买了以后
    可以卖，s2是卖了以后的cooldown，所以transition state是s2 = s1 + prices[i]，s1 =max(s1, s0 - prices[i])，
   s0 =max(s0, lastS2)。这次还理解了O(1) space的做法
2. longest string chain: 先把所有words根据长度排序，在每个word的时候找去掉一个char的substring有没有在map里，
    有的话就记所有substring里面map对应的chain length最长的，同时把当前word和chain length放进map，每次update
    最后result
3. friend circles：第一次学union find还不是很理解，感觉是在把array转成tree，明天还是要在学习一下
4. power of four: 先用num>0和num&(num - 1) == 0找power of two, 因为(k^n-1)%(k-1) = 0, 加上(num - 1)%3=0
   来从power of two里面找power of four
5. intersection of two arrays: 复习一下，用两个set，第一个装num1出现过的元素，第二个set装intersection，最后再
    转成array

今日打卡咯

练习bit manipulation
Reverse Bits
Divide Two Integers：从大往小一边减一边update结果
Sum of Two Integers：因为用了python，处理negative比较tricky，而且需要一个mask保证数字一直是在32bit(negative数字left有很多trailing 1，while positive数字left有很多trailing 1）、
Missing Number:用xor来去除存在的
Counting Bits:规律是每次把res array增加两倍时，后半部分是前半部分每个数字加一
Number of Steps to Reduce a Number to Zero：用bitwise operation count 1 和0的个数
Power of Two: 用n&(n-1)可以去除最后一个1，然后看一下剩下数是不是为0

20200725:
3: 0284, 0341, 0723, 0935, 1213, 1498
4: 1062
5:

最近要面试了 刷高频

SHALLWEFZUW 发表于 2020-7-30 13:09
最近要面试了 刷高频

恭喜拿到面试机会，祝你成功拿offer，也希望自己能有面试，早拿offer