剑指offer-5

剑指offer day5

41、数据流中的中位数https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/

本题的大致思路是：我们维护两个堆，其中左边为最大堆，右边为最小堆，并且最大堆中元素的数量和最小堆只相差1.

这样可以保证，他们中间的那个数正好是中位数。如果两个堆中数量大小相同，则为堆顶元素的平均数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MedianFinder {
    PriorityQueue<Integer>left;
    PriorityQueue<Integer>right;
   
    public MedianFinder() {
           left=new PriorityQueue<>((a,b)->b-a);
           right=new PriorityQueue<>();
    }
    
    public void addNum(int num) {
         left.add(num);
        right.add(left.poll());
      //保证堆中数量大小只相差1，且最大堆数量大于最小堆数量
      if(left.size()<right.size()){
         left.add(right.poll());
      }
    }
    
    public double findMedian() {
          if(left.size()>right.size()) return (double)left.peek();
       return (left.peek()+right.peek())/2.0;
    }
}

42、连续子数组的最大和 https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/

题目意思很明确，让我们求出连续子数组的最大和，我们可以尝试利用暴力解法。

直接枚举两个数所在的位置 其中时间复杂度为O(n^2)

  • 暴力枚举
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution{
  public int maxSubArray(int []nums){
     int res=Integer.MIN_VALUE;
       for(int i=0;i<nums.length;i++){
           int sum=0;
         for(int j=i;j<nums.length;j++){
             sum+=nums[j];
           res=Math.max(res,sum);
         }
       }
    return res;
  }
}

但是在本题最后一个案例通不过。既然O(n^2)不行，我们可以像进一步优化

  • dp

    实际上看到“最”这个字，就可以知道这是一个很明显的dp问题。

我们定义dp[i]为前i个数的连续子数组的最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxSubArray(int[] nums) {
        int dp[]=new int[nums.length+1];
         dp[0]=nums[0];
        for(int i=1;i<nums.length;i++){
            if(dp[i-1]<=0) dp[i]=nums[i];
            else if (dp[i-1]>0) dp[i]=dp[i-1]+nums[i];
        }
        int res=Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
             res=Math.max(res,dp[i]);
        }
        return res;
    }
}

事实上，本题我们不必要开一个数组，即我们可以做到空间复杂度为O(1)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
           int dp=nums[0];
        int res=dp;
        for(int i=1;i<nums.length;i++){
            if(dp<0) dp=nums[i];
            else dp+=nums[i];
            res=Math.max(res,dp);
        }
        return res;
    }
}

43、 1～n整数中1出现的次数 https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/

  • 如果最高位为1，举个例子 1234 其中1-999中1出现的个数为f(cur-1) 然后1000到1234中 千分位中1所出现的次数为234+1 即 1+last，剩下的为234中1出现的次数，即 f(last)即 总共为 f(cur-1)+1+last+f(last)

  • 如果最高位不是1，举个例子 2345 其中1-999中1出现的次数为f(cur-1)，然后1000-1999中千分位中1出现的次数为1000，即cur，然后 后面剩下的1出现的次数为f(cur-1) 最后算2000-2345中出现的次数为f(last)，

    即f(cur-1)*high+cur+f(last)

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
class Solution{
  public int countDigitOne(int n){
    return f(n);
  }
  //f(n)的含义是1-n这n个整数十进制表示中1的个数
  private int f(int n){
    if(n<=0) return 0;
      if(n<10) return 1;
      String s=String.valueOf(n);
    //最高位
      int high=s.charAt(0)-'0';
    //数量级
    int cur=(int)Math.pow(10,s.length()-1);
    int last=n-high*cur;
    if(high==1){
      //表示最高位为1  f(cur-1) 表示计算1-999中的个数
      //而1000-1xxx这个范围的1要分为两部分，
      //最容易算得就是 除去1000后，后面的百位代表应该是f(last)
      //而千分 位为1的个数：1xxx-1000 及last+1
      return f(cur-1)+1+last+f(last);
    }else{
      return f(cur-1)*high+cur+f(last);
    }
    
  }
}

44、数字序列中某一位的数字 https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/

这题跟上面那一题一样，都是属于找规律的题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findNthDigit(int n) {
        int dig=1;
        long start=1;
        long count=9;
        while(n>count){
            n-=count;
            dig++;
            start*=10;
            count=dig*start*9;
        }
        long num=start+(n-1)/dig;
        return Long.toString(num).charAt((n-1)%dig)-'0';
    }
}

45、把数组排成最小的数

这道题有一个比较直接的做法，就是我们求出所有数的全排列，然后拼接起来，这听起来比较像之前求字符串的排列那一道题。 我们利用同样的方法可以求出数字的全排列，然后将其拼接再比较。

或者，我们可以自定义一个排序规则。 即，给定两个数m，n我们需要找到一个排序规则，确定m和n谁应该排在前面，而不是仅仅只比较数值。 最直接的方式就是我们将数字转换为字符串

1
2
3
4
5
6
7
8
9
class Solution {
    public String minNumber(int[] nums) {
            List<String>list=new ArrayList<>();
          for(int num:nums) list.add(String.valueOf(num));
      //  30 和3  303<330 在这里 30<3    
        list.sort((o1,o2)->(o1+o2).compareTo(o2+o2));
      return String.join("",list);
    }
}

46、把数字翻译成字符串 https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/

事实上是一个加强版的爬楼梯，不过有一个额外的限制条件。即当数字首位为1或者首位为2并且后一位小于6 时，相当于有多种选择。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution{
  //dp[n]表示前n个数字所能翻译的字符串
  public int translateNum(int num){
    String s=String.valueOf(num);
    int len=s.length();
    int dp[]=new int[len+1];
    dp[0]=dp[1]=1;
    for(int i=2;i<=len;i++){
      if(s.charAt(i-2)=='1'||(s.charAt(i-2)=='2'&&s.charAt(i-1)<'6') dp[i]=dp[i-1]+dp[i-2];
         else dp[i]=dp[i-1];
    }
    return dp[len];
  }
}

47、礼物的最大价值 https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/

标准的dp，就不解释了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution{
  public int maxValue(int[][]grid){
       if(grid.length==0||grid.[0].length==0) return 0;
       int m=grid.length;
       int n=grid[0].length;
      int dp[][]=new int[m][n];
      for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
          if(i==0&&j==0) dp[i][j]=grid[i][j];
          else if(i==0) dp[i][j]=dp[i][j-1]+grid[i][j];
          else if(j==0) dp[i][j]=dp[i-1][j]+grid[i][j];
          else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j];
        }
      }
    return dp[m-1][n-1];
  }
}

48、最长不含重复字符的子字符串 https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/

维护一个窗口，然后一直扫过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
  public int lengthOfLongestSubstring(String s){
      if(s==null||s.length()==0) return 0;
     int i=0,j=0,res=0;
     int freq[]=new int[128];
    while(j<s.length()){
      char c1=s.charAt(j);
      j++;
      freq[c1]++;
      while(freq[c1]>1){
         char c2=s.charAt(i);
        i++;
        freq[c2]--;
      }
      res=Math.max(res,j-i);
    }
    return res;
  }
}

49、丑数 https://leetcode-cn.com/problems/chou-shu-lcof/

既然想求按顺序从小到大的丑数，我们可以利用最小堆，这样堆顶元素就是最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int nthUglyNumber(int n) {
      //为了防止数据溢出，这里用Long
            PriorityQueue<Long>queue=new PriorityQueue<>();
         long res=1L;
      for(int i=1;i<n;i++){
         queue.add(res*2);
        queue.add(res*3);
        queue.add(res*5);
        res=queue.poll();
        while(!queue.isEmpty()&&queue.peek()==res) queue.poll();
      }
      return (int)res;
    }
}

上述方法执行效率不高，现在我们需要一种更加高效的解法，三指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution{
  public int nthUglyNumber(int n) {
        if(n<=0) return -1;
    int index[]=new int[n];
      index[0]=1;
    int i2=0,i3=0,i5=0;
    for(int i=1;i<n;i++){
      
      index[i]=Math.min(index[i2]*2,Math.min(index[i3]*3,index[i5]*5));
      //指针后移
      if(index[i2]*2==index[i]) i2++;
      if(index[i3]*3==index[i]) i3++;
      if(index[i5]*5==index[i])i5++;
      
    }
    return index[n-1];
  }
}

50、第一个只出现一次的字符 https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/

哈希表存储加扫描

1
2
3
4
5
6
7
8
9
10
class Solution {
    public char firstUniqChar(String s) {
          int freq[]=new int[128];
        for(char c:s.toCharArray()) freq[c]++;
        for(char c:s.toCharArray()){
            if(freq[c]==1) return c;
        }
        return ' ';
    }
}
赏

谢谢你请我喝奶茶

微信

扫一扫，分享到微信

微信分享二维码

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>谢谢大家