剑指offer-3

2020-06-27

剑指offer day3

22 、链表中倒数第k个节点 https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

剑指offer中对这道题有一个隐蔽性的判断条件，即我们需要判断k是否大于0且小于链表的长度，这就意味着我们一定要遍历一遍链表，然后获得整个链表的长度。leetcode相对于更加弱化了一点，在这里我们直接利用快慢指针即可

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
            if(head==null||k<0) return null;
        ListNode fast=head;
        ListNode slow=head;
      //先让快指针走k步，然后当快指针到达链表尾部时，慢指针此时所在的位置就是链表中倒数第k个位置
        for(int i=0;i<k;i++){
            fast=fast.next;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

24、反转链表 https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

递归

class Solution {
    public ListNode reverseList(ListNode head) {
           if(head==null||head.next==null) return head;
        ListNode newNode=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return newNode;
    }
}

非递归

class Solution {
    public ListNode reverseList(ListNode head) {
          if(head==null||head.next==null) return head;
      //创建一个新的头节点，遍历整个链表， 然后将其挂接
        ListNode newNode=null;
        ListNode cur=head;
        while(cur!=null){
           ListNode temp=cur.next;
          cur.next=newNode;
            newNode=cur;
            cur=temp;
        }
        return newNode;
        
           
    }
}

25、合并两个排序的链表 https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

该题类似于归并排序的最后一个步骤，merge两个排好序的数组，这里也用一样的思路来进行

非递归

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode dummy=new ListNode(0);
           ListNode cur=dummy;
    while(l1!=null&&l2!=null){
        if(l1.val<=l2.val){
            cur.next=l1;
            l1=l1.next;
            cur=cur.next;
        }else{
            cur.next=l2;
            l2=l2.next;
            cur=cur.next;
        }
    }
        if(l1!=null) cur.next=l1;
        if(l2!=null) cur.next=l2;
        return dummy.next;
    }
}

递归

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
           if(l1==null)return l2;
           if(l2==null) return l1;
        if(l1.val<=l2.val){
            l1.next=mergeTwoLists(l1.next,l2);
            return l1;
        }else{
            l2.next=mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

26、树的子结构 https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/

经典双递归

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null||B==null)return false;
      //继续递归的判断A的左子树和A的右子树
         return helper(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
    }
  //辅助函数，判断B是否为A的子结构
    private boolean helper(TreeNode A,TreeNode B){
        if(B==null)return true;
        if(A==null) return false;
        if(A.val!=B.val)return false;
        return helper(A.left,B.left)&&helper(A.right,B.right);
    }
}

27、二叉树的镜像 https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/

非递归-BFS

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
           if(root==null) return null;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int n=queue.size();
            for(int i=0;i<n;i++){
              //在层序遍历的时候直接对左右两个节点进行交换
                TreeNode cur=queue.poll();
                TreeNode temp=cur.left;
                cur.left=cur.right;
                cur.right=temp;
                if(cur.left!=null) queue.add(cur.left);
                if(cur.right!=null) queue.add(cur.right);
            }
        }
        return  root;
    }
}

递归

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
           if(root==null) return null;
       TreeNode left=root.left;
        root.left=mirrorTree(root.right);
        root.right=mirrorTree(left);
        return root;
    }
}

28、对称的二叉树 https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/

递归判断

class Solution {
    public boolean isSymmetric(TreeNode root) {
              if(root==null) return true;
              return helper(root,root);
    }
    private boolean helper(TreeNode s,TreeNode t){
         if(s==null&&t==null) return true;
            if(s==null||t==null) return false;
            if(s.val!=t.val) return false;
        return isSame(s.left,t.right)&&isSame(s.right,t.left);
    }
}

29、顺时针打印矩阵 https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/

经典搜索模拟题，碰到边界掉转方向

class Solution {
    public int[] spiralOrder(int[][] matrix) {
            if(matrix.length==0||matrix[0].length==0) return new int[0];
             int m=matrix.length;
             int n=matrix[0].length;
        int res[]=new int[m*n];
        boolean[][]vis=new boolean[m][n];
        List<Integer>list=new ArrayList<>();
        //初始方位
        int a=0,b=0,d=1;
        int dx[]={-1,0,1,0};
        int dy[]={0,1,0,-1};
        for(int i=0;i<m*n;i++){
            list.add(matrix[a][b]);
             vis[a][b]=true;
            int x=a+dx[d],y=b+dy[d];
          //碰到边界
           if(x<0||x>=m||y<0||y>=n||vis[x][y]==true){
               d=(d+1)%4;
               x=a+dx[d];
               y=b+dy[d];
           }
            a=x;
            b=y;
        }
        for(int i=0;i<list.size();i++){
            res[i]=list.get(i);
        }
        return res;
    }
}

30、包含min函数的栈 https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/submissions/

利用两个栈实现最小栈，辅助栈为单调栈

class MinStack {

    Stack<Integer>stack1;
    Stack<Integer>stack2;
    public MinStack() {
           stack1=new Stack<>();
           stack2=new Stack<>();
    }
    
    public void push(int x) {
           stack1.push(x);
           if(stack2.isEmpty()) stack2.push(x);
        else{
            stack2.push(Math.min(x,stack2.peek()));
        }
    }
    public void pop() {
          stack1.pop();
          stack2.pop();
    }
    public int top() {
            return stack1.peek();
    }    
    public int min() {
          return stack2.peek();
    }
}

31、栈的压入、弹出序列 https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/

用栈去模拟该过程

class Solution{
     public boolean validateStackSequences(int[]pushed,int []popped){
           Stack<Integer>stack=new Stack<>();
           int j=0;
       for(int num:pushed){
          stack.push(num);
         //当栈顶元素和出栈的第一个元素相同，将该元素弹出，指针后移，继续判断.
         while(j<pushed.length&&!stack.isEmpty()&&stack.peek()==popped[j]){
             j++;
             stack.pop();
         }
       }
       return j==pushed.length;
     }
}

32-1、从上到下打印二叉树 https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/

BFS

class Solution{
    public int[] levelOrder(TreeNode root){
         if(root==null) return new int[0];
       List<Integer>list=new ArrayList<>();
       Queue<TreeNode>queue=new LinkedList<>();
      queue.add(root);
      
      while(!queue.isEmpty()){
           TreeNode cur=queue.poll();
          list.add(cur.val);
          if(cur.left!=null) queue.add(cur.left);
          if(cur.right!=null) queue.add(cur.right);
      }
      int res[]=new int[list.size()];
      for(int i=0;i<list.size();i++){
        res[i]=list.get(i);
      }
      return res;
    }
}