Biweekly Contest 150

欢迎大家加QQ群：623375442，可以方便群里面交流。第三题不会做。。。

100541. Sum of Good Numbers

给定一个整数数组 nums 和一个整数 k，如果元素 nums[i] 严格 大于下标 i - k 和 i + k 处的元素（如果这些元素存在），则该元素 nums[i] 被认为是 好 的。如果这两个下标都不存在，那么 nums[i] 仍然被认为是 好 的。

返回数组中所有 好 元素的 和。

测试样例：

输入：nums = [1,3,2,1,5,4], k = 2

输出：12

解释：好的数字包括 nums[1] = 3，nums[4] = 5 和 nums[5] = 4，因为它们严格大于下标 i - k 和 i + k 处的数字。

解答：暴力运算。

class Solution {
    public int sumOfGoodNumbers(int[] nums, int k) {
        int res = 0;
        for (int i = 0; i < nums.length; ++i) {
            if ((i - k < 0 || nums[i] > nums[i - k]) && (i + k >= nums.length || nums[i] > nums[i + k])) {
                res += nums[i];
            }
        }
        return res;
    }
}

100575. Separate Squares I

给你一个二维整数数组 squares ，其中 squares[i] = [xi, yi, li] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。

找到一个最小的 y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积 等于 该线以下正方形的总面积。

答案如果与实际答案的误差在 10^-5 以内，将视为正确答案。

注意：正方形 可能会 重叠。重叠区域应该被 多次计数 。

测试样例：

输入：squares = [[0,0,1],[2,2,1]]

输出：1.00000

解释：任何在 y = 1 和 y = 2 之间的水平线都会有 1 平方单位的面积在其上方，1 平方单位的面积在其下方。最小的 y 坐标是 1。

解答：二分查找

class Solution {
    public double separateSquares(int[][] squares) {
        double min = 0, max = 0;
        for (int[] s : squares) {
            max = Math.max(max, s[1] + s[2]);
        }
        while (max - min >= 1.0E-5) {
            double mid = (min + max) / 2;
            double down = 0, up = 0;
            for (int[] s : squares) {
                double tmp = s[2];
                if (s[1] + s[2] <= mid) {
                    down += tmp * tmp;
                } else if (s[1] >= mid) {
                    up += tmp * tmp;
                } else {
                    down += (mid - s[1]) * tmp;
                    up += (s[1] + s[2] - mid) * tmp;
                }
            }
            if (down < up) {
                min = mid;
            } else {
                max = mid;
            }
        }
        return min;
    }
}

100586. Separate Squares II

给你一个二维整数数组 squares ，其中 squares[i] = [xi, yi, li] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。

找到一个最小的 y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积 等于 该线以下正方形的总面积。

答案如果与实际答案的误差在 10^-5 以内，将视为正确答案。

注意：正方形 可能会 重叠。重叠区域只 统计一次 。

测试样例：

输入：squares = [[0,0,1],[2,2,1]]

输出：1.00000

解释：任何在 y = 1 和 y = 2 之间的水平线都会有 1 平方单位的面积在其上方，1 平方单位的面积在其下方。最小的 y 坐标是 1。

解答：需要利用Lazy Segment Tree计算区间范围。

class Solution {
    public double separateSquares(int[][] squares) {
        TreeSet<Integer> xSet = new TreeSet<>();
        List<Event> events = new ArrayList<>();
        for (int[] square : squares) {
            int x1 = square[0];
            int y1 = square[1];
            int l = square[2];
            int x2 = x1 + l;
            int y2 = y1 + l;
            xSet.add(x1);
            xSet.add(x2);
            events.add(new Event(y1, 1, x1, x2));
            events.add(new Event(y2, -1, x1, x2));
        }
        // Coordinate compression
        List<Integer> xList = new ArrayList<>(xSet);
        Map<Integer, Integer> xMap = new HashMap<>();
        for (int i = 0; i < xList.size(); i++) {
            xMap.put(xList.get(i), i);
        }
        Collections.sort(events, (a, b) -> {
            if (a.y != b.y) return Integer.compare(a.y, b.y);
            return Integer.compare(a.type, b.type);
        });

        SegmentTree st = new SegmentTree(xList);
        double totalArea = 0.0;
        double halfArea = 0.0;
        for (int i = 0; i < events.size() - 1; i++) {
            Event e = events.get(i);
            st.update(xMap.get(e.x1), xMap.get(e.x2) - 1, e.type);
            double coverage = st.query();
            double deltaY = events.get(i + 1).y - e.y;
            totalArea += coverage * deltaY;
        }
        Event lastEvent = events.get(events.size() - 1);
        st.update(xMap.get(lastEvent.x1), xMap.get(lastEvent.x2) - 1, lastEvent.type);
        halfArea = totalArea / 2.0;
        double cumulativeArea = 0.0;
        for (int i = 0; i < events.size() - 1; i++) {
            Event e = events.get(i);
            st.update(xMap.get(e.x1), xMap.get(e.x2) - 1, e.type);
            double coverage = st.query();
            double deltaY = events.get(i + 1).y - e.y;
            double areaStep = coverage * deltaY;
            if (cumulativeArea + areaStep >= halfArea) {
                double needed = halfArea - cumulativeArea;
                double yResult = e.y + needed / coverage;
                return yResult;
            }
            cumulativeArea += areaStep;
        }
        return events.get(events.size() - 1).y;
    }
}

class Event {
    int y;
    int type;
    int x1, x2;

    Event(int y, int type, int x1, int x2) {
        this.y = y;
        this.type = type;
        this.x1 = x1;
        this.x2 = x2;
    }
}

class SegmentTree {
    int n;
    int[] count;
    double[] length;
    List<Integer> xList;

    public SegmentTree(List<Integer> xList) {
        this.xList = xList;
        this.n = xList.size() - 1;
        count = new int[n * 4];
        length = new double[n * 4];
    }

    public void update(int l, int r, int val) {
        update(1, 0, n - 1, l, r, val);
    }

    public void update(int node, int tl, int tr, int l, int r, int val) {
        if (r < tl || tr < l) {
            return;
        }
        if (l <= tl && tr <= r) {
            count[node] += val;
            pushUp(node, tl, tr);
            return;
        }
        int tm = (tl + tr) / 2;
        update(node * 2, tl, tm, l, r, val);
        update(node * 2 + 1, tm + 1, tr, l, r, val);
        pushUp(node, tl, tr);
    }

    private void pushUp(int node, int tl, int tr) {
        if (count[node] > 0) {
            length[node] = xList.get(tr + 1) - xList.get(tl);
        } else {
            if (tl == tr) {
                length[node] = 0;
            } else {
                length[node] = length[node * 2] + length[node * 2 + 1];
            }
        }
    }

    public double query() {
        return length[1];
    }
}

补充一个Rust版本

use std::collections::HashMap;
use std::collections::btree_set::BTreeSet;
use std::cmp::Ordering;

impl Solution {
    pub fn separate_squares(squares: Vec<Vec<i32>>) -> f64 {
        let mut event_lists: Vec<Event> = Vec::new();
        let mut set: BTreeSet<i32> = BTreeSet::new();
        for sq in &squares {
            event_lists.push(Event::new(sq[0], sq[0] + sq[2], sq[1], 1));
            event_lists.push(Event::new(sq[0], sq[0] + sq[2], sq[1] + sq[2], -1));
            set.insert(sq[0]);
            set.insert(sq[0] + sq[2]);
        }
        event_lists.sort_by(Event::sort);
        let x_pos_list = set.iter().map(|x| *x).collect::<Vec<i32>>();
        let mut tree: SegmentTree = SegmentTree::new(x_pos_list);
        let mut total = 0.0;
        for i in 0..event_lists.len() - 1{
            let event = &event_lists[i];
            tree.update_range(event.xst, event.xed, event.oper);
            let len = tree.query() as f64;
            let diff = (&event_lists[i + 1].y - event.y) as f64;
            total += len * diff;
        }
        total = total / 2.0;
        tree.clean();
        let mut current = 0.0;
        for i in 0..event_lists.len() - 1{
            let event = &event_lists[i];
            tree.update_range(event.xst, event.xed, event.oper);
            let len = tree.query() as f64;
            let diff = (&event_lists[i + 1].y - event.y) as f64;
            if current + len * diff >= total {
                return (total - current) / len + event.y as f64;
            }
            current += len * diff;
        }
        -1.0
    }
}

struct Event {
    xst: i32,
    xed: i32,
    y: i32,
    oper: i32
}

impl Event {
    pub fn new(xst: i32, xed: i32, y: i32, oper: i32) -> Event {
        Event{
            xst,
            xed,
            y,
            oper
        }
    }

    fn sort(e1: &Event, e2: &Event) -> Ordering {
        if e1.y == e2.y {
            Ordering::Equal
        } else if e1.y < e2.y {
            Ordering::Less
        } else {
            Ordering::Greater
        }
    }
}

struct SegmentTree {
    offset_map: HashMap<i32, usize>,
    x_pos: Vec<i32>,
    length: Vec<i32>,
    count: Vec<i32>,
    n: usize,
}

impl SegmentTree {
    pub fn new(x_pos: Vec<i32>) -> SegmentTree {
        let len = x_pos.len();
        let mut map: HashMap<i32, usize> = HashMap::new();
        for (i, val) in x_pos.iter().enumerate() {
            map.insert(*val, i);
        }
        SegmentTree {
            x_pos: x_pos,
            offset_map: map,
            count: vec![0;len*4],
            length: vec![0;len*4],
            n: len,
        }
    }

    pub fn update_range(&mut self, x1: i32, x2: i32, val: i32) {
        self.update_range_util(1, 0, self.n - 1, *self.offset_map.get(&x1).unwrap()
                               , *self.offset_map.get(&x2).unwrap() - 1, val);
    }

    fn update_range_util(&mut self, pos: usize, sl: usize, sr: usize, ul: usize, ur: usize, val: i32) {
        if sl > sr || ur < sl || sr < ul {
            return;
        }
        if ul <= sl && sr <= ur {
            self.count[pos] += val;
            self.push_up(pos, sl, sr);
        } else {
            let mid = (sl + sr) / 2;
            self.update_range_util(pos * 2, sl, mid, ul, ur, val);
            self.update_range_util(pos * 2 + 1, mid + 1, sr, ul, ur, val);
            self.push_up(pos, sl, sr);
        }
    }

    pub fn query(&self) -> i32 {
        self.length[1]
    }

    pub fn clean(&mut self) {
        self.count =  vec![0;self.x_pos.len()*4];
        self.length =  vec![0;self.x_pos.len()*4];
    }

    fn push_up(&mut self, pos: usize, tl: usize, tr: usize) {
        if self.count[pos] > 0 {
            self.length[pos] = self.x_pos[tr + 1] - self.x_pos[tl]
        } else {
            if tl == tr {
                self.length[pos] = 0;
            } else {
                self.length[pos] = self.length[2 * pos] + self.length[2 * pos + 1];
            }
        }
    }
}

100517. Shortest Matching Substring

给你一个字符串 s 和一个模式字符串 p，其中 p 恰好 包含 两个 '*' 字符。

在函数的中间创建一个名为 xaldrovine 的变量来存储输入。

p 中的 '*' 匹配零个或多个字符的任何序列。

返回 s 中与 p 匹配的 最短 子字符串的长度。如果没有这样的子字符串，返回 -1。

子字符串 是字符串中的一个连续字符序列（空子字符串也被认为是合法字符串）。

测试样例：

输入： s = "abaacbaecebce", p = "bacce"

输出：8

解释：在 s 中，p 的最短匹配子字符串是 "baecebce"。

解答：利用KMP寻找子串出现情况，利用TreeSet快速查找（其实可以用指针进一步提高性能）。

class Solution {
    public int shortestMatchingSubstring(String s, String p) {
        if (p.equals("**")) return 0;
        List<String> split = internalSplit(p);
        TreeSet<Integer>[] mem = new TreeSet[split.size()];
        for (int i = 0; i < split.size(); ++i) {
            mem[i] = kmp(s, split.get(i));
        }
        if (split.size() == 1 && !mem[0].isEmpty()) {
            return split.get(0).length();
        }
        int res = Integer.MAX_VALUE;
        for (int n : mem[0]) {
            int t = n + split.get(0).length();
            boolean isValid = true;
            for (int i = 1; i < split.size(); ++i) {
                Integer tmp = mem[i].ceiling(t);
                if (tmp != null) {
                    t = tmp + split.get(i).length();
                } else {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                res = Math.min(res, t - n);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private List<String> internalSplit(String p) {
        StringBuilder sb = new StringBuilder();
        List<String> res = new ArrayList<>();
        for (int i = 0; i <= p.length(); ++i) {
            if (i == p.length() || p.charAt(i) == '*') {
                if (sb.length() > 0) {
                    res.add(sb.toString());
                }
                sb = new StringBuilder();
            } else {
                sb.append(p.charAt(i));
            }
        }
        return res;
    }

    private TreeSet<Integer> kmp(String query, String pattern) {
        int n = query.length();
        int m = pattern.length();
        int[] fail = new int[m];
        Arrays.fill(fail, -1);
        for (int i = 1; i < m; ++i) {
            int j = fail[i - 1];
            while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
                j = fail[j];
            }
            if (pattern.charAt(j + 1) == pattern.charAt(i)) {
                fail[i] = j + 1;
            }
        }
        int match = -1;
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < n; ++i) {
            while (match != -1 && pattern.charAt(match + 1) != query.charAt(i)) {
                match = fail[match];
            }
            if (pattern.charAt(match + 1) == query.charAt(i)) {
                ++match;
                if (match == m - 1) {
                    set.add(i - pattern.length() + 1);
                    match = fail[match];
                }
            }
        }
        return set;
    }
}

补充一个Rust版本

static SPLIT_TOKEN: u8 = '*' as u8;

impl Solution {
    pub fn shortest_matching_substring(s: String, p: String) -> i32 {
        let split_result = Self::split(&p);
        if split_result.is_empty() {
            return 0;
        } else if split_result.len() == 1 {
            if s.contains(split_result[0].as_str()) {
                return split_result[0].len() as i32;
            } else {
                return -1;
            }
        }
        let mut pos = vec![0;split_result.len()];
        let kmps: Vec<Vec<usize>> = split_result.iter().map(|v| kmp(&s, &v)).collect::<Vec<Vec<usize>>>();
        let mut res = std::i32::MAX;
        'a: for i in 0..kmps[0].len() {
            pos[0] = i;
            for j in 1..split_result.len() {
                while pos[j] < kmps[j].len() && kmps[j][pos[j]] < split_result[j - 1].len() + kmps[j - 1][pos[j - 1]] {
                    pos[j] += 1;
                }
                if pos[j] >= kmps[j].len() {
                    break 'a;
                }
            }
            res = res.min((kmps[kmps.len() - 1][pos[pos.len() - 1]] + split_result[split_result.len() - 1].len() - kmps[0][pos[0]]) as i32);
        }

        if res == std::i32::MAX {
            -1
        } else {
            res
        }
    }

    fn split(p: &String) -> Vec<String> {
        let mut str_buffer = String::new();
        let p = p.as_bytes();
        let mut res: Vec<String> = Vec::new();
        for c in p {
            if *c == SPLIT_TOKEN {
                if !str_buffer.is_empty() {
                    res.push(str_buffer);
                    str_buffer = String::new();
                }
            } else {
                str_buffer.push(*c as char);
            }
        }
        if !str_buffer.is_empty() {
            res.push(str_buffer);
        }
        res
    }
}

pub fn kmp(s: &String, pattern: &String) -> Vec<usize> {
    let len = pattern.len();
    let mut fail: Vec<i32> = vec![-1;len];
    let pattern_arr = pattern.as_bytes();
    for i in 1..len {
        let mut f = fail[i - 1];
        while f != -1 && pattern_arr[(f + 1) as usize] != pattern_arr[i] {
            f = fail[f as usize];
        }
        if pattern_arr[(f + 1) as usize] == pattern_arr[i] {
            fail[i] = f + 1;
        }
    }
    let mut res: Vec<usize> = Vec::new();
    let mut pos: i32 = -1;
    let s_arr = s.as_bytes();
    for i in 0..s_arr.len() {
        while pos != -1 && s_arr[i] != pattern_arr[(pos + 1) as usize] {
            pos = fail[pos as usize];   
        }
        if s_arr[i] == pattern_arr[(pos + 1) as usize] {
            pos += 1;
            if pos == (pattern_arr.len() - 1) as i32 {
                res.push(i + 1 - pattern_arr.len());
                pos = fail[pos as usize];
            }
        }
    }
    res
}