建网站公司郑州,百度网站怎样做,网站开发简直,做手机网站的好处【LeetCode】3356、零数组变换 II 文章目录 一、数据结构-差分-一维差分、二分1.1 数据结构-差分-一维差分、二分1.1.1 题意复述1.1.2 思路1.1.3 手写二分1.1.4 sort.Search() 二分1.1.5 sort.Find() 二分 二、多语言解法 一、数据结构-差分-一维差分、二分
1.1 数据结构-差分…【LeetCode】3356、零数组变换 II 文章目录 一、数据结构-差分-一维差分、二分1.1 数据结构-差分-一维差分、二分1.1.1 题意复述1.1.2 思路1.1.3 手写二分1.1.4 sort.Search() 二分1.1.5 sort.Find() 二分 二、多语言解法 一、数据结构-差分-一维差分、二分
1.1 数据结构-差分-一维差分、二分
1.1.1 题意复述
题意复述: 有 nums[] 数组(如 [2, 0, 2]), 有 queries[] 数组(如 [[0,2,1], [0,2,1], [1,1,3]])
遍历 queries, 对每个 queries[i] 为 [li, ri, vali] 可以把 介于 nums[li…ri] 的元素的子集, 减去 [0…vali] 的数
问最终需操作几个 queries[], 可使 nums[] 全部变为 0. 记答案为 k(即操作的是 queries[0…k])
1.1.2 思路
因为操作的是 nums[li…ri] 的【子集】, 且减小的数 【最多】为 vali, 所以 k【越多越好】. 即 k 越多, 越满足答案. 【具备单调性】, 所以可用 【二分法】.
二分法: 是指, 从 queries[] 数组的长度的二分, 即 queries[0…len(queries)] 中 k 从 i 0, j len(queries) 的 二分. 二分的 check() 函数, 即为 【LeetCode 3355】 的过程. 最终返回二分的 k 即可.
二分法的注意: 用 开区间 确实更容易写边界条件
没有 1 或 -1 的判断最后返回的值 肯定是 l 或 r, 只需根据 二分的分支 确定 l 的含义, r 的含义, 即可
1.1.3 手写二分
// go
func minZeroArray(nums []int, queries [][]int) int {n : len(nums)check : func(k int) bool {d : make([]int, n1) // 差分数组for _, q : range queries[:k] { // k锁定了queries[]的前k项start, end, val : q[0], q[1], q[2]d[start]vald[end1]-val}now : 0for i : range n {now d[i]if now nums[i] {return false}}return true}q : len(queries)l, r : -1, q1 // 左开右开区间for l 1 r {m : l (r-l)1if check(m) {r m // m 已经符合, 但为了找更小的, 再向左找} else {l m // 不符合, 则需找更大的(向右找), 因为k越大越符合题意}}if r q {return r // 因为二分中 check(m) 符合时, r 为 m. 所以最终返回的 r 就是符合题意的}return -1 // r q1
}1.1.4 sort.Search() 二分
func minZeroArray(nums []int, queries [][]int) int {n : len(nums)check : func(k int) bool {d : make([]int, n1) // 差分数组for _, q : range queries[:k] { // k锁定了queries[]的前k项start, end, val : q[0], q[1], q[2]d[start]vald[end1]-val}now : 0for i : range n {now d[i]if now nums[i] {return false}}return true}q : len(queries)ans : sort.Search(q1, func(k int) bool { // sort.Search() 是找第一个 true 的下标return check(k)})if ans q {return ans}return -1 // r q1
}1.1.5 sort.Find() 二分
func minZeroArray(nums []int, queries [][]int) int {n : len(nums)check : func(k int) bool {d : make([]int, n1) // 差分数组for _, q : range queries[:k] { // k锁定了queries[]的前k项start, end, val : q[0], q[1], q[2]d[start]vald[end1]-val}now : 0for i : range n {now d[i]if now nums[i] {return false}}return true}q : len(queries)// 因为 sort.Search() 是找第一个 f() true 的下标, 而 sort.Find() 是找第一个 f() 0 的下标, 所以此处定义 sort.Find() 的 f 为 if check(k) {return 0}ans, found : sort.Find(q1, func(k int) int { // sort.Find() 是找第一个 f() 0 的下标if check(k) {return 0 // 0}return 1})if found {return ans}return -1 // r q1
}二、多语言解法 C p p / G o / P y t h o n / R u s t / J s / T s Cpp/Go/Python/Rust/Js/Ts Cpp/Go/Python/Rust/Js/Ts
// cpp// go 同上# python// rust// js// ts
