1.Hash related
When using HashMap, why can you find the corresponding value according to map.get(key) with time complexity O(1)?
Because the physical structure uses a hash table
Calculate the array position where the Entry should be stored according to a special algorithm. If the positions are the same, there are various methods to solve the conflict and find the value after the conflict

Press button T387 to find the first non repeating character of the string and return its index
Using hash, value can put all kinds of things, such as the position of the first occurrence. If it occurs many times, it will be set to  1. Hash storage is not sequential, but it can be found as quickly as possible, O(1)

q49 letter ectopic word grouping
The meaning of the title is to group the abc,bac,cab... Of the string array
When this type thinks of hash, it first thinks of what is the key and what is the value
Keys are unique. The only common point of the same group is that their letters and times are unique, but their positions are different. This is the most key point in solving problems
 Alphabetical as key
 The number of times the same letter appears as the key
Knowledge points:
 String key = String(array) is better than String.valueOf(array) is better than array.toString
 valueOf can prevent the array from being null, but it will be converted to the string "null"
 Many types of conversions cannot be forced. Generally, new is a required type, and then new is added at the same time

Subarray with q560 and K
Hash + sub prefix method. In the hash array, the key stores the sum of all arrays from the beginning to this position in the traversal process, and value is the number of occurrences
Pre is the sum of all previous elements, from j to I = > pre [j − 1]==pre[i] − k
For example, if the sum of the first six elements is 14 and the goal is to find 7, then map.get(147) to see how many elements meet the sum of 7 from the beginning to a certain location
[external link image transfer failed. The source station may have an antitheft chain mechanism. It is recommended to save the image and upload it directly (imggxx8vv501637714619647) (C: / users / chenzhijian / appdata / roaming / typora / typora user images / image20211111202134415. PNG)]
public int subarraySum(int[] nums, int k) { int count = 0; Map<Integer, Integer> map = new HashMap<>(); map.put(0 ,1); int pre = 0; for (int i = 0; i < nums.length; i++) { pre += nums[i]; if (map.containsKey(pre  k)) { count+=map.get(pre  k); } map.put(pre, map.getOrDefault(pre, 0) + 1); } return count; }
2. Linked list operation

Force buckle T19, traverse and delete the penultimate node of the linked list
Pay attention to the special case of deleting the head node

Force buckle T206 reverse linked list
The most common method is to use the iterative method of three pointers (including head pointer) to save the front and rear nodes with pointers. Pay attention to prevent null pointer exception when defining multiple pointers at the beginning
if(head == null  head.next == null){ return head; }
This is not too stupid, so you don't have to judge with a non null pointer
ListNode pre = null, p = head; while (p != null) { ListNode next = p.next; p.next = pre; pre = p; p = next; } return pre;
Recursive methods are difficult to understand
public ListNode reverseList(ListNode head) { //Recursive exit. This head==null prevents the ListNode linked list provided from being empty and should be written in front to prevent null pointer exceptions if (head == null  head.next == null){ return head; } //This newHead has not changed from beginning to end. It is the first node of the result ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; }

Force buckle T61 rotation linked list (right translation linked list)
At the beginning, inspired by the reverse linked list, I wrote a method to reverse the linked list, which was done by translating the array. However, the code is very complex, and it is prone to null pointers and linked list ring exceptions. After looking at the force buckle solution, I originally made the linked list ring and then disconnected. Can I define three more pointers and traverse the method only once

Sword fingers t25 merge two sorted linked lists
You can use the recursive method to understand the idea of recursion through this question

Copy of sword finger t35 complex linked list

Method with high time complexity
 Copy the trunk first
 Find the point pointed by the pointer from scratch, complexity O(n ²)

Trade space for time

Store the corresponding relationship between the original node and the node in the map

Copying pointers through relationships
while(cur != null) { map.get(cur).next = map.get(cur.next); map.get(cur).random = map.get(cur.random); cur = cur.next; }



Q442 returns the first node of the ring linked list
The simplest way is to store each node in the hashset, and the repeated answer is the answer
If O(1) space is required, the mathematical column formula is deduced
a+n(b+c)+b=a+(n+1)b+nca+n(b+c)+b=a+(n+1)b+nc
a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)
When we find that slow meets fast, we use an additional pointer ptr. At first, it points to the head of the linked list; then, it and slow move back one position at a time. Finally, they will meet at the entry point
// Fast! = null cannot be used as the condition here. There may not be a ring while (fast != null) { slow = slow.next; if (fast.next != null) { fast = fast.next.next; } else { return null; } if (fast == slow) { ListNode p = head; while (p != slow) { p = p.next; slow = slow.next; } return p; } }

LRU caching mechanism
You are required to encapsulate a class. You need to use a hash table and a twoway linked list. In fact, java has a similar data structure, LinkedHashMap
The hash table is used to quickly find the nodes in the twoway linked list. The latest inserted or found nodes are placed at the head of the twoway linked list. If the space is full, the nodes in the tail will be eliminated. It is very convenient to use pseudo head and pseudo tail nodes
I just don't understand how this class can be defined like this. The foundation is not good
There are two things I didn't consider
 Get the value from the map through the key. What if the new put node exists
 After deleting nodes from the list, the nodes in the corresponding map should also be deleted
public class LRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() {} public DLinkedNode(int _key, int _value) { key = _key; value = _value; } } private int size; private int capacity; private Map<Integer, DLinkedNode> cache = new HashMap<>(); private DLinkedNode head; private DLinkedNode tail; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head; } public int get(int key) { // Use hashmap to determine whether there is if (cache.containsKey(key)) { // Find the corresponding node of DLinkedNode through hashmap DLinkedNode node = cache.get(key); // Move the node to the header moveToHead(node); return node.value; } else { return 1; } } public void put(int key, int value) { DLinkedNode node = cache.get(key); if (node == null) { // Put it into hashmap first DLinkedNode newNode = new DLinkedNode(key, value); cache.put(key, newNode); // Determine whether it is full if (size == capacity) { DLinkedNode tail = removeTail(); cache.remove(tail.key); size; } addToHead(newNode); size++; } else { node.value = value; moveToHead(node); } } ... }

q148 sorting linked list
Analysis: the sorting time complexity of O(nlogn) includes fast, hope, return and heap. Only merge sorting conforms to the linked list. Topdown recursive merge is simpler, but the space complexity depends on the stack space of recursive call. Bottomup recursion can achieve O(1)

recursion
Recursion before merging
Odd nodes find the midpoint, even nodes find the node on the left of the center, and then cut off from the back
The combination uses to create a pseudo head node first, and the smaller of the two linked lists will be followed by it
public ListNode sortList(ListNode head) { if (head == null  head.next == null) { return head; } // Find the middle point through the fast and slow pointer ListNode slow = head, fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode tmp = slow.next; slow.next = null; ListNode lHead = sortList(head); ListNode rHead = sortList(tmp); // merge ListNode nHead = merge(lHead, rHead); return nHead; } private ListNode merge(ListNode p, ListNode q) { ListNode fakeHead = new ListNode(0); ListNode temp = fakeHead; while (p != null && q != null) { if (p.val <= q.val) { temp.next = p; p = p.next; } else { temp.next = q; q = q.next; } temp = temp.next; } if (p != null) { temp.next = p; } else { temp.next = q; } return fakeHead.next; }

Iteration is really complex, and the details are difficult to grasp
Use the for (int sublength = 1; sublength < length; sublength < < = 1) cycle. In the first cycle, each group has one node, which is to split all the nodes in the linked list, sort left and right and merge them into two groups. In the second cycle, each group has two nodes, and then sort and merge them into four or four groups
Do it later


q160 intersecting linked list
There are many ways

First get the long length  the short length a, the long pointer goes the length a, and then go together

Store the nodes in hashset

A's individual length m, B's individual length N, and the common length C. If a can't complete the interaction to B, B can't complete the interaction to a, then it is empty at the same time. m+c+n = n+c+m
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null  headB == null) { return null; } ListNode p = headA, q = headB; while (p != q) { p = p == null ? headB : p.next; q = q == null ? headA : q.next; } return p; }


q234 palindrome linked list

If the time complexity is not limited, you can directly copy the linked list into the array and then judge

Limit the time complexity to O(1). First find the midpoint through the fast and slow pointer, and then reverse and compare the subsequent linked list. If the original structure cannot be changed, reverse and restore again
public boolean isPalindrome(ListNode head) { if (head == null) { return true; } // The speed pointer finds the midpoint ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } ListNode newHead = reverse(slow.next); ListNode p1 = head; ListNode p2 = newHead; // p2.length == p1 or p11 while (p2 != null) { if (p1.val != p2.val) { return false; } p1 = p1.next; p2 = p2.next; } return true; } // Operation method of transferring linked list private ListNode reverse(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; } return prev; }


Copy of sword finger t35 complex linked list

Connect the old and new nodes through map
if (head == null) { return null; } Node node = head; Map<Node, Node> map = new HashMap<>(); while (node != null) { Node newNode = new Node(node.val); map.put(node, newNode); node = node.next; } node = head; Node newHead = map.get(head); while (node != null) { Node newNode = map.get(node); newNode.next = map.get(node.next); newNode.random = map.get(node.random); node = node.next; } return newHead;

Recursive writing of method 1
if (!map.containsKey(head)) { Node newHead = new Node(head.val); map.put(head, newHead); newHead.next = copyRandomList(head.next); newHead.random = copyRandomList(head.random); } return map.get(head);

Method 2: connect them together and then disassemble them
// New and connect for (Node p = head; p != null; p = p.next.next) { Node node = new Node(p.val); node.next = p.next; p.next = node; } // Find random pointer position for (Node p = head; p != null; p = p.next.next) { if (p.random != null) { p.next.random = p.random.next; } } // separate Node newHead = head.next; for (Node p = head, q = newHead; p != null; p = p.next, q = q.next) { p.next = q.next; if (p.next != null) { q.next = p.next.next; } } return newHead;

3. Double pointer
When we need to enumerate two elements in the array, if we find that the second element decreases with the increase of the first element, we can use the double pointer method to reduce the time complexity of enumeration from O(N^2) to O(N)

q11 container with the most water
I thought that the simple method was just to walk in at the same time. If you encounter a shorter jump, you can walk in at the same time

q15 sum of three numbers
After a few hours, there are still various problems... The violence method needs a triple loop. If you use double pointers, the time complexity can be reduced to O(n) ²), Under the second for loop, the right pointer only needs to move to the left (the first for loop needs to update the right pointer to the rightmost every time). As long as we consider the traversal process of the first two pointers, we should pay attention to some problems: the order of the three pointers cannot be changed. If two identical numbers are together, we should skip the first for loop.
We also encountered an empty array exception similar to the null pointer exception. Before writing num [I1], we must ensure that I > 0 is written to its left
if(i>0 && nums[i] == nums[i1])

q16 the sum of the three closest trees
It is similar to the previous question, but I accidentally wrote it into a triple cycle. It is also similar to q11. Temporarily fix the first one, the other two go to the middle, and the first one goes back

The penultimate node in the sword finger t22 lin k ed list (pay attention to robustness)
 The linked list cannot be empty
 k will not 0
 k is not greater than the length of the linked list

Find the first node of the link in the linked list
 The fast and slow pointer finds the first node where the pointer meets first
 The number of nodes in the ring is calculated from this node
 In the double pointer, the previous pointer first goes through the nodes of the loop and then steps together until it meets

Q441 circular linked list

In the Hash table method, it can store linked list nodes directly, not only numbers. It is more convenient to use HashSet here, because repeated storage will directly false, which is less than ArrayList

Tortoise and rabbit race
However, for fast and slow pointers, pay more attention to null pointer exceptions. You should not only judge at the beginning, but also judge whether the fast pointer has reached the tail node or whether the next pointer has reached the tail node


q438 find all letter words in the string

sliding window
 Because the characters in the string are all lowercase letters, an array with a length of 26 can be used to record the number of letters
 Let n = len(s), m = len §. Record the letter frequency p_cnt of the P string and the frequency s_cnt of the first m letters of the s string
 If p_cnt and s_cnt are equal, the first ectopic word index 0 is found
 Continue to traverse the letter of s string index [m, n), add a new letter in s_cnt each time, and remove an old letter
 Judge whether p_cnt and s_cnt are equal. If they are equal, add an ectopic word index i  m + 1 in the return value res
public List<Integer> findAnagrams(String s, String p) { List<Integer> list = new ArrayList<>(); int n = s.length(); int m = p.length(); // This situation has been forgotten if (n < m) { return list; } int[] sArr = new int[26]; int[] pArr = new int[26]; for (int i = 0; i < m; i++) { sArr[s.charAt(i)  'a'] += 1; pArr[p.charAt(i)  'a'] += 1; } if (Arrays.equals(sArr, pArr)) { list.add(0); } for (int i = m; i < n; i++) { sArr[s.charAt(im)  'a'] = 1; sArr[s.charAt(i)  'a'] += 1; if (Arrays.equals(sArr, pArr)) { list.add(im+1); } } return list; }

Double pointer

4. String operation

q14 longest common prefix
Generally, those without systematic training choose vertical brute force cracking, which is compared one by one. However, although my brute force cracking is successful, it is too complex. The subsequent ones only need to be equal to the corresponding characters of the first string. Moreover, the end condition of the first for loop condition can be temporarily subject to the length of the first string. When entering later, judge whether it exceeds this limit String length to compare when
Many test cases are not considered
 Non null judgment
 There is only one element in the array
 Judgment of other situations
There are many ingenious methods to use strings, such as startsWith and substring
public String longestCommonPrefix(String[] strs) { if(strs.length==0)return ""; //The common prefix is shorter than all strings. Choose any one first String s=strs[0]; for (String string : strs) { while(!string.startsWith(s)){ if(s.length()==0)return ""; //If the public prefix does not match, make it shorter! s=s.substring(0,s.length()1); } } return s; }

q763 divide letter interval
There is an idea that needs to be studied. If you already know that it is a fixed length structure such as letters or numbers, you can directly use the int array: arr[S.charAt(i)  'a'], so that arr[0] corresponds to a
First get the int array corresponding to the last position of the letter. Judge whether the last position of the letter scanned locally is larger than the current one. If so, update and expand the end condition of the while loop
int i=0,k; while (i < S.length()) { k = S.charAt(i)'a'; int cur = i; while (i<=last[k]){ if(last[S.charAt(i)'a']>last[k]){ k = S.charAt(i)'a'; } i++; } list.add(i  cur); }

q6 Z font transformation
The most concise solution is really too brainy. How can you think of something you haven't seen? Let flag participate in the calculation
public String convert(String s, int numRows) { if(numRows < 2) return s; List<StringBuilder> rows = new ArrayList<StringBuilder>(); for(int i = 0; i < numRows; i++){ rows.add(new StringBuilder()); } int i = 0, flag = 1; for(char c : s.toCharArray()) { rows.get(i).append(c); if(i == 0  i == numRows 1) flag =  flag; i += flag; } StringBuilder res = new StringBuilder(); for(StringBuilder row : rows) res.append(row); return res.toString(); }
At first, I didn't want to define Arraylist. I wanted to use StringBuider array. It was found that if the initial value of the array was null, I couldn't use the. append method. Instead, I changed it to String array, but in the first round, I had to assign an empty String first. Otherwise, if I used "" + c, the first bit would be null and an error would be reported. This can succeed, but the increase or decrease cost of String array is too large. It's not as good as list

The sword finger t17 prints from 1 to the maximum n digits
 n may be very large. The number type will be removed and the string will be used instead. The large number problem
 Optimize to quickly determine whether the maximum bit is reached, and use the O(1) method to optimize the output code
 It should also be noted that the previous zero is not output for the user experience
 Full Permutation (in doubt)

q3 longest substring without duplicate characters
You can use set and map
//In the sliding window, i is the beginning and end is the end for (int i = 0; i < len; i++) { while (end<len && !occ.contains(s.charAt(end))){ occ.add(s.charAt(end)); if((endi+1)>max){ max = endi+1; } end++; } occ.remove(s.charAt(i)); }
mistake
 If end is ignored before, it will not move forward, and the complexity of full emptying set is high
 The length judgment in while should be put in front to prevent crossing the boundary

q394 string encoding

There are many details about stack operation, but it's not difficult to understand. When you encounter '[' into the stack, when you encounter ']', start decoding this paragraph. See the notes for details
Summary:
 StringBuilder can easily operate a single character without defining a large collection
 Character.isLetter is the api to determine whether it is a character
public String decodeString(String s) { // Scan it first and put it on the stack except ']' Stack<Character> stack = new Stack<>(); for (char c : s.toCharArray()) { if (c != ']') { stack.push(c); } else { //Find letter position StringBuilder sb = new StringBuilder(); while (!stack.isEmpty() && Character.isLetter(stack.peek())) { sb.insert(0, stack.pop()); } stack.pop(); // Remove '[' String sub = sb.toString(); //Find digit sb = new StringBuilder(); while (!stack.isEmpty() && Character.isDigit(stack.peek())) { sb.insert(0, stack.pop()); } // StringBuild => String => Integer int count = Integer.valueOf(sb.toString()); while (count > 0) { for (char ch : sub.toCharArray()) { stack.push(ch); } count; } } } // Convert all the letters in the stack into String StringBuilder retv = new StringBuilder(); while (!stack.isEmpty()) { retv.insert(0, stack.pop()); } return retv.toString(); }
The above is the international version of the praise code, which is really better understood than the official analysis of the Chinese website


q647 palindrome substring
Traverse from the middle to both sides to judge the qualified quantity. Both odd and even numbers should be considered
public int countSubstrings(String s) { int num = 0; int n = s.length(); for (int i = 0; i < n; i++) { for (int j = 0; j <= 1; j++) { int l = i, r = i+j; while (l>=0 && r<=n1 && s.charAt(l) == s.charAt(r++)) { num++; } } } return num; }

The sword finger t45 arranges the array into the smallest number
First, convert the number into a string array, and sort the string array using java's campareTo method and fast sorting
public String minNumber(int[] nums) { // First convert the nums array into a string array String[] strs = new String[nums.length]; for (int i = 0; i < nums.length; i++) { strs[i] = String.valueOf(nums[i]); } quickSort(strs, 0, nums.length1); // String splicing is not recommended. It needs to be copied again, which is slow StringBuilder res = new StringBuilder(); for (String str : strs) { res.append(str); } return res.toString(); } // Standard writing of fast row private void quickSort(String[] strs, int low, int high) { if (low < high) { int middle = getMiddle(strs, low, high); quickSort(strs, low, middle  1); quickSort(strs, middle + 1, high); } } private int getMiddle(String[] strs, int i, int j) { // Select the left boundary as the pivot String tmp = strs[i]; while (i < j) { while (i < j && (strs[j] + tmp).compareTo(tmp + strs[j]) >= 0) j; strs[i] = strs[j]; while (i < j && (strs[i] + tmp).compareTo(tmp + strs[i]) <= 0) i++; strs[j] = strs[i]; } strs[i] = tmp; return i; }
5. Digital operation

q7 integer inversion (my weakness)
For some prior knowledge, the int of java type is 32 bits, and negative numbers can display one bit more than positive numbers. Interger.MAX_VALUE = 2147483647 is used
At each step, judge whether the size exceeds the limit. Do not save the middle as an array. Directly rev = rev * 10 + pop
If you can use long, it won't be so troublesome, because it won't overflow anyway. You can get the result and compare it with Interger.MAX_VALUE

q9 palindromes
Be proficient in the inversion code of numbers and understand all special situations
Special case: the last number is 0, odd or even, negative, and exceeds the maximum value of int during inversion
This question is half reversed
while (x>revertedNumber){ int k = x % 10; revertedNumber = revertedNumber *10 + k; x /= 10; }

The integral power of sword finger t16 value
 The simple solution to the problem did not take into account many special situations
 Considering special cases, exceptions are passed to global variables
 Recursion, the 16th power can be regarded as the 8th power rediscovery

q31 next spread

Traverse from back to front to find the first non descending number i

Judge whether i > 0, otherwise execute 5 directly (i have an error in processing here)

Traverse from back to front to find the first number j greater than i

Swap i, j

Number after inverting i+1

Code optimization
while (i>=0){ if(nums[i+1] > nums[i]){ break; } i; } // Can be optimized to while (i>=0 && nums[i] >= nums[i + 1]){ i; }


q33 search rotation sort array
To make the event complexity O(log n), use binary search. Half of the binary search is ordered. Pay attention to the boundary problem
code:
public int search(int[] nums, int target) { int n = nums.length; int l = 0, r = n  1; if(n == 0){ return 1; } if(n == 1){ return nums[0]==target?0:1; } // Note the boundary conditions, when less than, when less than or equal to while (l <= r){ int mid = (l+r)/2; if(nums[mid] == target){ return mid; } // If the left is sequential; You must add equal to because in the case of only two numbers, 0==mid if(nums[0]<=nums[mid]){ // This is left closed and right open if(nums[l]<=target && target<nums[mid]){ r = mid1; } else { l = mid+1; } } // If the right side is sequential, check from the right side else { if(nums[mid]<target && target<=nums[n1]){ l = mid+1; } else { r = mid1; } } } return 1; }
Summary:
 For the middle number, the subscript is generally (length1)/2. In the case of even numbers, it is customary to lose some in the first half. However, if only the left and right are divided, the middle number will be divided to the left
 The left and right pointer loop exit conditions are left < = right
 Pay attention to when it is less than or equal to, and you can't let go of any situation

q34 finds the first and last positions of elements in a sorted array
The same dichotomy is used to find the subscript of the first element greater than target with the adapted dichotomy
int leftIdx = binarySearch(nums, target1); int rightIdx = binarySearch(nums, target)1;
// Binary search to find the first numeric subscript greater than target public int binarySearch(int[] nums, int target){ int left = 0, right = nums.length 1, ans = nums.length; while (left <= right){ int mid = (left+right)/2; // Why is there no equal to? Because it is greater than, it is put in the else below if(nums[mid]>target){ right = mid1; ans = mid; } else { left = mid + 1; } } return ans; }

q48 rotate image
Rotation in place is required. Temporary array cannot be returned
The simplest way is to overwrite the original array with the temporary array, but it's certainly not good
The best solution is to rotate the horizontal axis first, and then the main diagonal (don't rotate all one side in the process, so the value won't change)

q75 color classification
It is a special case of fast platoon to get the result in place and again. 1 is the middle number. If there is no requirement to traverse only once, directly find 1 as the sentry first.
Summary write quick sort: select a flag. After each traversal, the smaller one is on its left, the larger one is on its right, and the flag is in its final position. Divide and conquer left and right recursively to get the result

The concept of loop invariants, find the loop invariants of this problem, and it is best to write notes
//all in [p0,i) = 0 //all in [i,p2) = 1 //all in [p2,len1] = 2

A single pointer needs to be traversed twice, and a double pointer can only be traversed once
while (i <= p2) { if (nums[i] == 0) { //The exchange cannot be 0 swap(nums, i++, p0); p0++; } else if (nums[i] == 1) { //1 don't worry i++; } else if (nums[i] == 2) { //The exchange may be 2, so i can't add one swap(nums, i, p2); p2; } }


q128 longest continuous sequence
Linear time complexity required
 You must first put the original array into the hashset and arrange the duplication by the way
 Judge from the beginning. When you get each bit, you should constantly go to the one bit larger than it until the end to traverse whether it exists. If it exists, add one to the number
 Because inner traversal is still O(n ²)， Therefore, it is necessary to judge in the middle of the outer traversal. Only the smaller bit of the current number exists can enter the inner traversal
public int longestConsecutive(int[] nums) { // Save to hashset Set<Integer> num_set = new HashSet<>(); for (int num : nums) { num_set.add(num); } int longestStreak = 0; for (int num : num_set) { if (!num_set.contains(num1)) { int currentStreak = num; int currentNum = 1; while (num_set.contains(currentStreak + 1)) { currentStreak+=1; currentNum+=1; } longestStreak = Math.max(currentNum, longestStreak); } } return longestStreak; }

q169 most elements

Hash table save times

Sort first, and the last median element is the result

Randomize, randomly select a number in the middle each time, and traverse whether the count occupies more than half of the length

Divide and conquer, seek the mode from the top to the bottom

Voting algorithm, a little impression before. It can be proved
Voting algorithm proof:
 If the candidate is not a maj, maj will oppose the candidate together with other non candidates, so the candidate will step down (a general election occurs when maj==0)
 If the candidate is a maj, maj will support himself and other candidates will oppose him. Similarly, maj will be elected successfully because maj has more than half of the votes
nums: [7, 7, 5, 7, 5, 1  5, 7  5, 5, 7, 7  7, 7, 7, 7]
candidate: 7 7 7 7 7 7 5 5 5 5 5 5 7 7 7 7
count: 1 2 1 2 1 0 1 0 1 2 1 0 1 2 3 4if (nums[i] == candidate) { count++; } else { count; if (count < 0) { candidate = nums[i]; count = 1; } }
The optimization code is
if (count == 0) { candidate = nums[i]; } count += nums[i] == candidate ? 1 : 1;

6. Array operation

q238 product of arrays other than itself
It is required that division cannot be used, and it should be completed in O(n), with the lowest spatial complexity
Define two arrays, one is the product of all numbers on the left of the current index, and the other is the product of all numbers on the right. The endpoint value is 1. The result array is the multiplication of the two arrays
The second array can operate at the position of the first array
public int[] productExceptSelf(int[] nums) { int len = nums.length; if (len == 0) { return null; } int res[] = new int[len]; res[0] = 1; for (int i = 1; i < len; i++) { res[i] = res[i1] * nums[i1]; } int R = 1; for (int i = len  1; i >= 0; i) { res[i] = res[i] * R; R *= nums[i]; } return res; }

q240 search twodimensional matrix

Use binary lookup for each row
for (int[] row : matrix)
The loop condition of binary search is while (left < = right)

Z igzag
Starting from the upper right corner, the larger one moves to the left and the smaller one moves to the right


q4 find the median of two ordered arrays

analysis
Sort first and then search in sequence. The event complexity is O(m+n). log(m+n) is required. Only two points can be used, one small half and one small half can be excluded

step
 If the median should be the smallest k (even number is the average of the middle two numbers), define a function to find the smallest k in the two arrays
 Compare the last sliding window sequence number in the two arrays, exclude the k/2 number of the smaller one each time, and refresh k

summary
 Pay attention to the boundary condition, k=1 or at the end of the sequence number, you can get the answer directly
 In the future, half of this exclusion is generally k/21, so as to ensure safety under the condition of excluding as many as possible
 The final answer is that int is calculated as double, and finally divided by 2.0


q56 merge interval
There are many things to learn about this problem

Two dimensional array sorting, using the method of overriding the Comparator interface

Common method
//First, sort the twodimensional array according to the size of the left boundary for (int i = 0; i < intervals.length1; i++) { if(intervals[i][0]>intervals[i+1][0]){ for (int j = 0; j < 2; j++) { } } }

Good way
Arrays.sort(intervals, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[0]o2[0]; } });
0 in brackets represents column 0, left minus right represents ascending order, and ordinary onedimensional array sorting without brackets


Conversion between arrays and collections

It's better to convert the array to the collection by a for loop and add one by one (if the asList method is an array, it must be a reference type)

The. toArray method can be used to convert a collection to an array, with the parameters that need to be converted to (Object type without parameters)

If there is an array to connect, the size of arrays initialization is arbitrary. If it is directly converted internally, it must be initialized to list.size(), otherwise the array length will be extended and zero will be filled later. See the following source code for details
public <T> T[] toArray(T[] a) { if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; }

int[] nums = new int[3]; List<Integer> list = new ArrayList<Integer>(){}; list.add(1); list.add(2); list.add(3); // Integer[] arrays = new Integer[0]; // Integer[] we = list.toArray(arrays); // System.out.println(we[2]); Integer[] arrays = new Integer[list.size()]; list.toArray(arrays); System.out.println(arrays[3]);
 Object [] cannot be converted to String []. To convert, you can only take out each element and convert it again. The forced type conversion in java is only for a single object. You can't be lazy to convert the whole array into another type of array, which is similar to the need to initialize the array one by one.



q283 move zero
I can't do simple questions, that is, double pointers. Both pointers start from the 0 position. The right pointer is responsible for finding nonzero numbers, and the left pointer is responsible for pointing to the last position in a fixed sequence
public void moveZeroes(int[] nums) { int i = 0, j = 0; while (j < nums.length) { if (nums[j] != 0) { swap(nums, i, j); i++; } j++; } }

q287 finding duplicate arrays

My method is to create an array of the same length, traverse a value, and assign it as the value of the array index to 1. If I find the index value again, I find that it is not 0. But this is not a constant space
public int findDuplicate(int[] nums) { int n = nums.length; int[] ind = new int[n]; for (int i = 0; i < n; i++) { if (ind[nums[i]1] != 0) { return nums[i]; } ind[nums[i]1] = 1; } return 0; }

Speed pointer
Construct a graph for the nums array, and each position I is connected with an edge of I → nums[i]. Because there is a duplicate number target, the position of target must have at least two edges pointing to its value. Therefore, there must be a ring in the whole graph, and then use the previous ring linked list method to find the entry of the ring

dichotomy
I don't quite understand for the moment. When it is an ordered array, take left = 1, right = len  1 directly, and then calculate Mid. the result is equivalent to sorting and then calculating mid?


q347 top K high frequency elements, same type: Sword finger t40

Using hash + small top heap, hash thought of it. I don't know how to optimize with small top heap
PriorityQueue is a heap api in java. It traverses the number of occurrences of each number in the hash. If it is larger than the small top heap, it will be replaced
public int[] topKFrequent(int[] nums, int k) { // Store each element and its number of occurrences in the hash table Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>(); for (int num : nums) { occurrences.put(num, occurrences.getOrDefault(num, 0) + 1); } // Build small root heap PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() { @Override public int compare(int[] m, int[] n) { return m[1]  n[1]; } }); // Maintain heap values for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) { int num = entry.getKey(), count = entry.getValue(); if (queue.size() == k) { if (count > queue.peek()[1]) { queue.poll(); queue.offer(new int[]{num, count}); } } else { queue.offer(new int[]{num, count}); } } // Return result array int[] res = new int[k]; for (int i = 0; i < k; i++) { res[i] = queue.poll()[0]; } return res; }

Based on the quick sort method, I'll look at it later. I understand the general meaning


q406 reconstruct the queue according to height
The installation shall be sorted from low to high first. If the height is the same, it shall be sorted according to the position from large to small, because the high always ignores the low. If the low is arranged first, it will not affect the "greater than or equal" position of the high. If the height is the same, the high "greater than or equal" value shall be arranged first, which will not affect the small value. Otherwise, it is troublesome to judge the size every time
Determine the position in the twodimensional array according to the spaces value and person[1] value
public int[][] reconstructQueue(int[][] people) { // Sort first Arrays.sort(people, (person1, person2) > { // If the two are the same, first determine the latter, and the front will not be affected if (person1[0] == person2[0]) { return person2[1]  person1[1]; } else { return person1[0]  person2[0]; } }); // Application array int n = people.length; int[][] res = new int[n][]; for (int[] person : people) { int spaces = person[1] + 1; for (int i = 0; i < n; i++) { if (res[i] == null) { spaces; } if (spaces == 0) { res[i] = person; break; } } } return res; }

q448 find all missing numbers in the array
Since the request needs to be in place, you can only use the original array. Finally, see whether the request needs to be restored
Learn this idea. Traverse the array, take each value as a subscript, and add n after finding the position. After that, the number subscript that does not disappear exceeds n, and the subscript that does not exceed is the answer. Note that the subscript calculation is: int x = (Num [i]  1)% n;

q494 objectives and

Violent backtracking, the positive and negative of each element
int count = 0; public int findTargetSumWays(int[] nums, int target) { // Violent backtracking dfs(nums, target, 0, 0); return count; } private void dfs(int[] nums, int target, int index, int sum) { if (index == nums.length) { if (sum == target) { count++; } } else { dfs(nums, target, index+1, sum  nums[index]); dfs(nums, target, index+1, sum + nums[index]); } }

Into knapsack problem
The sum of the elements added with the  sign is neg = > (sum − neg) − neg=sum − 2 ⋅ neg=target
neg=(sum−target)/2
The value in the behavior array is listed as a combined number, up to neg
Boundary condition: dp[0] [0] = 1
My three questions are shown in the following notes
public int findTargetSumWays(int[] nums, int target) { int sum = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i]; } int dif = sum  target; // 1. Forget to add this judgment if (dif < 0  dif % 2 == 1){ return 0; } int neg = dif / 2; int[][] dp = new int[nums.length + 1][neg + 1]; // boundary condition dp[0][0] = 1; for (int i = 1; i <= nums.length; i++) { for (int j = 0; j <= neg; j++) { // 2. Ignored  1 if (nums[i1] > j) { // 3. I don't remember+= dp[i][j] += dp[i1][j]; } else { dp[i][j] += dp[i1][j] + dp[i1][jnums[i1]]; } } } return dp[nums.length][neg]; }
Optimized to a onedimensional array
// boundary condition dp[0] = 1; for (int num : nums) { // Traverse from back to front, because the later ones need to use the previous calculation to prevent the previous ones from changing first // Yes > = num, not > 0 for (int j = neg; j >= num; j) { dp[j] += dp[jnum]; } } return dp[neg];


q581 shortest unordered continuous subarray

First sort the array, and then compare which places in the middle to sort

Double pointer
Find left from right to left, update min if it is less than min, mark it as left if it is greater than min, and the last left is the real left. Find right. The same is true

It is divided into three parts


q739 daily temperature

Violence, see note for details
public int[] dailyTemperatures(int[] temperatures) { // next []: the subscript for the first occurrence of each temperature. The subscript represents the temperature, and the value represents the subscript for the first occurrence // index: higher than its temperature and the nearest subscript; int n = temperatures.length; int[] next = new int[101]; int[] ans = new int[n]; Arrays.fill(next, Integer.MAX_VALUE); // Traverse from back to front for (int i = n  1; i >= 0; i) { // Find the first element after it in the next that is larger than it, such as temperatures[i] == 76 °, and find it from 77 ° // Find everything bigger than him, and then find the one closest to it int index = Integer.MAX_VALUE; for (int j = temperatures[i] + 1; j < 101; j++) { if (next[j] < index) { index = next[j]; } } // I forgot to add this before. If there is no higher temperature than that later if (index < Integer.MAX_VALUE) { ans[i] = index  i; } next[temperatures[i]] = i; } return ans; }

Monotone stack: ensure that the number in the stack decreases monotonically. If the element to be put into the stack is larger than the element at the top of the stack, then all the elements smaller than him are out of the stack, and calculate the distance to get the result
public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] ans = new int[n]; Deque<Integer> stack = new LinkedList<>(); for (int i = 0; i < n; i++) { // Compare the size of the traversed element and the top element of the stack while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int pop = stack.pop(); ans[pop] = i  pop; } stack.push(i); } return ans; }


The minimum value of sword finger t11 rotation array. See notes for details
public int minArray(int[] numbers) { int left = 0, right = numbers.length  1; while (left < right) { // In this way, the midpoint will not overflow int mid = left + (right  left) / 2; if (numbers[mid] < numbers[right]) { right = mid; } else if (numbers[mid] > numbers[right]){ // This mid cannot be the minimum value, so it can be excluded left = mid + 1; } else { // mid and right are the same, and one right can be excluded right; } } return numbers[left]; }
7. Tree operation

Substructure of sword finger t27 tree
 Recursively traverse the main tree to find nodes with the same root node value
 If the root node is the same, start to enter whether the two trees are the same recursive traversal

q98 validate binary search tree

ergodic
public boolean isValidBST(TreeNode node, long lower, long upper){ if(node == null){ return true; } if(node.val <= lower  node.val >= upper){ return false; } return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper); }
Why use long? Because the maximum value of a single node in the test case is the maximum value of lnt type

Medium order traversal
The middle order traversal of binary search tree is incremental. If you want to reduce the time complexity, use stack
To judge whether the collection is empty, you cannot use = = null, but. isEmpty or. size == 0
public boolean isValidBST(TreeNode root) { Deque<TreeNode> stack = new LinkedList<TreeNode>(); long inorder = Long.MIN_VALUE; while (!stack.isEmpty()  root != null){ while (root != null){ stack.push(root); root = root.left; } root = stack.pop(); if(root.val <= inorder){ return false; } inorder = root.val; root = root.right; } return true; }


q101 symmetric binary tree

I use the traversal order of the left and right roots and the right and left roots, and then compare the values. This is a typical error. The same result may be asymmetric trees, such as 1, 2 and 3 with only left subtrees

The first method is recursion, going left and back
public boolean isSymmetric(TreeNode root) { if(root == null) { return true; } return helper(root.left, root.right); } public boolean helper(TreeNode p, TreeNode q) { if(p == null && q == null) { return true; } if(p == null  q == null) { return false; } //If one of them is false, it is false. If all of them are true, it is true return p.val == q.val && helper(p.left, q.right) && helper(p.right, q.left); }
If all the values passed into the helper for the first time are root, the comparison times will be doubled

The second method is to iterate, using queue comparison. The left side enters the team and the right side enters the team, and the two are the same continuously
public boolean check(TreeNode u, TreeNode v) { Queue<TreeNode> q = new LinkedList<TreeNode>(); q.offer(u); q.offer(v); while (!q.isEmpty()) { u = q.poll(); v = q.poll(); if (u == null && v == null) { continue; } if ((u == null  v == null)  (u.val != v.val)) { return false; } q.offer(u.left); q.offer(v.right); q.offer(u.right); q.offer(v.left); } return true; }
If it's not recursion, then true and false are a hammer deal


Hierarchical traversal of q102 binary tree
The main purpose of using a queue is to find out which layer it belongs to. Otherwise, record each node and its level when transmitting values. In fact, you can also calculate the number of nodes in the current layer before you go out of the queue and join the children in the queue. After understanding this, you can write it without looking at the official code
A good way to write code: don't try to be perfect at the beginning. You can write it in sequence without adding a loop, and then add a loop according to the loop logic. The while loop here is added later
Two things have been changed through test cases
 In the left and right stages, you can't join the team until you judge that it can't be empty
 Judge whether the root node is empty before joining the queue
public List<List<Integer>> levelOrder(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); List<List<Integer>> res = new ArrayList<>(); List<Integer> list = new ArrayList<>(); if (root == null){ return res; } queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode p = queue.poll(); list.add(p.val); if (p.left != null) { queue.offer(p.left); } if (p.right != null) { queue.offer(p.right); } } res.add(new ArrayList<>(list)); list.clear(); } return res; }
You can optimize it again. List = new ArrayList < > (); Change to the beginning of the while loop, so only res.add(list) is used; You don't need clear

Depth of binary tree

At the beginning, I wrote a preorder traversal, but I don't remember the deepest record, g

It records the deepest layer, but the basic type of java is value transfer, which will not affect the basic type value of the main function. A global Max must be defined. this.max, g when transferring the value
int max = 0; public int maxDepth(TreeNode root) { if(root == null) { return 0; } int depth = 0; preOrder(root, depth, max); return max; } public void preOrder(TreeNode node, int depth, int max) { depth++; if (node != null){ if(depth>max){ this.max = depth; } preOrder(node.left, depth, this.max); // depth; Don't add this! Basic type, recursion will not change itself!!! preOrder(node.right, depth, this.max); // depth; } }

For this basic type of design problem, it is best to set the return value when defining the dfs function
public int maxDepth(TreeNode root) { return getDepth(root, 0); } public int getDepth(TreeNode node, int depth) { if(node == null){ return depth; } return Math.max(getDepth(node.left, depth+1), getDepth(node.right, depth+1)); }
Official explanation
public int maxDepth(TreeNode root) { if (root == null) { return 0; } else { int leftHeight = maxDepth(root.left); int rightHeight = maxDepth(root.right); return Math.max(leftHeight, rightHeight) + 1; } }

You can also use hierarchy traversal to return the last number of layers


q105 construct binary tree from preorder and inorder traversal sequences
I can only analyze, draw pictures by hand, and write code
Look at the problem solution. You can use recursion
[the external chain image transfer fails. The source station may have an antitheft chain mechanism. It is recommended to save the image and upload it directly (imgw0tk8jsz163771461965 9) (C: / users / chenzhijian / appdata / roaming / typora / typera user images / image20211021200146164. PNG)]
When building a binary tree (you can think about similar problems in this way), think macroscopically. First get the root node, and then recursively get the left node and right node of the root node. The interval of the recursive function continues to narrow until it is as small as one, get the root node (leaf node) of the deepest stack, or even go too far. Return null and start to exit the recursive stack
public TreeNode buildTree(int[] preorder, int[] inorder) { int n = inorder.length; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < n; i++) { map.put(inorder[i], i); } return myBuildTree(preorder, 0, n1, map, 0, n1); } private TreeNode myBuildTree(int[] preorder, int preLeft, int preRight, Map<Integer, Integer> map, int inLeft, int inRight) { if(preLeft > preRight  inLeft > inRight){ return null; } int rootVal = preorder[preLeft]; TreeNode root = new TreeNode(rootVal); int pIndex = map.get(rootVal); root.left = myBuildTree(preorder, preLeft+1, pIndexinLeft+preLeft, map, inLeft, pIndex1); root.right = myBuildTree(preorder, pIndexinLeft+preLeft+1, preRight, map, pIndex+1, inRight); return root; }
Here, the root node value found in the preorder traversal sequence is used to find the index corresponding to the inorder traversal sequence. The hash table is used for space for time

q114 binary tree expanded into linked list

Learn the iterative writing method of preorder traversal first
The preorder traversal of binary tree iterates to realize root left right
Idea:
1. Borrowing stack structure
2. First push(root)
3, node = pop()
3.1,list.add( node.val )
3.1,push( node.right )
3.3,push( node.left )
4. Loop step 3 until the stack is empty 
Use the first order traversal, store the nodes in the traversal order into the List, and then create a new linked List according to the original root directory address, because treenode newroot = root; The address pointed to by newroot is also the address pointed to by root, so it can also be regarded as in place. java print pointer is generally the address pointed to by the output pointer


q208 implements prefix tree
Code Trie[] children = new Trie[26]; It means to create 26 child nodes of the same type for the Trie node, and the next child node is node.children[i]
Now let's learn how to define a class
class Trie { private Trie[] children; private boolean isEnd; public Trie() { children = new Trie[26]; isEnd = false; } public void insert(String word) { Trie node = this; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); int index = c  'a'; if (node.children[index] == null) { node.children[index] = new Trie(); } node = node.children[index]; } node.isEnd = true; } public boolean search(String word) { Trie node = searchPrefix(word); return node != null && node.isEnd; } public boolean startsWith(String prefix) { return searchPrefix(prefix) != null; } private Trie searchPrefix(String prefix) { Trie node = this; for (int i = 0; i < prefix.length(); i++) { char c = prefix.charAt(i); int index = c  'a'; if (node.children[index] == null) { return null; } node = node.children[index]; } return node; } }

236 nearest common ancestor of binary tree
 Find the recursive exit, find the return node, and return null if not found
 Left's left child found, return is also left
 After this round of recursion, judge that if left does not exist, right will be returned to TreeNode right, and if right does not exist, left will be returned
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) { return null; } if (root == p  root == q) { return root; } TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p ,q); if (left == null) { return right; } if (right == null) { return left; } return root; }

q337 house raiding III
We can use f(o) to represent the maximum weight sum of the selected node on the subtree of O node when O node is selected; g(o) represents the maximum weight sum of the selected node on the subtree of the O node without selecting the O node; l and r represent the left and right children of O.
When o is selected, the left and right children of O cannot be selected, so the sum of the maximum weights of the selected points on the subtree when o is selected is the sum of the maximum weights of l and r that are not selected, that is, f(o) = g(l) + g ®
When o is not selected, the left and right children of O can be selected or not selected. For a specific child X of O, its contribution to o is the larger value of the sum of weights when x is selected and not selected. So g(o) =max{f(l),g(l)}+max{f ®, g ®}Why use followup traversal, because you must first determine the son before you can determine whether the father chooses or not

Use a hash table to store the maximum value corresponding to the tree node
public int rob(TreeNode root) { Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>(); Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>(); dfs(root, f, g); return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0)); } private void dfs(TreeNode node, Map<TreeNode, Integer> f, Map<TreeNode, Integer> g) { if (node != null) { dfs(node.left, f, g); dfs(node.right, f, g); f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0)); g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0))); } }

Omit the hash array, and only use two arrays with length of 2 to represent the left and right respectively, 0 means to select and 1 means not to select
public int rob(TreeNode root) { int[] res = dfs(root); return Math.max(res[0], res[1]); } private int[] dfs(TreeNode node) { if (node != null) { int[] l = dfs(node.left); int[] r = dfs(node.right); int selected = node.val + l[1] + r[1]; int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]); return new int[]{selected, notSelected}; } else { return new int[]{0, 0}; } }


q437 path sum III

Violence law, one dfs at each location, dfs set of dfs

Prefix, I don't understand. Keep reading
/** * Analysis of algorithm ideas *The number of paths that meet the requirements. Obviously, all paths need to be considered (traversing the tree) * Traverse the tree in depth, and find the sum cur of the path node values from the root to the current node for each node visited; (that is, the prefix sum of the node, and the node prefix sum includes itself) * At this time, HashMap has recorded the prefix sum of all nodes before the node (HashMap < prefix sum, quantity >) * By searching cur targetsum, you can know the number of solutions that end at the current node path; (in the process of traversing the tree, count the number of solutions that end at each access node, so as to obtain all solutions.) * HahsMap.put(cur ，HashMap.get(Current prefix and) + 1) * HashMap Pop up occurs when the current node recursively returns * Algorithm structure design * * For each node * When traversing down, update the HashMap first * Update (restore) HashMap on recursive return * Solve the current node solution * */ public class SoPathSum { int res=0; Map<Integer,Integer> map = new HashMap<>(); public int pathSum(TreeNode root,int targetSum){ map.put(0,1);//Each node's own value = targetSum traverse(root,0,targetSum); return res; } private void traverse(TreeNode node,int cur,int targetSum){ if(node == null){ return ; } cur+=node.val; map.put(cur,map.getOrDefault(cur,0)+1); traverse(node.left,cur,targetSum); traverse(node.right,cur,targetSum); map.put(cur,map.get(cur)1); //Process current node res+= map.getOrDefault(curtargetSum,0); } }


q538 transforms binary search tree into cumulative tree
It is reverse middle order traversal. The original return value can also be used as no return value
That's OK
class Solution { // In fact, it is more recommended not to define global traversal and define a recursive function to follow int sum = 0; public TreeNode convertBST(TreeNode root) { if (root != null) { convertBST(root.right); sum += root.val; root.val = sum; convertBST(root.left); } } }

Diameter of q543 binary tree
By recursively calculating the depth, the answer = max (left subtree depth, right subtree depth). The answer does not enter the recursion stack, but only uses the recursive process data
int ans = 0; public int diameterOfBinaryTree(TreeNode root) { depth(root); return ans; } private int depth(TreeNode node) { if (node == null) { return 0; } int L = depth(node.left); int R = depth(node.right); ans = Math.max(ans, L + R); return Math.max(L, R) + 1; }

q617 merge binary tree
Simple dfs with return value still can't write and can only be understood
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if (root1 == null) { return root2; } if (root2 == null) { return root1; } TreeNode root = new TreeNode(root1.val + root2.val); root.left = mergeTrees(root1.left, root2.left); root.right = mergeTrees(root1.right, root2.right); return root; }

Substructure of sword finger t26 tree
For two dfs, first find the same bytes as the root node of the sub tree on the main tree, and then start the dfs comparison
If the left subtree of a and the left subtree of b are empty at the same node, it is proved that the left subtree is ok, otherwise it is reverse
public boolean isSubStructure(TreeNode A, TreeNode B) { // Traverse the node of A until it is the same as the root node of B // This result is very useful in many recursions whose return value is bool type. It is applicable to success with a successful result boolean result = false; if (A != null && B != null) { if (A.val == B.val) result = reCur(A, B); if (!result) result = isSubStructure(A.left, B); // Give me another chance if (!result) result = isSubStructure(A.right, B); // Keep giving it a chance. There's an achievement anyway } return result; } private boolean reCur(TreeNode a, TreeNode b) { if (b == null) return true; if (a == null) return false; if (a.val != b.val) return false; return reCur(a.left, b.left) && reCur(a.right, b.right); }

Mirror image of sword finger t27 binary tree
public TreeNode mirrorTree(TreeNode root) { if (root == null) { return null; } // My method is also OK // TreeNode node = root.left; // root.left = root.right; // root.right = node; // mirrorTree(root.left); // mirrorTree(root.right); // This can be used as a template for binary tree recursion with return value TreeNode left = mirrorTree(root.left); TreeNode right = mirrorTree(root.right); root.left = right; root.right = left; return root; }

Sword finger t28 symmetric binary tree
I wrote it myself, but it's not beautiful enough. The annotation is the standard answer
In the future, the topic of simultaneous comparison of binary trees is that two parameters are recursive at the same time
public boolean isSymmetric(TreeNode root) { // return root == null ? true : recur(root.left, root.right); return isSymmetric(root, root); } private boolean isSymmetric(TreeNode root1, TreeNode root2) { if (root1 == null && root2 != null) return false; if (root1 != null && root2 == null) return false; if (root1 == null && root2 == null) return true; if (root1.val != root2.val) return false; // if (root1 == null && root2 == null) return true; // if (root1 == null  root2 == null  root1.val != root2.val) return false; return isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left); }
8. Operation diagram

q200 number of islands

Using dfs, it is set to '0' after each traversal
The height and width can not follow the recursive function, because they can be obtained every time. Whether the traversed position is in the graph can be determined after recursion, rather than before each recursion
public int numIslands(char[][] grid) { if (grid == null  grid.length == 0) { return 0; } int h = grid.length; int l = grid[0].length; int num_islands = 0; for (int i = 0; i < h; i++) { for (int j = 0; j < l; j++) { if (grid[i][j] == '1') { num_islands++; dfs(grid, i, j); } } } return num_islands; } private void dfs(char[][] grid, int i, int j) { // Lower right and upper left to judge whether it is within the boundary int h = grid.length; int l = grid[0].length; if (i >= 0 && i < h && j >= 0 && j < l && grid[i][j] != '0') { grid[i][j] = '0'; dfs(grid, i, j + 1); dfs(grid, i + 1, j); dfs(grid, i, j  1); dfs(grid, i  1, j); } }

Using bfs is the same as dfs except that the traversal method is different
Deque for stack and Quere for team are LinkedList
Since the traversal here is a twodimensional array, the first node must be traversed once at the beginning of each position, so the double for loop first enters the queue. Then, if the queue is not empty, go out of the queue every time to judge whether there is a nearby node with '1'. If there is, enter the queue. The node added here is a onedimensional value of the twodimensional array, which can be restored to twodimensional coordinates
for (int i = 0; i < h; i++) { for (int j = 0; j < l; j++) { if (grid[i][j] == '1') { num_islands++; grid[i][j] = '0'; Queue<Integer> queue = new LinkedList<>(); queue.add(i * l + j); while (!queue.isEmpty()) { int id = queue.remove(); int row = id / l; int col = id % l; if (row  1 >= 0 && grid[row1][col] == '1') { grid[row1][col] = '0'; queue.add((row1)*l+col); } if (row + 1 < h && grid[row+1][col] == '1') { grid[row+1][col] = '0'; queue.add((row+1)*l+col); } if (col  1 >= 0 && grid[row][col1] == '1') { grid[row][col1] = '0'; queue.add(row * l + col  1); } if (col + 1 < l && grid[row][col+1] == '1') { grid[row][col+1] = '0'; queue.add(row * l + col + 1); } } } } }


q207 Curriculum
The same can be done using two recursive methods
At the beginning, my thinking was limited. I thought it was too complicated to operate through twodimensional array. In fact, I transformed it into a graph according to twodimensional array, and then solved the problem further. The result is whether the directed graph has a ring (whether it is a topological graph or not)
Thinking:
 The basic data type cannot change with the change of the function, so the bool value is directly regarded as a global traversal and cannot change with recursion
 In fact, courses are incremented continuously by default, so edges.get(item[1]).add(item[0]) just uses numCourses space
 There are three states: 0 has not been accessed, 1 is being accessed, and access completion = = 2 (as long as it is not 01)
boolean valid = true; public boolean canFinish(int numCourses, int[][] prerequisites) { List<List<Integer>> edges = new ArrayList<>(); int[] visited = new int[numCourses]; for (int i = 0; i < numCourses; i++) { edges.add(new ArrayList<>()); } for (int[] item : prerequisites) { edges.get(item[1]).add(item[0]); } for (int i = 0; i < numCourses && valid; i++) { if (visited[i] == 0) { dfs(edges, visited, i); } } return valid; } public void dfs(List<List<Integer>> edges, int[] visited, int i) { visited[i] = 1; List<Integer> list = edges.get(i); for (int u : list) { if (visited[u] == 0) { dfs(edges, visited, u); // The following three lines are not added. They are added faster if(!valid) { return; } } if (visited[u] == 1) { valid = false; return; } } visited[i] = 2; }
bfs method, forward thinking, first find the node with access degree of 0, remove it, and then remove the node with access degree of 0 every time. Finally, if there is no node, it is proved to be a topology graph
In the code
Use a queue for breadth first search. Initially, all nodes with a degree of 0 are put into the queue. They are the top nodes that can be sorted as topology, and the relative order between them is irrelevant.
In each step of breadth first search, we take out the first node uu:
We put uu in the answer;
We remove all out edges of uu, that is, reduce the penetration of all adjacent nodes of uu by 1. If the penetration of an adjacent node v becomes 0, we put v in the queue.
At the end of the breadth first search process. If the answer contains these n nodes, then we find a topological sort. Otherwise, it means that there are rings in the graph, and there is no topological sort.

q79 word search

Since it is not required to find the path, as long as the result, dfs is best defined as a function with a return value of bool type

If no result is found, the points at all positions should be traversed as the starting point. In the process of traversing the previous starting point, if it gets false, it will not be processed. If one of them is true, there will be a solution

The problem solution defines a function for calculating the orientation. If you go in more directions, you'd better use the orientation function. My idea is to judge which side to go from
int[][] directions = {{0, 1}, {0, 1}, {1, 0}, {1, 0}};
for (int[] dir : directions) {
int newi = i + dir[0], newj = j + dir[1];
if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) 
Be sure to use [i][j] = false before leaving;

When the return value of a recursive function is bool type, this method is used when you want to return false and return true successfully
if(dfs(board, chars, used, ni, nj, k+1)) return true;
public boolean exist(char[][] board, String word) { int m = board.length; if(m == 0){ return false; } int n = board[0].length; //Mark whether to walk boolean[][] used = new boolean[m][n]; char[] chars = word.toCharArray(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if(dfs(board, chars, used, i, j, 0)){ return true; } } } return false; } public boolean dfs(char[][] board, char[] chars, boolean[][] used, int i, int j, int k){ //Top right and left x if(k == chars.length1){ return board[i][j] == chars[k]; } if (board[i][j] == chars[k]){ int[][] directions = {{0, 1}, {0, 1}, {1, 0}, {1, 0}}; used[i][j] = true; for (int[] direction : directions) { int ni = i + direction[0]; int nj = j + direction[1]; //Judge whether it is still in the matrix area and the next area has not been accessed if(ni >= 0 && ni < board.length && nj >= 0 && nj < board[0].length && used[ni][nj] == false){ if(dfs(board, chars, used, ni, nj, k+1)){ return true; } } } used[i][j] = false; } return false; }


Motion range of sword finger t13 robot

dfs without return value, I wrote it
int count = 0; public int movingCount(int m, int n, int k) { // dfs, judge whether it is out of bounds and whether the digit sum exceeds k each time // If the location has been accessed, the result is + 1, and it will no longer be restored to not accessed // Do it with bfs boolean[][] vis = new boolean[m][n]; bfs(m, n, 0, 0, k, vis); return count; } private void bfs(int m, int n, int i, int j, int k, boolean[][] vis) { // Do not remember to write vis[i][j] == false condition, resulting in timeout if (i < m && j < n && (singleSum(i) + singleSum(j)) <= k && vis[i][j] == false) { count++; vis[i][j] = true; bfs(m, n, i+1, j, k ,vis); bfs(m, n, i, j+1, k ,vis); } } private int singleSum(int i) { int sum = 0; while (i != 0) { sum += i % 10; i /= 10; } return sum; }

dfs with return value, written by Tsinghua boss
public int movingCount(int m, int n, int k) { boolean[][] visited = new boolean[m][n]; return dfs(0, 0, m, n, k, visited); } public int dfs(int i, int j, int m, int n, int k, boolean[][] visited) { if(i >= m  j >= n  k < getSum(i) + getSum(j)  visited[i][j]) { return 0; } visited[i][j] = true; return 1 + dfs(i + 1, j, m, n, k, visited) + dfs(i, j + 1, m, n, k, visited); }

bfs, similar to the hierarchical traversal of a tree
public int movingCount(int m, int n, int k) { int count = 0; boolean[][] vis = new boolean[m][n]; int[][] directions = new int[][]{{0, 1}, {1, 0}}; Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{0, 0}); vis[0][0] = true; count++; while (!queue.isEmpty()) { int[] poll = queue.poll(); int i = poll[0]; int j = poll[1]; for (int[] direction : directions) { int ni = i + direction[0]; int nj = j + direction[1]; if (ni < m && nj < n && !vis[ni][nj] && (singleSum(ni) + singleSum(nj) <= k)) { queue.offer(new int[]{ni, nj}); vis[ni][nj] = true; count++; } } } return count; }


Sword finger t29 clockwise print matrix

Defines whether a twodimensional array has been accessed, and changes the left side of the row and column every time
int[][] directions = {{0, 1}, {1, 0}, {0, 1}, {1, 0}}; int directionIndex = 0; for (int i = 0; i < total; i++) { order[i] = matrix[row][column]; visited[row][column] = true; int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1]; if (nextRow < 0  nextRow >= rows  nextColumn < 0  nextColumn >= columns  visited[nextRow][nextColumn]) { directionIndex = (directionIndex + 1) % 4; } row += directions[directionIndex][0]; column += directions[directionIndex][1]; }

Search by layer
be careful:
 Array equal to null is different from length equal to 0. Judge whether it is null first
 During the 3rd and 4th searches on each layer, first check whether there is only one row or column, otherwise the search will be repeated
public int[] spiralOrder(int[][] matrix) { if (matrix == null  matrix.length == 0  matrix[0].length == 0) { return new int[0]; } int rows = matrix.length; int columns = matrix[0].length; int[] ans = new int[rows * columns]; int index = 0; int left = 0, right = columns1, top = 0, bottom = rows1; while (left <= right && top <= bottom) { // Search in four directions for (int i = left; i <= right; i++) { ans[index++] = matrix[top][i]; } for (int j = top+1; j <= bottom; j++) { ans[index++] = matrix[j][right]; } // Prevent repeated searches when there is only one row or one column if (left < right && top < bottom) { for (int i = right1; i >= left; i) { ans[index++] = matrix[bottom][i]; } for (int j = bottom1; j > top; j) { ans[index++] = matrix[j][left]; } } left++; right; top++; bottom; } return ans; }

9. Stack related

q20 valid parentheses
Why does the stack here use double ended queues?
Deque<Character> stack = new LinkedList<Character>();
Since Vector has been abandoned due to efficiency problems, the Stack inherited from Vector also has efficiency problems, so it is not recommended.
Another reason is that deque double ended queue can realize a variety of data structures, which can be simulated as a stack structure. Deque is very upmarket, with upper in and upper out, upper in and lower out, and even lower in and upper out. Only you can't think of it, and I can't do it.
Understand Java's collection framework and polymorphism (join the army for the father)
Here, the Map code is more concise
Map<Character, Character> pairs = new HashMap<Character, Character>() {{ put(')', '('); put(']', '['); put('}', '{'); }};

Implementation of queue with stack in q232
It's not as complicated as I thought. When you exit the stack directly from the stack on the right, enter the stack to judge whether the stack on the left is full, and then enter the left.
It is similar to the implementation of stack with queue. It mainly deals with the operation of entering the stack and entering the queue

q155 minimum stack
At first, I thought it was simple to record the minimum value of the current stack or the position pointing to the minimum value every time, but I ignored that the minimum value may be restored after leaving the stack, so I must record the minimum value every time, and open up a unified stack space to retain the minimum value of the stack at each position
Or another stack space holds elements that are not strictly decremented
Note: in Math.min(Integer.MIN_VALUE, Integer.MAX_VALUE) operation, Integer.MAX_VALUE is the minimum value

Push in popup sequence of sword finger t31 stack
Two previous mistakes
 Don't remember to while out of the stack
 Before stack.peek in while, ensure that the stack is not empty, otherwise it is a null pointer exception
Where two compilers help me optimize
 Finally, when you return, you don't need if(stack.isEmpty()) and else, just return
 If the loop index value is not used inside the for loop, it is more concise to use enhanced for instead
public boolean validateStackSequences(int[] pushed, int[] popped) { // Simulate a stack and check whether it is empty according to push and pop operations Deque<Integer> stack = new LinkedList<>(); int i = 0; for (int k : pushed) { stack.push(k); while (!stack.isEmpty() && stack.peek() == popped[i]) { stack.pop(); i++; } } return stack.isEmpty(); }
10. Team related

q225 imitate stack with queue
Only the push operation is special. Two queues are established. For each element in the queue, all elements in the other queue must be added to the team. In fact, all elements added to the team are stacked. In the interaction of two queues, because of the novelty of the team, the "stack" can only be processed one by one
class MyStack {
Queue queue1;
Queue queue2;class MyStack { Queue<Integer> queue1; Queue<Integer> queue2; /** Initialize your data structure here. */ public MyStack() { queue1 = new LinkedList<Integer>(); queue2 = new LinkedList<Integer>(); } /** Push element x onto stack. */ public void push(int x) { queue2.offer(x); while (!queue1.isEmpty()) { queue2.offer(queue1.poll()); } Queue<Integer> temp = queue1; queue1 = queue2; queue2 = temp; } /** Removes the element on top of the stack and returns that element. */ public int pop() { return queue1.poll(); } /** Get the top element. */ public int top() { return queue1.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return queue1.isEmpty(); } }
11. Dynamic planning

Characteristics that can be solved with dynamic specifications
 optimizable
 Decomposable into subproblems
 The subproblem can be decomposed into smaller subproblems
 Analyze problems from top to bottom and solve problems from bottom to top
 Store small problems that have been solved
 If we can mathematically prove that a case is the optimal solution, we can use greed

q5 longest palindrome string

Write the state transition equation and two boundary conditions to solve the problem
 P(i,j)=P(i+1,j−1)∧(Si==Sj)
 {P(i,i)=true；P(i,i+1)=(Si==Si+1)

thinking

initialization
for (int i = 0; i < len; i++) { dp[i][i] = true; }

Loop method, boundary size from small to large loop
//The iteration starts with a substring length of 2 for(int L=2; L <= len; L++){ // Left boundary for (int i = 0; i < len; i++) { // Right boundary int j = i+L1;

As a result, the dp value is true and the left and right boundaries are the largest
if (dp[i][j] && j  i + 1 > maxLen) { maxLen = j  i + 1; begin = i; }


The center expansion algorithm can be used to expand from the middle (boundary conditions) to both sides each time


q55 jump game
Without looking at the parsing, it is a dynamic programming algorithm. It applies for a bool type array with a length of nums, two for loops, sets the reachable to true, and returns the bool value of the last position. In fact, it can be done greedily. Just maintain the farthest subscript max that can be reached. Note I < = max
public boolean canJump(int[] nums) { int len = nums.length; int max = 0; for (int i = 0; i < Math.min(len, max+1); i++) { max = Math.max(max, i+nums[i]); if(max>=len1){ return true; } } return false; }

q72 edit distance difficulty dp

q96 different binary search trees
First understand the definition of binary search tree: it is either an empty tree or a binary tree with the following properties: if its left subtree is not empty, the values of all nodes on the left subtree are less than the values of its root node; if its right subtree is not empty, the values of all nodes on the right subtree are greater than the values of its root node; its left and right subtrees are also binary sort trees respectively.
According to the dynamic programming solution, the state transition equation is found
G(n)=i=1∑n**F(i,n) (1)
F(i,n)=G(i−1)⋅G(n−i) (2)
G(n)=i=1∑n**G(i−1)⋅G(n−i) (3)
Apply for one more bit in the array

Q339 word splitting
A jump version of the dp problem, in fact, the solution is the same, but this onedimensional array needs two for loops to determine
dp[i]=dp[j] && check(s[j...i−1])
for (int i = 1; i < s.length() + 1; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordDictSet.contains(s.substring(j, i))) { dp[i] = true; break; } } }

q152 product maximum subarray
A typical mistake is made: the optimal solution of the current position of this problem may not be obtained by the transfer of the optimal solution of the previous position, such as [ 2, 3,  4]
Each traversal should record the maximum and minimum values ending with the current node
max(num[i], num[i]*mx, num[i]*mn)
public int maxProduct(int[] nums) { int[] maxf = new int[nums.length]; int[] minf = new int[nums.length]; maxf[0] = nums[0]; minf[0] = nums[0]; int max = nums[0]; for (int i = 1; i < nums.length; i++) { maxf[i] = Math.max(Math.max((nums[i] * minf[i1]), nums[i]), Math.max((nums[i] * maxf[i1]), nums[i])); minf[i] = Math.min(Math.min((nums[i] * minf[i1]), nums[i]), Math.min((nums[i] * maxf[i1]), nums[i])); max = Math.max(max, maxf[i]); } return max; // The following method can reduce the space complexity to O(1). Since the ith state is only related to the ith − 1 state, according to the idea of "rolling array", we can only use two variables to maintain the state at the time of i − 1, one to maintain fmax and the other to maintain fmin. Other similar dynamic programming problems can also be optimized in this way int maxf = nums[0]; int minf = nums[0]; int max = nums[0]; for (int i = 1; i < nums.length; i++) { int mx = maxf, mn = minf; maxf = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i])); minf = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i])); max = Math.max(maxf, max); } return max; }

q198 house raiding
The original dp array is the largest, and does not necessarily include the current number
So the state transition formula is dp[i] = Math.max(dp[i2] + nums[i], dp[i1])
public int rob(int[] nums) { int len = nums.length; if(len == 0) { return 0; } if(len == 1) { return nums[0]; } int[] dp = new int[len]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < len; i++) { dp[i] = Math.max(dp[i2] + nums[i], dp[i1]); } return Math.max(dp[len  1], dp[len2]); }
Dynamic programming can often optimize the spatial complexity. Rolling arrays can be used. At each time, only the maximum total amount of the first two houses needs to be stored
int left = nums[0]; int right = Math.max(nums[0], nums[1]); for (int i = 2; i < len; i++) { int new_right = Math.max(left + nums[i], right); left = right; right = new_right; } return right;

q221 maximum square
I didn't think of his state transition equation: dp(i,j)=min(dp(i − 1,j),dp(i − 1,j − 1),dp(i,j − 1)) + 1
This state transition equation exists only when = = ='1 '
There is no need to consider the boundary condition here. If (I = = 0  J = = 0) is the boundary condition
The result is not the last one of dp, but the square of its maximum
java initializes the int array to all zeros by default
for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (matrix[i][j] == '1') { if (i == 0  j == 0) { dp[i][j] = 1; } else { dp[i][j] = Math.min(Math.min(dp[i1][j], dp[i][j1]), dp[i1][j1]) + 1; } maxSide = Math.max(maxSide, dp[i][j]); } } }

279 perfect square
I thought of the state transition equation, but it won't be transformed into code
i don't know how to find the complete square next to the sum of squares. A for loop keeps looking, as long as it is smaller than i
public int numSquares(int n) { int dp[] = new int[n + 1]; for (int i = 0; i <= n; i++) { dp[i] = i; for (int j = 0; j * j <= i; j++) { dp[i] = Math.min(dp[i], dp[i  j * j] + 1); } } return dp[n]; }

q300 longest ascending subsequence

Ordinary dp
dp[i]=max(dp[j])+1, where 0 ≤ J < I and num [J] < num [i]
The minimum value of dp at each position is 1. It is not necessary to define it as negative infinity
dp[i] = Math.max(dp[i], dp[j] + 1);

Greedy + binary optimization can be used
Maintain a monotonically increasing sequence with D [], scan backward, and the number newly added each time is as small as possible. If num [i] > d [len], update len = len + 1, otherwise use dichotomy to find the ordinal number in front of D [], find the subscript i satisfying D [I  1] < num [J] < d [i], and update d [i] = num [J]
[the external chain image transfer fails. The source station may have an antitheft chain mechanism. It is recommended to save the image and upload it directly (imgcxnxdqar1637714619661) (C: / users / chenzhijian / appdata / roaming / typora / typora user images / image20211103111050368. PNG)]
Binary search can be used not only to find certain numbers, but also here
public int lengthOfLIS(int[] nums) { int len = 1, n = nums.length; if (n == 0) { return 0; } // The same number will replace the same number int[] d = new int[n + 1]; d[1] = nums[0]; for (int i = 1; i < n; i++) { if (nums[i] > d[len]) { d[++len] = nums[i]; } else { int l = 1, r = len, pos = 0; //Start dichotomy to find the nearest position less than it while (l <= r) { int mid = (l + r) / 2; if (nums[i] > d[mid]) { pos = mid; l = mid + 1; } else { r = mid  1; } } d[pos + 1] = nums[i]; } } return len; }


The best time to buy and sell stocks includes the freezing period
Use f[i] to represent the "cumulative maximum return" after the end of day I. there are three states

We currently hold a stock, and the corresponding "cumulative maximum return" is recorded as f[i] [0];

At present, we do not hold any stocks and are in the freezing period. The corresponding "cumulative maximum return" is recorded as f[i] [1];

At present, we do not hold any shares and are not in the freezing period. The corresponding "cumulative maximum return" is recorded as f[i] [2].
f[i] [0] = max(f[i1] [0], f[i1] [2]  prices[i])
I held a stock yesterday and did not sell it or was not in the freezing period yesterday. I bought it today
f[i] [1] = f[i1] [0]+prices[i]
It was sold yesterday, so it's in the freezing period
f[i] [2] = max(f[i1] [1], f[i1] [2])
It was sold just yesterday or before yesterday
The final answer is max(f[n1] [1], f[n1] [2]). Holding stocks on the last day is meaningless, and the freezing period represents that day, so it is the last one
public int maxProfit(int[] prices) { if (prices.length == 0) { return 0; } int n = prices.length; // f[i][0]: maximum return from holding stocks // f[i][1]: the cumulative maximum return of not holding stocks and in the freezing period // f[i][2]: the cumulative maximum return that does not hold stocks and is not in the freezing period int[][] f = new int[n][3]; f[0][0] = prices[0]; for (int i = 1; i < n; ++i) { f[i][0] = Math.max(f[i  1][0], f[i  1][2]  prices[i]); f[i][1] = f[i  1][0] + prices[i]; f[i][2] = Math.max(f[i  1][1], f[i  1][2]); } return Math.max(f[n  1][1], f[n  1][2]); }
Spatial optimization
f[i] [?] is only related to f[i1] [?] and has nothing to do with f[i2] [?] and all previous states, so you only need to store f[i1] [?] in three variables
int n = prices.length; int f0 = prices[0]; int f1 = 0; int f2 = 0; for (int i = 1; i < n; ++i) { int newf0 = Math.max(f0, f2  prices[i]); int newf1 = f0 + prices[i]; int newf2 = Math.max(f1, f2); f0 = newf0; f1 = newf1; f2 = newf2; } return Math.max(f1, f2);
 Dynamic programming and space can be optimized in one dimension


q322 change

The direct use of backtracking will timeout, and the memory search needs to be done with the help of array, which belongs to the topdown optimization
State transition equation F(S)=F(S − C)+1
public int coinChange(int[] coins, int amount) { return coinChange(coins, amount, new int[amount]); } // Recursion is to borrow money and let future generations repay it private int coinChange(int[] coins, int amount, int[] count) { if (amount < 0) { return 1; } if (amount == 0) { return 0; } if (count[amount1] != 0) { return count[amount1]; } int min = Integer.MAX_VALUE; for (int coin : coins) { int res = coinChange(coins, amount  coin, count); if (res >= 0 && res < min) { min = res + 1; } } count[amount1] = min == Integer.MAX_VALUE ? 1 : min; return count[amount1]; // This is the case without memory search // return min == Integer.MAX_VALUE ? 1 : min; }

Bottom up dynamic programming
F(i)=minF(i−cj)+1 j=0...n−1
My writing
public int coinChange(int[] coins, int amount) { int[] dp = new int[amount+1]; dp[0] = 0; for (int i = 1; i <= amount; i++) { int min = Integer.MAX_VALUE; for (int coin : coins) { if (icoin >= 0 && dp[icoin] < min && dp[icoin] >= 0) { dp[i] = dp[icoin]+1; min = dp[icoin]; } } if (min == Integer.MAX_VALUE) { dp[i] = 1; } } return dp[amount]; }
The official solution is more ingenious. The array is initially assigned as amount + 1, which is convenient to find the minimum value
public int coinChange(int[] coins, int amount) { int max = amount + 1; int[] dp = new int[amount + 1]; Arrays.fill(dp, max); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int j = 0; j < coins.length; j++) { if (coins[j] <= i) { dp[i] = Math.min(dp[i], dp[i  coins[j]] + 1); } } } return dp[amount] > amount ? 1 : dp[amount]; }


q416 split equal sum subset
In fact, it can be transformed into 01 knapsack problem. The number inside can be combined into exactly half of the total. In dp, the behavior selects or deselects this number and lists it as the total
When dp is initialized, when the capacity is given to n bits and n+1 bits, the rows here are given to N and the columns are given to n+1, because n+1 is convenient for operation
Return false
 One number is more than half the total
 There are only 1 or 0 numbers
 The sum is odd
Judge whether the current number is greater than half of the total. You can judge less if (J > = num [i])
public boolean canPartition(int[] nums) { // Calculate sum int sum = 0, max = 0, n = nums.length; if (n < 2) { return false; } for (int i = 0; i < n; i++) { sum += nums[i]; max = Math.max(max, nums[i]); } if (sum % 2 == 1) { return false; } int halfSum = sum / 2; if (max > halfSum) { return false; } boolean[][] dp = new boolean[n][halfSum + 1]; // Initialization, the following step can be omitted // for (int i = 0; i < n; i++) { // dp[i][0] = true; // } dp[0][nums[0]] = true; for (int i = 1; i < n; i++) { for (int j = 1; j <= halfSum; j++) { if (j >= nums[i]) { dp[i][j] = dp[i1][j]  dp[i1][jnums[i]]; } else { dp[i][j] = dp[i1][j]; } } } return dp[n1][halfSum]; }

Sword fingers t46 translate numbers into strings, similar to climbing stairs

Conventional dp writing
String s = String.valueOf(num); int[] dp = new int[s.length()+1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= s.length(); i++) { String tmp = s.substring(i2, i); // This compares the string size if (tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0) { dp[i] = dp[i2] + dp[i1]; } else dp[i] = dp[i1]; } return dp[s.length()];

dp optimized writing method
String s = String.valueOf(num); //a is equivalent to dp[i2] b is equivalent to dp[i1] c is equivalent to dp[i] int a = 1,b = 1,c; for (int i = 2; i <= s.length(); i++) { String tmp = s.substring(i2, i); c = (tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0) ? a + b : b; a = b; b = c; } return b;

dfs writing method
Writing method 1: public int translateNum(int num) { //Convert string to number String str = String.valueOf(num); //dfs traversal string solution return dfs(str, 0); } //Indicates that there are many translation methods starting from the index position public int dfs(String str, int index){ //If the current subscript is greater than or equal to the length of the string  1, it indicates that the current position jumped here from the last time, and 1 is returned directly if(index >= str.length()  1) return 1; //First solve the number of methods that translate one character at a time int res = dfs(str, index + 1); //Start with the subscript of the current character, intercept two digits, and judge whether the composed number is between 10 and 25 //If you can translate two characters directly at this time, then start the translation from the position after the two characters String temp = str.substring(index, index + 2); if(temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0) res += dfs(str, index + 2); return res; } Method 2: int translateNum(int num) { return f(num); } int f(int num) { if (num < 10) { return 1; } if (num % 100 < 26 && num % 100 > 9) { return f(num / 10) + f(num / 100); } else { return f(num / 10); } }

12. Bit operation

Number of 1 in binary
 Move the number to the right and compare it with 1
 Compare with 1, shift left and compare again (prevent negative numbers)
 1 and itself until it is 0

q128 is a number that appears only once
The nature of using XOR
(a1⊕a1)⊕(a2⊕a2)⊕⋯⊕(a**m⊕a**m)⊕a**m+1
0⊕0⊕⋯⊕0⊕a**m+1=a**m+1

q338 bit count

If i is an even number, then f(i) = f(i/2)
If i is an odd number, then f(i) = f(i  1) + 1 
Brian Kernighan algorithm
while (x > 0){x &= (x  1);ones++;}

Highest bit
For example, s(13) = s(8) + s(5), 8 is the highest bit of 13, and there is only one 1 in it. I didn't expect the method to quickly find the most significant bit. I thought it would need extra calculation every time. In fact, it can depend on the traversal process, using the algorithm of 2
public int[] countBits(int n) { int[] dp = new int[n+1]; dp[0] = 0; int highBit = 0; for (int i = 1; i < n + 1; i++) { // Find the most significant bit of i if ((i & (i1)) == 0) { highBit = i; } dp[i] = dp[i  highBit] + 1; } return dp; }

Lowest bit
If xx is an even number, bits[x] = bits[x/2]
If xx is an odd number, bits[x] = bits[x/2]+1
bits[i] = bits[i >> 1] + (i & 1);

The lowest setting bit is essentially the algorithm of method 2
y = x & (x1) => bits[x] = bits[y] + 1
bits[x] = bits[x&(x1)] + 1


q461 Hamming distance
The reason why I can't do it is because I don't know that there is a bitwise and operator. This is the basis of this problem. z = x ^ y, just find the number of digits of 1 of z. Whether it's wheel adjustment or Brian Kernighan algorithm

Integer power of sword finger t16 array
This question tests the consideration of various special values and the accelerated optimization of the algorithm

Recursive Method
public double myPow(double x, int n) { if (x == 0 && n < 0) { return 0; } long absEx = n; if (n < 0) absEx = absEx; // Cannot use absEx = n, different types double res = getPow(x, absEx); if (n < 0) { res = 1 / res; } return res; } private double getPow(double x, long absEx) { //Recursive exit if (absEx == 0) { return 1; } if (absEx == 1) { return x; } double ans = getPow(x, absEx>>1); ans *= ans; // absEx odd or even if ((absEx & 1) == 1) { ans *= x; } return ans; }

Fast power analysis
double res = 1.0; while (absEx > 0) { if ((absEx & 1) == 1) { res *= x; } x *= x; absEx >>= 1; } return res;

13. Backtracking

Backtracking, depth first, recursion, dynamic programming

Backtracking usually uses the simplest recursion. "Backtracking algorithm" emphasizes the use of the idea of "depth first traversal". It uses a changing variable to search the required results in the process of trying various possibilities. The rationality of fallback operation for search is emphasized.

Depth first search: when the edges of node v have been explored, the search will be traced back to the starting node of the edge where node v is found.

Dynamic programming only requires us to evaluate how much the optimal solution is, and what the specific solution corresponding to the optimal solution is not required. Therefore, it is suitable for evaluating the effect of a scheme

When to use the used array and when to use the begin variable
For the arrangement problem, pay attention to the order (that is, when [2,2,3] and [2,3,2] are regarded as different lists), it is necessary to record which numbers have been used. In this case, use the used array;
The combination problem does not pay attention to the order (that is, when [2,2,3] and [2,3,2] are regarded as the same list), it needs to search in a certain order. In this case, use the begin variable.


t22 bracket generation

The simplest is the violence law. Start with 2*n '(' and judge whether it is reasonable every time it is full
 The reasonable judgment function is: add one in the left bracket and subtract one in the right bracket. If it is less than zero in the middle, it is unreasonable, and the final result is zero

Backtracking method
If the number of left parentheses is not greater than n, we can put an left parenthesis. If the number of right parentheses is less than the number of left parentheses, we can put a right parenthesis. There is no need to judge
public void backtrack(List<String> res, StringBuilder cur, int open, int close, int max){ // Get a result if(cur.length() == 2*max){ res.add(cur.toString()); return; } if(open < max){ cur.append('('); backtrack(res, cur, open+1, close, max); cur.deleteCharAt(cur.length()1); } if(close < open){ cur.append(')'); backtrack(res, cur, open, close+1, max); cur.deleteCharAt(cur.length()1); } }


q39 array sum
The key idea of this problem is how to draw this backtracking tree. Take target as the root node of the tree, subtract the value of a candidate as the child node, and the leaf node with zero result is a solution
code
public List<List<Integer>> combinationSum(int[] candidates, int target) { int len = candidates.length; List<List<Integer>> res = new ArrayList<>(); if(len == 0){ return res; } Deque<Integer> path = new ArrayDeque<>(); dfs(candidates, 0, len, target, path, res); return res; } /** * @param candidates Candidate array * @param begin Search starting point * @param len Redundant variables are attributes in candidates and can not be passed * @param target Every time you subtract an element, the target value becomes smaller * @param path The path from the root node to the leaf node is a stack * @param res Result set list */ private void dfs(int[] candidates, int start, int len, int target, Deque<Integer> path, List<List<Integer>> res) { if(target<0){ return; } if(target==0){ res.add(new ArrayList<>(path)); return; } // Focus on understanding the semantics of searching from begin here for (int i = start; i < len; i++) { path.addLast(candidates[i]); // Note: since each element can be reused, the starting point of the next round of search is still i, which is very easy to make mistakes here dfs(candidates, i, len, targetcandidates[i], path, res); path.removeLast(); } } }
prune:
Sort first and start detection in the for loop
if(targetcandidates[i]<0){ break; }
Recursive exits with target less than 0 can be deleted

q46 full arrangement
Parameters passed recursively are
Candidate array, array length (also derived from candidate array), recursion depth, path in recursion, result set list
If there are duplicate elements, two methods are used to remove the duplicate. One is to judge the duplicate before adding the result set (Sword finger t38 timeout). The other is to sort first. If it is the same as the previous one, skip it
Following the recursive routine of the previous question, I have two main problems
 After recursion, the path does not remember to remove the last one
 res.add(path); if there is a problem with the writing method, it should be written as res.add (New ArrayList < > (path)); see the following for details:
java knowledge points:
[the external chain image transfer fails. The source station may have an antitheft chain mechanism. It is recommended to save the image and upload it directly (imgxrfhceh21637714619663) (C: / users / chenzhijian / appdata / roaming / typora / typora user images / image20211012200830758. PNG)]
The above ls is a new pointer to list1, similar to
ArrayList ls = new ArrayList();
ls = list1
After path enters the parameter, it means that different pointers point to the same address. Each time add goes in, it points to the same address. Therefore, once the value in that address changes, all the values in res will change together. Finally, after returning to the root node, it will become an empty array
There is another way of thinking. The official analysis of 38 questions of sword finger offer. The number after the Interactive start and the number after it must not be repeated. During recursion, the original char [] array changes
class Solution { List<String> rec; boolean[] used; public String[] permutation(String s) { char[] ch = s.toCharArray(); StringBuilder str = new StringBuilder(); rec = new ArrayList<>(); used = new boolean[s.length()]; Arrays.sort(ch); dfs(ch, 0, str); String[] ans = new String[rec.size()]; for (int i = 0; i < rec.size(); i++) { ans[i] = rec.get(i); } return ans; } private void dfs(char[] ch, int deep, StringBuilder str) { int length = ch.length; if (deep == length) { String s = new String(ch); if (!rec.contains(s)) { rec.add(s); } } for (int i = deep; i < length; i++) { swap(ch, deep, i); dfs(ch, deep+1, str); swap(ch, deep, i); // if (used[i]  (i > 0 && !used[i  1] && ch[i  1] == ch[i])) { // continue; // } // used[i] = true; // str.append(ch[i]); // dfs(ch, deep+1, str); // used[i] = false; // str.deleteCharAt(str.length()1); } } private void swap(char[] ch, int i, int j) { char temp = ch[i]; ch[i] = ch[j]; ch[j] = temp; } }

q53 maximum suborder sum
A simple dynamic programming problem, the key is how to find the state transition equation
There should be no aftereffect when selecting sub problems
 Sub question 1: what is the maximum sum of continuous sub arrays ending with  2;
 Sub question 2: what is the maximum sum of continuous sub arrays ending with  1;
 ...
There is a link between these sub problems
There was a problem that I didn't figure out before. I thought that the maximum sum of continuous sub arrays ending with a certain number is the previous maximum. In fact, if this number is less than zero, it must be less than the previous number
You can use divide and conquer to solve this problem. Try to write it later

q78 subset
The first thought is recursion, which can set q46 fully arranged templates. The official solution is a little different
List<List<Integer>> ans = new ArrayList<>(); List<Integer> t = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { dfs(0, nums); return ans; } private void dfs(int cur, int[] nums){ if (cur == nums.length) { ans.add(new ArrayList<Integer>(t)); return; } t.add(nums[cur]); dfs(cur + 1, nums); t.remove(t.size()  1); dfs(cur + 1, nums); }
The path in the middle and the traversal of the result set are placed in the global, and len is recalculated in the recursion, so three variables are written less in the recursion
The difference is that you don't need a for loop, but it's more difficult to write a recursive function
Conventional recursive writing
public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); dfs(0, nums, new ArrayList<Integer>(), ans); return ans; } private void dfs(int cur, int[] nums, ArrayList<Integer> t, List<List<Integer>> ans){ ans.add(new ArrayList<Integer>(t)); for (int i = cur; i < nums.length; i++) { t.add(nums[i]); dfs(i + 1, nums, t, ans); t.remove(t.size()  1); } }
Another way to solve this problem is to use binary
Take 123 as an example, 011 –'23'101 –'13 '
14. Recursion

Postorder traversal sequence of sword finger t33 binary search tree
The root is on the far right, and the dividing point of the left and right subtrees is the first number larger than the root
public boolean verifyPostorder(int[] postorder) { return verify(postorder, 0, postorder.length  1); } private boolean verify(int[] postorder, int i, int j) { if (i >= j) return true; int p = i; while (postorder[p] < postorder[j]) p++; int m = p; while (postorder[p] > postorder[j]) p++; // Let p a round of swimming to see if the left is smaller than root and the right is larger than root return p == j && verify(postorder, i, m  1) && verify(postorder, m, j1); // Such a return value is often used when the left and right subtrees need to meet the conditions at the same time } }

Sword finger t36 binary search tree and bidirectional linked list

right key
Node head, pre; public Node treeToDoublyList(Node root) { if (root == null) { return null; } treeToDoublyList1(root); pre.right = head; head.left =pre;//The order of these two sentences can also be reversed by pointing to each other between the head node and the tail node return head; } // Medium order traversal private void dfs(Node cur) { if (cur == null) { return; } dfs(cur.left); // pre is the previous cur of the current node and is used to convert it into a twoway linked list if (pre == null) { // Head head = cur; } else { pre.right = cur; cur.left = pre; } // Automatically updates to the tail pre = cur; dfs(cur.right); }

My wrong answer
If root is returned, the output will ignore the right subtree of the left child and the left subtree of the right child
public Node treeToDoublyList1(Node root) { if (root == null) { return null; } Node left = treeToDoublyList1(root.left); if (pre == null) { head = root; } if (left != null) { left.right = root; root.left = left; } pre = root; Node right = treeToDoublyList1(root.right); if (right != null) { root.right = right; right.left = root; } return root; }
