esc to dismiss
x
Home / week-85 / 838

信息

题解

Tip
  1. 两个相邻的被推倒的牌互不影响, 不管方向是否一致
  2. 一个推倒了的牌只能对另一个站着的牌起作用

因此只需要关注初始状态为 . 的, 以及哪个被推倒的(L/R)最先影响到它. 

pub fn push_dominoes(dominoes: String) -> String {
    let mut dominoes = dominoes;
    let s = unsafe { dominoes.as_bytes_mut() };
    // 只需要关注前面最后一个向右倒的, 以及后面最早一个向左倒的
    // 其他组合不会影响当前的状态, 可以不记录
    let (mut last_right, mut next_left): (Option<usize>, Option<usize>) = (None, None);

    let mut cursor = 0;
    while cursor < s.len() {
        if s[cursor] == b'R' {
            last_right.replace(cursor);
        } else if s[cursor] == b'L' {
            last_right.take();
        } else if s[cursor] == b'.' {
            next_left.take();
            for j in cursor + 1..s.len() {
                if s[j] == b'L' {
                    next_left.replace(j);
                    break;
                } else if s[j] == b'R' {
                    break;
                }
            }
            if last_right.is_none() && next_left.is_none() {
                // 不变
            } else if last_right.is_none() {
                s[cursor] = b'L';
            } else if next_left.is_none() {
                s[cursor] = b'R';
            } else {
                let (r, l) = (last_right.unwrap(), next_left.unwrap());
                match (cursor - r).cmp(&(l - cursor)) {
                    std::cmp::Ordering::Equal => {}
                    std::cmp::Ordering::Greater => {
                        s[cursor] = b'L';
                    }
                    std::cmp::Ordering::Less => {
                        s[cursor] = b'R';
                    }
                }
            }

            // last_right.take();
            // if s[cursor] == b'R' {
            //     last_right.replace(cursor);
            // }
        }
        cursor += 1;
    }
    dominoes
}

按照上面代码, 在R......L 这种只有两端的序列下, 效果最差, 复杂度达到\(O(n^2)\)

观察可知,
对于任意一个 . 只需要在其两端, 找到离它最近的两个变动的即可
同理对于任意连续的 . 也是可以的.
* 原本的R/L都不会变 

pub fn push_dominoes(dominoes: String) -> String {
    let mut dominoes = dominoes;
    let s = unsafe { dominoes.as_bytes_mut() };

    let (mut cursor, mut last) = (0, None::<u8>);

    while cursor < s.len() {
        if s[cursor] == b'R' || s[cursor] == b'L' {
            last.replace(s[cursor]);
            cursor += 1;
            continue;
        }

        let mut end = cursor;
        while end + 1 < s.len() && s[end + 1] == b'.' {
            end += 1;
        }

        let tmp = end + 1; // 暂存
        let next = s.get(tmp).copied();
        // cursor, end
        match (last, next) {
            (Some(b'R'), Some(b'L')) => {
                while cursor < end {
                    s[cursor] = b'R';
                    s[end] = b'L';

                    cursor += 1;
                    end -= 1;
                }
            }
            (_, Some(b'L')) => {
                for i in cursor..tmp {
                    s[i] = b'L';
                }
            }
            (Some(b'R'), _) => {
                for i in cursor..tmp {
                    s[i] = b'R';
                }
            }
            _ => {}
        }
        cursor = tmp;
    }
    dominoes
}

一次性处理一段连续的. 然后跳过, 这样最多遍历\(2n\)次, 时间复杂度\(O(n)\)

Backlinks

Tags

x