Some of the key
Note: there may be no code hints for handwriting or computer tests, so remember some basic function names
-
Integer, string rotation
//int -> string Integer.toString(x) //String -> int Integer.valueOf(s) Copy the code -
Character reversal function
/* * toString() can't be forgotten, because the StringBuilder class does not have a reverse() method * StringBuilder threads are not safe; StringBuffer is thread safe */ new StringBuilder(s).reverse().toString() Copy the code -
String to character array function
s.toCharArray() s.charAt(i) Copy the code -
The size of strings, arrays, and linked lists
// The () of the string cannot be short s.length(); arr.length; list.size(); Copy the code -
The use of the stack
Suitable for stack problems: parenthesis problem, path problem, lifO problem;
// First out of the stack Stack<Integer> stack = new Stack<>(); stack.pop();/ / the pop-up stack.push(object);/ / pumped stack.empty();// Whether the stack is empty stack.peek();// View the element at the top of the stack without removing it Copy the codeLinked list implementation stack
-
KMP algorithm
K m P 3 personal initials KMP algorithm is a fast algorithm to find matching strings
-
Dynamic programming
The basic solution is to know the sum of the largest subarrays of an array;
-
Math common functions
Math.max(a, b) // Compare the size, return the largest Math.abs(a) / / the absolute value Math.pow(doublea, doubleb) // a^b Copy the code -
It is an integer ranging from 0 to 9 characters
char c = '9'; int i = c - '0'; int i2 = Intger.parseInt(Character.toString(c)); Copy the code -
The maximum suborder sum of an array
Idea: Dynamic programming,
-
Binary tree
Find maximum depth
public int maxDept(TreeNode root){ if(root == null) {return 0; } return 1 + Math.max(maxDept(root.left), maxDept(root.right)); } Copy the codeFront, middle and back order traversal is the foundation, simple to remember
// preorder traversal public void recursionA(TreeNode root){ if(root == null) {return; } System.out.println(root.val); if(root.left ! =null){ recursion(root.left); } if(root.right ! =null){ recursion(root.right); }}// middle order traversal public void recursionB(TreeNode root){ if(root == null) {return; } if(root.left ! =null){ recursion(root.left); } System.out.println(root.val); if(root.right ! =null){ recursion(root.right); }}// after the sequence traversal public void recursionC(TreeNode root){ if(root == null) {return; } if(root.left ! =null){ recursion(root.left); } if(root.right ! =null){ recursion(root.right); } System.out.println(root.val); } Copy the code -
The ascII character
“A” for 65; “A” for 97; “0” to 48
Code does not use numbers can also use characters in judgment, can not remember the corresponding number
character ascii character ascii character ascii 0 48 A 65 a 97 1 49 B 66 b 98 2 50 C 67 c 99 3 51 D 68 d 100 4 52 E 69 e 101 5 53 F 70 f 102 6 54 G 71 g 103 7 55 H 72 h 104 8 56 I 73 i 105 9 57 J 74 j 106 K 75 k 107 L 76 l 108 M 77 m 109 N 78 n 110 O 79 o 111 P 80 p 112 Q 81 q 113 R 82 r 114 S 83 s 115 T 84 t 116 U 85 u 117 V 86 v 118 W 87 w 119 X 88 x 120 Y 89 y 121 Z 90 z 122 -
Palindromes are usually judged by double pointer algorithm
A two-pointer sorted array, one at the front and one at the back, is searched and subtracted according to the criteria
Find the midpoint of the palindrome pointer to the linked list and flip the following paragraph to compare with the beginning
-
Properties of bit operations
The number that doesn’t repeat is the same number, so use either or or, different is 1, same is 0, a to the 0 is equal to a, a to the a is equal to 0
-
Check if the list has a loop and check if it’s in a loop
Hash: Iterates through a list of linked elements. If the element has a ring in the hash table, add it to the list otherwise
Fast and slow pointer method (turtle rabbit algorithm) : one fast and one slow, until the fast and slow meet, indicating a ring, space O (1)
-
Linked list, tree form in code
/ / list ListNode{ // The saved value int val; // Next pointer address ListNode next; ListNode(){} ListNode(int val, ListNode node){ this.val = val; this.next = node; }}/ / = = = = = = = = = = = = = ^. ^ = = = = = = = = = = = = = = = = = = / / binary tree TreeNode{ // The saved value int val; // Left child node TreeNode left; // Right child node TreeNode right; TreeNode(){} TreeNode(int val, TreeNode left, TreeNode right){ this.val = val; this.left = left; this.right = right; }}Copy the code -
Common methods
- The enumeration of violence
Usually o (n ^ 2)
- Hash table method
Keep a record of each number count, finally pick the largest number O (n)
- Moore’s voting method is against spell consumption
Selects the mode, the element with the most values in an array
-
ans = ans * 26 + num
Base 26, * 26 is equal to carry 1 bit
-
SQL database
Select distinct where group by group order by sort HAVING count() ifnull(dd, cc) DateDiff (a.recorddate, b.recorddate) is the difference between two datesCopy the codeWhat’s the difference between on and where?
The ON condition is used when generating temporary tables. It returns the records in the left table regardless of whether the condition in ON is true.
The WHERE condition is used to filter temporary tables after they are created. Since there is no sense of LEFT JOIN at this point (records from the LEFT table must be returned), records that are not true will be filtered out.
-
Reverse a linked list
/** * invert the list, changing the direction of the arrow, so that the next node of the element points to the previous node, and the previous node is saved * time o(n) space (1) */ public ListNode reverseList(ListNode head){ ListNode cur = head; ListNode pre = null; while(cur ! =null) {// Save the next node ListNode next = cur.next; // Reset the next node to the previous node cur.next = pre; // The current node is saved as the previous node pre = cur; // loop to the next node cur = next; } return pre; } Copy the code
To be continued…