笔记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--) {