Time: 2021.8.31-2021.9.3
Mapping of any element
By using hash function, the key value (key)(large integer, string, floating point number, etc.) is converted into an integer and then mod the table length, so that the key value is converted into an integer within the table length range of the hash table.
The zipper method resolves conflicts and constructs hash tables
Join all nodes with the same hash function results in a single linked list. If the selected hash table is of length M, the hash table can be defined as an array of Pointers t[0..m-1] of length M, each pointer in the array of Pointers points to a single linked list with the same hash function result.
Insert value: Inserts the element value into the hash table. If the hash function value of the element value is hash_key, insert the node corresponding to the value into the single linked list with t[hash key] as the pointer.
Find value: If the hash function value of the element value is hash_key, traverse the single linked list with t[hash_ key] as the header pointer to find whether the value range of each node in the list is value.
1. Longest palindrome string of LeetCode409
1. Use the character hash method to count all the characters in the string.
2. Set the longest palindrome string to max_ length = 0.
3. Set whether the center flag is set to 0.
If count is even,max_ length += count; if count is even,max_ length += count; If count is odd,max_ length += count-l, flag= 1;
5. The maximum length of the substring is max_ length + flag.
class Solution {
public int longestPalindrome(String s) {
int[] char_map = new int[128];// character hash
int max_length = 0;// The maximum length of the even part of the palindrome string
int flag = 0;// Whether there is a central point
for(int i=0; i<s.length(); i++){char c = s.charAt(i);
char_map[c]++;// Use the array subscript of integers to implement character hash, count the number of characters
}
for(int i=0; i<128; i++){if(char_map[i]%2= =0) {// If a character is even, it can be used in a palindrome string
max_length += char_map[i];
}else{
max_length += char_map[i]-1;// If a character has an odd number of characters, one is discarded and the rest are used in the palindrome string
flag = 1;// The tag palindrome string can have a center point}}return max_length + flag;// The end result is the maximum length of the even-numbered part + the center dot character}}Copy the code2. LeetCode290 Rules of words
1. Set the mapping between words (string) and pattern characters (hab). Use the array Used [128] to record whether the pattern character is used.
2. Iterate over STR, split words according to Spaces, and move the corresponding pointer to pattern character forward, split each word, judge:
If the word never appears in the hash table: If the current pattern character is already in use, false is returned; Map the word to the currently pointed attern character. Marks the currently pointed Pattern character as used, otherwise: Returns false if the current word in the hash is not mapped to the currently pointed Pattern character.
3. If the number of words does not match that of pattern characters, false is returned.
LeetCode Comment code
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] strings = s.split("");
if(pattern.length() ! = strings.length) {return false;
}
HashMap<Object, Integer> hashMap = new HashMap<>();
// If a position mismatch occurs, or one is already present and the other is not, the match fails. Null values can be avoided using the objects.equals method
for (int i = 0; i < pattern.length(); i++) {
if(! Objects.equals(hashMap.put(pattern.charAt(i), i), hashMap.put(strings[i], i))){return false; }}return true; }}Copy the code3. LeetCode49 letter heterotopic word grouping
STRS [I] = STRS [I] = STRS [I] = STRS [I] = STRS [I] = STRS [I]
1) Set the temporary variable STR = STRS [I] to sort STR.
2) If sr does not appear in anagram, set the mapping of STR to an empty string vector.
3) Add STRS [I] to string vector anagram[STR].
Iterate through the hash table Anagram and push the values corresponding to all keys into the final result.
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
char[] chars = strs[i].toCharArray();
// Sort the characters inside the string
Arrays.sort(chars);
String key = String.valueOf(chars);
// Add different groups according to key
if(! map.containsKey(key)) {// If the key cannot be found in the hash table, set an empty string
List<String> list = new ArrayList<>();
list.add(strs[i]);
map.put(key, list);
} else {
// Push the result in the corresponding stringmap.get(key).add(strs[i]); }}return newArrayList<>(map.values()); }}Copy the codeLeetCode3 The oldest string without repeating characters
1. Create a char hash (char_map) that records the number of characters.
2. Set a record of the current condition of the most string variable word;
3. Set two Pointers (I and begin) to the first character of the string.
4. Set the longest substring length result.
5. The I pointer scans the string one by one, using char_ map to record the number of characters. If the character does not appear in Word, add a character to the end of word and check if result needs to be updated. Otherwise :begin moves forward, updating the number of characters in char_map until the number of characters s[I] is 1; Update word by assigning word to a substring between begin and I.
In the whole process, begin and I are used to maintain a window in which the substring meets the topic condition (no repeated characters), the window slides forward linearly, and the overall time complexity is O(n).
LeetCode Comment code
class Solution {
public int lengthOfLongestSubstring(String s) {
int result=0;
int start=0,end=0;// represents the start and end positions of the current window
Set<Character> set=new HashSet<Character>();
// start++ when repeated characters appear in the window, and end++ when no repetition, the maximum length of each update
while(start<s.length() && end<s.length()){
if(set.contains(s.charAt(end))){
set.remove(s.charAt(start));
start++;
}
else{ set.add(s.charAt(end)); end++; result=Math.max(result, end-start); }}returnresult; }}Copy the code5. Repeated DNA sequence of LeetCode189
Enumerate all substrings of length 10 in the DNA string, insert them into the hash Map, and record the number of substrings; Iterate over the hash map and store all substrings that occur more than once into the result. The algorithm complexity is O(n).
LeetCode official solution
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
int L = 10, n = s.length();
HashSet<String> seen = new HashSet(), output = new HashSet();
for (int start = 0; start < n - L + 1; ++start) {
String tmp = s.substring(start, start + L);
if (seen.contains(tmp)) output.add(tmp);
seen.add(tmp);
}
return newArrayList<String>(output); }}Copy the code6. LeetCode76 minimum coverage substring
1. Set two character hash arrays, map_s and map_t, map_s represents the number of characters in the current window interval, map_t represents the number of characters in the substring T.
2. Set two Pointers to the first character of the string.
3. The I pointer scans the string backwards one by one. During this process, the begin pointer is checked to see if it can move forward.
If the character T pointed to by begin does not appear, begin is directly advanced. If the character T to which begin points is present, but there are enough characters in the current interval window, move begin forward and update map_ s; Otherwise, begin cannot be moved.
4. Check to see if the final result can be updated each time the pointer scans forward one character (find the smallest window containing each character in T). In the whole process, use BEGIN and I to maintain a window, the substring in the window satisfies the topic condition (including all characters in T), the window slides forward linearly, and the overall time complexity is O(n).
LeetCode Comment code
class Solution {
public static String minWindow(String s, String t) {
int left = 0,right = 0;
int count = t.length();
int res_left = 0;
int res_right = -1;
int substringLen = Integer.MAX_VALUE;
int[] map = new int[128];
for (int i = 0; i < t.length(); i++) {
map[t.charAt(i)]++;
}
while (right < s.length()) {
map[s.charAt(right)]--;
if (map[s.charAt(right)] >= 0) {
count--;
}
while (count == 0) {
int tempLen = right - left + 1;
if (substringLen > tempLen) {
res_left = left;
res_right = right;
substringLen = tempLen;
}
char departingCharacter = s.charAt(left);
map[departingCharacter]++;
if (map[departingCharacter] > 0) {
count++;
}
left++;
}
right++;
}
return s.substring(res_left, res_right + 1); }}Copy the code