8月刷题/Mock interview接龙活动（缺米刷题的来）

今天5道题之后  我没有感觉精辟立即  我感觉我j进步了 T _ T

Count Servers that Communicate
这算是一个想法题目。本身code并不难写。
走两遍matrix
第一遍存入int[] row和int[] column ++
第二遍判断grid[i][j] == 1 && row[i]>1 || column[j]>1  res++


Shortest Path with Alternating Colors
比较难得BFS
先build一个graph
然后queue里是 Queue<Pair<Integer, Boolean>> qq
boolean代表red或者blue
开始是
        qq.add(new Pair<>(0, true));
        qq.add(new Pair<>(0, false));


Is Graph Bipartite?
BFS, int[] colors

不用build额外的graph 题目中的graph是已经build好的了

不需要set因为有n个点所以用一个int[] colors = new int[n];就可以
完成assign color 比较和看有没有visit过

第12天打卡
18. 4Sum 和3Sum的思路类似，通过两维遍历数列，然后用2Sum的办法来找到最优解。另外还可以利用已经排过序的优势再去掉最小和最大的连续和如果他们无法达到target的话。

5. Longest Palindromic Substring 这是一道medium题，关键是想明白判断palindrome从中间往两边比较而不是从头尾往中间比较，然后考虑奇数长度和偶数长度的区别对待就行了。

6.ZigZag Conversion 这是一道medium题，关键是想明白采用哪种算法，一种是类似仿真，同步build每一行的string,另外一种是直接计算出每一行的string.然后要处理第一行和最后一行的corner case. 另外我个人漏了考虑输入长度为1的特殊情况。

4. Median of Two Sorted Arrays 今天刷了一道Hard题 到达到O(log(m+n))就需要binary search, 不能通过遍历或者insertion的算法，关键想明白什么是median以及如何判定收敛，核心思路是在两个array上找到两个cut，分别将所有数分成左右两部分，左边的最大值小于右边的最小值，然后对四个边界值求解中位数。corner case也花了一些时间处理，关键是想明白如何会发生corner case（数组越界）然后引入math.inf和-math.inf进行一般化处理就能实现。

8月12号，

今天4道

PS， 最近看别人玩Fall Guys 太逗了

8.12 复习5

菜鸡八月

1. pascal's triangle II: august challenge 里的，可以每行从右到左把j设成get(j-1)+get(j)
2. delete and earn: 有点类似house robber，先把不同的number分别加到一起，每次看要不要
    拿当前的bucket，可以用skip和take两个来记， prevskip = skip，skip = max(skip, take)，
    take = prevskip + count[i]，最后看skip和take哪个更大
3. subarray product less than K: 学习了sliding windows，先移j，然后向右移i直到当前乘积<k,
    注意每次count加j-i+1个subarray

8.12 Day12 打卡，今天复习了binary search
做了两道题，一道hard一道medium

今天继续每日挑战，multiply 那道题其实思路对了，我用的就是从后面往前面乘，但是result index 在哪里存储我哪方面没有思考清楚。还需要进步

8.12 每日一题 杨辉三角
这道题一看 O(k) 要求就知道有公式trick，杨辉三角和二项式有关，所以 n 行 k 位为组合数 C(n-1,k-1)，套公式就行
不过有时候可能会遇到乘法过大导致运行速度下降的问题，所以也可以改为加法。每层数字的总数为n，一层层计算即可。
复习题 637，102，107 也还是层次遍历的题，稍微改改之前写的代码即可。

今天继续 八月Day4