剑指offer-6

剑指offer day6

51、数组中的逆序对 https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

回忆一下归并排序，其中在merge操作的时候我们可以很容易的发现逆序对，那么接下来我们利用merge_sort来寻找逆序对。

直接写出merge_sort 模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution{
  public int reversePairs(int[] nums){
      return merge_sort(nums,0,nums.length-1);
  }
  private int merge_sort(int[]nums,int l,int r){
    if(l>=r) return 0;
    int mid=l+(r-l)/2;
    int res=merge_sort(nums,l,mid)+merge_sort(nums,mid+1,r);
    int temp[]=new int[r-l+1];
     int i=l,j=mid+1;
    for(int k=0;k<r-l+1;k++){
      if(i>mid){
        temp[k]=nums[j++];
        continue;
      }
      if(j>r){
        temp[k]=nums[i++];
        continue;
      }
      if(nums[i]<=nums[j]){
        temp[k]=nums[i++];
      }else{
        //nums[i]>nums[j] 产生逆序对
       //并且可以很容易得到此时逆序对的个数为mid-i+1
        res+=mid-i+1;
        temp[k]=nums[j++];
      }
    }
    for(int k=0;k<r-l+1;k++){
       nums[l+k]=temp[k];
    }
    return res;
  }
}

52、两个链表的第一个公共节点 https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

首先说一下通用做法，我们直接利用Set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      if(headA==null||headB==null) return null;
           Set<ListNode>set=new HashSet<>();
          while(headA!=null){
            set.add(headA);
            headA=headA.next;
          }
         while(headB!=null){
           if(set.contains(headB)) return headB;
           headB=headB.next;
         }
      return null;
    }
}

但是上述解法效率不高.接下来我们尝试寻求一种效率更高的解法

假设链表A的长度为a，链表B的长度为b，且两者交集的长度为c

即如果有交集的话，a+c+b=b+c+a

如果没有交集 a+b=b+a

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
 public ListNode getIntersectionNode(ListNode headA,ListNode headB){
    if(headA==null||headB==null) return null;
   ListNode l1=headA,l2=headB;
     while(l1!=l2){
      if(l1==null){
        l1=headB;
      }else{
        l1=l1.next;
      }
      if(l2==null){
        l2=headA;
      }else{
        l2=l2.next;
      }
     }
   return l1;
 }
}

如果使用三目运算符，代码看起来比较简洁

1
2
3
4
5
6
7
8
9
10
11
class Solution{
 public ListNode getIntersectionNode(ListNode headA,ListNode headB){
    if(headA==null||headB==null) return null;
   ListNode l1=headA,l2=headB;
     while(l1!=l2){
          l1=l1==null?headB:l1=l1.next;
          l2=l2==null?headA:l2=l2.next;
     }
   return l1;
 }
}

在热评中看到这样一句话： 两个节点不断的在对方的轨迹中寻找对方的身影，只要两人有交集，就终会相遇。

53-1、在排序数组中查找数字 https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/

题目的意思是让统计一个数字在排序数组中出现的位置

我们可以先用二分法查找出左边界，然后右边线性搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution{
  public int search(int[] nums, int target){
         if(nums==null||nums.length==0) return 0;
         int l=0,r=nums.length;
    while(l<r){
       int mid=l+(r-l)/2;
       if(nums[mid]<target) l=mid+1;
      else r=mid;
    }
     int res=0;
    for(int i=l;i<nums.length;i++){
      if(nums[i]==target) res++;
    }
    return res;
  }
}

或者我们可以直接利用二分法求出左右边界，然后就可以求出正确答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int search(int[] nums, int target) {
            if(nums==null||nums.length==0) return 0;
        int l=0,r=nums.length;
       while(l<r){
           int mid=l+(r-l)/2;
           if(nums[mid]<target) l=mid+1;
           else r=mid;
       }
        int start=l;
        l=0;
        r=nums.length;
        while(l<r){
            int mid=l+(r-l)/2;
            if(nums[mid]>target) r=mid;
            else l=mid+1;
        }
       int end=l-1;
        return end-start+1;
    }
}

53-2、0～n-1中缺少的数字 https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内

我们可以直接利用二分查找，如果当前某个数，不在自己的位置上，那么在他之前一定发生了缺失。

因为一个递增的排序数组，从0开始，每一个数都应该在自己的索引处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int missingNumber(int[] nums) {
           int l=0,r=nums.length;
            while(l<r){
                int mid=l+(r-l)/2;
              //说明在此之前一定发生了乱序，那么在前半部分继续搜索
                if(nums[mid]!=mid) r=mid;
                else  l=mid+1;
                
            }
        return l;
     
    }
}

54、二叉搜索树的第k大节点 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

二叉搜索树的一个极其重要的性质就是其中序遍历是有序的，这里我们可以直接对其进行中序遍历，然后取出第k个大节点，虽然有点浪费，但是是最直接的方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
  List<Integer>list=new ArrayList<>();
    public int kthLargest(TreeNode root, int k) {
        inOrder(root);
      return list.get(list.size()-k);
    }
  private void inOrder(TreeNode root){
      if(root==null) return ;
    inOrder(root.left);
    list.add(root.val);
    inOrder(root.right);
  }
}

或者不用开O（n）的空间，当找到第k个节点的时候直接返回结果 但是记住这里是第K大，即我们应该对其进行逆序遍历，那么先遍历右子树，然后左子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int res=0;
    int count=0;
    public int kthLargest(TreeNode root, int k) {
       inOrder(root,k);
        return res;
    }
    private void inOrder(TreeNode root,int k){
          if(root==null) return ;
        inOrder(root.right,k);
        count++;
        if(k==count) res=root.val;
         inOrder(root.left,k);
    }
}

55-1、二叉树的深度 https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/

BFS求深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxDepth(TreeNode root) {
         if(root==null) return 0;
      Queue<TreeNode>queue=new LinkedList<>();
      queue.add(root);
      int res=0;
      while(!queue.isEmpty()){
           int n=queue.size();
        for(int i=0;i<n;i++){
          TreeNode cur=queue.poll();
          if(cur.left!=null) queue.add(cur.left);
          if(cur.right!=null) queue.add(cur.right);
        }
        res++;
      }
      return res;
    }
}

递归

1
2
3
4
5
class Solution {
    public int maxDepth(TreeNode root) {
          return root==null?0:Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

55-2 平衡二叉树 https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/

我们自己在实现一颗平衡二叉树时，往往会通过判断两颗子树的高度差来实现，这里前文已经求过了二叉树的深度，我们这里也可以利用求深度.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isBalanced(TreeNode root) {
            return  getHeight(root)>=0;
    }
  private int getHeight(TreeNode root){
          if(root==null) return 0;
          int l=getHeight(root.left);
          int r=getHeight(root.right);
    //左右子树高度差不超过1为平衡二叉树
        if(l>=0&&r>=0&&Math.abs(r-l)<=1) return Math.max(l,r)+1;
    return -1;
  }
}

56-1、数组中数字出现的次数 https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

不会位运算，只好使用最笨的办法 ，贴一个计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] singleNumbers(int[] nums) {
            int temp[]=new int[10001];
          for(int i=0;i<nums.length;i++){
              temp[nums[i]]++;
          }
        int res[]=new int [2];
        int j=0;
        for(int i=0;i<temp.length;i++){
            if(temp[i]==1){
                res[j]=i;
                j++;
            }
        }
        return res;
    }
}

首先要知道，如果两个数相等，那么异或为0,根据这个性质我们可以做这一题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] singleNumbers(int[] nums) {
        //假设两个只出现过一次的数分别为x,y
           int sum=0;
        // x,y异或之和，并且两数不相等，即x^y!=0
         for(int num:nums) sum^=num;
        
        //如果x^y不为0，那么sum的二进制中至少有一位为1
        int k=0;
        while(((sum>>k)&1)==0) k++;
        //此时第k位为1，我们根据第k位为0  or  1，分为两个集合
    int first=0;
        for(int num:nums){
            //first 为第一个只出现过一次的数
            if(((num>>k)&1)==0) first^=num;
        }
        return new int[]{first,first^sum};
    }
}

56-2、数组中数字出现的次数 https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/

暂时不会位运算， 先贴一个map，以后修改

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int singleNumber(int[] nums) {
            Map<Integer,Integer> map=new HashMap<>();
            for(int num:nums){
               map.put(num,map.getOrDefault(num,0)+1);
            }
        for(int num:nums){
            if(map.get(num)==1) return num;
         }
        return -1;
    }
}

57、和为s的两个数字 https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

由于题目给定递增排序那么直接左右指针即可

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int[] twoSum(int[] nums, int target) {
         int l=0,r=nums.length-1;
      while(l<r){
           if(nums[l]+nums[r]==target) return new int[]{nums[l],nums[r]};
         else if(nums[l]+nums[r]<target)  l++;
        else r--;
      }
      return new int[]{-1,-1};
    }
}
赏

谢谢你请我喝奶茶

微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家