overview
LeetCode Hot: realize Trie (prefix tree), the K largest element in the array, the largest square, flip binary tree, palindrome linked list, the nearest common ancestor of binary tree, the product of arrays other than itself, the maximum value of sliding window, search two-dimensional matrix II and complete square number
LeetCode Hot
2.61 implementation of Trie (prefix tree)
Trie (pronounced like "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in string data sets. This data structure has many application scenarios, such as automatic completion and spell checking.
Please implement the Trie class:
Trie() initializes the prefix tree object.
void insert(String word) inserts the string word into the prefix tree.
boolean search(String word) returns true if the string word is in the prefix tree (that is, it has been inserted before retrieval); Otherwise, false is returned.
boolean startsWith(String prefix) returns true if one of the prefixes of the previously inserted string word is prefix; Otherwise, false is returned.
Example:
input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
output
[null, null, true, false, true, null, true]
explain
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // Return True
trie.search("app"); // Return False
trie.startsWith("app"); // Return True
trie.insert("app");
trie.search("app"); // Return True
class Trie {
class TireNode { //26 fork tree
private boolean isEnd;
TireNode[] next;
public TireNode() {
isEnd = false; //Is this node the end of a string
next = new TireNode[26];//Alphabet mapping table
}
}
private TireNode root;
public Trie() {
root = new TireNode();
}
//This operation is very similar to building a linked list. First, match the first character of word from the child node of the root node until there is no corresponding character on the prefix chain. At this time, continue to open up new nodes until the last character of word is inserted. At the same time, the last node isEnd = true;, Indicates that it is the end of a word.
public void insert(String word) {
TireNode node = root;
for (char c : word.toCharArray()) {
if (node.next[c - 'a'] == null) {
node.next[c - 'a'] = new TireNode();
}
node = node.next[c - 'a'];
}
node.isEnd = true;
}
//Start from the child node of the root node and match it all the way down. If the node value is empty, false will be returned. If the last character is matched, we just need to judge node - > Isend.
public boolean search(String word) {
TireNode node = root;
for (char c : word.toCharArray()) {
node = node.next[c - 'a'];
if (node == null) {
return false;
}
}
return node.isEnd;
}
//Similar to the search operation, it is only unnecessary to judge the isEnd of the last character node, because since the last character can be matched, there must be a word prefixed with it.
public boolean startsWith(String prefix) {
TireNode node = root;
for (char c : prefix.toCharArray()) {
node = node.next[c - 'a'];
if (node == null) {
return false;
}
}
return true;
}
}
2.62 the kth largest element in the array
Given the integer array nums and integer k, please return the K largest element in the array.
Please note that you need to find the K largest element after the array is sorted, not the k different element.
Example 1: input: [3,2,1,5,6,4] and k = 2 output: 5
//Treatment based on rapid elimination and reduction
public class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
int left = 0;
int right = len - 1;
// The subscript of the k-th element is len - k
int target = len - k;
while (true) {
int index = partition(nums, left, right);
if (index == target) {
return nums[index];
} else if (index < target) {
left = index + 1;
} else {
right = index - 1;
}
}
}
/**
* Perform the partition operation on the sub interval [left..right] of the array num, and return the position where num [left] should be after sorting
* Definition of keeping loop invariants during traversal:
* nums[left + 1..j] < nums[left]
* nums(j..i) >= nums[left]
*/
public int partition(int[] nums, int left, int right) {
int pivot = nums[left];
int j = left;
for (int i = left + 1; i <= right; i++) {
if (nums[i] < pivot) {
// The initial value of j is left. Move it to the right first and then exchange it. All elements less than pivot are exchanged to the front
j++;
swap(nums, j, i);
}
}
// During the previous traversal, satisfy num [left + 1.. J] < pivot, and num (J.. I) > = pivot
swap(nums, j, left);
// After exchange, Num [left.. J - 1] < pivot, Num [J] = pivot, Num [J + 1.. right] > = pivot
return j;
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
2.63 maximum square
In a two-dimensional matrix consisting of '0' and '1', find the largest square containing only '1' and return its area.
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 4
//DP
//Let dp(i,j) represent the maximum side length of a square with (i,j) as the lower right corner and containing only 1.
//If the value of this position is 1, the value of dp(i,j) is determined by the dp values of the three adjacent positions above, to the left and to the left. Specifically, the element value of the current position is equal to the minimum value of the elements of three adjacent positions plus 1
//State transition equation: dp(i,j)=min(dp(i − 1,j),dp(i − 1,j − 1),dp(i,j − 1)) + 1
class Solution {
public int maximalSquare(char[][] matrix) {
int maxSide = 0;
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int rows = matrix.length, columns = matrix[0].length;
int[][] dp = new int[rows][columns];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) { //Can only be 1 on the boundary
dp[i][j] = 1;
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
}
2.64 flip binary tree
Recursive solution to offer25 problem of tongjianzhi
2.65 palindrome linked list
Give you the head node of a single linked list. Please judge whether the linked list is a palindrome linked list. If yes, return true; Otherwise, false is returned.
Input: head = [1,2,2,1] Output: true
//Speed pointer, reverse linked list
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
// Find the tail node of the first half of the linked list and reverse the second half of the linked list
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
// Judge whether palindrome
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
// Restore linked list and return results
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
//Reverse linked list
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
//Through the speed pointer, when fast is finished, slow is right in the middle of the linked list
private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
2.66 nearest common ancestor of binary tree
Recursive solution to offer74 problem of tongjianzhi
1.67 product of arrays other than itself
Same sword finger offer71 question
2.68 maximum value of sliding window
Monotonic queue of offer 61 with sword finger
2.69 search two-dimensional matrix II
Same sword finger offer2 question
2.70 perfect square
Give you an integer n and return the minimum number of complete squares with a sum of n.
A perfect square is an integer whose value is equal to the square of another integer; In other words, its value is equal to the product of the self multiplication of an integer. For example, 1, 4, 9, and 16 are perfect squares, while 3 and 11 are not.
Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4
//DP
//Dynamic transfer equation: DP [i] = math Min (DP [i], DP [I - j*j] + 1), DP [i-j*j] find a j, subtract j*j, and i-j*j remains. Continue to find the square of the least quantity, and add J (+ 1) this time
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1]; // The default initialization value is 0
for (int i = 1; i <= n; i++) {
dp[i] = i; // The worst case scenario is + 1 (1 * 1) each time
for (int j = 1; i >= j * j; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // Dynamic transfer equation
}
}
return dp[n];
}
}
summary
1. Because some questions of LeetCode Hot are selected from sword finger offer, there will be repetition, so don't write them repeatedly. Brush the questions all day later and try to finish Hot100 questions before the 20th;
2. Now some large factories have launched internal promotion and spring recruitment online application.