每日一题（1）

2024-05-15

2589. 完成所有任务的最少时间

思路与题解：

将所有区间按右端点大小排序，排序之后对于 $task[i]$ 来说，它要么和所有的区间没有交集，要么和别的区间存在一定交集。

定义 $run$ 数组标记区间是否已在运行，对于 $task[i]$ 来说，如果在区间 $[start, end]$ 已在运行的节点个数大于 $duration$，则直接可以全部运行。反之则需要从右往左新增运行节点，直至全部运行（节点按照根据右端点大小排序过，优先更新右端点可以让下一个区间统计到更多已运行节点）。

func findMinimumTime(tasks [][]int) int {  
    slices.SortFunc(tasks, func(a, b []int) int {  
        return a[1] - b[1]  
    })  
    run := make([]bool, tasks[len(tasks)-1][1]+1)  
  
    res := 0  
    for _, task := range tasks {  
        start, end, d := task[0], task[1], task[2]  
        for _, b := range run[start : end+1] {  
            if b {  
                d--  
            }  
        }  
  
        for i := end; d > 0; i-- {  
            if !run[i] {  
                run[i] = true  
                d--  
                res++  
            }  
        }  
    }  
  
    return res  
}

2024-05-17

题目：826. 安排工作以达到最大收益

思路与题解：

$worker$ 按照小到大排序，第 $i$ 个工人能做的工作，他右边的工人也能做。对于第 $i$ 个工人能做的工作 $j$（ $difficulty[j]<= worker[i]$ ）。第 $i+1$ 个工人必然可做，因为 $worker[i+1]>= worker[i]$，所以 $difficulty[j]<= worker[i+1]$.

将工作难度和工作收益绑定到一起，然后根据难度从小到大排序。在遍历 $worker$ 的同时找出最大的 $porfit[j]$，因为上面说到的原因，无需再遍历 $difficulty$，最后累加每个工人最大的 $porfit$ 就是结果

func maxProfitAssignment(difficulty []int, profit []int, worker []int) int {  
    n := len(difficulty)  
    jobs := make([][]int, n)  
    for i, d := range difficulty {  
        jobs[i] = []int{d, profit[i]}  
    }  
    sort.Slice(jobs, func(i, j int) bool {  
        return jobs[i][0] < jobs[j][0]  
    })  
    sort.Ints(worker)  
  
    i, maxP, res := 0, 0, 0  
    for _, w := range worker {  
        for i < n && jobs[i][0] <= w { // 找到难度小于等于当前工人能力的工作  
            maxP = max(maxP, jobs[i][1])  
            i++ //  
        }  
        res += maxP  
    }  
  
    return res  
}

2024-05-18

题目：2644. 找出可整除性得分最大的整数

思路与题解：

直接暴力枚举，找到能被整除的数，求最大的

func maxDivScore(nums []int, divisors []int) int {  
    res := 0  
    maxCnt := -1  
    for _, d := range divisors {  
        cnt := 0  
        for _, n := range nums {  
            if n%d == 0 {  
                cnt++  
            }  
        }  
        if cnt > maxCnt || cnt == maxCnt && d < res {  
            maxCnt = cnt  
            res = d  
        }  
    }  
    return res  
}

因为小于 $divisors[i]$ 的正整数无法被 $divisors[i]$ 整除，对 $nums$ 排序，只需要遍历 $>=divisors[i]$，反之直接退出内层循环

func maxDivScore(nums []int, divisors []int) int {  
    res := 0  
    maxCnt := -1  
    sort.Slice(nums, func(i, j int) bool {  
        return nums[i] > nums[j]  
    })  
    for _, d := range divisors {  
        cnt := 0  
        for _, n := range nums {  
            if n < d {  
                break  
            }  
            if n%d == 0 {  
                cnt++  
            }  
        }  
        if cnt > maxCnt || cnt == maxCnt && d < res {  
            maxCnt = cnt  
            res = d  
        }  
    }  
    return res  
}

还有个更顶的思路：暴力枚举+排序优化

2024-05-19

题目：1535. 找出数组游戏的赢家

思路与题解：

根据题意定义 $maxNum$ 记录最大值，$winNum$ 记录连胜次数，根据游戏流程循环数组，当 $win=k$ 就退出循环，返回当前 $maxNum$。

如果循环接收都没有合适的 $maxNum$，就表示最后一个数字式最大的，此时右边的所有数字都小于它，后面再进行比较都会是它大。

func getWinner(arr []int, k int) int {  
    mn := arr[0]  
    win := 0  
    for i := 1; i < len(arr) && win != k; i++ {  
        if arr[i] > mn {  
            mn = arr[i]  
            win = 1  
        } else {  
            win++  
        }  
    }  
    return mn  
}

2024-05-20

题目： 1542. 找出最长的超赞子字符串

思路与题解：

前置知识：前缀异或和。见 [[前缀和#[1177. 构建回文串检测](https //leetcode.cn/problems/can-make-palindrome-from-substring/)]]，详见： 一步步优化！从前缀和到前缀异或和，

首先用一个长度为 10 的二进制 $mark$ 记录子串中每个数字的出现次数的奇偶性，比如 $mark=1000010010$ （从右往左）表示子串中数字 9，4，1 出现了奇数次，其余数字出现了偶数次。

定义 $s$ 的异或前缀和 $pre[i]$，等于 $s[0]$ 到 $s[i]$ 这个子串（前缀）中的每个数字出现次数的奇偶性。

按照定义，从 $s[i+1]$ 到 $s[j]$ 的这个长为 $j-i$ 的子串，其中每个数字出现的奇偶性等于，$pre[j]\oplus pre[i]$。

额外定义 $pre[-1]=0$，以兼顾 $i+1=0$ 的情况。

分类讨论：

• 如果从 $s[i]$ 到 $s[j]$ 的子串长度是偶数，要使子串可以重新排列为回文串，每个数字出现的次数都得是偶数，所以 $pre[j] \oplus pre[i] = 0$，即 $pre[i] = pre[j]$
• 如果从 $s[i]$ 到 $s[j]$ 的子串长度是奇数，要使子串可以重新排列为回文串，有且只有一个数字出现次数为奇数，其余数字为偶数，所以 $pre[j] \oplus pre[i] = 2^k$，即 $pre[i]=pre[j] \oplus 2^k (0≤k≤9)$。$2^k$ 对应出现一次的数字。

遍历 $pre[j]$，因为子串长度等于 $j-i$，当 $j$ 固定时，$i$ 越小，子串长度越大，多个相同异或前缀和，我们只关心最小那个（$i$ 最小）。用数组 $pos$ 记录每个前缀异或和首次出现位置。例如 $pos[1001]=2$，表示一个等于 $1001$ 的前缀和首次出现下标是 $2$。特别地，$pos[0]=-1$，因为 $pre[-1]=0$。

对于上面讨论的两种情况：

• 偶数：$pre[i]$ 首次出现的下标 $i=pos[pre[j]]$。子串长度为： $j-i$
• 奇数：枚举 $k$，$pre[i]$ 首次出现下标 $i=pos[pre[j] \oplus 2^k]$。子串长度为 $j-i$

遍历 $s$ 时，可以一边计算 $pre$，$pre[i]$ 可以通过计算所得，而 $pre[j]$ 就是当前 $pre$，所以 $pre$ 不需要数组，一个变量即可

func longestAwesome(s string) int {  
    const D = 10  
    n := len(s)  
    pos := [1 << D]int{}  
    for i := range pos {  
        pos[i] = n // 没有前缀和默认用最大值  
    }  
  
    pos[0] = -1  
    pre := 0 // 因为是遍历的同时计算,所以pre即pre[j]  
    res := 0  
    for i, c := range s {  
        pre ^= 1 << (c - '0')  
        for d := 0; d < D; d++ {  
            res = max(res, i-pos[pre^(1<<d)]) // 奇数pre[i]=pre[j]^(1<<d)  
        }  
        res = max(res, i-pos[pre]) // 偶数 pre[i]=pre[j]        if pos[pre] == n {         // 标记前缀和首次出现位置  
            pos[pre] = i  
        }  
    }  
    return res  
}