剑指Offer41~50

数组中出现次数超过一半的数字

题链
题解:这道题就是求解数组中的众数.思路就是遍历整个数组,当数组中两个元素不同时将这两个元素都"删除"掉,遍历完元素后,剩下的那些元素(>0)就都是众数.这里通过记录一个time值来模拟删除.

  	public int majorityElement(int[] nums) {
        int n = nums.length;
        if(n == 1){
            return nums[0];
        }
        int time = 1;
        int num = nums[0];
        for(int i = 1; i < n; i++){
            if(time == 0){
                num = nums[i];
                time = 1;
            }else if(num != nums[i]){
                time--;
            }else if(num == nums[i]){
                time++;
            }
        }
        return num;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

最小的K个数

题链
题解:经典TopK问题.建立一个大小为k的优先级队列(最大堆).将数组中前k个元素放入到堆中,之后当堆顶元素大于数组元素就将堆顶元素弹出,将数组元素放入到堆中,直到遍历完数组.堆中的K个数就是最小的K个数

	 public int[] getLeastNumbers(int[] arr, int k) {
         int[] ans = new int[k];
        int n = arr.length;
        if(n == 0 || k == 0){
            return ans;
        }
        PriorityQueue<Integer> p = new PriorityQueue<>(k, (o1, o2) -> o2 - o1);
        for(int num : arr){
            if(p.size() < k){
                p.offer(num);
            }else{
                if(p.peek() > num){
                    p.poll();
                    p.add(num);
                }
            }
        }
        for(int i = 0; i < k; i++){
            ans[i] = p.poll();
        }
        return ans; 
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

数据流中的中位数

题链
题解:这道题的潜规则就是时间复杂度达到O(1).因此我们可以维护两个堆,一个最小堆,一个最大堆,最小堆中存放数组中较大的一半元素,最大堆中存放数组中较小的一半元素.当数组中元素为奇数时,我们规定最大堆中元素个数比最小堆中元素多一个(也可以反过来).这样当两个堆中元素个数相同时,说明数组元素为偶数,就取出两个堆的堆顶元素(位于中间的两个元素)取平均数,否则就取出大堆中的堆顶元素.

	PriorityQueue<Integer> maxQ;
    PriorityQueue<Integer> minQ;
    public MedianFinder(){
         maxQ = new PriorityQueue<>((o1,o2)->(o2-o1));
        minQ= new PriorityQueue<>();
    }
    public void addNum(int num){
        if(maxQ.size() != minQ.size()){
            maxQ.add(num);
            minQ.add(maxQ.poll());
        }else{
            minQ.add(num);
            maxQ.add(minQ.poll());
        }
    }
    public double findMedian(){
        if(maxQ.size() == minQ.size()){
            return (maxQ.peek()+minQ.peek())/2.0;
        }else{
            return maxQ.peek();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

连续子数组的最大和

题链
题解:经典DP,f[i]表示以i为下标的元素为结尾的最大连续子数组.
f[i] = f[i-1] < 0 ? nums[i] : f[i-1]+nums[i]

	int len = nums.length;
    int[] f = new int[len];
     f[0] = nums[0];
     int max = nums[0];
     for(int i = 1; i < len; i++){
         f[i] = f[i-1] < 0 ? nums[i] : nums[i]+f[i-1];
         max = Math.max(max,f[i]);
     }
     return max;
1
2
3
4
5
6
7
8
9

1～n 整数中 1 出现的次数

题链
题解:对于整数n,我们可以取求每一位上有多少个1出现.例如n=2468348,我们求千位上有多少个1,我们知道1-1999中一共有[999-000+1]个1,也就是1000个1.而2468348中一共有246*1000个1,也就是0~2460000中千位上1的个数.对于多出来的8348,当这个数大于等于1999时,有1000个1,当小于1000时有0个1,在这之间则有x-1000+1个1.所以在千位上1的个数一共有[n/10000]*1000+min(max(x-1000+1,0),1000)个1.对于第i位一共有[n/(10^(i+1)] *(10^i )+min(max(0,(n%10^(i+1))-(10^i)+1),10 ^i).然后统计每一位上1的个数求和.

public int countDigitOne(int n) {
     long mulk = 1;
     int ans = 0;
     for (int k = 0; n >= mulk; ++k) {
         ans += (n / (mulk * 10)) * mulk + Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
         mulk *= 10;
     }
     return ans;
   }
1
2
3
4
5
6
7
8
9

数字序列中某一位的数字

题链
题解:首先有n的最大值可知n中最大的一个数有10位,所以要想知道某一位具体的数字,首先要将其绑定到某一个具体的位组成的序列中,然后找到序列中具体的数字,然后找到数字中具体的某一位上的数,一共分成3个步骤.
首先第一步我们要打表:定义一个long数组sum,sum[i]表示数字位数为i及其之前的所有数字的个数:sum[i] = sum[i-1]+9i10^(i-1).
比较n个sum[i]的值,找到将n卡在sum[k-1]和sum[k]中间的k值:sum[k-1] 最后我们得到了原序列中第n位上的数即为数num的第p位上.然后通过num/(10^(k-p))%10得到最终结果

	 static long[] sum = new long[11];
    static{
        for(int i = 1; i <= 10; i++){
            sum[i] = sum[i-1] + 9L *i*(int)Math.pow(10,i-1);
        }
    }
    public int findNthDigit(int n) {
        if(n == 0){
            return 0;
        }
        int index = 0;
        for(int i = 0; i < 10; i++){
            if(sum[i] < n && sum[i+1] >= n){
                index = i+1;
                break;
            }
        }
        n -= sum[index-1];
        int p = (n+index-1)/index;
        int pp = (n+index-1)%index;
        int num = (int)Math.pow(10,index-1)+p-1;
        return num /(int)Math.pow(10,index-pp-1) % 10;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

把数组排成最小的数

题链
题解:首先我们需要将原来的整数数组转换成字符串数组.这道题其实是在考字符串排序,只需要比较两个字符串数a,b是a+b大还是b+a大.

	public String minNumber(int[] nums) {
        int n = nums.length;
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(s, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1+o2).compareTo(o2+o1);
        }
        });
        String ans = "";
        for(String str : s){
            ans += str;
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

把数字翻译成字符串

题链
题解:这道题可以用动态规划来做,我们规定f[i]表示以第i位结尾的可以组成的最大数字.根据规则,f[i]可以由f[i-1](不和前一个字符匹配)和f[i-2](和前一个字符匹配)得来.因此关键点在于什么情况下不能和前一位匹配,什么时候必须和前一位匹配,什么时候两者都可以.
根据规则.首先初始化f[0]=1,f[1] = num[0]==0 || num[0]*10+num[1]>=26 ? 1 : 2,之后根据规则我们得知num[i]一定可以不可前一位匹配,也就是f[i]=f[i-1],当num[i-1]!=0&&num[i-1]*10+num[i]在[0,25]内,f[i]+=f[i-2].

 	 public int translateNum(int num) {
        int n = getK(num);
        if(n == 1 || num == 0){
            return 1;
        }
        //将num的每一位存储到nums数组中
        int[] nums = new int[n];
        for(int i = 0; i < n; i++){
           nums[i] = num/(int)(Math.pow(10,n-1-i)) % 10;
        }
        int[] f = new int[n];
        f[0] = 1;
        if(nums[0] == 0 || nums[0]*10+nums[1] >= 26){
            f[1] = 1;
        }else{
            f[1] = 2;
        }
        for(int i = 2; i < n; i++){
            f[i] += f[i-1];
            int key = nums[i-1]*10+nums[i];
            if(nums[i-1] != 0  && key > 0 && key < 26){
                f[i]+=f[i-2];
            }
        }
        return f[n-1];
    }
    public int getK(int n){
        int ans = 0;
        int cur = n;
        while(cur != 0){
            ans++;
            cur /= 10;
        }
        return ans;
    }
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
35

礼物的最大价值

题链
题解:典型的dp题,和机器人走路径那道题类似.定义f[i][j]为到达坐标为(i,j)时的最大路径,f[i][j] = max(f[i-1][j],f[i][j-1])

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

最长不含重复字符的子字符串

题链
题解:双指针问题.最差的做法就是定义两个指针l,r.l从0~n-1,然后每次r=l+1往前试探遍历直到遇到重复的字符串,是否重复可以通过将遍历过的字符放入HashSet中.这样的时间复杂度是O(n2),但事实上,我们定义的r指针无须每次都等于l+1.因为通过HashSet我们已经知道在上一次遍历过程中,l~r区间内没有重复的字符,那么下次遍历从l+1开始遍历时,l+1~r区间一定是没有重复字符的,所以我们可以做一步优化:r的指针无须变化.

  public int lengthOfLongestSubstring(String s) {
         Set<Character> set = new HashSet<>();
       int r = -1,ans = 0;
       int n = s.length();
       for(int i = 0; i < n; i++){
           if(i != 0){
           		//每次遍历之前把前一个字符从HashSet中去除掉.
               set.remove(s.charAt(i-1));
           }
           while(r+1<n && !set.contains(s.charAt(r+1))){
               set.add(s.charAt(r+1));
               r++;
           }
           ans = Math.max(ans,r-i+1);
       }
       return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17