LeetCode Weekly Contest 240解题报告
No.1 人口最多的年份解题思路
数据范围比较小，直接枚举统计即可。
代码展示
class Solution {
public int maximumPopulation(int[][] logs) {
int[] population = new int;
for (var log : logs) {
for (int i = log; i < log; i++) {
population++;
}
}
int res = 1950;
for (int i = 1951; i <= 2050; i++) {
if (population > population) {
res = i;
}
}
return res;
}
}
No.2下标对中的最大距离
解题思路
输入的两个数组都是单调的，可以使用双指针。
代码展示
class Solution {
public int maxDistance(int[] nums1, int[] nums2) {
int n = nums1.length, m = nums2.length;
int res = 0;
for (int i = 0, j = -1; i < n; i++) {
while (j + 1 < m && nums1 <= nums2) {
j++;
}
res = Math.max(res, j - i);
}
return res;
}
}
No.3 子数组最小乘积的最大值
解题思路
单调栈的变形，可以先去做一下最大矩形回顾一下单调栈。
当子数组的最小值确定时，肯定是数组越长越好，所以我们需要知道每个元素左右第一个比它小的元素的位置，以在枚举每个元素作为子数组最小值时，这个子数组最大可以是多大。
代码展示
class Solution {
public int maxSumMinProduct(int[] nums) {
int n = nums.length;
long[] preSum = new long;
for (int i = 1; i <= n; ++i) {
preSum = preSum + nums;
}
int[] l = new int;
int[] r = new int;
Arrays.fill(r, n - 1);
LinkedList<Integer> stack = new LinkedList<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums > nums) {
r = i - 1;
}
stack.addFirst(i);
}
stack = new LinkedList<>();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums > nums) {
l = i + 1;
}
stack.addFirst(i);
}
long res = 0;
for (int i = 0; i < n; i++) {
res = Math.max(res, (preSum - preSum) * nums);
}
return (int) (res % 1000000007L);
}
}
No.4 有向图中最大颜色值
解题思路
先判断图中是否有环，有环直接返回 -1.
无环的话则使用动态规划求解。
代码展示
class Solution {
public int largestPathValue(String colors, int[][] edges) {
// 建图
int n = colors.length();
Node[] nodes = new Node;
for (int i = 0; i < n; i++) {
nodes = new Node();
}
for (int[] e : edges) {
nodes].nei.add(nodes]);
}
// 判环
for (Node node : nodes) {
if (findCircle(node)) {
return -1;
}
}
// 动态规划
int best = 0;
for (int i = 'a'; i <= 'z'; i++) {
for (int j = 0; j < n; j++) {
nodes.dp = -1;
nodes.val = colors.charAt(j) == i ? 1 : 0;
}
for (int j = 0; j < n; j++) {
best = Math.max(best, dp(nodes));
}
}
return best;
}
public int dp(Node cur) {
if (cur.dp == -1) {
cur.dp = 0;
for (Node node : cur.nei) {
cur.dp = Math.max(cur.dp, dp(node));
}
cur.dp += cur.val;
}
return cur.dp;
}
// 精简版的 Tarjan 算法：
// 仅用作判环，而无需求出强连通分量
// 所以并不需要真正使用栈，只需要一个标志位即可
boolean findCircle(Node cur) {
if (cur.vis) {
return cur.stk;
}
cur.vis = cur.stk = true;
for (Node node : cur.nei) {
if (findCircle(node)) {
return true;
}
}
cur.stk = false;
return false;
}
}
class Node {
int val, dp;
boolean vis, stk;
List<Node> nei;
Node() {
dp = -1;
nei = new ArrayList<>();
}
}
页:
[1]