解题思路分享，求加米

995. Minimum Number of K Consecutive Bit Flips
Topic: sliding window + greedy.基本思路

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

我觉得你这个200分的设置有点恶意 骗我点开的嫌疑

1062. Longest Repeating Substring
Basic knowledges:
1. Rolling hash: A rolling hash (also known as recursive hashing or rolling checksum) is a hash function where the input is hashed in a window that moves through the input.
A few hash functions allow a rolling hash to be computed very quickly—the new hash value is rapidly calculated given only the old hash value, the old value removed from the window, and the new value added to the window.
Polynomial rolling hash
The Rabin–Karp string search algorithm is often explained using a rolling hash function that only uses multiplications and additions:
H = c1a^(k-1) + c2a^(k-2) + ... + cka^0
2. Rabin–Karp algorithm
In computer science, the Rabin–Karp algorithm or Karp–Rabin algorithm is a string-searching algorithm that uses hashing to find an exact match of a pattern string in a text. It uses a rolling hash to quickly filter out positions of the text that cannot match the pattern, and then checks for a match at the remaining positions.
The Naive String Matching algorithm slides the pattern one by one. After each slide, it one by one checks characters at the current shift and if all characters match then prints the match.
Like the Naive Algorithm, Rabin-Karp algorithm also slides the pattern one by one. But unlike the Naive algorithm, Rabin Karp algorithm matches the hash value of the pattern with the hash value of current substring of text, and if the hash values match then only it starts matching individual characters.

877. Stone Game
此题有bug，先手player可以每次选好奇数和大还是偶数和大，然后每次都取奇数index的stone或者相反来确保自己总是取胜，所以直接回复true即可。

不过此题真正考的是DP, minimax.
关键点是明白dp的推导公式：dp[i][j] = Math.max(piles[i] - dp[i+1][j], piles[j] - dp[i][j - 1])
为何是减?
这里使用的是minimax的思想：
1）assumption是：两个player在每一局都会选择对自己来说的最优解
2）最优解的定义：在每一局选择时，都要计算当我选择左边的值时，下一轮对手可能拿到的最大分数和我选择右边时，下一轮对手能拿到的最大值，然后比较这两种情况，哪一种情况我最终能得到更多的值。

看都看不了咋给米呢？ 😳

753. Cracking the Safe
Topic: backtracking
基本思路：
1. 为了确保能解锁，正确的密码必须是我们给出的密码的substring。为了guarentee这个条件，我们需要确保每一个n长度的combination都是我们给出的密码的substring。
2. 用backtracking的办法，在当前给出的密码的最后n - 1位digits后面try to append digit

1088. Confusing Number II
Topic: backtracking
基本思路:
Instead of going through each value from 1 to n, construct values by trying different possible digits at each position.

408. Valid Word Abbreviation
Topic: String
Corner case: abbr = "01"

411. Minimum Unique Word Abbreviation
Topic: bit manipulate + backtracking
基本思路：
1. bit manipulate: 找到和target长度相同的word，对比每个word和target，创建一个新的bit sequence来代表每个word，word和target字符相同的位置用0表示，不同的位置用1表示。并把这些word的bit sequence存到一个list里。同时把所有bit sequence里所有的1合并到一个变量candidate里
2. backtracking: 从1开始，寻找一个bit mask，并且（bit mask） & candidate > 0, 找到能形成unique abbr的bit mask， 并从中找出能形成最短unique abbr的bit mask

1444. Number of Ways of Cutting a Pizza
Topic: dfs + memoization
基本思路：
关键是从右下角开始存一个反向的preSum array，并用它来检查每次横切割或者竖切割是否可以保证上面或者左面被切割的pizza是否有apple

1483. Kth Ancestor of a Tree Node
关键是创建一个2维的数组用来存储node的（2^i）th祖先，i.e. parents[i][node]代表node的第（2^i）th ancestor，用来方便快速查找第k个祖先