Design a HashMap without using any built-in hash table libraries.
Implement the MyHashMap class:
MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value. int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.
Explanation MyHashMap myHashMap = new MyHashMap(); myHashMap.put(1, 1); // The map is now [[1,1]] myHashMap.put(2, 2); // The map is now [[1,1], [2,2]] myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]] myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]] myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value) myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]] myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]] myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]
Constraints:
0 <= key, value <= 10<sup>6</sup> At most 10<sup>4</sup> calls will be made to put, get, and remove.
题目大意：
设计HashMap
LL解题思路(推荐)：
大学学到的方法，用Array实现，将key mod prime num找到index插入。难点在于冲突处理，这里用chaining方法，也就是LL
Design a data structure to store the strings’ count with the ability to return the strings with minimum and maximum counts.
Implement the AllOne class:
AllOne() Initializes the object of the data structure.
inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1. dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "". getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".
Constraints:1 <= key.length <= 10 key consists of lowercase English letters.
It is guaranteed that for each call to dec, key is existing in the data structure. At most `5 104calls will be made toinc,dec,getMaxKey, andgetMinKey`.
dp[i][j] = max{dp[i][m] + nums[i]×nums[m]×nums[j] + dp[m][j]}, i < m < j
多状态型DP(DP有多个终止状态)
1 2 3 4 5
dp = dp if s[i] = '0' = dp + 1 if s[i] = '1' dp2 = min(dp2 + 1, dp + 1) if s[i] = '0' = min(dp2, dp) if s[i] = '1'
解题步骤：
9zhang按照DP四部曲
[初始化]dp数组
[实现]
[答案]
[优化]是否可以用滚动内存优化空间
单序列或匹配型DP模板
实现注意事项(5点)：
[多1][初始化]初始化矩阵，dp是原长度加1。因为令边界计算方便. 遍历从多少开始，取决于前状态多少个，若递归式含dp[i-1],从1开始，如果dp[i-2]就从2开始.数值型DP，如硬币个数DP长度是数值amount，不是数组长度。Python用dp = [[0 for _ in range(M)] for _ in range(N)], M为col数，再row数
longest, res = dp[-1][-1], '' while m >= 0and n >= 0: if dp[m - 1][n] == longest: m -= 1 elif dp[m][n - 1] == longest: n -= 1 else: res += text1[m - 1] longest -= 1 m -= 1 n -= 1
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
Example 1:
Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.
Example 1:
Input: text1 = “abcde”, text2 = “ace” Output: 3 Explanation: The longest common subsequence is “ace” and its length is 3.
Example 2:
Input: text1 = “abc”, text2 = “abc” Output: 3 Explanation: The longest common subsequence is “abc” and its length is 3.
Example 3:
Input: text1 = “abc”, text2 = “def” Output: 0 Explanation: There is no such common subsequence, so the result is 0.
Constraints:1 <= text1.length, text2.length <= 1000 * text1 and text2 consist of only lowercase English characters.
longest, res = dp[-1][-1], '' while m >= 0and n >= 0: if dp[m - 1][n] == longest: m -= 1 elif dp[m][n - 1] == longest: n -= 1 else: res += text1[m - 1] longest -= 1 m -= 1 n -= 1 return res[::-1]
