笔记1

用两个栈实现队列

1            、进栈时候进入第一个栈内

2 
  
 
  
 
  
 
  
 
  
 
  
、出栈时将栈1的内容再次压入栈2中 
  
  
  
  
  
 ，即正向

3











、如果栈2没有元素
  
  
  
  
  
  ，弹栈需要栈1进栈

4 
  
  
  
  
  
 、如果栈2有元素
 


 


 


 


 


 

，即上一次进栈元素没有全部弹栈 
 
 
 
 
 
，直接弹栈

package esay.jz9用两个栈实现队列; ​ 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() { if (stack2.isEmpty()) { while (stack1.size() != 0) { stack2.push(stack1.pop()); } } return stack2.pop(); } }

旋转数组的最小数字

/** * 二分法实现 * * @param array * @return */ public static int minNumberInRotateArray(int[] array) { if (array.length == 0) { return 0; } ​ int l = 0; int r = array.length - 1; ​ while (l < r - 1) { int mid = (l + r) >> 1; if (array[l] < array[mid]) { l = mid; //说明mid是在左边递减数列中 } else if (array[r] > array[mid]) { r = mid; //说明mid是在右边递减数列中 } else { int result = array[0]; for (int i = 0; i < array.length; i++) { result = Math.min(result, array[i]); } return result; } } ​ return array[r]; }

二进制中1的个数

package esay.JZ15二进制中1的个数; ​ public class Solution { public static void main(String[] args) { System.out.println(new Solution().NumberOf1(10)); } public int NumberOf1(int n) { int res = 0; for (int i = 0; i < 32; i++) { if ((n & 1) == 1) { res++; } n >>= 1; } return res; } } ​

打印从1到最大的n位数

package esay.JZ17打印从1到最大的n位数; ​ public class Solution { /** * 代码中的类名 
  
  
  
  
  
 、方法名

 


 


 


 


 


 
、参数名已经指定
   
   
   
   
   
   ，请勿修改
 

 

 

 

 

 
，直接返回方法规定的值即可 * * * @param n int整型 最大位数 * @return int整型一维数组 */ public int[] printNumbers (int n) { // write code here int max = (int) Math.pow(10, n); int[] result = new int[max -1]; for (int i = 1; i <= max - 1; i++) { result[i - 1] = i; } return result; } }

删除链表的节点

package esay.JZ18删除链表的节点; ​ public class Solution { /** * 代码中的类名 
 
 
 
 
 
、方法名 
   
   
   
   
   
  、参数名已经指定 

 

 

 

 

 

，请勿修改            ，直接返回方法规定的值即可 * * @param head ListNode类 * @param val int整型 * @return ListNode类 */ public ListNode deleteNode(ListNode head, int val) { // write code here ListNode p = head; //判断是否删除的是头结点 if (p.val == val) { head = p.next; return head; } //如果不是遍历删除 while (p.next != null) { if (p.next.val == val) { p.next = p.next.next; } else { p = p.next; } } return head; } } ​ ​ class ListNode { int val; ListNode next = null; ​ public ListNode(int val) { this.val = val; } }

链表中倒数最后k个结点

1
 

 

 

 

 

 
、将节点全部放入list集合中

2
 

 

 

 

 

 
、将最后第length - k 个元素输出即可

package esay.JZ22链表中倒数最后k个结点; ​ import java.util.*; ​ public class Solution { /** * 代码中的类名            、方法名 

 
 

 
 

 
 

 
 

 
 

 
、参数名已经指定

 
 

 
 

 
 

 
 

 
 

 
 ，请勿修改











，直接返回方法规定的值即可 * * @param pHead ListNode类 * @param k int整型 * @return ListNode类 */ public ListNode FindKthToTail(ListNode pHead, int k) { // write code here if (k == 0) { return null; } List<ListNode> list = new ArrayList<>(); while (pHead != null) { list.add(pHead); pHead = pHead.next; } if (list.size() < k) { return null; } return list.get(list.size() - k); } } ​ class ListNode { int val; ListNode next = null; ​ public ListNode(int val) { this.val = val; } }

反转链表

1











、准备一个list

2                  、对链表遍历                  ，每个元素都插入list的第一个位置即可实现反转

List -> add(index, element); // 插入特定位置

3 
 
 
 
 
 
 
 
 
 
 
 
、创建一个新的链表接收即可

package esay.JZ24反转链表; ​ import java.util.ArrayList; import java.util.List; ​ class ListNode { int val; ListNode next = null; ​ ListNode(int val) { this.val = val; } } ​ public class Solution { public ListNode ReverseList(ListNode head) { if (head == null) { return null; } ​ List<ListNode> reverse = new ArrayList<>(); while (head != null) { reverse.add(0, head); head = head.next; } ​ ListNode temp = reverse.get(0); ListNode result = temp; for (int i = 1; i < reverse.size(); i++) { temp.next = reverse.get(i); temp = temp.next; } temp.next = null; return result; } } ​

合并两个排序的链表

1

















、保证下一个元素不为空
 
 
 
 
 
 
 
 
 
 
 
 ，即temp.next = list2; 不能使用temp = list2;

package esay.JZ25合并两个排序的链表; ​ class ListNode { int val; ListNode next = null; ​ ListNode(int val) { this.val = val; } } public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if (list1 == null || list2 == null) { return list1 != null ? list1 : list2; } ListNode temp = new ListNode(-1); ListNode result = temp; ​ while (list1 != null && list2 != null) { if (list1.val >= list2.val) { temp.next = list2; list2 = list2.next; } else { temp.next = list1; list1 = list1.next; } temp = temp.next; } ​ if (list1 != null) { temp.next = list1; return result.next; } else { temp.next = list2; return result.next; } } ​ public static void main(String[] args) { ListNode temp = new ListNode(0); ListNode result = temp; ​ temp.next = new ListNode(1); temp = temp.next; temp.next = null; ​ while (result != null) { System.out.println(result.val); result = result.next; } } }

二叉树的镜像

1            、递归进行

package esay.JZ27二叉树的镜像; ​ import java.util.*; ​ class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; ​ public TreeNode(int val) { this.val = val; } } ​ public class Solution { /** * 代码中的类名 
  
 
  
 
  
 
  
 
  
 
  
、方法名











、参数名已经指定

















，请勿修改            ，直接返回方法规定的值即可 * * @param pRoot TreeNode类 * @return TreeNode类 */ public TreeNode Mirror(TreeNode pRoot) { // write code here if (pRoot == null) { return null; } ​ TreeNode pLeft = Mirror(pRoot.left); TreeNode pRight = Mirror(pRoot.right); ​ pRoot.left = pRight; pRoot.right = pLeft; ​ return pRoot; } }

对称的二叉树

1 
  
  
  
  
  
 、左右不为空
  
 
  
 
  
 
  
 
  
 
  
 ，且值相同

package esay.JZ28对称的二叉树; ​ class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; ​ public TreeNode(int val) { this.val = val; ​ } ​ } public class Solution { boolean isSymmetrical(TreeNode pRoot) { return recursion(pRoot, pRoot); } ​ public boolean recursion(TreeNode root1, TreeNode root2) { if (root1 == null && root2 == null) { return true; } ​ if (root1 == null || root2 == null || root1.val != root2.val) { return false; } ​ return recursion(root1.left, root2.right) && recursion(root1.right, root2.left); } } ​

顺时针打印矩阵

1 
  
  
  
  
  
 、从外到内一层一层打印

package esay.JZ29顺时针打印矩阵; ​ import javax.management.MBeanRegistration; import javax.swing.plaf.nimbus.AbstractRegionPainter; import java.util.ArrayList; public class Solution { ​ public static void main(String[] args) { int[][] a = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}}; System.out.println(new Solution().printMatrix(a)); } ​ public ArrayList<Integer> printMatrix(int [][] matrix) { if (matrix.length == 0) { return null; } ​ ArrayList<Integer> res = new ArrayList<>(); //左边界 int left = 0; //右边界 int right = matrix[0].length - 1; //上边界 int up = 0; //下边界 int down = matrix.length - 1; ​ while (left <= right && up <= down) { //左边界到右边界 for (int i = left; i <= right; i++) { res.add(matrix[up][i]); } up++; if (up > down) { break; } for (int i = up; i <= down; i++) { res.add(matrix[i][right]); } right--; if (left > right) { break; } for (int i = right; i >= left; i--) { res.add(matrix[down][i]); } down--; if (up > down) { break; } for (int i = down; i >= up ; i--) {