戳印序列

戳印序列
每次找到可以将stamp匹配的子串，刷掉，将对应的字符改成?表示已经刷完，

class Solution {
    public int[] movesToStamp(String stamp, String target) {
        List<Integer> res=new ArrayList<Integer>();
        while(true){
            boolean flag=true;
            //找下一个可以刷的位置
            for(int i=0;i+stamp.length()<=target.length();i++){
                if(check(stamp,target,i)){
                    flag=false;
                    res.add(i);
                    char[] chs=target.toCharArray();
                    for(int j=0;j<stamp.length();j++){
                        chs[j+i]='?';
                    }

                    target=new String(chs);
                }
            }
            if(flag){
                break;
            }
        }
        for(int i=0;i<target.length();i++){
            if(target.charAt(i)!='?'){
                return new int[]{};
            }
        }
          Collections.reverse(res);
        int[] re=new int[res.size()];
        for(int i=0;i<res.size();i++){
            re[i]=res.get(i);
        }
        return re;
    }

    public boolean check(String stamp,String target,int start){
        //如果已经全部是？当前位置不需要刷
        boolean flag=true;
        for(int i=0;i<stamp.length();i++){
            if(target.charAt(start+i)!='?'){
                flag=false;
                break;
            }
        }
        if(flag){
            return false;
        }

        for(int i=0;i<stamp.length();i++){
            if(target.charAt(start+i)!='?'&&target.charAt(start+i)!=stamp.charAt(i)){
                return false;
            }
        }

        return true;
    }
}

多次求和构造目标数组

多次求和构造目标数组
int溢出导致的除0异常
每次都将最大的数减到小于次小值；获取最大的数，通过最大堆
创建最大堆：

 PriorityQueue<Integer> queue
 =new PriorityQueue<Integer>(Collections.reverseOrder());

class Solution {
        public boolean isPossible(int[] target){
        if(target.length==1){
            return target[0]==1;
        }
        //创建大根堆
        PriorityQueue<Long> queue=new PriorityQueue<>(Collections.reverseOrder());
        long sum=0;
        for(int i=0;i<target.length;i++){
            sum+=target[i];
            queue.offer((long)target[i]);
        }
        while (!queue.isEmpty()) {
            Long node=queue.poll();
            if(node==1){
                return true;
            }
            //轮数
            if(queue.peek()==1){
                return (node-1)%(sum-node)==0;
            }else{
                long n=(node-queue.peek())/(sum-node)+1;
                long t=node-n*(sum-node);
                if (t <= 0) {
                    return false;
                }
                sum=node-(n-1)*(sum-node);
                queue.offer(t);
            }
        }
        return true;
    }
}

向下取整数对和 计数+前缀和

向下取整数对和
逆向枚举d结果，

class Solution {
     public int sumOfFlooredPairs(int[] nums){
        int MOD=1000000007;
        //求最大值
        int maxv=Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            maxv=Math.max(maxv,nums[i]);
        }
        //对每个元素出现次数计数
        int[] cnt=new int[maxv+1];
        for(int i=0;i<nums.length;i++){
            cnt[nums[i]]++;
        }

        int[] prefix=new int[maxv+1];
        for(int i=1;i<=maxv;i++){
            prefix[i]=prefix[i-1]+cnt[i];//prefix[i]表示小于等于i的元素出现次数
        }

        long res=0;
        for(int i=1;i<=maxv;i++){
            if(cnt[i]!=0){
                //当前i出现过
                //对于每一个d
                for(int d=1;d*i<=maxv;d++){
                    res+=1L*d*cnt[i]*(prefix[Math.min(maxv,(d+1)*i-1)]-prefix[d*i-1]);
                }
            }
        }
        return (int)(res%MOD);
    }
}