解题思路分享，求加米

小糖块儿 发表于 2020-12-26 03:45
877. Stone Game
此题有bug，先手player可以每次选好奇数和大还是偶数和大，然后每次都取奇数index的stone ...

"dp[i][j] actually means maximum(alex stone - lee stone) and maximum(lee stone - alex stone) alternatively, depending on who picks from piles[i]~piles[j] first.
If alex picks from piles[i]~piles[j] first, then dp[i][j] means maximum(alex stone - lee stone);
If Lee pick from piles[i]~piles[j] frist, then dp[i][j] means maximum(lee stone - alex stone) ."
quote others: @lMiaoj

1345. Jump Game IV
Topic: BFS + HashTable
解题思路：
1. 先创建一个table，key是array里各个value，value是所有值为key的array的index组成的list
2. BFS时的一个关键是，每次访问完table的一个key的list，要clear一下，防止下次碰见同一个值时再次访问。

1463. Cherry Pickup II
Topic: dfs with memoization
解题思路：关键是两个robots所在的位置组合要当做不同的state，所以创建一个3D数组来记录不同state时能摘到樱桃的最大值

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.

小糖块儿 发表于 2020-12-27 09:11
1062. Longest Repeating Substring
Basic knowledges:
1. Rolling hash: A rolling hash (also known as ...

Monte Carlo version.
・Always runs in n logn time.
・Extremely likely to return correct answer (but not always!).
Las Vegas version.
・Always returns correct answer.
・Extremely likely to run in n logn time (but worst case is n^2 log n)

1027. Longest Arithmetic Subsequence
关键：每一个位置可能组成多组差值不同的等差数列，所以每个位置可以用一个hashmap来记录差值和长度，差值做key，长度做value