跳转至

力扣第235场周赛

题一 截断句子

描述

句子 是一个单词列表，列表中的单词之间用单个空格隔开，且不存在前导或尾随空格。每个单词仅由大小写英文字母组成（不含标点符号）。

  • 例如，"Hello World"、"HELLO" 和 "hello world hello world" 都是句子。

给你一个句子 s 和一个整数 k ，请你将 s 截断 ，使截断后的句子仅含 前 k 个单词。返回 截断 s后得到的句子。

 

思路

  • 按空格切分句子获得单词
  • 按题目要求拼成截断后的句子

代码

public class N1 {
    public String truncateSentence(String s, int k) {
        String[] strs=s.split(" ");
        StringBuilder sb=new StringBuilder();
        for (int i=0;i<k;i++)sb.append(strs[i]).append(" ");
        sb.deleteCharAt(sb.length()-1);
        return sb.toString();
    }
}

题二 查找用户活跃分钟数

描述

给你用户在 LeetCode 的操作日志，和一个整数 k 。日志用一个二维整数数组 logs 表示，其中每个 logs[i] = [IDi, timei] 表示 ID 为 IDi 的用户在 timei 分钟时执行了某个操作。

多个用户 可以同时执行操作，单个用户可以在同一分钟内执行 多个操作 。

指定用户的 用户活跃分钟数（user active minutes，UAM） 定义为用户对 LeetCode 执行操作的 唯一分钟数 。 即使一分钟内执行多个操作，也只能按一分钟计数。

请你统计用户活跃分钟数的分布情况，统计结果是一个长度为 k 且 下标从 1 开始计数 的数组 answer ，对于每个 j（1 <= j <= k），answer[j] 表示 用户活跃分钟数 等于 j 的用户数。

返回上面描述的答案数组 answer 。

思路

把日志记录存在

Map<Integer,Set<Integer>> map=new HashMap<>();

Key 是用户ID，Value存的是活跃时间的集合。

接着遍历map即可得到答案。

代码

public class N2 {
    public int[] findingUsersActiveMinutes(int[][] logs, int k) {
        Map<Integer,Set<Integer>> map=new HashMap<>();
        for (int[] log:logs){
            if(! map.containsKey(log[0]))map.put(log[0],new HashSet<>());
            map.get(log[0]).add(log[1]);
        }
        int[] res=new int[k];
        for (Map.Entry<Integer,Set<Integer>> e:map.entrySet()){
            res[e.getValue().size()-1]++;
        }
        return res;
    }
}

题三 绝对差值和

描述

给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。

数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|（0 <= i < n）的 总和（下标从 0 开始）。

你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。

在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 109 + 7 取余 后返回。

|x| 定义为：

  • 如果 x >= 0 ，值为 x ，或者
  • 如果 x <= 0 ，值为 -x

思路

  • 先求出绝对差值和。
  • 对每一个位置idx的nums1[idx]尝试替换成最接近nums2[idx]的值
  • 通过二分查找num1中最接近nums2[idx]的值
  • 遍历所有idx

代码

public class N3 {

    private final static int MOD=(int) (1e9+7);

    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        long sum=0L;
        long min=0L;
        for (int i=0;i<nums1.length;i++)
        {
            sum+=Math.abs(nums1[i]-nums2[i]);
        }
        int[] arr=new int[nums1.length];
        System.arraycopy(nums1, 0, arr, 0, arr.length);
        min=sum;

        Arrays.sort(arr);

        for (int i=0;i<nums1.length;i++)
        {
            int idx=find(nums2[i],arr);
            for (int j=Math.max(0,idx-2);j<=Math.min(idx+2,arr.length-1);j++)
            {
                long tmp=sum-Math.abs(nums1[i]-nums2[i])+Math.abs(arr[j]-nums2[i]);
                min=Math.min(min,tmp);
            }
        }
        return (int) (min%MOD);

    }

    private int find(int tar, int[] arr) {
        if(tar<=arr[0])return 0;
        if(tar>=arr[arr.length-1])return arr.length-1;
        int left=0,right=arr.length-1;
        int res=right;
        while (left<=right){
            int mid=(left+right)/2;
            if(arr[mid]==tar)return mid;
            if(arr[mid]>tar){
                res=mid;
                right=mid-1;
            }
            else left=mid+1;
        }
        return res;
    }
}

题四 序列中不同最大公约数的数目

描述

给你一个由正整数组成的数组 nums 。

数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。

  • 例如，序列 [4,6,16] 的最大公约数是 2 。

数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。

  • 例如，[2,5,10] 是 [1,2,1,**2**,4,1,**5**,**10**] 的一个子序列。

计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。

思路

  • 预计算算出这个范围内数的所有因数

  • 如果一个序列中能被K整除有m个，被tk(t>1,且t为整数)整除的数也有m个，那么如果k是一个序列的公约数，tk也是这个序列的公约数。

所以能被K整除个数不等于能被tk整除个数，那么k是一个最大公约数。

代码

public class N4 {
    private final static int MAX=2*100000+1;
    private final static List<Integer>[] factors=new List[MAX];
    private final static int[] book=new int[MAX];
    static{
        //预计算
        for (int i=1;i<MAX;i++)factors[i]=new ArrayList<>();
        for (int i=1;i<MAX;i++){
            for (int j=i;j<MAX;j+=i){
                factors[j].add(i);
            }
        }
    }

    public int countDifferentSubsequenceGCDs(int[] nums) {
        int max=0;
        for (int i:nums)max=Math.max(max,i);
        Arrays.fill(book,0);
        for (int num:nums){
            for (int factor:factors[num]){
                book[factor]++;
            }
        }

        int res=0;
        for (int i=max;i>=1;i--){
            if(book[i]==0)continue;
            boolean flag=true;
            for (int j=i*2;j<=max;j+=i){
                if(book[i]==book[j]){
                    flag=false;
                    break;
                }
            }
            if(flag)res++;
        }
        return res;

    }

}