❌

阅读视图

发现新文章，点击刷新页面。

3637. 三段式数组 I

✇LeetCode 每日一题题解
stormsunshine

解法一

思路和算法

数组 $\textit{nums}$ 的长度是 $n$。最直观的思路是遍历 $0 < p < q < n - 1$ 的所有下标对 $(p, q)$，判断是否同时满足三段式数组的全部条件。

  • 下标范围 $[0, p]$ 严格递增。

  • 下标范围 $[p, q]$ 严格递减。

  • 下标范围 $[q, n - 1]$ 严格递增。

当遇到满足全部条件的下标对 $(p, q)$ 时，返回 $\text{true}$。如果不存在满足全部条件的下标对 $(p, q)$，返回 $\text{false}$。

代码

###Java

class Solution {
    public boolean isTrionic(int[] nums) {
        int n = nums.length;
        for (int p = 1; p < n - 2; p++) {
            if (!isMonotonicInRange(nums, 0, p, 1)) {
                continue;
            }
            for (int q = p + 1; q < n - 1; q++) {
                if (isMonotonicInRange(nums, p, q, -1) && isMonotonicInRange(nums, q, n - 1, 1)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean isMonotonicInRange(int[] nums, int start, int end, int direction) {
        for (int i = start; i < end; i++) {
            if ((nums[i + 1] - nums[i]) * direction <= 0) {
                return false;
            }
        }
        return true;
    }
}

###C#

public class Solution {
    public bool IsTrionic(int[] nums) {
        int n = nums.Length;
        for (int p = 1; p < n - 2; p++) {
            if (!IsMonotonicInRange(nums, 0, p, 1)) {
                continue;
            }
            for (int q = p + 1; q < n - 1; q++) {
                if (IsMonotonicInRange(nums, p, q, -1) && IsMonotonicInRange(nums, q, n - 1, 1)) {
                    return true;
                }
            }
        }
        return false;
    }

    public bool IsMonotonicInRange(int[] nums, int start, int end, int direction) {
        for (int i = start; i < end; i++) {
            if ((nums[i + 1] - nums[i]) * direction <= 0) {
                return false;
            }
        }
        return true;
    }
}

复杂度分析

  • 时间复杂度：$O(n^3)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。需要遍历的下标对数量是 $O(n^2)$，每个下标对判断是否符合三段式数组的全部条件的时间是 $O(n)$，因此时间复杂度是 $O(n^3)$。

  • 空间复杂度：$O(1)$。

解法二

思路和算法

可以遍历数组 $\textit{nums}$ 一次，判断是否符合三段式的条件。

三个子数组的单调性必须依次满足严格单调递增、严格单调递减、严格单调递增。首个子数组的起始下标是 $0$，从起始下标向右遍历，遍历过程中执行如下操作。

  • 由于三个子数组都满足严格单调递增或严格单调递减，因此不允许出现相邻元素相等的情况。如果遇到相邻元素相等的情况，则一定不符合三段式的条件。

  • 如果遍历到数组 $\textit{nums}$ 的末尾或者遇到相邻元素的单调性与当前子数组的单调性条件相反的情况（已经排除相邻元素相等的情况），则可以确定当前子数组的结束下标。将当前子数组的结束下标作为下一个子数组的起始下标，继续遍历下一个子数组。

当数组 $\textit{nums}$ 可以恰好分成三个子数组且依次满足严格单调递增、严格单调递减、严格单调递增时，返回 $\text{true}$，否则返回 $\text{false}$。

代码

###Java

class Solution {
    public boolean isTrionic(int[] nums) {
        int n = nums.length;
        int index = 0;
        for (int i = 0, direction = 1; i < 3; i++, direction *= -1) {
            index = findMonotonicRangeEnd(nums, index, direction);
            if (index < 0) {
                return false;
            }
        }
        return index == n - 1;
    }

    public int findMonotonicRangeEnd(int[] nums, int start, int direction) {
        int n = nums.length;
        int end = -1;
        for (int i = start; i < n && end < 0; i++) {
            if (i < n - 1 && nums[i + 1] == nums[i]) {
                return -1;
            }
            if (i == n - 1 || (nums[i + 1] - nums[i]) * direction < 0) {
                end = i;
            }
        }
        return end > start ? end : -1;
    }
}

###C#

public class Solution {
    public bool IsTrionic(int[] nums) {
        int n = nums.Length;
        int index = 0;
        for (int i = 0, direction = 1; i < 3; i++, direction *= -1) {
            index = FindMonotonicRangeEnd(nums, index, direction);
            if (index < 0) {
                return false;
            }
        }
        return index == n - 1;
    }

    public int FindMonotonicRangeEnd(int[] nums, int start, int direction) {
        int n = nums.Length;
        int end = -1;
        for (int i = start; i < n && end < 0; i++) {
            if (i < n - 1 && nums[i + 1] == nums[i]) {
                return -1;
            }
            if (i == n - 1 || (nums[i + 1] - nums[i]) * direction < 0) {
                end = i;
            }
        }
        return end > start ? end : -1;
    }
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。最多需要遍历数组一次。

  • 空间复杂度：$O(1)$。

3650. 边反转的最小路径总成本

✇LeetCode 每日一题题解
stormsunshine

解法

思路和算法

根据题目要求，图中有 $n$ 个结点，每个结点最多可以使用一次边反转的开关。对于 $0 \le i < n$ 的每个结点 $i$，使用边反转的开关的效果是将一条终点是结点 $i$ 的边反转成起点是 $i$ 且反转后的边的成本加倍。

由于所有边的成本都是正整数，因此为了将从结点 $0$ 到结点 $n - 1$ 的路径总成本最小化，应确保同一个结点最多访问一次。理由如下：如果一条从结点 $0$ 到结点 $n - 1$ 的路径中存在一个结点访问两次，则将两次访问该结点之间的部分去除之后，该路径仍可以从结点 $0$ 到结点 $n - 1$，且总成本更小。

由于当路径总成本最小时同一个结点最多访问一次，因此边反转的开关的最多可使用一次的限制不需要考虑。对于边数组 $\textit{edges}$ 中的每条边 $[u, v, w]$，等价于如下两条边。

  • 从结点 $u$ 出发到达结点 $v$ 的成本为 $w$ 的边。

  • 从结点 $v$ 出发到达结点 $u$ 的成本为 $2w$ 的边。

根据边数组 $\textit{edges}$ 中的每条边对应两条边的规则构建有向带权图，然后即可使用最短路算法计算从结点 $0$ 到结点 $n - 1$ 的最小路径总成本。如果不存在从结点 $0$ 到结点 $n - 1$ 的路径，则答案是 $-1$。

由于图中的结点数 $n$ 的最大值是 $5 \times 10^4$，边数组 $\textit{edges}$ 的长度的最大值是 $10^5$，因此这道题适合使用基于小根堆实现的 Dijkstra 算法。

为了方便处理，需要首先将边数组转换成邻接列表的形式，转换后可以使用 $O(1)$ 时间得到一个结点的全部相邻结点。

代码

###Java

class Solution {
    public int minCost(int n, int[][] edges) {
        List<int[]>[] adjacentArr = new List[n];
        for (int i = 0; i < n; i++) {
            adjacentArr[i] = new ArrayList<int[]>();
        }
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            adjacentArr[u].add(new int[]{v, w});
            adjacentArr[v].add(new int[]{u, 2 * w});
        }
        int[] distances = new int[n];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[1] - b[1]);
        pq.offer(new int[]{0, 0});
        while (!pq.isEmpty()) {
            int[] pair = pq.poll();
            int curr = pair[0], distance = pair[1];
            if (distances[curr] < distance) {
                continue;
            }
            for (int[] adjacent : adjacentArr[curr]) {
                int next = adjacent[0], weight = adjacent[1];
                if (distances[next] > distance + weight) {
                    distances[next] = distance + weight;
                    pq.offer(new int[]{next, distances[next]});
                }
            }
        }
        return distances[n - 1] != Integer.MAX_VALUE ? distances[n - 1] : -1;
    }
}

###C#

public class Solution {
    public int MinCost(int n, int[][] edges) {
        IList<int[]>[] adjacentArr = new IList<int[]>[n];
        for (int i = 0; i < n; i++) {
            adjacentArr[i] = new List<int[]>();
        }
        foreach (int[] edge in edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            adjacentArr[u].Add(new int[]{v, w});
            adjacentArr[v].Add(new int[]{u, 2 * w});
        }
        int[] distances = new int[n];
        Array.Fill(distances, int.MaxValue);
        distances[0] = 0;
        PriorityQueue<int[], int> pq = new PriorityQueue<int[], int>();
        pq.Enqueue(new int[]{0, 0}, 0);
        while (pq.Count > 0) {
            int[] pair = pq.Dequeue();
            int curr = pair[0], distance = pair[1];
            if (distances[curr] < distance) {
                continue;
            }
            foreach (int[] adjacent in adjacentArr[curr]) {
                int next = adjacent[0], weight = adjacent[1];
                if (distances[next] > distance + weight) {
                    distances[next] = distance + weight;
                    pq.Enqueue(new int[]{next, distances[next]}, distances[next]);
                }
            }
        }
        return distances[n - 1] != int.MaxValue ? distances[n - 1] : -1;
    }
}

复杂度分析

  • 时间复杂度：$O((n + m) \log n)$，其中 $n$ 是图中的结点数，$m$ 是图中的边数。将边数组转换成邻接列表的时间是 $O(n + m)$，Dijkstra 算法的时间是 $O((n + m) \log n)$，因此时间复杂度是 $O((n + m) \log n)$。

  • 空间复杂度：$O(n + m)$，其中 $n$ 是图中的结点数，$m$ 是图中的边数。邻接结点列表的空间是 $O(n + m)$，记录到达每个结点的最小总成本的空间和优先队列的空间是 $O(n)$，因此空间复杂度是 $O(n + m)$。

❌