No.1 Year with the largest population

Their thinking

Data range is relatively small, enumeration statistics can be directly.

The code shown

public int maximumPopulation(int[][] logs) { int[] population = new int[2051]; for (var log : logs) { for (int i = log[0]; i < log[1]; i++) { population[i]++; } } int res = 1950; for (int i = 1951; i <= 2050; i++) { if (population[i] > population[res]) { res = i; } } return res; }}Copy the code

No.2 Maximum distance in a pair of subscripts

Their thinking

Both arrays of input are monotonic, and double Pointers can be used.

The code shown

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[i] <= nums2[j + 1]) { j++; } res = Math.max(res, j - i); } return res; }}Copy the code

No.3 The maximum value of the minimum product of subarrays

Their thinking

Monotone stack deformation, you can first do the maximum rectangle review monotone stack.

When the minimum of a subarray is determined, the longer the array is, the better, so we need to know the position of the first smaller element around each element to determine how large the subarray can be when enumerating each element as the minimum of the subarray.

The code shown

int getMinSwaps(String num, int k) { char[] nums = num.toCharArray(); char[] target = num.toCharArray(); for (int i = 0; i < k; i++) { nextPermutation(target); } int ans = 0, n = nums.length; for (int i = 0; i < n; ++i) { if (nums[i] ! = target[i]) { int j = i + 1; while (j < n && nums[j] ! = target[i]) { j++; } for (; j > i; j--) { swap(nums, j - 1, j); ans++; } } } return ans; } public void nextPermutation(char[] nums) { for (int i = nums.length - 2; i >= 0; i--) { if (nums[i] < nums[i + 1]) { for (int j = nums.length - 1; j > i; j--) { if (nums[i] < nums[j]) { swap(nums, i, j); reverse(nums, i + 1, nums.length - 1); return; } } } } reverse(nums, 0, nums.length - 1); } private void swap(char[] nums, int left, int right) { char temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; } private void reverse(char[] nums, int left, int right) { while (left < right) swap(nums, left++, right--); }}Copy the code

No.4 Maximum color value in a directed graph

Their thinking

First check whether there is a ring in the graph. If there is a ring, return -1.

For acyclic solution, dynamic programming is used.

The code shown

Public int largestPathValue(String colors, int[][] edges) {int n = color.length (); Node[] nodes = new Node[n]; for (int i = 0; i < n; i++) { nodes[i] = new Node(); } for (int[] e : edges) { nodes[e[0]].nei.add(nodes[e[1]]); } 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[j].dp = -1; nodes[j].val = colors.charAt(j) == i ? 1:0; } for (int j = 0; j < n; j++) { best = Math.max(best, dp(nodes[j])); } } 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; } // A simplified version of Tarjan: Boolean findCircle(Node cur) {if (cur.vis) {return cur.stk; 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<>(); }}Copy the code