【水】做题家每天做题碎碎念

搬砖
266

https://leetcode.com/problems/combination-sum-ii

我知道是回溯，捣鼓半天写出来了但还是不懂，屌大的坛友能不能讲讲为什么“如果不选择元素i，那所有和a[i]相等的元素全部不能选”和“没有重复的组合”是等价的？

我的代码：

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end(), std::greater<int>());
        vector<vector<int>> soln;
        std::function<void(int, int, vector<int>&, int)> search = [&](int idx, int remaining, vector<int>& curr_nums, int ignore) -> void {
            if (remaining == 0) {
                vector<int> s (curr_nums);
                soln.push_back(s);
                return;
            }
            if (idx >= candidates.size()) return;
            if (candidates[idx] <= remaining && candidates[idx] != ignore) {
                curr_nums.push_back(candidates[idx]);
                search(idx + 1, remaining - candidates[idx], curr_nums, ignore);
                curr_nums.pop_back();
            }
            search(idx + 1, remaining, curr_nums, candidates[idx]);
        };
        vector<int> temp;
        search(0, target, temp, -1);
        return soln;
    }

广告：
\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

267

这个题里这不是说了里面都只出现一次吗

求的是和那不就等价吗

又一个一看组合题就不读题的是吧 :yaoming:

268

因为这题的定义里是不区分相同元素。对于相同元素，如果你已经选了一个，只可能是继续叠加才能不同；而如果你skip了一个，继续选择则有可能会出现相同的组合。

对于这种题目我一般会先预处理出所有元素的频次，然后搜索的时候做整体处理，对于每一个元素递归进选0、1、2…个的情况，也就不会有重复的了。有点类似于多重背包的处理手法。

2 个赞
269

wocao，太透彻了，%%%

270

只做过i 等会看看

271

https://leetcode.com/problems/find-k-th-smallest-pair-distance/

写了好久二分，最后看题解发现

  1. 需要滑动窗口（我本来以为是再用lower_bound二分）
  2. 桶排序也是可以过的
    说实话，现在写二分也写不动了，ctmd，我废了

广告：
\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

272

这题里的abs其实是没用的，直接排序之后只计数 (i, j) where i < j 的所有pair就跟原来的abs等价了。接下来就二分答案，对于每个 i 看看有多少个使得 a[j] - a[i] < ans ，算一下比 k 多还是少。两重二分 O(n log^2 n) 。

确实可以优化掉第二个二分。不过如果是打比赛我肯定想不起 :yaoming:

1 个赞
273

膜%%%%%%%

1 个赞
274

今天题非常简单，模拟+贪心
https://leetcode.com/problems/lemonade-change

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

275

https://leetcode.com/problems/minimum-moves-to-get-a-peaceful-board/

还有这种贪心题，就是你觉得可能确实是贪心，写出来也能过样例，但是你就是想不通为什么是对的

276

大家快来看呀，这里有个变钛啦

2 个赞
277

https://leetcode.com/problems/maximum-distance-in-arrays/

有一种贪心的即视感，最后写出来确实也是维护最大的最大值和最小的最小值，然后用2sum那种回头看来保证没有重复
一开始还以为是两个大小为2的堆，我真是弱智

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

278

https://leetcode.com/problems/tuple-with-same-product/

观察法可以得出每两组积相同的数对可以有8个元组（222），那n个积相同的数对就有 \binom{n}{2}\times8 个
最后用Python写的，因为STL没有comb函数

\color{purple}\Biggl(\color{blue}\biggl(\color{green}\Bigl(\color{yellow}\bigl(\color{orange}\,(\color{black}{\Huge{\color{red}征友，\color{blue}希望可以婚绿\color{orange}130}} \,\color{orange})\,\color{yellow}\bigr)\color{green}\Bigr)\color{blue}\biggr)\color{purple}\Biggr)

1 个赞
279

comb是什么函数 :troll:

280

算组合数咯 :troll:

281

就是 a!/b!(a-b)! 吗？ :troll:

282

对的

283

确实，但是自己写就要考虑溢出、打表、复杂度，不如换个语言用现成的

1 个赞
284

https://leetcode.com/problems/maximum-number-of-points-with-cost

朴素O(mn^2)解法会TLE，DP很简单但是仔细一看就会发现DP完全没有复用任何状态，本质就是暴力
看了题解才知道是DP套DP可以O(mn)，真tm弱智

1 个赞
285

也可以dp套单调栈
比如对于第一行，想象每个位置都是一个高度是对应的值，然后左右斜率-1/1的帐篷形状，易发现只需要维护帐篷的天际线就可以满足下一行的转移。
这个天际线很容易用单调栈计算。
然后之后每一行帐篷高度就是那个位置的dp值，这样还不用像题解一样2 pass，1 pass就可以了。

My Solution 
impl Solution {
    pub fn max_points(points: Vec<Vec<i32>>) -> i64 {
        let m = points.len();
        let n = points[0].len();

        let mut last_row: Vec<(i64, i64)> = Vec::with_capacity(n);
        let mut this_row: Vec<(i64, i64)> = Vec::with_capacity(n);

        let mut points_it = points.into_iter();
        for (i, v) in points_it.next().unwrap().into_iter().enumerate() {
            let i = i as i64;
            let v = v as i64;
            if last_row.last().map(|last| v > last.1 + last.0 - i).unwrap_or(true) {
                while last_row.last().map(|last| last.1 <= v + last.0 - i).unwrap_or(false) {
                    last_row.pop();
                }
                last_row.push((i, v));
            }
        }

        for row in points_it {
            let mut candidate_it = last_row.drain(..).peekable();

            let mut candidate = candidate_it.next().unwrap();
            for (i, v) in row.into_iter().enumerate() {
                let i = i as i64;
                let v = v as i64;
                if let Some(new_candidate) = candidate_it.next_if(|new_candidate| candidate.1 + candidate.0 + new_candidate.0 <= new_candidate.1 + 2 * i) {
                    candidate = new_candidate;
                }
                let v = v + candidate.1 - candidate.0.abs_diff(i) as i64;
                if this_row.last().map(|last| v > last.1 + last.0 - i).unwrap_or(true) {
                    while this_row.last().map(|last| last.1 <= v + last.0 - i).unwrap_or(false) {
                        this_row.pop();
                    }
                    this_row.push((i, v));
                }
            }
            drop(candidate_it);
            std::mem::swap(&mut this_row, &mut last_row);
        }

        last_row.into_iter().map(|(_, v)| v).max().unwrap()
    }
}
2 个赞