This is the 26th day of my participation in the Novembermore Challenge.The final text challenge in 2021
Some of the problems in the LeetCode problem set may have been skipped directly, so clean up the previous brush with LeetCode
211. Add and search words – Data structure design
Design a data structure that supports the following two operations:
void addWord(word)
bool search(word)
Copy the codeSearch (word) searches for literal or regular expression strings that contain only letters. Or a – z. . Can represent any letter.
Example:
addWord("bad") addWord("dad") addWord("mad") search("pad") -> false search("bad") -> true search(".ad") -> true search("b.." ) -> trueCopy the codeDescription:
You can assume that all words are made up of lowercase letters a-z.
class WordDictionary {
Map<Integer,Set<String>> map = new HashMap<>();// Store them separately according to the length of the string
public WordDictionary(a) {}public void addWord(String word) {
int length = word.length();
if(map.get(length)! =null){
map.get(length).add(word);
}else{
Set<String> set = newHashSet<>(); set.add(word); map.put(length, set); }}public boolean search(String word) {
Set<String> set = map.get(word.length());
if(set==null) {// No string of this length exists, return false;
return false;
}
if(set.contains(word)) return true;
char[] chars = word.toCharArray();
P:for(String s : set){
if(word.length()! =s.length()){continue;
}
char[] cs = s.toCharArray();
for(int i = 0; i< cs.length; i++){// Character-by-character comparison
if(chars[i] ! ='. '&& chars[i] ! = cs[i]){continue P;
}
}
set.add(word);
return true;
}
return false; }}/** * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * boolean param_2 = obj.search(word); * /
Copy the code212. Word Search II
Given a two-dimensional grid board and a list of words in a dictionary, find all the words that appear in both the two-dimensional grid and the dictionary.
Words must be formed in alphabetical order by letters in adjacent cells, where “adjacent” cells are those that are horizontally or vertically adjacent. Letters in the same cell are not allowed to be used twice in a word.
Example:
Input:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
Copy the codeOutput: [“eat”,”oath”] Note: You can assume that all input consists of lowercase letters A-Z.
Tip:
You need to optimize the backtracking algorithm to pass larger data tests. Could you stop backtracking earlier? If the current word does not exist in all word prefixes, you can stop backtracking immediately. What data structures can effectively perform such operations? Do hash tables work? Why is that? How about a prefix tree? If you want to learn how to implement a basic prefix tree, look at this problem first: Implement Trie (prefix tree).
First build a dictionary tree, and then add a dictionary tree during DFS, and things that end with a certain string reduce the number of searches why don't you use the beginning and the end here, '(● strap ●) the end is just, I'm done searching one, I can compare it directly, and if it isn't, I return the last one,Copy the codeclass TrieNode {
private static final int ALPHABET_SIZE = 26;
TrieNode[] children = new TrieNode[ALPHABET_SIZE];
// Determine if the prefix is the end of a string
boolean isEndOfWord = false;
TrieNode() {
isEndOfWord = false;
for (int i = 0; i < ALPHABET_SIZE; i++)
children[i] = null; }}class Trie {
public TrieNode root;
/** Initialize your data structure here. */
public Trie(a) {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode curNode = root;
int index;
for (int i = 0; i < word.length(); i++) {
index = word.charAt(i) - 'a';
if (curNode.children[index] == null) {
curNode.children[index] = new TrieNode();
}
curNode = curNode.children[index];
}
curNode.isEndOfWord = true; }}class Solution {
public List<String> findWords(char[][] board, String[] words) {
List<String> result = new ArrayList<>();
if (words == null || words.length == 0 || board == null || board.length == 0 || board[0].length == 0)
return result;
Trie trie = new Trie();
for (String temp : words)
trie.insert(temp);
TrieNode root = trie.root;
boolean[][] visited = new boolean[board.length][board[0].length];
Set<String> tempResult = new HashSet<>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (root.children[board[i][j] - 'a'] != null ) {
dfs(board, visited, i, j, root.children[board[i][j] - 'a'], tempResult, sb); }}}// We need to copy the tempResult set to the actual result List
Iterator<String> iterator = tempResult.iterator();
while (iterator.hasNext()) {
result.add(iterator.next());
}
return result;
}
private void dfs(char[][] board, boolean[][] visited, int startIInBoard, int startJInBoard
, TrieNode curNode, Set<String> resultSet, StringBuilder curStrBuilder) {
curStrBuilder.append(board[startIInBoard][startJInBoard]);
visited[startIInBoard][startJInBoard] = true;
if (curNode.isEndOfWord) {
resultSet.add(curStrBuilder.toString());
}
// Search up, if the above grid has not been searched
if (startIInBoard > 0 && !visited[startIInBoard - 1][startJInBoard]
&& curNode.children[board[startIInBoard - 1][startJInBoard] - 'a'] != null) {
dfs(board, visited,startIInBoard - 1, startJInBoard
, curNode.children[board[startIInBoard - 1][startJInBoard] - 'a'], resultSet, curStrBuilder);
}
// Search down
if (startIInBoard < board.length - 1 && !visited[startIInBoard + 1][startJInBoard]
&& curNode.children[board[startIInBoard + 1][startJInBoard] - 'a'] != null) {
dfs(board, visited,startIInBoard + 1, startJInBoard
, curNode.children[board[startIInBoard + 1][startJInBoard] - 'a'], resultSet, curStrBuilder);
}
// Search left
if (startJInBoard > 0 && !visited[startIInBoard][startJInBoard - 1]
&& curNode.children[board[startIInBoard][startJInBoard - 1] - 'a'] != null) {
dfs(board, visited, startIInBoard, startJInBoard - 1
, curNode.children[board[startIInBoard][startJInBoard - 1] - 'a'], resultSet, curStrBuilder);
}
// Search right
if (startJInBoard < board[0].length - 1 && !visited[startIInBoard][startJInBoard + 1]
&& curNode.children[board[startIInBoard][startJInBoard + 1] - 'a'] != null) {
dfs(board, visited, startIInBoard, startJInBoard + 1
, curNode.children[board[startIInBoard][startJInBoard + 1] - 'a'], resultSet, curStrBuilder);
}
// Restore the scene
curStrBuilder.setLength(curStrBuilder.length() - 1);
visited[startIInBoard][startJInBoard] = false; }}Copy the code214. The shortest palindrome string
Given a string s, you can convert it to a palindrome string by preadding characters to the string. Find and return the shortest palindrome string that can be converted in this way.
Example 1:
Input: “aacecAAA” Output: “aaACecAAA” Example 2:
Input: abcd Output: dcbabcd
class Solution {
public static String shortestPalindrome(String s) {
StringBuilder r = new StringBuilder(s).reverse();
String str = s + "#" + r;
int[] next = next(str);
// If it is a palindrome string 1234321 # 1234321
//next[str.length]=7,r.substring(0,0)="
// If 123432 # 234321 next[str.length]=5
//r.substring(0,6-5), just the first digit
String prefix = r.substring(0, r.length() - next[str.length()]);
return prefix + s;
}
/ / next array
// next[j]=x; // next[j]=x
// Maybe so
private static int[] next(String P) {
int[] next = new int[P.length() + 1];
next[0] = -1;
int k = -1;
int i = 1;
//next [k] saves the last time I was equal
// If I am not equal, I will match it from the last time I was equal
// I is a fast pointer, k is a slow pointer
while (i < next.length) {
if (k == -1 || P.charAt(k) == P.charAt(i - 1)) {
next[i++] = ++k;
} else{ k = next[k]; }}returnnext; }}Copy the code215. The KTH largest element in an array
Finds the KTH largest element in the unsorted array. Note that you need to find the KTH largest element of the sorted array, not the KTH distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2 output: 5 example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4 output: 4
You can assume that k is always valid, and that 1 ≤ k ≤ the length of the array.
class Solution {
public int findKthLargest(int[] nums, int k) {
if(nums.length < 2) {return nums.length == 1 ? nums[0] : -1;
}
return countingSort(nums, k);
}
private int countingSort(int[] nums, int k){
int max = 0;
int min = 0;
for(int i = 0; i < nums.length; i++){
if(nums[i] > max){
max = nums[i];
}
if(nums[i] < min){ min = nums[i]; }}int length = (max - min) + 1;
int[] newArray = new int[length];
// This array records the number of persons that are different from the minimum value
for(int i = 0; i < nums.length; i++){
newArray[nums[i] - min]++;
}
int j = 0;
for(int i = newArray.length - 1; i >= 0; i--){
// Start with the maximum value
if(newArray[i] > 0){
j = newArray[i] + j;
if(j >= k){
returni + min; }}}return -1; }}Copy the code216. Sum of combinations III
Find all the combinations of k numbers that add up to n. Only positive integers from 1 to 9 are allowed in a combination, and there are no duplicate digits in each combination.
Description:
All numbers are positive integers. The solution set cannot contain repeated combinations. Example 1:
Input: k = 3, n = 7 output: [[1,2,4]] example 2:
Input: k = 3, n = 9 output: [[1,2,6], [1,3,5], [2,3,4]]
class Solution {
/ / the result set
public List<List<Integer>> lists = new ArrayList<>();
/ / temporary set
public List<Integer> list = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
// Backtrace the entry
backTracking(list, 0.1, k, n, 0);
return lists;
}
public void backTracking(List<Integer> list, int index, int c, int k, int n, int sum){
// Backtrace export
// Make sure it is the sum of k numbers, and, and are the specified values
if(index == k && sum == n){
// satisfy the add join set
List<Integer> currentList = new ArrayList<>();
currentList.addAll(list);
lists.add(currentList);
return;
}
// Prune
if(sum > n){
return;
}
// Traceback conditions
for(int i = c; i <= 9; ++i){
list.add(i);
sum += i;
backTracking(list, index + 1, i + 1, k, n, sum);
list.remove(list.size() - 1); sum -= i; }}}Copy the code217. There are duplicate elements
Given an array of integers, determine whether there are duplicate elements.
The function returns true if any value appears in the array at least twice. Return false if each element in the array is different.
Example 1:
Input: [1,2,3,1] output: true example 2:
Input: [1,2,3,4] output: false
Input: [1,1,1,3,3,4,3,2,4,2] output: true
Set does not hold the contents of the same element, returns false if the same element is added, and is not addedCopy the codeclass Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> res = new HashSet<Integer>();
for(int i:nums)
res.add(i);
return res.size()<nums.length?true:false; }}Copy the code218. Skyline problem
The skyline of a city is the outer outline of all the buildings in the city as viewed from a distance. Now, assuming you have the positions and heights of all the buildings shown on the cityscape photo (Figure A), write A program to output the skyline formed by those buildings (Figure B).
Buildings Skyline Contour
The geometric information of each building is represented by a triplet [Li, Ri, Hi], where Li and Ri are the X coordinates of the left and right edges of the ith building, and Hi is its height. 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX and Ri-Li > 0 can be guaranteed. You can assume that all buildings are perfect rectangles on absolutely flat surfaces of zero height.
For example, the dimensions of all buildings in Figure A are recorded as follows: [[2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8]].
Output is [[x1,y1], [x2, y2], [x3, y3]… A list of “key points” (red dots in Figure B) of the format that uniquely define the skyline. The key point is the left end of the horizontal segment. Note that the last key point of the building on the far right is only used to mark the end of the skyline and is always zero height. In addition, the ground between any two adjacent buildings should be considered part of the skyline profile.
For example, the skyline in Figure B should be expressed as: [[2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0]].
Description:
The number of buildings in any input list is guaranteed to be within [0, 10000]. The input list is already arranged in ascending order by the left x coordinate Li. The output list must be sorted by x bits. There shall be no consecutive horizontal lines of the same height in the output skyline. For example, […[2 3], [4 5], [7 5], [11 5], [12 7]… Is the wrong answer; Three height is 5 lines should be in the final output into a: [… [2, 3], [4, 5], [7],…
class Solution {
/ / segment tree
public List<List<Integer>> getSkyline(int[][] buildings) {
int len = buildings.length;
if (len == 0) return new ArrayList<>();
return segment(buildings, 0, len - 1);
}
private List<List<Integer>> segment(int[][] buildings, int l, int r) {
// Create the return value
List<List<Integer>> res = new ArrayList<>();
// Find the end condition under the tree -> a building
if (l == r) {
res.add(Arrays.asList(buildings[l][0], buildings[l][2])); // Top left coordinate
res.add(Arrays.asList(buildings[l][1].0)); // Lower right coordinates
return res;
}
int mid = l + (r - l) / 2; // take the middle value
// The left side recurses
List<List<Integer>> left = segment(buildings, l, mid);
// The right side recurses
List<List<Integer>> right = segment(buildings, mid + 1, r);
// Merge left and right
// Create left and right index positions
int m = 0, n = 0;
// Create the current height of left and right
int lpreH = 0, rpreH = 0;
// Two coordinates
int leftX, leftY, rightX, rightY;
while (m < left.size() || n < right.size()) {
// When one side is fully added to the RES, the remaining part is added
if (m >= left.size()) res.add(right.get(n++));
else if (n >= right.size()) res.add(left.get(m++));
else { // Start judging left and right
leftX = left.get(m).get(0); // Null will not appear, can be used directly int
leftY = left.get(m).get(1);
rightX = right.get(n).get(0);
rightY = right.get(n).get(1);
// See which of my two rectangles is on the left
if (leftX < rightX) {
// If the left side is still higher than before, add left side
if (leftY > rpreH) res.add(left.get(m));
// the left side is higher than the right side. I'm going to add the left side and the previous right side because I'm going to have a new height 2,10
else if (lpreH > rpreH) res.add(Arrays.asList(leftX, rpreH));
// Replace the height on my left with the height on my right
lpreH = leftY;
m++;
} else if (leftX > rightX) {
if (rightY > lpreH) res.add(right.get(n));
else if (rpreH > lpreH) res.add(Arrays.asList(rightX, lpreH));
rpreH = rightY;
n++;
} else { // Left and right are equal
if(leftY >= rightY && leftY ! = (lpreH > rpreH ? lpreH : rpreH)) res.add(left.get(m));else if(leftY <= rightY && rightY ! = (lpreH > rpreH ? lpreH : rpreH)) res.add(right.get(n)); lpreH = leftY; rpreH = rightY; m++; n++; }}}returnres; }}Copy the code219. Repeated element II is present
Given an integer array and an integer k, determine whether there are two different indexes I and j in the array such that nums [I] = nums [j] and the absolute value of the difference between I and j is at most K.
Example 1:
Input: nums = [1,2,3,1], k = 3 output: true example 2:
Input: nums = [1,0,1,1], k = 1 Output: true Example 3:
Input: nums = [1,2,3,1,2,3], k = 2 output: false
The sliding windowCopy the codeclass Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if(set.contains(nums[i])){
return true;
}
set.add(nums[i]);
if(set.size() == k+1){ set.remove(nums[i - k]); }}return false; }}Copy the code220. Presence of repeated element III
Given an integer array, judge whether there are two different indexes I and J in array such that the absolute values of the difference between NUMs [I] and nums [j] are maximum k, and the absolute values of the difference between I and J are maximum K.
Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0
Input: nums = [1,0,1,1], k = 1, t = 2
Input: nums = [1,5,9,1,5,9], k = 2, t = 3 output: false
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
// The slider window is the lookup table itself (control the size of the lookup table).
TreeSet<Long> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
// add and find
If nums[I] -t is greater than nums[I] -t and less than nums[I] + t
Long ceiling = set.ceiling((long) nums[i] - (long) t);
if(ceiling ! =null && ceiling <= ((long) nums[i] + (long) t)) {
return true;
}
// Control the size of the lookup table (window) and remove the left-most element of the window
set.add((long) nums[i]);
if (set.size() == k + 1) {
set.remove((long) nums[i - k]); }}return false; }}Copy the code