2022-07-23

[Zheaoli]

2022-07-23

[SaraadKun]

剑指 Offer II 115. 重建序列

    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        //拓扑排序,若排序后与nums不一致(顺序,长度;有环无环情况均包含),则false
        //遍历sequences,统计各元素入度,每轮BFS入度为0的元素入队,
        //若当前队列元素数量大于1,则存在不止一个最短超序列,返回false,否则校验当前元素是否满足要求
        //循环结束判断已校验过的元素和nums.length是否相同,不同返回false
        int n = nums.length;
        int[] cnts = new int[n + 1];
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] seq: sequences) {
            for (int i = 1; i < seq.length; i++) {
                cnts[seq[i]]++;
                adj.get(seq[i - 1]).add(seq[i]);
            }
        }
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            if (cnts[i] == 0) {
                q.offer(i);
            }
        }
        int idx = 0;
        while (!q.isEmpty()) {
            //若当前队列元素数量大于1,则存在不止一个最短超序列,返回false;
            if (q.size() > 1) {
                return false;
            }
            int cur = q.poll();
            //校验当前元素和nums序列
            if (cur != nums[idx++]) {
                return false;
            }
            for (int ne: adj.get(cur)) {
                if (--cnts[ne] == 0) {
                    q.offer(ne);
                }
            }
        }
        return idx == n;
    }

---

WeChat: Saraad

[dreamhunter2333]

#
# [剑指 Offer II 115. 重建序列](https://leetcode.cn/problems/ur2n8P/)
#
class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        n = len(nums)
        graph = {i+1: [] for i in range(n)}
        count = {i+1: 0 for i in range(n)}

        # build graph
        for seq in sequences:
            for j in range(1, len(seq)):
                graph[seq[j-1]].append(seq[j])
                count[seq[j]] += 1

        in_nodes = [i for i in count if count[i] == 0]
        index = 0
        while in_nodes:
            if len(in_nodes) > 1:
                return False
            num = in_nodes.pop(0)
            if nums[index] != num:
                return False
            index += 1
            for node in graph[num]:
                count[node] -= 1
                if count[node] == 0:
                    in_nodes.append(node)

        return True

---

微信id: 而我撑伞

[gongpeione]

/*
 * @lc app=leetcode id=287 lang=javascript
 *
 * [287] Find the Duplicate Number
 * 剑指 Offer 03. 数组中重复的数字
 * 和 cn 上这题不同的是有额外限制：must solve the problem without modifying the array nums and uses only constant extra space.
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
// var findDuplicate = function(nums) {
//     const numObj = {};
//     for (let i = 0; i < nums.length; i++) {
//         if (!numObj[nums[i]]) {
//             numObj[nums[i]] = true;
//             continue;
//         }
//         return nums[i];
//     }
// };
var findDuplicate = function(nums) {
    // Number range
    let low = 1;
    let high = nums.length - 1;

    // duplicate num
    let dup = null;

    while (low <= high) {
        // middle num
        const curNum = ~~((low + high) / 2);

        // count numbers that less or equals to current num
        let lessCount = 0;
        nums.forEach(num => num <= curNum && lessCount++);

        // if lessCount is greater than cur
        // then the duplicate num is smaller than cur
        if (lessCount > curNum) {
            dup = curNum;
            high = curNum - 1;
        }
        // else the duplicate num is greater than cur
        else {
            low = curNum + 1
        }
    }

    return dup;
};
// @lc code=end

---

微信id: 弘树 来自 vscode 插件