剑指offer day4

2020-06-28

剑指offer day4

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

这连续三题都是一样的套路，BFS

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

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

与上一题也没什么不一样的，我们只需要加一个条件进行反转就可以了

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
           List<List<Integer>> res=new ArrayList<>();
           if(root==null) return res;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        int count=0;
        while(!queue.isEmpty()){
            int n=queue.size();
            List<Integer>list=new ArrayList<>();
            for(int i=0;i<n;i++){
                TreeNode cur=queue.poll();
                list.add(cur.val);
                if(cur.left!=null) queue.add(cur.left);
                if(cur.right!=null) queue.add(cur.right);
            }
          //当count为奇数时，反转这个集合
            if(count%2==1){
                Collections.reverse(list);
            }
            res.add(new ArrayList<>(list));
            count++;
        }
        return res;
    }
}

33、二叉搜索树的后序遍历序列 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

本题我们要充分利用树，以及二分搜索树的充分性质，首先我们可以很容易的找出根节点，即后续遍历的最后一个数。

我们可以依靠这个根节点，把树分为左子树和右子树，即我们即将完成一个建树的过程，这在之前的根据前序遍历和中序遍历中已经体现过。 所有小于根节点的数，应该都是左子树，所有大于根节点的数，都是右子树。

class Solution {
    public boolean verifyPostorder(int[] postorder) {
            return helper(postorder,0,postorder.length-1);
        
    }
    private boolean helper(int []postorder,int l,int r){
         if(l>=r) return true;
        //根节点
         int value=postorder[r];
         int k=l;
        while(postorder[k]<value) k++;
        for(int i=k;i<r;i++){
            //如果此时右子树中含有小于根节点的树，不可能建树
            if(postorder[i]<value) return false;
        }
        return helper(postorder,l,k-1)&&helper(postorder,k,r-1);
    }
}

34、二叉树中和为某一值的路径 https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

dfs+回溯

class Solution{
  private List<List<Integer>>res=new ArrayList<>();
   public List<List<Integer>> pathSum(TreeNode root, int sum){
        dfs(root,sum,new ArrayList<>());
     return res;
   }
  private void dfs(TreeNode root,int sum,List<Integer>list){
          if(root==null) return ;
          list.add(root.val);
          sum-=root.val;
    //到达叶子节点并且此时和为sum
     if(root.left==null&&root.right==null&&sum==0) res.add(new ArrayList<>(list));
     dfs(root.left,sum,list);
    dfs(root.right,sum,list);
    //回溯
    list.remove(list.size()-1);

 }
}

35、复杂链表的复制 https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/

首先我们很容易的想到空间复杂度为O(n)的解法，我们利用一个哈希表存储复制的节点

class Solution{
  public Node copyRandomList(Node head){
        Map<Node,Node>map=new HashMap<>();
       Node node=head;
    while(node!=null){
       Node copy=new Node(node.val);
      map.put(node,copy);
      node=node.next;
    }
    //重置node，接下来处理next和random指针
    node=head;
    while(node!=null){
          map.get(node).next=map.get(node.next);
          map.get(node).random=map.get(node.random);
          node=node.next;
    }
    return map.get(head);
  }
}

但是我们更应该学习原地解法，即我们不利用额外的空间复杂度。

将这个步骤分为三步

将所有链表复制一份，并且放在该链表的后面，例如 1->2->3->4 —-> 1->1->2->2->3->3->4->4
我们处理random指针
将所有的复制节点拼接起来

class Solution {
    public Node copyRandomList(Node head) {
        //复制链表，并且接在原节点的后面
         for(Node node=head;node!=null;){
             Node copy=new Node(node.val);
             Node next=node.next;
             node.next=copy;
             copy.next=next;
             node=next;
         }
        //处理random指针
        for(Node node=head;node!=null;node=node.next.next){
            if(node.random!=null){
                node.next.random=node.random.next;
            }
        }
        
        //拼接链表
        Node dummy=new Node(0);
        Node cur=dummy;
        for(Node node=head;node!=null;node=node.next){
             cur.next=node.next;
             cur=node;
            
        }
        return dummy.next;
    }
}

36、二叉搜索树与双向链表 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

我们只要记录上一个节点即可。

这里我们对二叉搜索树进行中序遍历，这样得到的序列是有序的

class Solution {
    private  Node pre=null,head=null;
    public Node treeToDoublyList(Node root) {
            if(root==null) return null;
        inOrder(root);
      //第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点
        head.left=pre;
        pre.right=head;
        return head;
    }
  //中序遍历
    private void inOrder(Node root){
            if(root==null) return ;
        inOrder(root.left);
        root.left=pre;
     //如果上一个节点不为空，使其连接为循环链表
        if(pre!=null){
           pre.right=root;
        }
       //如果上一个节点为空，那么该节点为头节点
      else  head=root;
        pre=root;
        inOrder(root.right);
    }
}

37、序列化二叉树 https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/

我们利用前序遍历来对其进行序列化的过程.

public class Codec {

     private StringBuilder sb=new StringBuilder();
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
           dfs_s(root);
           return sb.toString();
    }

  private void dfs_s(TreeNode root){
          if(root==null){
            sb.append("null,");
            return ;
          }
     //前序遍历
        sb.append(root.val);
        sb.append(",");
       dfs_s(root.left);
      dfs_s(root.right);
  }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
          String str[]=data.split(",");
          List<String>list=new LinkedList<>(Arrays.asList(str));
         return dfs_d(list);
    }
  private TreeNode dfs_d(List<String>list){
          if(list.get(0).equals("null")){
             list.remove(0);
            return null;
          }
      TreeNode root=new TreeNode(Integer.valueOf(list.get(0)));
      list.remove(0);
      root.left=dfs_d(list);
      root.right=dfs_d(list);
    return root;
  }
}

38、字符串的排列 https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

其实就是全排列题目的变题，这里我们可以利用set集合去重，本质还是dfs+回溯

class Solution{
private List<String>list=new ArrayList<>();
private StringBuilder sb=new StringBuilder();
public String[] permutation(String s){
    char c[]=s.toCharArray();
   boolean vis[]=new boolean [c.length];
   dfs(vis,c);
   String res[]=new String[list.size()];
  for(int i=0;i<list.size();i++){
        res[i]=list.get(i);
    }
   return res; 
 }
private void dfs(boolean[]vis,char[]c){
   if(sb.length()==c.length){
       list.add(sb.toString());
      return ;
   }
  Set<Character> set=new HashSet<>();
  for(int i=0;i<c.length;i++){
      if(vis[i]==false){
        if(set.contains(c[i])) continue;
        sb.append(c[i]);
        set.add(c[i]);
        vis[i]=true;
        dfs(vis,c);
        vis[i]=false;
        sb.deleteCharAt(sb.length()-1);
      }
  }
}  
}

39、数组中出现次数超过一半的数字 https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/

摩尔投票法:

每次从序列中选出两个不相同的数字删除掉。

最后剩下的一个数字或几个相同的数字，就是出现总和大于一半的数字。

class Solution{
   public int majorityElement(int nums[]){
        if(nums==null||nums.length==0) return -1;
        int res=nums[0];
     int count=1;
     for(int i=1;i<nums.length;i++){
        if(count==0){
          res=nums[i];
          count++;
        }
       else if(nums[i]==res)count++;
       else if(nums[i]!=res) count--;
     }
     return res;
   }
}

40、最小的k个数 https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

如果我们直接排序，那么时间复杂度为O(nlogn)

class Solution{
  public int[] getLeastNumbers(int[] arr, int k) {
      if(k==0) return new int[0];
     Arrays.sort(arr);
     int res[]=new int[k];
    for(int i=0;i<k;i++){
      res[i]=arr[i];
    }
    return res;
  }
}

这题我们可以利用堆的性质，从堆中取出最大，最小元素都是O(1)的操作。但是总效率不高

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k==0) return new int[0];
         PriorityQueue<Integer>queue=new PriorityQueue<>((a,b)->b-a);
        for(int num:arr){
            if(queue.size()<k){
            queue.add(num);
        } else if(queue.peek()>num){
                queue.poll();
                queue.add(num);
            }
        }
        int res[]=new int[k];
            int index=0;
            while(!queue.isEmpty()){
                res[index++]=queue.poll();
            }
        return res;
    }
}

利用计数排序

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
           if(arr.length==0||k==0)  return new int[0];
          int count[]=new int[10001];
          for(int num:arr){
             count[num]++;
          }
      int res[]=new int[k];
      int index=0;
      for(int i=0;i<count.length;i++){
        while(index<k&&count[i]-->0){
           res[index++]=i;
        }
        if(index==k) break;
      }
      return res;
    }
}