Sword finger Offer - java version
JZ01
In a two-dimensional array (each one-dimensional array has the same length), each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Please complete a function, input such a two-dimensional array and an integer, and judge whether the array contains the integer.
Violent solution, direct double cycle. The time complexity is: O(n^2).
public boolean Find(int target, int [][] array) {
for(int i = 0 ; i < array.length; i++){
for(int j = 0; j < array[i].length; j++){
if(target == array[i][j]){
return true;
}
}
}
return false;
}
According to the meaning of the question, it is an array increasing from small to large, so according to this law, first compare the number at the end of each line. If the target is less than this number, traverse the line; If it exists, return directly; No, go to the next line.
JZ02 replace spaces
Please implement a function to replace each space in a string with "% 20". For example, when the string is We Are Happy Then the replaced string is We%20Are%20Happy.
Traverse and replace spaces directly.
public String replaceSpace(StringBuffer str) {
String sb = "";
for(int i = 0; i < str.length(); i++){
if( str.charAt(i) != ' '){
sb = sb + str.charAt(i);
} else
sb = sb + "%20";
}
return sb;
}
In addition, you can call java functions directly replace()
public String replaceSpace(StringBuffer str) {
return str.toString().replace(" ", "%20");
}
JZ03 print linked list from end to end
Enter a linked list and return an ArrayList from end to end.
Enter the value of ArrayList in the array in reverse order.
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> arry = new ArrayList<Integer>();
int[] arr = new int[10000];
int i = 0;
if(listNode == null)
return arry;
while(listNode.next != null ){
arr[i] = listNode.val;
listNode = listNode.next;
i++;
}
arr[i] = listNode.val;
for( int j = i ; j >= 0 ; j--){
arry.add(arr[j]);
}
return arry;
}
JZ04 rebuilding binary tree
Enter the results of preorder traversal and inorder traversal of a binary tree. Please rebuild the binary tree. It is assumed that the input pre order traversal and middle order traversal results do not contain duplicate numbers. For example, if the preorder traversal sequence {1,2,4,7,3,5,6,8} and the middle order traversal sequence {4,7,2,1,5,3,8,6} are input, the binary tree will be reconstructed and returned.
Here, we must first clarify the pre order, middle order and post order traversal of binary tree.
- Preface: left and right root
- Middle order: left root right
- Post order: left and right root
Then the first value of preorder traversal is the root node; The middle order traversal before the root node is the middle order traversal of the left subtree, and the number of nodes of the left subtree can be obtained. Then the front order traversal of the left subtree can be obtained in the front order traversal. The rest of the two becomes the right subtree, which can be brought into the traversal. Each traversal returns a root node, that is, the last child node. In addition, because you want to cut the array, you use Java util. copyOfRange() in the arrays tool class. Remember to open left and close right.
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if( pre.length == 0 || in.length == 0 )
return null;
TreeNode root = new TreeNode(pre[0]);
for(int i = 0 ; i < in.length ; i++){
if( pre[0] == in[i]) {
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
break;
}
}
return root;
}
JZ05 implements queues with two stacks
Two stacks are used to implement a queue to complete the Push and Pop operations of the queue. The element in the queue is of type int.
First of all, it should be clear: stack, first in and then out; Queue, first in, first out. Therefore, it is considered to directly output the value that comes out of the stack first, save the remaining values with the second stack, and then input back to the first stack after output. It's kind of like the tower of Hanoi.
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
int lenth = stack1.size();
for (int i = 0; i < lenth; i++) {
stack2.push(stack1.pop());
}
int res = stack2.pop();
lenth = stack2.size();
for (int i = 0; i < lenth ; i++) {
stack1.push(stack2.pop());
}
return res;
}
}
JZ06 minimum number of rotation array
Moving the first elements of an array to the end of the array is called array rotation. Enter a rotation of a non decrementally sorted array and output the smallest element of the rotated array. For example, if the array {3,4,5,1,2} is a rotation of {1,2,3,4,5}, the minimum value of the array is 1. NOTE: all elements given are greater than 0. If the array size is 0, please return 0.
- Direct use of traversal, violence to solve.
public int minNumberInRotateArray(int [] array) {
int min = array[0];
for(int i = 1; i< array.length; i++){
min = (min < array[i] ? min : array[i]);
}
return min;
}
- Using the idea of dichotomy, because the topic is the rotation of the array after non decreasing sorting, this feature can be used, but at the same time, the specificity of this feature should also be considered (011111 or a rotation similar to the same array). A group of non decreasing sorted arrays can be divided into two segments by the minimum value after rotation. Think of dichotomy and compare mid with last. There are the following situations:
- If mid > last, the minimum value is between mid and last.
- Mid < last, the minimum value is between first and mid.
- mid == last, can't distinguish clearly, can only reduce the value of last step by step.
public int minNumberInRotateArray(int [] array) {
if( array.length == 0 )
return 0;
int first = 0;
int last = array.length - 1;
while (first < last ){
if( array[first] < array[last] )
return array[first];
int mid = ( first + last) >> 1;
if( array[mid] < array[last]){
last = mid;
} else if ( array[mid] > array[last])
first = mid + 1;
else
--last;
}
return array[first];
}
JZ07 Fibonacci sequence
We all know the Fibonacci sequence. Now it is required to input an integer n. please output the nth item of the Fibonacci sequence (starting from 0, item 0 is 0, and item 1 is 1).
n<=39
Classic problem: direct recursion.
public int Fibonacci(int n) {
if(n == 0)
return 0;
if(n==1)
return 1;
return Fibonacci(n-1) + Fibonacci(n-2);
}
JZ08 step jumping problem
A frog can jump up one step or two steps at a time. Find out the total number of jumping methods for the frog to jump up an n-step step (different results are calculated in different order).
See this problem, directly solve the Fibonacci sequence. It should be noted that f0 has different values in different series.
public int JumpFloor(int target) {
if( target <= 1)
return 1;
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
Of course, you can also use bottom-up dynamic programming to solve problems.
public int JumpFloor(int target) {
int[] dp = new int[target + 1];
if(target == 0)
dp[0] = 1;
if(target >= 1)
{
dp[0] = 1;
dp[1] = 1;
}
for(int i = 2; i < target + 1; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[target];
}
JZ09 frog jumping steps
A frog can jump up one step or two steps at a time... It can also jump up n steps. Find out the total number of jumping methods for the frog to jump up an n-step step.
Obvious recursion problem: there are n jump methods for the first jump. If you jump x steps for the first time, there are still (n-x) steps left, and (n-x) returns to the original problem. When the number of remaining steps (n-x) is 0, it jumps to the end point, and then add 1.
public class Solution {
public static int COUNT = 0;
public int JumpFloorII(int target) {
COUNT = 0;
jump(target);
return COUNT;
}
public void jump(int n){
for( int i = 1; i <= n; i++){
if( i== n)
COUNT ++;
else
jump(n-i);
}
}
}
Through test and analysis, it can be found that there is one kind when n = 1; When n = 2, there are 2 kinds; When n = 3, there are 4
It is found that the final total is the n-1 power of 2.
public class Solution {
public int JumpFloorII(int target) {
return Math.pow(2, target - 1);
}
}
JZ10 rectangular overlay
We can use a small rectangle of 2 * 1 to cover a larger rectangle horizontally or vertically. How many methods can you use n 2 * 1 small rectangles to cover a 2*n large rectangle without overlapping?
For example, when n=3, there are three covering methods for 2 * 3 rectangular blocks.
It seems complex, but it is actually Fibonacci sequence. Just note that at this time, the value of f(0) in f(n) sequence is 1, but in fact, the value of f(0) is 0. This should be considered.
public int RectCover(int target) {
int[] dp = new int[target + 1];
if(target == 0)
dp[0] = 1;
if( target >= 1 ) {
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i < target + 1; i++)
dp[i] = dp[i - 1] + dp[i - 2];
}
if( target == 0 ) return 0;
return dp[target];
}
Number of 1 in JZ11 binary
Enter an integer and output the number of 1 in the 32-bit binary representation of the number. Where negative numbers are represented by complements.
Check the bit operation, directly &1 to find whether the last bit is 1, and then move it to the right in turn. However, this simple method exceeds the operation time of 2ms in java.
public int NumberOf1(int n) {
int count = 0;
while ( n != 0 ){
if((n & 1) == 1)
count++;
n >>= 1;
}
return count;
}
So consider optimizing it. In the above method, 0 should be judged every time, so if you can cross 0, you can save time. After 11001000 - 1, it is 11000111, and then sum with the original number to get 11000000, that is, the rightmost 1 is removed every time.
public int NumberOf1(int n) {
int count = 0;
while ( n != 0 ){
++ count;
n = n & (n-1);
}
return count;
}
Integer power of JZ12 value
Given a floating-point number of type double, base and integer exponent of type int. Find the exponent power of base. Ensure that the base and exponent are not 0 at the same time
Directly use the pow() method under the Math package (import java.lang.Math).
public double Power(double base, int exponent) {
return Math.pow(base, exponent);
}
Of course, you can also directly a while loop, exponent --
JZ13 adjusts the array order so that odd numbers precede even numbers
Input an integer array and implement a function to adjust the order of numbers in the array, so that all odd numbers are in the first half of the array and all even numbers are in the second half of the array, and ensure that the relative position between odd numbers and odd numbers, even numbers and even numbers remains unchanged.
Violence solution: direct three cycles. 1. Put the odd number in the array into the temporary storage array. 2. Put the even numbers in the array into the temporary storage array. 3. Put the temporary array back to the original array.
public void reOrderArray(int [] array) {
int[] b = new int[array.length];
int j = 0;
for(int i = 0; i < array.length ; i++) {
if( array[i] % 2 == 1 ){
b[j] = array[i];
j ++;
}
}
for(int i = 0; i < array.length ; i++) {
if( array[i] % 2 == 0 ){
b[j] = array[i];
j ++;
}
}
for(int i = 0; i < array.length ; i++) {
array[i] = b[i];
}
}
The penultimate node in JZ14 lin k ed list
Input a linked list and output the penultimate node in the linked list.
Two ideas: one is to directly traverse the linked list to obtain the length of the linked list. The penultimate node is the positive (n+1-k).
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k <= 0 )
return null;
int length = 0;
ListNode out = head;
while( out != null){
out = out.next;
length ++;
}
if( k > length)
return null;
for(int i = 0; i < length - k ; i++) {
head = head.next;
}
return head;
}
The second is the fast and slow pointer. At the same time, two pointers traverse the linked list. The fast pointer takes k steps first. When fast reaches null, slow will reach the penultimate position.
public ListNode FindKthToTail(ListNode head,int k) {
if( head == null || k <= 0 ) return null;
ListNode slow = head;
ListNode fast = head;
while( k > 0 ){
if( fast == null)
return null;
fast = fast.next;
k--;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
JZ15 reverse linked list
Enter a linked list and output the header of the new linked list after reversing the linked list.
Use three pointers to adjust the position of the pointer.
- The pre pointer points to the last node of the inverted linked list. At first, there is no inversion, so it points to nullptr
- The cur pointer points to the first node of the linked list to be reversed, and the first node to be reversed at the beginning, so it points to head
- The nex pointer points to the second node of the linked list to be reversed.
First, keep the pointer pointing to the next position in nex; Then reverse the operation.
Point the pointer to the next position of the current element to the previous element.
Then connect the current element to the pre.
The current element points to the next element in the original sequence.
public ListNode ReverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode nex = null;
while( cur != null ) {
nex = cur.next;
cur.next = pre;
pre = cur;
cur = nex;
}
return pre;
}
JZ16 combines two sorted linked lists
Input two monotonically increasing linked lists and output the synthesized linked list. Of course, we need the synthesized linked list to meet the monotonic irreducible rule.
There are two ideas. One is to compare directly in turn, and then output the whole linked list. The second is iteration.
Direct comparison requires two pointers to the head of the new linked list. One is to save the header of the new linked list as output; The other is to point to the current element and add it. So at the end of each cycle, it will point to next.
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode newList = null;
ListNode head = null;
if( list1 == null ) return list2;
if( list2 == null ) return list1;
if(list1.val < list2.val){
newList = list1;
list1 = list1.next;
}
else {
newList = list2;
list2 = list2.next;
}
head = newList;
while( !( list1 == null && list2 == null ) ){
if(list1 == null ) {
newList.next = list2;
list2 = list2.next;
} else if (list2 == null ) {
newList.next = list1;
list1 = list1.next;
}else if(list1.val < list2.val) {
newList.next = list1;
list1 = list1.next;
}
else {
newList.next = list2;
list2 = list2.next;
}
newList = newList.next;
}
return head;
}
The second is to get the final result through iteration. What needs to be considered is what is the termination condition of the iteration? Whether both pointers entered are null or at least one is null. When at least one is empty, connect the rest.
public ListNode Merge(ListNode list1,ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
ListNode head = null;
if(list1.val <= list2.val){
head = list1;
head.next = Merge(list1.next, list2);
} else {
head = list2;
head.next = Merge(list1, list2.next);
}
return head;
}
Substructure of JZ17 tree
Input two binary trees a and B to judge whether B is the substructure of A. (ps: we agree that an empty tree is not a substructure of any tree)
Wrong idea:
There are also two ideas
1. Directly traverse all nodes of A and compare with B.
2. Iterative comparison, direct comparison between A and B, if A= B compares whether the left and right subtrees of A are the same as B.
Substructure: the root nodes of tree A and tree B are equal, the left subtree of tree a is equal to the left subtree of tree B, and the right subtree of tree a is equal to the right subtree of tree B.
- Function of recursive function: judge whether two numbers have the same structure. If they are the same, return true, otherwise return false.
- Recursive termination condition: if tree B is empty, it returns true. At this time, it is true whether tree A is empty or not.
Otherwise, if tree B is not empty but tree A is empty, false is returned. At this time, B is not empty but A is empty, which is obviously false. - Next step recursive parameter: if the root node of A is not equal to the root node of B, return false directly. Otherwise, if they are equal, continue to judge the left subtree of A and the left subtree of B, and the right subtree of A and the right subtree of B
Then it is to correctly traverse each root node in tree A and judge these root nodes.
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if( root1 == null || root2 == null ) return false;
return equals(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
}
public boolean equals (TreeNode root1,TreeNode root2) {
if( root2 == null ) return true;
if( root1 == null ) return false;
return root1.val == root2.val && equals(root1.left, root2.left) && equals(root1.right, root2.right);
}
Wrong iteration method:
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if( root1 == null || root2 == null )
return false;
if( equals(root1, root2) )
return true;
else
return HasSubtree(root1.left, root2) || HasSubtree(root1.left, root2);
}
public boolean equals(TreeNode root1,TreeNode root2) {
if( root2 != null ) {
if( root1.val != root2.val )
return false;
else {
boolean left;
boolean right;
if( root2.left != null)
left = equals(root1.left, root2.left);
else
left = false;
if( root2.right != null)
right = equals(root1.right, root2.right);
else
right = false;
if( left && right)
return true;
else
return false;
}
} else return false;
}
Image of JZ18 binary tree
Operate the given binary tree and transform it into a mirror image of the source binary tree.
It is still a traversal problem, but pay attention to the appropriate termination. When the node is null or the two child nodes of the node are empty, exit. In other cases, exchange the positions of two nodes, and then continue to traverse the node.
public void Mirror(TreeNode root) {
TreeNode temp;
if( root == null );
else if( root.left == null && root.right == null ) {
} else {
temp = root.left;
root.left = root.right;
root.right = temp;
Mirror(root.left);
Mirror(root.right);
}
}
JZ19 clockwise print matrix
Enter a matrix and print out each number in clockwise order from the outside to the inside. For example, if you enter the following 4 X 4 matrix: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16, the numbers 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10 will be printed out in turn
For obvious circulation problems, pay attention to the end point of the circulation body. Define the upper, lower, left and right boundaries and constantly shrink the boundaries of the matrix. When out of bounds, terminate the loop.
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> list = new ArrayList<>();
if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
return list;
int up = 0;
int down = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
while(true) {
for(int col = left; col <= right ; col++)
list.add(matrix[up][col]);
up ++;
if(up > down)
break;
for(int row = up; row <= down; row++)
list.add(matrix[row][right]);
right --;
if(right < left)
break;
for(int col = right; col >= left; col--)
list.add(matrix[down][col]);
down --;
if( down < up)
break;
for(int row = down; row >= up; row-- )
list.add(matrix[row][left]);
left ++;
if( left > right)
break;
}
return list;
}
JZ20 stack containing min function
To define the data structure of the stack, please implement a min function in this type that can get the smallest element in the stack (the time complexity should be O (1)).
Use the double stack method. Note: the operation of fetching the top element of the stack in java is the peek() method.
import java.util.Stack;
public class Solution {
Stack<Integer> stack = new Stack<>();
Stack<Integer> stackMin = new Stack<>();
public void push(int node) {
stack.push(node);
if(stackMin.isEmpty())
stackMin.push(node);
else if( node < stackMin.peek())
stackMin.push(node);
else
stackMin.push(stackMin.peek());
}
public void pop() {
stack.pop();
stackMin.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return stackMin.peek();
}
}
In addition to the double stack method, the compression reduction method can also be used. Every element on the stack is related to the minimum value. However, the compression reduction method will be in INT_MIN and INT_MAX, overflow occurs because the difference is too large.
The difference is stored each time. Note that the difference used when leaving the stack should be calculated in the same way as the difference used when entering the stack.
public void push(int node) {
if(stack.isEmpty()){
min = node;
stack.push(0);
} else {
if(node < min) {
stack.push(min - node);
min = node;
} else
stack.push(min - node);
}
}
public void pop() {
if( stack.peek() > 0 ) {
min = min + stack.peek();
stack.pop();
} else
stack.pop();
}
Push in and pop-up sequence of JZ21 stack
Enter two integer sequences. The first sequence represents the push in order of the stack. Please judge whether the second sequence may be the pop-up order of the stack. Assume that all the numbers pushed into the stack are not equal. For example, sequence 1,2,3,4,5 is the pressing sequence of a stack, and sequence 4,5,3,2,1 is a pop-up sequence corresponding to the pressing sequence, but 4,3,5,1,2 cannot be the pop-up sequence of the pressing sequence. (Note: the length of these two sequences is equal)
Note that the pressing sequence does not mean that it is finished at one time. You can press and play a little; Press a little more and play a little more.
Use an auxiliary stack to simulate. Stack each element in the push sequence. When the top element of the stack is the same as the pop-up sequence, pop up the element and move the pointer to the next position of the pop-up sequence, continue to judge whether the top element of the stack is consistent with the pop-up sequence, and repeat the cycle. Continue to press the stack until it is inconsistent.
After the for loop of pressing the stack is completed, if the stack can pop up smoothly and completely, there is no element isEmpty() == true in the stack, otherwise, it is false
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if( pushA.length == 0 || popA.length == 0 || pushA.length != popA.length )
return false;
Stack<Integer> stack = new Stack<>();
int j = 0;
for(int i = 0; i < pushA.length; i++){
stack.push(pushA[i]);
while( !stack.isEmpty() && stack.peek() == popA[j]) {
stack.pop();
j++;
}
}
return stack.isEmpty();
}
}
JZ22 print binary tree from top to bottom
Each node of the binary tree is printed from top to bottom, and the nodes of the same layer are printed from left to right.
Traverse all nodes, but some nodes need to be temporarily stored. The idea of queue is used here, first in, first out. Since queue is an abstract class and cannot be instantiated, it should be instantiated by using the polymorphic characteristics of java. Queue<TreeNode> queue = new LinkedList<>();
The nodes that are traversed to and have no output temporarily are stored in the queue.
Note that related operations of the queue:
- Exceptions will not be thrown when the capacity is insufficient or the queue is empty: offer (add the tail element), peek (access the head element), poll (access the head element and remove it)
- Throw exceptions when the capacity is insufficient or the queue is empty: add, element (access queue element), remove (access queue header element and remove)
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if(root == null) return list;
queue.offer(root);
while( !queue.isEmpty() ) {
TreeNode temp = queue.poll();
list.add(temp.val);
if(temp.left != null) queue.offer(temp.left);
if(temp.right != null) queue.offer(temp.right);
}
return list;
}
}
Postorder traversal of JZ23 binary tree
Enter an integer array to judge whether the array is the result of post order traversal of a binary search tree. If yes, return true; otherwise, return false. Suppose that any two numbers of the input array are different from each other.
Wrong idea:
Directly traverse the binary tree in sequence, and compare with the array at the same time.
It should be noted that the existence of binary tree is not given in the title stem. Therefore, the algorithm should be universal, which needs to start with the data structure of binary search tree. The left subtree is smaller than the root node, and the root node is smaller than the right subtree. This is the correct binary search tree storage idea.
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if( sequence == null || sequence.length == 0 )
return false;
return VerifyHelper(sequence, 0, sequence.length - 1);
}
int i;
public boolean VerifyHelper(int [] sequence, int start, int end) {
if(start >= end ) return true;
int root = sequence[end];
for(i = 0 ; i < end ; i++ ){
if(sequence[i] > root)
break;
}
for(int j = i ; j < end ; j++ ){
if( sequence[j] < root ) {
return false;
}
}
return VerifyHelper(sequence, start, i - 1) && VerifyHelper(sequence, i, end - 1);
}
}
Path with a value in JZ24 binary tree
Enter the root node and an integer of a binary tree, and print out all paths in which the sum of node values in the binary tree is the input integer in dictionary order. Path is defined as a path from the root node of the tree down to the leaf node.
Iteration first, clarify three points:
- What the iteration does: traverse all child nodes, FindPath(TreeNode* root,int sum), and start from the root node to find the path with sum.
- Termination condition of iteration: the node is a leaf node, and the sum of the path is the evaluated value.
- Parameters for the next iteration: starting from the left subtree and right subtree of the node, the parameter passed in is target Val, that is, how much is the difference.
public class Solution {
private ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> list = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if( root == null )
return result;
list.add(root.val);
target -= root.val;
if( target == 0 && root.left == null && root.right == null)
result.add( new ArrayList<Integer>(list));
ArrayList<ArrayList<Integer>> r1 = FindPath(root.left, target );
ArrayList<ArrayList<Integer>> r2 = FindPath(root.right, target );
list.remove(list.size() - 1);
return result;
}
}
Copy of JZ25 complex linked list
Enter a complex linked list (each node has a node value and two pointers, one pointing to the next node and the other special pointer random pointing to a random node). Please make a deep copy of this linked list and return the copied head node. (Note: please do not return the node reference in the parameter in the output result, otherwise the problem determination program will directly return null)
There are several points to pay attention to in this topic:
- The node reference in the parameter cannot appear, that is, you need to instantiate the same number of nodes and assign values to these nodes. At the same time, ensure that the next and random relationships between these nodes correspond one by one.
- Consider the boundary case, that is, when the input linked list is empty.
The steps of the algorithm are as follows: first copy the nodes in the linked list, and then copy the corresponding relationship between the nodes.
HashMap < randomlistnode, randomlistnode > is used to store nodes before and after replication.
import java.util.HashMap;
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
if (pHead == null ) return null;
RandomListNode ppHead = pHead;
HashMap<RandomListNode, RandomListNode> hash = new HashMap<>();
while( pHead != null ) {
RandomListNode node = new RandomListNode(pHead.label);
hash.put(pHead, node);
pHead = pHead.next;
}
pHead = ppHead;
while( pHead != null ) {
RandomListNode node = hash.get(pHead);
node.next = (pHead.next == null )? null : hash.get(pHead.next);
node.random = (pHead.random == null) ? null : hash.get(pHead.random);
pHead = pHead.next;
}
return hash.get(ppHead);
}
}
JZ26 binary search tree and bidirectional linked list
Enter a binary search tree and convert the binary search tree into a sorted two-way linked list. It is required that no new nodes can be created, and only the node pointer in the tree can be adjusted.
According to the meaning of the question, the binary tree is a binary search tree. If you use medium order traversal, the results will be orderly and from small to large, and then rearrange the pointers.
In the process of traversal, the time complexity of judging whether the input is null is high. In order to save time, the three cases should be processed separately, and the data can be processed one layer in advance.
import java.util.ArrayList;
import java.util.Iterator;
public class Solution {
public ArrayList<TreeNode> list = new ArrayList<>();
public TreeNode Convert(TreeNode pRootOfTree) {
if( pRootOfTree == null ) return null;
DFS(pRootOfTree);
if(list.size() == 1)
return pRootOfTree;
for(int i = 0 ; i < list.size() - 1; i++) {
list.get(i).right = list.get(i+1);
list.get(i+1).left = list.get(i);
}
return list.get(0);
}
public void DFS(TreeNode root) {
if(root.left != null)
DFS(root.left);
list.add(root);
if(root.right != null)
DFS(root.right);
}
}
JZ27 string arrangement
Enter a string and print out all the permutations of characters in the string in dictionary order. For example, if you enter the string abc, all strings abc,acb,bac,bca,cab and cba that can be arranged by the characters a, B and C will be printed in dictionary order.
Arrange all the characters in the string, then store them in < set >, remove the duplicate, convert them into ArrayList < string > and sort them. Need attention
- When the parameter passed in is an array, what is actually passed in is its reference, which will change the original value when used.
- After iteration, the used value should be restored.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Set;
import java.util.HashSet;
import java.util.Comparator;
public class Solution {
Set<String> sets = new HashSet<>();
public ArrayList<String> Permutation(String str) {
ArrayList<String> list = new ArrayList<>();
if (str.length() == 0)
return list;
char[] chs = str.toCharArray();
boolean[] used = new boolean[chs.length];
quanpailie(chs, used, chs.length, new StringBuilder());
for (String s : sets) {
list.add(s);
}
list.sort(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.compareTo(o2);
}
});
return list;
}
public void quanpailie(char[] chars, boolean[] used, int pos, StringBuilder sb) {
StringBuilder stringBuilder = new StringBuilder(sb);
boolean[] uu = new boolean[chars.length];
for (int i = 0; i < chars.length; i++)
uu[i] = used[i];
if (pos != 0) {
for (int i = 0; i < chars.length; i++) {
if (!uu[i]) {
stringBuilder.append(chars[i]);
uu[i] = true;
quanpailie(chars, uu, pos - 1, stringBuilder);
uu[i] = false;
stringBuilder.deleteCharAt(stringBuilder.length() - 1);
} else
continue;;
}
} else {
sets.add(stringBuilder.toString());
}
}
}
A number that appears more than half the times in the JZ28 array
A number in the array appears more than half the length of the array. Please find this number. For example, enter an array {1,2,3,2,2,2,2,5,4,2} with a length of 9. Since the number 2 appears five times in the array, more than half the length of the array, 2 is output. If it does not exist, 0 is output.
For a simpler solution, make a direct comparison, and then count whether it is the same. The time complexity here is O(n^2)
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int count = 0;
if(array.length == 1)
return array[0];
for(int i = 0 ; i < array.length - 1 ; i++){
count = 0;
for(int j = i ; j < array.length ; j++ ) {
if( array[i] == array[j] ){
count ++;
}
if( count > array.length / 2)
return array[i];
}
}
return 0;
}
}
If the cycle time is too long, consider optimization and change the termination condition of i from i < array Length - 1 is changed to i < (array. Length + 1) / 2, that is, only the first half of the number is used for comparison. Because the number of required numbers must exceed half of the array length, it is good to compare only the first half of the number.
Another idea is to sort the array first. Since the number of occurrences exceeds half of the length of the array, the number must be the middle number, that is, the number of occurrences of the middle number in the array. If it is greater than half of the length of the array, the number will be output; Otherwise, output 0.
import java.util.Arrays;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
Arrays.sort(array);
int half = array.length/2;
int count = 0;
for( int i = 0; i < array.length ; i ++)
if( array[i] == array[half] )
count++;
if(count > half)
return array[half];
else
return 0;
}
}
If sorting is used, the time complexity depends on the speed of the sorting algorithm.
import java.util.Arrays;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
Arrays.sort(array);
int half = array.length/2;
int count = 0;
for( int i = 0; i < array.length ; i ++)
if( array[i] == array[half] )
count++;
if(count > half)
return array[half];
else
return 0;
}
}
Minimum k number of JZ29
Enter n integers and find the smallest number of K. For example, if you enter 8 numbers: 4,5,1,6,2,7,3,8, the smallest 4 numbers will be 1,2,3,4.
A simpler approach: sort first, and then directly output the first k numbers. The time complexity is O(n^2+k)
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
if( k > input.length)
return list;
Arrays.sort(input);
for(int i = 0 ; i < k ; i++){
list.add(input[i]);
}
return list;
}
}
If you optimize it, start with the sorting. Considering the bubble sorting algorithm, after each round, the one floating to the far right is the maximum value, so you can do the opposite. After each round, the one floating to the far left is the minimum value, and then the value is output. At this time, the time complexity is O(kn).
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
if( k > input.length)
return list;
for(int i = 0 ; i < k; i++) {
for( int j = input.length - 1; j > i ; j-- ){
if( input[j-1] > input[j]){
swap(input, j-1, j);
}
}
list.add(input[i]);
}
return list;
}
public void swap(int[] chars, int i, int j) {
int temp;
temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}
Maximum sum of JZ30 continuous subarrays
HZ occasionally uses some professional questions to fool those non computer majors. Today, after the meeting of the test group, he said again: in the ancient one-dimensional pattern recognition, it is often necessary to calculate the maximum sum of continuous sub vectors. When the vectors are all positive, the problem is well solved. However, if the vector contains negative numbers, should it contain a negative number and expect the positive number next to it to make up for it? For example: {6, - 3, - 2,7, - 15,1,2,2}, the maximum sum of continuous sub vectors is 8 (from 0 to 3). Give an array and return the sum of its largest continuous subsequence. Will you be fooled by it? (the length of the subvector is at least 1)
Direct traversal, listing the sum of all sub vectors.
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length == 0) return 0;
if(array.length == 1) return array[0];
int max = array[array.length-1];
for(int i = 0; i < array.length - 1; i++){
for( int j = i; j <array.length; j++ ) {
max = (Sum(array, i, j) > max ? Sum(array, i, j) : max);
}
}
return max;
}
public int Sum(int[] array, int i, int j) {
int sum = 0;
for(int k = i; k<= j ; k++)
sum += array[k];
return sum;
}
}
In another way, dynamic programming can be used. dp[n] represents the maximum sum of continuous subsequences with the current element as the cut-off point. If dp[n-1] > 0, dp[n]=dp[n]+dp[n-1], because the current number plus a positive number will become larger; If dp[n-1] < 0, dp[n] remains unchanged, because the current number plus a negative number will be smaller. Use a variable max to record the maximum dp value and return it.
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int max = array[0];
for(int i = 1; i < array.length ; i++){
array[i] += array[i-1] > 0 ? array[i-1] : 0;
max = max > array[i] ? max : array[i] ;
}
return max;
}
}
Number of occurrences of 1 in JZ31 integer
Find the number of occurrences of 1 in 113 integers, and calculate the number of occurrences of 1 in 1001300 integers? Therefore, he specially counted the numbers 1, 10, 11, 12 and 13 in 1 ~ 13, so they appeared six times, but he had no way to solve the following problems. ACMer hopes you can help him and make the problem more general. You can quickly find the number of occurrences of 1 in any non negative integer interval (from 1 to 1 in n).
The simple way is to traverse directly.
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int count = 0;
for(int i = 1; i <= n; i++){
int num = i;
while( num != 0) {
if( num % 10 == 1 ) {
count ++;
num = num / 10;
}
}
}
return count;
}
}
However, the space of this method is too complex. So we should optimize it. Solve the situation of each person, then their sum is the required answer. High is the high bit, digital * cur is the current bit, and low is the low bit.
Take 20X4 as an example: when digit=10, i.e. on the tenth digit, there are three situations:
- cur == 0. At this time, the range of the number to be calculated is 0010 ~ 1910, that is, high * Digital
- cur == 1. At this time, the range of the number to be calculated is 0010 ~ 2014, that is, high*digit + low + 1
- cur == others. At this time, the range of the number to be calculated is 0010 ~ 2019, that is (high + 1)*digit
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int res = 0;
int digit = 1;
int high = n / 10;
int cur = n % 10;
int low = 0;
while( high != 0 || cur != 0 ) {
if( cur == 0 ) res += high * digit;
else if ( cur == 1 ) res += high * digit + low + 1;
else res += (high + 1) * digit;
low += cur*digit;
cur = high % 10;
high = high / 10;
digit = digit * 10;
}
return res;
}
}
JZ32 arranges the array into the smallest number
Enter an array of positive integers, put all the numbers in the array together to form a number, and print the smallest of all the numbers that can be spliced. For example, if you enter the array {3, 32321}, the minimum number that these three numbers can be arranged is 321323.
It is similar to sorting, but the difference is that the comparison method of sorting is different. It is not directly compared with the size, but with the size of the same digit. If it is the same, it is compared with the second digit. Finally, output in order. This sort method is also wrong. It should be to compare the two strings directly connected, which is bigger and which is smaller.
import java.util.ArrayList;
import java.lang.String;
public class Solution {
public String PrintMinNumber(int [] numbers) {
String[] strs = new String[numbers.length];
for( int i = 0 ; i < numbers.length ; i ++){
strs[i] = String.valueOf(numbers[i]);
}
for( int i = 0 ; i < numbers.length ; i ++){
for( int j = 0 ; j < numbers.length - 1 -i; j++) {
if( !Compare(strs[j], strs[j+1]) ) {
swap(strs, j, j+1);
}
}
}
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < numbers.length ; i++){
sb.append(strs[i]);
}
return sb.toString();
}
public boolean Compare (String str1, String str2) {
String s1 = str1 + str2;
String s2 = str2 + str1;
if( s1.compareTo(s2) < 0)
return true;
else
return false;
}
public void swap (String[] numbers, int i, int j){
String temp;
temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}
JZ33 ugly number
N umbers containing only qualitative factors 2, 3 and 5 are called ugly numbers. For example, 6 and 8 are ugly numbers, but 14 is not because it contains a quality factor of 7. Traditionally, we regard 1 as the first Ugly Number. Find the nth Ugly Number in the order from small to large.
It can be seen that each number can be factorized into 2^x*3^y*5^z. as long as these results can be orderly arranged in the array, we can get an orderly and non repetitive sequence of ugly numbers.
So how to make it orderly and not repeated. In 2^x, 3^y and 5^z, if x=y=z, the minimum ugly number must be multiplied by 2, but the key is that there may be x > y > Z, so we need to maintain three pointers to record the current minimum value multiplied by 2, 3 and 5, and then add the corresponding pointer + 1 when it is selected as the new minimum value; Because this pointer will gradually traverse the entire array, each value in the final array will be multiplied by 2, 3 and 5, which is to realize our initial idea, but not multiply by 2, 3 and 5 at the same time, but multiply by 2, 3 and 5 when necessary
In order to avoid repetition, we need to verify the minimum value after we get it. If it can be the bottom corresponding to another number * it, the pointer should be + 1.
public class Solution {
public int GetUglyNumber_Solution(int index) {
if (index < 7)
return index;
int[] res = new int[index];
res[0] = 1;
int p2=0, p3=0, p5=0;
for(int i = 1; i < index; i ++){
res[i] = Math.min(res[p2]*2, Math.min(res[p3]*3, res[p5]*5));
if(res[i] == res[p2]*2) p2++;
if(res[i] == res[p3]*3) p3++;
if(res[i] == res[p5]*5) p5++;
}
return res[index-1];
}
}
JZ34 first character that appears only once
Find the first character that appears only once in a string (0 < = string length < = 10000, all composed of letters), and return its position. If not, return - 1 (case sensitive) (counting from 0)
First, traverse, count the number of occurrences, store them in HashMap, and then traverse again to output the first character that appears only once.
import java.util.HashMap;
import java.util.Set;
public class Solution {
public int FirstNotRepeatingChar(String str) {
HashMap<Character, Integer> map = new HashMap<>();
for(int i = 0 ; i < str.length(); i++){
if(map.get(str.charAt(i)) != null) {
int ch = map.get(str.charAt(i));
ch ++;
map.put(str.charAt(i), ch);
} else
map.put(str.charAt(i), 1);
}
for(int i = 0 ; i < str.length(); i++){
if(map.get(str.charAt(i)) == 1)
return i;
}
return -1;
}
}
Of course, this hashmap can also be implemented as an array.
In addition to using this method, you can also directly double cycle to find. When it is greater than 1, it will jump out. Note that the second cycle should also start from 0 in order to make the following comparison.
public class Solution {
public int FirstNotRepeatingChar(String str) {
if(str == null ) return -1;
if(str.length() == 0) return -1;
char[] chars = str.toCharArray();
int pos = -1;
int i = 0, j = 0;
for( i = 0; i < chars.length; i++) {
for( j = 0 ; j < chars.length; j++) {
if( (chars[i] == chars[j]) && i != j )
break;
}
if( j == chars.length) {
pos = i;
break;
}
}
return pos;
}
}
Reverse order pairs in JZ35 array
Two numbers in the array. If the previous number is greater than the following number, the two numbers form an inverse pair. Enter an array and find the total number of reverse pairs P in this array. And output the result of P's modulus of 100000007. That is, output P%1000000007.
Direct enumeration:
public class Solution {
public int InversePairs(int [] array) {
int count = 0;
for(int i = 0;i < array.length ; i++){
for( int j = i + 1; j < array.length ; j ++){
if( array[i] > array[j] ){
count ++;
count %= 1000000007;
}
}
}
return count;
}
}
The idea of merging and sorting. When the left and right arrays to be merged are [3,4], [1,2]. It can be found that the reverse order pairs are 3,1,3,2,4,1,4,2 respectively
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
str = str.substring(1, str.length()-1);
String[] valueArr = str.split(",");
int[] array = new int[valueArr.length];
for (int i = 0; i < valueArr.length; i++) {
array[i] = Integer.parseInt(valueArr[i]);
}
System.out.println(InversePairs(array));
}
public static int cons = 1000000007;
public int InversePairs(int [] array) {
if(array == null) return 0;
int[] temp = new int[array.length];
return mergeSort(array, temp, 0, array.length-1);
}
public int mergeSort(int[] array, int[] temp, int low, int high) {
if(low >= high) return 0;
int res = 0;
int mid = low + ((high -low)>>1);
res += mergeSort (array, temp, low, mid);
res += mergeSort (array, temp, mid + 1, high);
res += merge(array, temp, low, mid, high);
res %= cons;
return res;
}
public int merge(int[] array, int[] temp, int low, int mid, int high) {
int i = low, j = mid + 1,k = low;
int res = 0;
while(i <= mid && j <= high) {
if(array[i] > array[j]) {
res += mid - i + 1;
res %= cons;
temp[k++] = array[j++];
} else
temp[k++] = array[i++];
}
while(i <= mid)
temp[k++] = array[i++];
while(j <= high)
temp[k++] = array[j++];
for (i = low; i <= high; i++)
array[i] = temp[i];
return res;
}
}
JZ36 is the first common node of two linked lists
Enter two linked lists and find their first common node. (note that the incoming data is displayed correctly in the linked list.)
Traverse the two linked lists at the same time. At this time, if the common node is not of the same length, it cannot be judged correctly. Either choose double loop, or choose to make two common nodes in the same length. Since a + b = b + a, if the first linked list is traversed, connect the second linked list; When the second linked list is traversed, the first linked list is connected, so it can ensure that the common nodes are of the same length.
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode p1 = pHead1, p2 = pHead2;
while( p1 != p2) {
p1 = (p1 != null) ? p1.next : pHead2;
p2 = (p2 != null) ? p2.next : pHead1;
}
return p1;
}
}
JZ37 number of occurrences of a number in an ascending array
Counts the number of times a number appears in an ascending array.
Direct traversal. When it is greater than k, return is supported.
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int count = 0;
for(int i = 0; i < array.length; i++){
if( array[i] == k)
count++;
else if (array[i] > k)
return count;
}
return count;
}
}
Use binary search. Find the upper and lower bounds of continuous k.
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int left = 0, right = 0;
int mid;
int l = 0, r = array.length;
while( l < r ) {
mid = l + (r-l)/2;
if( k > array[mid])
l = mid + 1;
else r = mid;
}
left = l;
l = 0;
r = array.length;
while( l < r ) {
mid = l + (r-l)/2;
if( k < array[mid])
r = mid;
else
l = mid + 1;
}
right = l;
return right - left;
}
}
Note: the priority of bit operation is particularly low, which is lower than addition and subtraction.
Depth of JZ38 binary tree
Enter a binary tree and find the depth of the tree. The nodes (including root and leaf nodes) passing from root node to leaf node form a path of the tree, and the length of the longest path is the depth of the tree.
A look at the topic is a traversal problem. For the traversal of numbers, there are three ways: pre order traversal, middle order traversal and post order traversal. The preorder traversal is temporarily used here.
It should be noted that if you enter an empty tree, you should directly return 0 At the same time, the idea of recursion is a little wrong. It should be to find out how deep the left node is and how deep the right node is.
public int TreeDepth(TreeNode root) {
if (root == null) return 0;
if (root.left == null ){
if (root.right == null) {
return 1;
}
return TreeDepth(root.right) + 1;
} else {
if (root.right == null)
return TreeDepth(root.left) + 1;
else {
return TreeDepth(root.left) > TreeDepth(root.right) ? ( TreeDepth(root.left) + 1 ) : (TreeDepth(root.right) + 1);
}
}
}
// Method 2
public int TreeDepth(TreeNode root) {
if(root==null){
return 0;
}
int left=TreeDepth(root.left);
int right=TreeDepth(root.right);
return (left > right) ? (left+1) : (right+1);
}
JZ39 balanced binary tree
Enter a binary tree to judge whether the binary tree is a balanced binary tree. Here, we only need to consider its balance, not whether it is a sorted binary tree.
Balanced binary tree: the height difference of subtrees at any node is less than or equal to 1.
Judge the depth of the left and right subtrees. If the difference is greater than 1, it is an unbalanced tree; If less than or equal to 1, it is a balanced tree.
To calculate the depth of the left and right subtrees, you need to use recursion. Note that if it is not traversal, its return value should be the deepest in its subtree.
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if( root == null )
return true;
else {
int leftDeepth = 0;
int rightDeepth = 0;
leftDeepth = TreeDeepth(root.left);
rightDeepth = TreeDeepth(root.right);
if(leftDeepth - rightDeepth > 1)
return false;
else if( rightDeepth - leftDeepth > 1)
return false;
else
return true;
}
}
public int TreeDeepth(TreeNode root){
int count = 1;
if( root == null)
return 0;
else {
int left = 0;
int right = 0;
left = TreeDeepth(root.left);
right = TreeDeepth(root.right);
count += Math.max(left, right);
return count;
}
}
}
A number that appears only once in the JZ40 array
In an integer array, all but two numbers appear twice. Please write a program to find these two numbers that only appear once.
First traverse the array and use hashmap to store the number of occurrences of each number. Then traverse the hashmap and output the key with vaule of 1.
//Num1 and num2 are arrays with length of 1 respectively. out parameter
//Set num1[0],num2[0] to return results
import java.util.HashMap;
import java.util.Set;
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
boolean first = true;
for(int i = 0 ; i < array.length ; i ++ ){
int ch = 0;
if(map.get(array[i]) == null)
ch = 0;
else
ch = map.get(array[i]);
map.put(array[i], ++ch);
}
Set<Integer> keys = map.keySet();
for( Integer i : keys) {
if(map.get(i) == 1 && first ) {
num1[0] = i;
first = false;
}
else if (map.get(i) == 1 && !first)
num2[0] = i;
}
}
}
Continuous positive sequence with JZ41 and S
Xiao Ming likes math very much. One day when he was doing his math homework, he asked to calculate the sum of 9 ~ 16. He immediately wrote the correct answer is 100. But he is not satisfied with this. He is wondering how many kinds of continuous positive number sequences have a sum of 100 (including at least two numbers). Before long, he got another set of sequences with a continuous positive sum of 100: 18, 19, 20, 21, 22. Now let'S leave the problem to you. Can you quickly find all the continuous positive sequences with sum S? Good Luck!
Output all continuous positive number sequences with sum S. The sequence is from small to large, and the sequence is from small to large.
Direct double loop exhaustive.
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer> > list = new ArrayList<ArrayList<Integer> > ();
int count = 0;
for(int i = 1 ; i <= sum / 2 ; i ++ ) {
int j = i;
count = 0;
ArrayList<Integer> list2 = new ArrayList<>();
while( true ) {
count += j;
if( count < sum ) {
list2.add(j);
j++;
} else if ( count == sum ) {
list2.add(j);
list.add(list2);
} else
break;
}
}
return list;
}
}
// The sum of consecutive positive sequences was 100. There were two groups of '9 10 11 12 13 14 15 16' and '18 19 20 21 22' It can be found that the number between them is the average of this group, or the average is plus or minus 0.5.
JZ42 and are two numbers of s
Input an incrementally sorted array and a number s, and find two numbers in the array so that their sum is exactly S. if the sum of multiple pairs of numbers is equal to s, output the smallest product of the two numbers.
Output two small cases first.
Note: here is a confusing message. If the sum of multiple pairs of numbers is equal to S, the smallest product of the two numbers will be output. From the knowledge of primary school, we can know that for the image surrounded by a rope, the smallest area is the rectangle with the largest side length gap, then the square is slightly larger, and the largest is a circle.
So the smallest product is the two numbers whose sum is S for the first time.
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> list = new ArrayList<Integer>();
for( int i = 0; i < array.length -1; i++ ) {
for( int j = i + 1; j < array.length ; j++ ){
if( array[i] + array[j] == sum ){
list.add(array[i]);
list.add(array[j]);
return list;
}
}
}
return list;
}
}
JZ43 left rotation string
There is a shift instruction in assembly language called circular left shift (ROL). Now there is a simple task to simulate the operation result of this instruction with a string. For a given character sequence S, please output the sequence after shifting it left by K bits. For example, the character sequence S = "abcXYZdef" requires the output of the result after the cyclic left shift of 3 bits, that is, "XYZdefabc". Isn't it simple? OK, take care of it!
Directly use the built-in library functions substring(int begin), substring(int begin, int end)
public class Solution {
public String LeftRotateString(String str,int n) {
if( n > str.length() )
return str;
String string = str.substring(n) + str.substring(0, n);
return string;
}
}
JZ44 reverse word order
Fish, a new employee of Niuke recently, always takes an English magazine and writes some sentences in the book every morning. Cat, a colleague, was very interested in the content written by fish. One day he borrowed it from fish, but he couldn't understand its meaning. For example, "student. a am I". Later I realized that this guy had reversed the order of sentences and words, and the correct sentence should be "I am a student.". Cat is not good at reversing the order of these words one by one. Can you help him?
Split the original string, and then put the resulting words into another array.
Finally, read the array in order.
public String ReverseSentence(String str) {
int count = 0;
for(int i = 0; i < str.length(); i++){
if(str.charAt(i) == ' ')
count++;
}
StringBuilder[] strs = new StringBuilder[count+1];
for(int i = 0 ; i < strs.length ; i++) {
strs[i] = new StringBuilder("");
}
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if( c != ' ' && c != '\0'){
strs[count].append(c);
} else {
count--;
}
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < strs.length - 1 ; i++)
{
sb.append(strs[i].toString());
sb.append(' ');
}
sb.append(strs[strs.length - 1].toString());
return sb.toString();
}
Note that SrtingBuilder[] strs = new SrtingBuilder [] {}; Is not initialized., Each element points to a null value, not a StringBuilder with a null value
JZ45 poker shunzi
LL is in A particularly good mood today, because he went to buy A deck of playing cards and found that there were two kings and two Xiaowang (A deck of cards was originally 54) He randomly drew five cards out of them to test his luck and see if he could draw shunzi. If so, he decided to buy A sports lottery, hehe!! "Hearts A, spades 3, Wang, Wang, Fang Pian 5", "Oh My God!" Not shunzi... LL was unhappy. He thought about it and decided that big / small Wang could be regarded as any number, and A was regarded as 1,J as 11,Q as 12 and K as 13. The above five cards can become "1,2,3,4,5" (the big and small kings are regarded as 2 and 4 respectively), "So Lucky!". LL decided to buy sports lottery tickets. Now, you are required to use this card to simulate the above process, and then tell us how lucky LL is. If the card can form A shunzi, it will output true, otherwise it will output false. For convenience, you can think that the size king is 0.
Get the questions and sort them first. Then count the number of big and small kings, and then count the difference between the first non-zero number and the subsequent number. If they are equal, return false; If there is a difference, if the difference - 1 is greater than the number of 0, it cannot be replaced by size; If less than or equal to, zero of the corresponding quantity will be consumed.
import java.util.Arrays;
public class Solution {
public boolean isContinuous(int [] numbers) {
if( numbers.length != 5 )
return false;
Arrays.sort(numbers);
int count = 0;
for (int i = 0 ; i < numbers.length - 1 ; i++ ){
if(numbers[i] == 0) {
count ++;
} else if( numbers[i+1] == numbers[i] && numbers[i+1] != 0) {
return false;
} else if( numbers[i+1] - numbers[i] - 1 > count )
return false;
else if( numbers[i+1] - numbers[i] - 1 <= count ) {
count -= (numbers[i+1] - numbers[i] - 1);
} else
return true;
}
return true;
}
}
JZ46 children's games
Every International Children's Day, Niuke prepares some small gifts to visit the children in the orphanage. This year is the same. As a senior veteran of Niuke, HF has naturally prepared some small games. Among them, there is a game like this: first, let the children form a big circle. Then, he randomly assigned a number m and asked the child with number 0 to start counting. Every time the child who cries out to m-1 wants to line up and sing a song, and then you can choose any gift in the gift box and don't go back to the circle. Starting from his next child, continue to count 0... m-1... This way... Until the last child is left, you don't need to perform, and get the valuable "famous detective Conan" Collection Edition of Niuke (the quota is limited!!). Please try to think about which child will get this gift? (Note: Children's numbers are from 0 to n-1)
If there are no children, please return - 1
Simulation method: use array to simulate bad deletion, so use list to save. At the same time, cur pointer is used to point to the starting element. m may be greater than n, and the cycle should start from scratch. After deletion, the cur pointer should be backtracked once.
import java.util.ArrayList;
import java.util.List;
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(n <= 0)
return -1;
else {
List<Integer> list = new ArrayList();
for (int i = 0 ; i < n ; i ++){
list.add(i);
}
int cur = -1;
while (list.size() > 1) {
for(int i = 0 ; i < m ; i ++){
cur++;
if(cur == list.size()) {
cur = 0;
}
}
list.remove(cur);
cur--;
}
return list.get(0);
}
}
}
Recursive problem. (M% n) is deleted every time. After knowing that the x-th element is deleted next time (n-1), then (M% N + x)% n is deleted this time; I.e. (x + m)% n
import java.util.ArrayList;
import java.util.List;
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if ( n <= 0 ) return -1;
return f(n, m);
}
public int f(int n, int m ) {
if ( n == 1 ) return 0;
int x = f(n-1, m);
return ( x + m ) % n;
}
}
JZ47 find 1 + 2 + 3 +... + n
For 1 + 2 + 3 +... + n, it is required that keywords such as multiplication and division, for, while, if, else, switch, case and conditional judgment statements (A?B:C) cannot be used.
Because we can't use judgment, multiplication and division and other methods. So use logical operations.
public class Solution {
public int Sum_Solution(int n) {
int sum = n;
boolean stop = (sum != 0 ) && ( ( sum += Sum_Solution( sum - 1 )) != 0);
return sum;
}
}
JZ48 addition without addition, subtraction, multiplication and division
Write a function and find the sum of two integers. It is required that the four operation symbols +, -, *, / shall not be used in the function body.
This question examines the problem of the phase of two numbers in bit operation, that is, consider the sum of two numbers themselves + carry three numbers. When there is no carry, and is bitwise XOR; When there is carry, and is bitwise XOR, and then bitwise XOR with carry... Until there is no carry.
So first add (bitwise XOR), then calculate the carry (bitwise AND), and then judge whether there is carry.
Note: carry is to carry another bit on the original bit, that is, it needs to move one bit to the left.
public int Add(int num1,int num2) {
int sum = 0;
while( num2 != 0 ){
sum = num1^num2;
num2 = (num1&num2) << 1;
num1 = sum;
}
return num1;
}
JZ49 converts a string to an integer
Converting a string to an integer requires that the library function that converts an integer from a string cannot be used. If the value is 0 or the string is not a legal value, 0 is returned
Traverse directly from tail to bottom. If the current is the first bit, there are three situations: symbol bit, number and others. Not the first, there are only two, numbers and others.
The strategy of converting to numbers when they are numbers.
The distance from the end of 10 to the power * the number of current positions + the number before.
public int StrToInt(String str) {
int res = 0;
for( int i = str.length() - 1; i >= 0 ; i-- ){
if( i == 0 ) {
if( str.charAt(i) == '+' ) {
return res;
}
if( str.charAt(i) == '-' ) {
return -res;
}
if( str.charAt(i) >= '0' && str.charAt(i) <= '9' ) {
res = ((int) Math.pow(10, (str.length() - 1 - i)))*(str.charAt(i) - '0') + res;
return res;
}
return 0;
} else {
if( str.charAt(i) >= '0' && str.charAt(i) <= '9' ) {
res = ((int) Math.pow(10, (str.length() - 1 - i)))*(str.charAt(i) - '0') + res;
} else
return 0;
}
}
return 0;
}
Duplicate number in JZ50 array
The length of n is in the range of 1-0. Some numbers in the array are repeated, but I don't know how many numbers are repeated. I don't know how many times each number is repeated. Please find any duplicate number in the array. For example, if you enter an array {2,3,1,0,2,5,3} with a length of 7, the corresponding output is the first repeated number 2.
Repeat problem, use hashmap to store the number of duplicates, and finally traverse again to get the result.
import java.util.HashMap;
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// Special attention should be paid here to return any duplicate one and assign duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0 ; i < length ; i ++ ){
if( !map.containsKey(numbers[i]) )
map.put(numbers[i], 1);
else {
int num = map.get(numbers[i]);
num++;
map.put(numbers[i], num);
}
}
for( int i = 0 ; i < length ; i++) {
if( map.get(numbers[i]) > 1 ) {
duplication[0] = numbers[i];
return true;
}
}
return false;
}
}
JZ51 build product array
Given an array A[0,1,..., n-1], please construct an array B[0,1,..., n-1], where the element B[i]=A[0]A[1]... * A[i-1]A[i+1]... * A[n-1]. Division cannot be used. (Note: it is stipulated that B[0] = A[1] * A[2] *... * A[n-1], B[n-1] = A[0] * A[1] *... * A[n-2];)
For the case where the length of A is 1, B is meaningless and cannot be constructed, so this case will not exist.
Direct for loop algorithm:
public int[] multiply(int[] A) {
int[] B = new int[A.length];
for(int i = 0; i < A.length; i++){
if( i == 0 ) {
B[i] = A[1];
for(int j = 2; j < A.length ; j++ )
B[i] = B[i] * A[j];
} else if( i == A.length - 1 ) {
B[i] = A[0];
for(int j = 1; j < A.length - 1 ; j++ )
B[i] = B[i] * A[j];
} else {
B[i] = A[0];
for(int j = 1; j < i ; j ++) {
B[i] = B[i] * A[j];
}
for(int j = i+1; j < A.length ; j ++) {
B[i] = B[i] * A[j];
}
}
}
return B;
}
However, it is obvious that the time complexity is particularly high according to the above method: O(n^2). Observe the law of B []. Each time you just don't multiply by B[i], it can be imagined as a matrix with one less diagonal. Since division cannot be used, the matrix can be separated from the diagonal. The left part and the right part are calculated first and then right.
public int[] multiply(int[] A) {
int[] B = new int[A.length];
int[] C = new int[A.length];
int[] D = new int[A.length];
for(int i = A.length - 1; i >= 0 ; i --){
if( i == A.length - 1)
C[i] = 1;
else{
C[i] = A[i+1] * C[i+1];
}
}
for(int i = 0; i < A.length; i ++){
if(i == 0)
D[i] = 1;
else{
D[i] = D[i-1] * A[i-1];
}
}
for(int i = 0; i < A.length; i ++){
B[i] = C[i] * D[i];
}
return B;
}
Time complexity becomes: O(3n)
JZ52 regular expression matching
Please implement a function to match including '.' Regular expressions for and '*'. Character '.' in mode Represents any character, and '*' indicates that the character before it can appear any time (including 0 times). In this question, matching means that all characters of the string match the whole pattern. For example, the string "aaa" matches the patterns "a.a" and "ab*ac*a", but not "aa.a" and "ab*a".
Solution 1: use String library function to directly ac
public boolean match(char[] str, char[] pattern){
return new String(str).matches(new String(pattern));
}
Solution 2: iteratively compare each character, of course, and then compare the next characters. In Java, you need to pass two numbers s and p as pointers to the currently compared elements.
- Both pointers point to the end and the match is complete.
- str is not empty, but pattern is already empty. Matching failed.
- The next position of the current position is not empty, and '*' appears. Change the matching rule. If the element in this position is the same or '.' There are two cases: 1) repeat 0 times, then the next judgment pointer position should be s, p+2, 2) repeat 1 or more times, and the next position is s+1, p. If this position is a different element, there is only one case. Repeat 0 times, and the pointer position of the next judgment should be s, p+2. Then its return value can meet one of the two.
- The next position of the current position is not empty, but '*' does not appear. Continue to judge.
- In other cases, matching fails.
public boolean match(char[] str, char[] pattern){
if (str == null || pattern == null)
return false;
return matchCore(str, 0, pattern, 0);
}
private boolean matchCore(char[] str, int s, char[] pattern, int p) {
//The next four lines are the end of recursion flag. Only when both pointers point to the end is the match, otherwise it will not match
if (s == str.length && p == pattern.length)
return true;
if (s < str.length && p == pattern.length)
return false;
//Although the ratio is in the position of P, when * appears after P, the rule needs to be changed.
if (p + 1 < pattern.length && pattern[p + 1] == '*') {
//* appears, and s and P point to the same. The three cases are juxtaposed
if ((s < str.length && pattern[p] == '.')
|| (s < str.length && pattern[p] == str[s])) {
return matchCore(str, s, pattern, p + 2)
|| matchCore(str, s + 1, pattern, p);
// || matchCore(str, s + 1, pattern, p + 2);
} else {//If there is a *, and s and p point to different points, then the character in front of * appears 0 times, p+2
return matchCore(str, s, pattern, p + 2);
}
}
//If it indicates that P is not followed by *, then make a conventional judgment. If it is the same, give the pointer + 1 respectively
if (s < str.length && (pattern[p] == str[s] || pattern[p] == '.'))
return matchCore(str, s + 1, pattern, p + 1);
//p is not followed by *, nor is it Give you support, if you dare to make a difference, it must be false
return false;
}
JZ53 is a string representing a numeric value
Please implement a function to judge whether the string represents a numeric value (including integer and decimal). For example, the strings "+ 100", "5e2", "123", "3.1416" and "- 1E-16" all represent numeric values. But "12e", "1a3.14", "1.2.3", "± 5" and "12e+4.3" are not.
Regular expression method.
import java.util.regex.Pattern;
public class Solution {
public static boolean isNumeric(char[] str) {
String pattern = "^[-+]?\\d*(?:\\.\\d*)?(?:[eE][+\\-]?\\d+)?$";
String s = new String(str);
return Pattern.matches(pattern,s);
}
}
Judging by conditions: the following characters will appear in the string:
- Sign * / -: appears only after the first digit or E/e
- decimal point.: Only one, before E.
- Index E/e: there is only one. After it appears, it must be followed by an integer (if there is no decimal point in front, it occupies a decimal point position).
- Normal number: char > = '0' & & char < = '9'
public class Solution {
public boolean isNumeric(char[] str) {
boolean point = false, exp = false;
for (int i = 0 ; i < str.length ; i ++ ) {
if(str[i] == '+' || str[i] == '-') {
if(i == 0 || str[i-1] == 'E' || str[i-1] == 'e') {
continue;
} else
return false;
}
if( str[i] == '.' ){
if( !point ) {
point = true;
continue;
} else
return false;
}
if( (str[i] == 'E' || str[i] == 'e') ) {
if( !exp && i != 0 && i != str.length - 1) {
exp = true;
point = true;
continue;
} else
return false;
}
if ( str[i] >= '0' && str[i] <= '9' ) {
continue;
} else
return false;
}
return true;
}
}
The first non repeating character in JZ54 character stream
Please implement a function to find the first character that appears only once in the character stream. For example, when only the first two characters "go" are read out from the character stream, the first character that appears only once is "g". When the first six characters "google" are read from the character stream, the first character that appears only once is "l". If there is no character that appears once in the current character stream, the return # character.
In the old method, hashmap is used to save, but it should be noted that the input is in order, so LinkedHashMap is used here.
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Set;
public class Solution {
HashMap<Character, Integer> map = new LinkedHashMap<Character, Integer>();
//Insert one char from stringstream
public void Insert(char ch)
{
if(map.containsKey(ch))
map.put(ch, -1);
else
map.put(ch, 1);
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
Set keys = map.keySet();
for(Object ch : keys ){
if(map.get(ch) == 1)
return (char) ch;
}
return '#';
}
}
JZ55 entry node in linked list
Give a linked list. If it contains a ring, please find the entry node of the ring of the linked list. Otherwise, null will be output.
Get the title and hash directly. If it exists in the table, that is, the node is the entrance of the ring. If it does not exist, add the point to hashmap and point to the next point.
public ListNode EntryNodeOfLoop(ListNode pHead)
{
HashMap<ListNode, Integer> list = new HashMap<>();
while( pHead != null ) {
if( list.containsKey(pHead) ) {
return pHead;
} else {
list.put(pHead, 1);
pHead = pHead.next;
}
}
return null;
}
JZ56 delete duplicate nodes in linked list
In a sorted linked list, there are duplicate nodes. Please delete the duplicate nodes in the linked list. The duplicate nodes are not retained and the chain header pointer is returned. For example, the linked list 1 - > 2 - > 3 - > 3 - > 4 - > 4 - > 5 is 1 - > 2 - > 5 after processing
The ratio is the val value of the node, and duplicate nodes are not retained. Then in the deletion process, there must be a pointer to the previous node.
First, traverse the whole linked list to find out the duplicate nodes.
Then traverse the linked list again. At this time, it should be noted that it should not only use one pointer, but three. A pointer to the linked list itself for traversal. The second one points to the new head node. The third point to the current node of the new linked list.
Note: if the third node does not automatically move to the end at the end of the traversal, you need to end it yourself.
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
if(pHead == null) return pHead;
ListNode p = pHead;
HashMap<Integer, Integer> list = new LinkedHashMap<>();
while ( p!= null ) {
if( list.containsKey(p.val) ) {
list.put(p.val, -1);
} else
list.put(p.val, 1);
p = p.next;
}
p = pHead;
ListNode head = null;
while (p != null) {
if( list.get(p.val) == 1 ) {
if( head == null ) {
head = p;
pHead = head;
}
else {
pHead.next = p;
pHead = pHead.next;
}
}
p = p.next;
}
pHead.next = null;
return head;
}
}
The next node of JZ57 binary tree
Given a binary tree and one of its nodes, please find the next node in the middle order traversal order and return. Note that the nodes in the tree contain not only left and right child nodes, but also pointers to parent nodes.
Direct simulation. Find the root node first. Then traverse the whole number from the root node. Finally, traverse again and output the next node.
import java.util.ArrayList;
public class Solution {
ArrayList<TreeLinkNode> list = new ArrayList<>();
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
TreeLinkNode temp = pNode;
while( pNode.next != null ) {
pNode = pNode.next;
}
TreeLinkNode root = pNode;
Bian(root);
for( int i = 0 ; i < list.size(); i++ ) {
if ( list.get(i) == temp ) {
return ( i == list.size() - 1 ) ? null : list.get(i + 1 );
}
}
return null;
}
public void Bian( TreeLinkNode root ){
if( root != null ) {
Bian(root.left);
list.add(root);
Bian(root.right);
}
}
}
Of course, you can also directly output the next node traversed in the middle order. There are mainly the following situations:
- The root node only considers its right subtree. If there is a right node, it is the leftmost child node of the right node. If there is no value of the leftmost child node, it is itself. null if there is no right node.
- For the left node, consider its right subtree. If there is a right node, it is the leftmost child node of the right node. If there is no value of the leftmost child node, it is itself. If there is no right node, it is its parent node.
- For the right node, consider its right subtree. If there is a right node, it is the leftmost child node of the right node. If there is no value of the leftmost child node, you need to trace along the parent node until you find that a node is the left subtree of its parent node. If there is such a node, the parent node of this node is the next node we want to find. If there is no such situation, null is returned.
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if(pNode == null) return null;
if(pNode.next == null ) {
// root node
if(pNode.right == null) {
return null;
} else {
TreeLinkNode pRight = pNode.right;
while (pRight.left != null ) {
pRight = pRight.left;
}
return pRight;
}
}
if ( pNode.next.left == pNode ) {
// left node
if(pNode.right == null )
return pNode.next;
else {
TreeLinkNode pRight = pNode.right;
while (pRight.left != null ) {
pRight = pRight.left;
}
return pRight;
}
} else {
// right node
// See if there is a right node. If there is, see if there is a left node in the right node. It is the leftmost node; If the right node has no left node, the right node will be returned.
// Return null if no
if( pNode.right != null ) {
TreeLinkNode pRight = pNode.right;
while (pRight.left != null ) {
pRight = pRight.left;
}
return pRight;
} else {
TreeLinkNode pRight = pNode;
if(pRight.next == null)
return null;
while (pRight.next.left != pRight ) {
pRight = pRight.next;
if (pRight.next == null) {
return null;
}
}
return pRight.next;
}
}
}
}
The above situation is poorly summarized. Take other people's induction:
- There is a right subtree, and the next node is the leftmost node in the right subtree
- If there is no right subtree and the node is the left subtree of the parent node of the node, the next node is the parent node of the node
- If there is no right subtree and the node is the right subtree of the parent node of the node, we keep tracing along the parent node until we find that a node is the left subtree of its parent node. If there is such a node, the parent node of this node is the next node we want to find. If there is no matching node, there is no next node.
public TreeLinkNode GetNext(TreeLinkNode pNode) {
// 1.
if (pNode.right != null) {
TreeLinkNode pRight = pNode.right;
while (pRight.left != null) {
pRight = pRight.left;
}
return pRight;
}
// 2.
if (pNode.next != null && pNode.next.left == pNode) {
return pNode.next;
}
// 3.
if (pNode.next != null) {
TreeLinkNode pNext = pNode.next;
while (pNext.next != null && pNext.next.right == pNext) {
pNext = pNext.next;
}
return pNext.next;
}
return null;
}
JZ58 symmetric binary tree
Please implement a function to judge whether a binary tree is symmetrical. Note that if a binary tree is the same as the mirror image of the binary tree, it is defined as symmetrical.
Iterate directly from top to bottom. Note: To compare whether two binary trees are symmetrical, first compare whether the values of their root nodes are consistent, and then compare whether their left and right subtrees correspond to each other, that is, root1 left && root2. right, root1. right && root2. left
boolean isSymmetrical(TreeNode pRoot) {
if (pRoot == null)
return true;
else
return isSame(pRoot.left, pRoot.right);
}
boolean isSame(TreeNode r1, TreeNode r2) {
if (r1 != null && r2 != null) {
if(r1.val == r2.val)
return isSame(r1.left, r2.right) && isSame(r1.right, r2.left);
else
return false;
}
if( r1 == null && r2 == null )
return true;
return false;
}
The algorithm cannot handle the case that the nodes are not the same. The left and right roots and the right and left roots of the tree are traversed once respectively, and the obtained values are the traversal values of the two groups, which can be compared respectively.
boolean isSymmetrical(TreeNode pRoot)
{
if ( pRoot == null ) return true;
if( pRoot.left == null && pRoot.right == null )
return true;
if( (pRoot.left == null) ^ (pRoot.right == null) )
return false;
TreeNode head = pRoot;
first(pRoot);
last(head);
for(int i = 0 ; i < firstList.size(); i++) {
if( firstList.get(i) == lastList.get(i))
continue;
else
return false;
}
return true;
}
void first(TreeNode root) {
if(root.left != null )
first(root.left);
if(root.right != null )
first(root.right);
if(root != null)
firstList.add(root.val);
}
void last(TreeNode root) {
if(root.right != null )
last(root.right);
if(root.left != null )
last(root.left);
if(root != null)
lastList.add(root.val);
}
JZ59 print binary tree in font order
Please implement a function to print the binary tree in zigzag, that is, the first line is printed from left to right, the second layer is printed from right to left, the third line is printed from left to right, and so on.
First, traverse the tree in the middle order. Note that the result of each layer should be ArrayList < integer >, and then put the result of this layer into ArrayList < ArrayList < integer > >. Traverse ArrayList < ArrayList < integer > > for the last time and flip some of its layers as needed. The flipping method used here is out of the stack and into the stack.
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
public int Deepth(TreeNode root) {
int deepth = 0;
if( root == null )
return 0;
if (root != null ) {
deepth ++;
int left = 0 ;
int right = 0;
if (root.left != null )
left = Deepth(root.left);
if (root.right != null)
right = Deepth(root.right);
return Math.max(left, right) + deepth;
}
return deepth;
}
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(pRoot == null)
return lists;
int deepth = Deepth(pRoot);
for(int i = 0 ; i < deepth; i++) {
ArrayList<Integer> list = new ArrayList<>();
lists.add(list);
}
Bianli(pRoot, 0);
for(int i = 0 ; i < lists.size() ; i++ ) {
if(i % 2 == 0 ) {
res.add(lists.get(i));
} else {
res.add(reverse(lists.get(i)));
}
}
return res;
}
public void Bianli(TreeNode pRoot, int deepth) {
if(pRoot != null )
lists.get(deepth).add(pRoot.val);
if(pRoot.left != null)
Bianli(pRoot.left, deepth + 1);
if(pRoot.right != null)
Bianli(pRoot.right, deepth + 1);
}
public ArrayList<Integer> reverse(ArrayList<Integer> list) {
ArrayList<Integer> newList = new ArrayList<Integer>();
Stack<Integer> stack = new Stack<>();
for(int i = 0 ; i < list.size() ; i++)
stack.push(list.get(i));
for(int i = 0 ; i < list.size() ; i++)
newList.add(stack.pop());
return newList;
}
}
Printing the data of each layer can be regarded as breadth first traversal, that is, it can be realized through queues. Flip can be inserted upside down, or you can use collections Reverse() method.
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >() ;
if( pRoot == null ) return res;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
boolean rev = true;
queue.add(pRoot);
while( !queue.isEmpty() ) {
int size = queue.size();
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i = 0 ; i < size ; i++ ) {
TreeNode node = queue.poll();
if(node == null)
continue;
if(rev)
list.add(node.val);
else
list.add(0, node.val);
queue.offer(node.left);
queue.offer(node.right);
}
if(list.size() != 0 )
res.add(list);
rev = !rev;
}
return res;
}
}
JZ60 prints a binary tree into multiple lines
The binary tree is printed from top to bottom by layer, and the nodes of the same layer are output from left to right. Each layer outputs one line.
Like the last one, there's nothing to say. Even simpler, there is no need to flip.
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >() ;
if( pRoot == null ) return res;
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(pRoot);
while( !queue.isEmpty() ) {
int size = queue.size();
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i = 0 ; i < size ; i++ ) {
TreeNode node = queue.poll();
if(node == null)
continue;
list.add(node.val);
queue.offer(node.left);
queue.offer(node.right);
}
if(list.size() != 0 )
res.add(list);
}
return res;
}
}
JZ61 serialized binary tree
Please implement two functions to serialize and deserialize the binary tree respectively
Serialization of binary tree refers to saving the result of traversal of a binary tree as a string in a certain format, so that the binary tree established in memory can be saved for a long time. Serialization can be modified based on the binary tree traversal method of first order, middle order, second order and sequence. The result of serialization is a string. During serialization, an empty node (#) is represented by a symbol to! Indicates the end of a node value (value!).
Deserialization of binary tree refers to reconstructing the binary tree according to the serialized string result str obtained in a certain traversal order.
For example, we can serialize a binary tree with a root node of 1 as "1", and then parse it back through our own function.
Directly follow the pre order traversal or middle order traversal to access all nodes of the binary tree, and then return different values for different situations. And deserialization, using string split("!") Method to split the serialized strings to get small strings. Generate the corresponding node according to the situation, or empty.
String Serialize(TreeNode root) {
return SerializeHelper(root);
}
String SerializeHelper(TreeNode root) {
String str = new String();
if(root == null) return str;
str += root.val + "!";
if(root.left != null)
str += SerializeHelper(root.left);
else
str += "#!";
if(root.right != null)
str += SerializeHelper(root.right);
else
str += "#!";
return str;
}
TreeNode Deserialize(String str) {
if(str.length() == 0 || str == null) return null;
String[] split = str.split("!");
return Deserialize2(split);
}
private int index = 0;
TreeNode Deserialize2(String[] strs) {
if(strs[index].equals("#")) {
index++;
return null;
} else {
TreeNode node = new TreeNode(Integer.parseInt(strs[index]));
index++;
node.left = Deserialize2(strs);
node.right = Deserialize2(strs);
return node;
}
}
If you are trying to solve this problem, you can directly save the Node as a global variable.
The k-th node of JZ62 binary search tree
Given a binary search tree, please find the k-th smallest node. For example, in (5, 3, 7, 2, 4, 6, 8), the value of the third node in the order of node value is 4.
If the binary search tree is traversed in middle order, the number of the k-1 position in the ArrayList obtained after traversal is the required node. But at this time, we should pay attention to the boundary conditions, i.e. K < = 0 and k > list size()
TreeNode KthNode(TreeNode pRoot, int k)
{
if(pRoot == null) return null;
Traverse(pRoot);
if( k <= 0 ) return null;
if( k > list.size() )
return null;
return list.get(k-1);
}
ArrayList<TreeNode> list = new ArrayList<>();
public void Traverse(TreeNode root) {
if(root.left != null)
Traverse(root.left);
if(root != null )
list.add(root);
if(root.right != null)
Traverse(root.right);
}
Median in JZ63 data stream
How to get the median in a data stream? If an odd number of values are read out from the data stream, the median is the value in the middle after all values are sorted. If an even number of values are read from the data stream, the median is the average of the middle two numbers after all values are sorted. We use the Insert() method to read the data stream and the GetMedian() method to get the median of the current read data.
Insert the data stream first, then sort, and then get the median.
ArrayList<Integer> nums = new ArrayList<>();
public void Insert(Integer num) {
nums.add(num);
nums.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
});
}
public Double GetMedian() {
int size = nums.size();
if (size == 0 ) {
return 0.00;
} else if ( size % 2 == 1 ) {
return nums.get(size / 2) * 1.00;
} else {
return (nums.get( size / 2) + nums.get( size / 2 - 1 ) )/2.00;
}
}
Maximum value of JZ64 sliding window
Given an array and the size of the sliding window, find the maximum value in all sliding windows. For example, if you enter the array {2,3,4,2,6,2,5,1} and the size 3 of the sliding window, there are six sliding windows, and their maximum values are {4,4,6,6,5}; There are six sliding windows for array {2,3,4,2,6,2,5,1}: {[2,3,4], 2,6,2,5,1}, {2, [3,4,2], 6,2,5,1}, {2,3, [4,2,6], 2,5,1}, {2,3,4, [2,6,2], 5,1}, {2,3,4,2, [6,5,5], 1}, {2,3,4,2,6, [2,5,1]}. When the window is larger than the length of the array, null is returned.
First consider the boundary case. If the size is too large or too small, directly return an empty list. In addition, we need to pay attention to the size of the sliding window and its relationship with the starting point and ending point of the sliding window.
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> list = new ArrayList<>();
if(size > num.length)
return list;
if(size == num.length) {
int max = num[0];
for(int i = 1; i < size; i++){
max = num[i] > max ? num[i] : max;
}
list.add(max);
return list;
}
if(size <= 0 )
return list;
for( int i = 0 ; i <= num.length - size ; i++ ){
int max = num[i];
for(int j = i + 1 ; j < i + size ; j ++ ) {
max = num[j] > max ? num[j] : max;
}
list.add(max);
}
return list;
}
Path in JZ65 matrix
By observing the given parameters, we can find that matrix and str are one-dimensional arrays. In other words, rows and cols specify the rows and columns of the matrix, so in order to move up, down, left and right in the matrix, either convert the two-dimensional coordinates into one-dimensional, or convert the one-dimensional coordinates into two-dimensional.
At the same time, it is also an obvious recursion.
When i and j exceed the bounds and the characters in the positions are different, the characters have been used out of date and do not meet the conditions. False is returned. When the current position is equal, enter the next recursion. When entering the next recursion, you should note that this character has been used once, and you need to set the symbol position to true. If it doesn't work, you need to set the value to false again for the next match.
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
boolean[] flags = new boolean[matrix.length];
for( int i = 0 ; i <rows; i++ ){
for( int j = 0 ; j < cols; j++) {
if(helper(matrix, rows, cols, i, j, str, 0, flags))
return true;
}
}
return false;
}
public boolean helper(char[] matrix, int rows, int cols, int i, int j, char[] str, int pos, boolean[] flags){
int index = i * cols + j;
if( i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[pos] || flags[index] )
return false;
if( pos == str.length - 1 ) return true;
flags[index] = true;
if( helper(matrix, rows, cols, i + 1, j , str, pos + 1, flags)
|| helper(matrix, rows, cols, i , j + 1, str, pos + 1, flags)
|| helper(matrix, rows, cols, i - 1, j , str, pos + 1, flags)
|| helper(matrix, rows, cols, i , j - 1, str, pos + 1, flags))
return true;
flags[index] = false;
return false;
}
}
Range of motion of JZ66 robot
There is a square with m rows and n columns on the ground. A robot starts to move from the grid with coordinates 0 and 0. Each time, it can only move one grid in the left, right, upper and lower directions, but it cannot enter the grid where the sum of digits of row coordinates and column coordinates is greater than k. For example, when k is 18, the robot can enter the grid (35,37) because 3 + 5 + 3 + 7 = 18. However, it cannot enter the grid (35,38) because 3 + 5 + 3 + 8 = 19. How many grids can the robot reach?
First, break down the problem into several parts.
- Can this grid go
- Can the next grid go
- Please sum up your numbers
Then start from 0, 0 and carry out dynamic planning.
Judge the following questions in turn:
- Is this step in scope?
- This step?
- Can't we go?
- Can we go next?
public class Solution {
int counts = 0;
public int movingCount(int threshold, int rows, int cols)
{
boolean[] flags = new boolean[rows*cols];
if( rows == 0 || cols == 0) return 0;
move(threshold, rows, cols, 0, 0, flags);
return counts;
}
public boolean move(int threshold, int rows, int cols, int i, int j, boolean[] flags){
int index = cols * i + j;
// Is it out of bounds
if( i < 0 || i >= rows || j < 0 || j >= cols ) {
return false;
}
// Judge whether this step has been taken?
if(flags[index])
return false;
// Judge whether the current step can be taken?
if(count(i) + count(j) <= threshold) {
if(flags[index] == false){
flags[index] = true;
counts++;
}
// Can we judge the next step?
if( move(threshold, rows, cols, i-1, j , flags)
|| move(threshold, rows, cols, i+1, j , flags)
|| move(threshold, rows, cols, i, j-1 , flags)
|| move(threshold, rows, cols, i, j+1 , flags)){
return true;
} else
return false;
} else {
return false;
}
}
public int count(int i ) {
int sum = 0;
while ( i != 0 ){
sum += i % 10;
i /= 10;
}
return sum;
}
}
JZ67 cutting rope
Here is a rope with a length of N. please cut the rope into m segments of integer length (M and N are integers, n > 1, M > 1, m < = n). The length of each segment of rope is recorded as k[1],..., k[m]. What is the possible maximum product of k[1]x... xk[m]? For example, when the length of the rope is 8, we cut it into three sections with lengths of 2, 3 and 3 respectively. At this time, the maximum product is 18.
Mathematically speaking, a rectangle formed by a piece of rope has the largest area only when it is surrounded by a square. Then extending to this problem, it is possible to get the maximum value only when the cut lengths are equal. Then f(x) is the maximum product and X is the length of a single piece of rope, that is, f(x) = x^(n/x). To make f(x) maximum, we can find its derivative when the first derivative is zero. In this formula, the maximum value is obtained when x = e. But x is an integer, so x=3.
So the question turns to how many 3's are multiplied.
- Can be divided by 3, (n/3)
- For the remaining 1, take one 3 from the front (n/3) 3 and form 2 * 2 with 1
- The rest 2, direct multiplication.
public class Solution {
public int cutRope(int target) {
if( target < 5 )
return target;
if( target % 3 == 0 ) {
return (int) Math.pow(3, target / 3);
} else if( target % 3 == 1 ) {
return (int) Math.pow(3, target / 3 - 1) * 4;
} else
return (int) Math.pow(3, target / 3 ) * 2;
}
}
Violent solution:
Directly simulate the process of cutting rope.
public int cutRope(int target) {
if(target == 2) {
return 1;
}
else if(target == 3) {
return 2;
}
return bak(target);
}
public int bak(int n) {
if( n < 5 )
return n;
int max = 0;
for(int i = 1 ; i < n ; ++i ){
max = i * bak(n - i ) > max ? i * bak(n - i ) : max;
}
return max;
}