Point to the offer part
The list
Merges two sorted lists
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
}
if(list1.val <= list2.val){
list1.next = Merge(list1.next,list2);
return list1;
}
else {
list2.next = Merge(list1,list2.next);
returnlist2; }}}Copy the codeCopy complex linked lists
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
if(pHead == null){
returnnull; } // add A1 to A (RandomListNode curNode = pHead);while(curNode ! = null){ RandomListNodecloneNode = new RandomListNode(curNode.label);
cloneNode.next = curNode.next;
curNode.next = cloneNode; curNode = curNode.next.next; } // iterate over the list and copy the old node's random pointer to the new node;while(curNode ! = null){ // RandomListNode nextNode = new RandomListNode(curNode.label); // nextNode = curNode.next; curNode.next.random = curNode.random == null? null:curNode.random.next; curNode = curNode.next.next; } // Split the linked list into the copied list and the original list. RandomListNode pclone = curNode.next;while(curNode ! =null){ RandomListNodecloneNode = curNode.next;
curNode.next = cloneNode.next;
cloneNode.next = cloneNode.next==null? null:cloneNode.next.next;
curNode=curNode.next;
}
returnpclone; }}Copy the codeAn array of
Prints the array clockwise
The idea is: first summarize the outer ring printing law for 4 directions, and then can summarize the inner ring and outer ring printing similarity
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> printList = new ArrayList<Integer>();
if(matrix==null || matrix.length==0){
return printList; } int rlen = matrix.length-1; int clen = matrix[0].length-1; // Be careful of this areaprintMatrix (0, 0, rlen, clen,printList,matrix);
return printList;
}
public void printMatrix(int startrow,int startcol,int endrow,int endcol,ArrayList<Integer> printList,int[][] matrix){
if(startrow < endrow && startCol <endcol){// When printing, it is best to think clearly about the logic of printing. In fact, you can write while thinking about ideasfor(int j=startcol; j<=endcol; j++)printList.add(matrix[startrow][j]); / / rightfor(int i=startrow+1; i<=endrow-1; i++)printList.add(matrix[i][endcol]); / /for(int j=endcol; j>=startcol; j--)printList.add(matrix[endrow][j]); / / leftfor(int i=endrow-1; i>=startrow+1; i--)printList.add(matrix[i][startcol]); / /printMatrix(startrow+1,startcol+1,endrow-1,endcol-1,printList,matrix);
}
else if(startrow == endrow && startcol<endcol){
for(int j=startcol; j<=endcol; j++)printList.add(matrix[startrow][j]);
}
else if(startrow<endrow && startcol==endcol){
for(int i=startrow; i<=endrow; i++)printList.add(matrix[i][startcol]);
}
else if(startrow == endrow && startcol == endcol){
printList.add(matrix[startrow][startcol]);
}
else {
return; }}} /* 12 3 4 5 6 7 9 10 11 12 13 14 15 16 */Copy the codeThe stack
The stack containing the min function
There are two methods: one is to borrow the auxiliary stack to keep the top element of the stack always the smallest, and the other is to maintain a variable that records the minimum value
- Maintains a variable that records minimum values
import java.util.Stack; import java.util.Iterator; Public class Solution {Stack<Integer> s = new Stack<Integer>(); //1 public void push(int node) { s.push(node); } public voidpop() {
s.pop();
}
public int top() {
return s.peek();
}
public int min() { int min=s.peek(); int tmp=0; Iterator<Integer> it = s.iterator(); / / 2while(it.hasNext()){//3
tmp=it.next();
if(min>tmp){ min=tmp; }}returnmin; }}Copy the code- Auxiliary stack
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> minStack = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
if(minStack.empty() || node < minStack.peek())
minStack.push(node);
}
public void pop() {
if(stack1.peek() == minstack.peek ()) // Since minStack maintains a minimum value for stack1, minStack should also pop minstack.pop () when stack1 does not have that minimum value; stack1.pop(); } public inttop() {
return stack1.peek();
}
public int min() {
returnminStack.peek(); }}Copy the codeStack push in, pop-up sequence
Idea: through the actual stack operation to simulate the stack pop-up, push in
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
//3 4 5 2 1
if(pushA==null || popA == null || pushA.length==0||popA.length==0||pushA.length! =popA.length){return false;
}
Stack<Integer> s = new Stack<Integer>();
int i=0,j=0;
s.push(pushA[i++]);
while(j<=popA.length-1){
while(popA[j]! =s.peek()){if(i == pushA.length) return false;
s.push(pushA[i++]);
}
s.pop();
j++;
}
return true; }}Copy the codeThe queue
Prints the binary tree from the top down
Use a queue to achieve the breadth of the binary tree traversal, which can be simulated directly with ArrayList
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> result = new ArrayList<>();
ArrayList<TreeNode> queue = new ArrayList<>();
if(root == null){
return result;
}
queue.add(root);
while(queue.size()! =0){ TreeNode tmp = queue.remove(0);if(tmp.left ! =null){ queue.add(tmp.left); }if(tmp.right ! =null){ queue.add(tmp.right); } result.add(tmp.val); }returnresult; }}Copy the code