剑指offer-7

2020-07-06

剑指offer day7

57-2、和为s的连续整数序列 https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

利用滑动窗口，标准的模版

class Solution {
    public int[][] findContinuousSequence(int target) {
         List<int[]>list=new ArrayList<>();
        int i=1,j=1,sum=0;
        while(j<target){
            sum+=j;
            j++;
            while(sum>target){
                sum-=i;
                i++;
            }
            if(target==sum){
                int temp[]=new int[j-i];
                for(int k=0;k<temp.length;k++){
                     temp[k]=k+i;
                }
                list.add(temp);
            }
        }
        int [][]res=new int[list.size()][];
        for(int k=0;k<list.size();k++){
            res[k]=list.get(k);
        }
        return res;
    }
}

58-1 反转单词顺序 https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/

本题可以直接利用API

class Solution{
  public String reverseWords(String s){
      String []str=s.trim().split(" +");
    Collections.reverse(Arrays.asList(str));
    return String.join("",str);
  }
}

58-2左旋转字符串 https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/

调用API

class Solution {
    public String reverseLeftWords(String s, int n) {
             return (s+s).substring(n,s.length()+n);
    }
}

59-1 滑动窗口的最大值

维护一个单调递减的队列

class Solution{
  public int[] maxSlidingWindow(int []nums,int k){
     if(nums.length==0||k==0) return new int [0];
    int n=nums.length;
    Deque<Integer>queue=new LinkedList<>();
    int res[]=new int[n-k+1];
    for(int i=0;i<n;i++){
      //如果当前要进入的元素比队尾大，那么将队尾弹出
       while(!queue.isEmpty()&&nums[i]>nums[queue.peekLast()]){
            queue.removeLast();
       }
      queue.add(i);
      //如果窗口索引无效
      if(i-k+1>queue.getFirst()) queue.removeFirst();
      if(i-k+1>=0) res[i-k+1]=nums[queue.getFirst()];
    }
    return res;
    
  }
}

除了单调队列，我们还可以利用每次求一个窗口的最大值来实现

59-2队列的最大值 https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

与上一题类似，都是滑动窗口的问题

class MaxQueue{
  private Deque<Integer>queue;
  private Deque<Integer>maxqueue;
   public MaxQueue(){
      queue=new LinkedList<>();
      maxqueue=new LinkedList<>();
   }
    public int max_value(){
         return maxqueue.isEmpty()?-1:maxqueue.peek();
    }
    public void push_back(int value){
        queue.add(value);
      while(!maxqueue.isEmpty()&&value>maxqueue.peekLast()) maxqueue.removeLast();
      maxqueue.add(value);
    }
  public int pop_front(){
     if(queue.isEmpty()) return -1;
    int value=queue.pop();
    if(maxqueue.peek()==value) maxqueue.pop();
    return value;
  }
}

60、n个骰子的点数 https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/

首先我们求出一共会出现哪些骰子，然后求出总和。第一版通过dfs的方式实现，但是即使我们加上缓存，也会在最后一个案例超时。

class Solution {
    private int [][]cache;
    public double[] twoSum(int n) {
            List<Integer>list=new ArrayList<>();
        cache=new int[100][12];
        for(int i=n;i<=6*n;i++)  list.add(dfs(i,n));
        double sum=0;
        for(int  num:list ) sum+=num;
        double[] res=new double[list.size()];
        for(int i=0;i<list.size();i++) res[i]=list.get(i)/sum;
        return res;
    }
    private  int  dfs(int sum,int n){
            if(sum<0) return 0;
          if(n==0) return sum==0?1:0;
          if(cache[sum][n]!=0) return cache[sum][n];
        int res=0;
        for(int i=1;i<=6;i++){
            res+=dfs(sum-i,n-1);
        }
        cache[sum][n]=res;
        return res;
        
    }
}

接下来我们用dp的思路来解决这个问题，本题和背包问题特别类似，即我们关心最后一次取得的是哪一个骰子即可。

class Solution {
    public double[] twoSum(int n) {
          List<Integer>list=new ArrayList<>();
        //dp[i][j]代表i个骰子，和为j的方案
          int dp[][]=new int[n+1][6*n+1];
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=6*i;j++){
                //k代表最后取的数字是多少
                for(int k=1;k<=Math.min(j,6);k++){
                    dp[i][j]+=dp[i-1][j-k];
                }
            }
        }
        //最后一行即是方案
        for(int i=n;i<=6*n;i++) list.add(dp[n][i]);
        
        double []res=new double[list.size()];
        double sum=0;
        for(int num:list) sum+=num;
        for(int i=0;i<list.size();i++) res[i]=list.get(i)/sum;
        return res;
    }
}

61、扑克牌中的顺子 https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/

在这里把大小王当成癞子

class Solution{
  public boolean isStraight(int []nums){
         Arrays.sort(nums);
        int index=0;
    //癞子的个数
    while(nums[index]==0) index++;
    int count=0;
    for(int i=index;i<nums.length;i++){
      //如果出现两张一样的牌，直接返回
      if(nums[i]==nums[i-1])return false;
      //需要癞子的个数
      count+=nums[i]-nums[i-1]-1;
    }
    return count<=index;
  }
}

62、圆圈中最后剩下的数字 https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/

常规解法，将所有人都放进一个数组中

class Solution {
    public int lastRemaining(int n, int m) {
          List<Integer>list=new ArrayList<>();
        for(int i=0;i<n;i++){
             list.add(i);
        }
        int index=0;
        while(n>1){
          //待删除的位置，由于从0开始，这里是m-1
            index=(index+m-1)%n;
            list.remove(index);
            n--;
        }
        return list.get(0);
    }
}

数学解法，约瑟夫环问题

其中数学表达式为f(N,M)=(f(N-1,M)+M)%N

f(N,M)表示，N个人报数，每报到M时杀掉那个人，最终胜利者的编号
f(N−1,M)f(N-1,M)f(N−1,M)表示，N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号

class Solution {
    public int lastRemaining(int n, int m) {
         //直接从第二个人开始反推
      int res=0;
      for(int i=2;i<=n;i++){
            res=(res+m)%i;
      } 
      return res;
    }
}

63、股票的最大利润 https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/

经典dp问题

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==0) return 0;
      //持有股票时获得的最大利润
            int hold=-prices[0];
      //不持有股票时获得的最大利润
             int sell=0;
        for(int i=1;i<prices.length;i++){
             sell=Math.max(sell,hold+prices[i]);
             hold=Math.max(hold,-prices[i]);    
        }
        return sell;
    }
}

64、求1+2+…+n https://leetcode-cn.com/problems/qiu-12n-lcof/

要求不能用乘除法，for,while,if,else ,switch,case 等关键词及条件判断语句

递归

class Solution {
    public int sumNums(int n) {
    
          int sum=n;
      //利用短路特性
        boolean flag=n>0&&(sum+=sumNums(n-1))>0;
        return sum;
    }
}