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

Day 39, solved 1 problem.

Tip: use DP for 3 cases.

31/7 打卡 今天比较轻松一点
70 653 167

July 最后一天了，掐指一算 坚持了 27天吧，每天至少三道题

Day 31:继续抱佛脚之今日刷了十题
只有sparse matrix multiplication是新题，这题要把两个matrix非零的entry的index (i,j)记录到hash maps里面，然后iterate一个map的key，say (i,k)，在看另一个map里面是否有(k,j)。

七月最后一天打卡

Median of Two Sorted Arrays
这是一道经典hard题目。
我最后最好的办法是看了youtube讲解视频，才真正透彻了解解法的思路。
x2<=y4, y3<=x3是我们要找的点
从小的array那边开始做binary search
这里这个加一很重要 partitionX + partionY = (x+y+1)/2


Random Pick with Weight
wsum[] 然后random一个小于sum[len-1] 的数值 然后binary search

想解题思路
Arrays.binarySearch
new Random()
random.nextInt(wSums[len-1]) 返回0(闭区间) 到 value(开区间)


  Fraction to Recurring Decimal
  想
  edge case比较多
  主要的edge cases就是
  分子分母为0
  正负
  和重复的Fraction可能有好几位

  这个题目的想法就是
  首先用循环
  要存一个hashmap来看重复的num和index

  StringBuilder的方法insert

今天做了merge k sorted list , 重点复习了优先队列和时间复杂度的知识点

新人继续求米求积分。求大佬们施舍

7月要过去了，加油

7/30 打卡第30天， 刷了3道题

23. Merge k Sorted Lists
用了两种方法，一种是divide and conquer, 另一种是min-heap

292. Nim Game
brainteaser, 先走的想法使n%4==0

299. Bulls and Cows
抄答案，用数组或hashing存'0'-'9'的count，
当secret[i]!=guess[i]
if count[secret[i]]<0, cow++，
if count[guess[i]]>0, cow++，
count[secret[i]] += 1
count[guess[i]] -= 1

隨意挑幾題寫，維持手感