5428. 重新排列数组

题目描述

给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,…,xn,y1,y2,…,yn] 的格式排列。

请你将数组按 [x1,y1,x2,y2,…,xn,yn] 格式重新排列，返回重排后的数组。

示例1：

输入：nums = [2,5,1,3,4,7], n = 3
输出：[2,3,5,4,1,7] 
解释：由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 ，所以答案为 [2,3,5,4,1,7]

示例2

输入：nums = [1,2,3,4,4,3,2,1], n = 4
输出：[1,4,2,3,3,2,4,1]

示例3：

输入：nums = [1,1,2,2], n = 2
输出：[1,2,1,2]

提示：

• 1 <= n <= 500
• nums.length == 2n
• 1 <= nums[i] <= 10^3

Solution

遍历

class Solution {public int[] shuffle(int[] nums, int n) {ArrayList<Integer> list = new ArrayList<>();for(int i = 0; i < n; i++){list.add(nums[i]);list.add(nums[i+n]);}int[] ans = new int[2*n];ans = list.stream().mapToInt(Integer::valueOf).toArray();return ans;}
}

这样应该快一点

class Solution {public int[] shuffle(int[] nums, int n) {int[] ans = new int[2*n];int index = 0;for(int i = 0; i < n; i++){ans[index++] = nums[i];ans[index++] = nums[i+n];}return ans;}
}

5429. 数组中的 k 个最强值

题目描述

给你一个整数数组 arr 和一个整数 k 。

设 m 为数组的中位数，只要满足下述两个前提之一，就可以判定 arr[i] 的值比 arr[j] 的值更强：

|arr[i] - m| > |arr[j] - m|
|arr[i] - m| == |arr[j] - m|，且 arr[i] > arr[j]
请返回由数组中最强的 k 个值组成的列表。答案可以以 任意顺序 返回。

中位数 是一个有序整数列表中处于中间位置的值。形式上，如果列表的长度为 n ，那么中位数就是该有序列表（下标从 0 开始）中位于((n - 1) / 2)的元素。

• 例如 arr = [6, -3, 7, 2, 11]，n = 5：数组排序后得到 arr = [-3, 2, 6, 7, 11] ，数组的中间位置为 m = ((5 - 1) / 2) = 2 ，中位数 arr[m] 的值为 6 。
• 例如 arr = [-7, 22, 17, 3]，n = 4：数组排序后得到 arr = [-7, 3, 17, 22] ，数组的中间位置为 m = ((4 - 1) / 2) = 1 ，中位数 arr[m] 的值为 3 。

示例1：

输入：arr = [1,2,3,4,5], k = 2
输出：[5,1]
解释：中位数为 3，按从强到弱顺序排序后，数组变为 [5,1,4,2,3]。最强的两个元素是 [5, 1]。[1, 5] 也是正确答案。
注意，尽管 |5 - 3| == |1 - 3| ，但是 5 比 1 更强，因为 5 > 1 。

示例 2：

输入：arr = [1,1,3,5,5], k = 2
输出：[5,5]
解释：中位数为 3, 按从强到弱顺序排序后，数组变为 [5,5,1,1,3]。最强的两个元素是 [5, 5]。

示例 3：

输入：arr = [6,7,11,7,6,8], k = 5
输出：[11,8,6,6,7]
解释：中位数为 7, 按从强到弱顺序排序后，数组变为 [11,8,6,6,7,7]。
[11,8,6,6,7] 的任何排列都是正确答案。

示例 4：

输入：arr = [6,-3,7,2,11], k = 3
输出：[-3,11,2]

示例 5：

输入：arr = [-7,22,17,3], k = 2
输出：[22,17]

提示：

• 1 <= arr.length <= 10^5
• -10^5 <= arr[i] <= 10^5
• 1 <= k <= arr.length

Solution

排序+双指针

class Solution {public int[] getStrongest(int[] arr, int k) {int[] ans = new int[k];int n = arr.length;if(k == n){return arr;}Arrays.sort(arr);int m = (n-1) / 2;int i = 0; int j = n-1;int index = 0;while(k > 0 && i < j){if((Math.abs(arr[i] - arr[m]) > Math.abs(arr[j] - arr[m])) || ((Math.abs(arr[i] - arr[m]) == Math.abs(arr[j] - arr[m])) && (arr[i] > arr[j]))){ans[index++] = arr[i];i++;k--;}else{ans[index++] = arr[j];j--;k--;}}return ans;}
}

top K问题，也可以用优先队列

class Solution {public int[] getStrongest(int[] arr, int k) {int n = arr.length;Arrays.sort(arr);int m = arr[(n - 1) / 2];PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {int a = Math.abs(arr[o1] - m);int b = Math.abs(arr[o2] - m);if (a == b) {return arr[o1] - arr[o2];} else {return a - b;}}});// 遍历arr数组，将下标放入优先队列for (int i = 0; i < arr.length; i++) {queue.add(i);if (queue.size() > k) {queue.poll();}}int[] result = new int[k];for (int i = 0; i < result.length; i++) {result[i] = arr[queue.poll()];}return result;}
}

5430. 设计浏览器历史记录

输入：
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
输出：
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]解释：
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // 你原本在浏览 "leetcode.com" 。访问 "google.com"
browserHistory.visit("facebook.com");     // 你原本在浏览 "google.com" 。访问 "facebook.com"
browserHistory.visit("youtube.com");      // 你原本在浏览 "facebook.com" 。访问 "youtube.com"
browserHistory.back(1);                   // 你原本在浏览 "youtube.com" ，后退到 "facebook.com" 并返回 "facebook.com"
browserHistory.back(1);                   // 你原本在浏览 "facebook.com" ，后退到 "google.com" 并返回 "google.com"
browserHistory.forward(1);                // 你原本在浏览 "google.com" ，前进到 "facebook.com" 并返回 "facebook.com"
browserHistory.visit("linkedin.com");     // 你原本在浏览 "facebook.com" 。 访问 "linkedin.com"
browserHistory.forward(2);                // 你原本在浏览 "linkedin.com" ，你无法前进任何步数。
browserHistory.back(2);                   // 你原本在浏览 "linkedin.com" ，后退两步依次先到 "facebook.com" ，然后到 "google.com" ，并返回 "google.com"
browserHistory.back(7);                   // 你原本在浏览 "google.com"， 你只能后退一步到 "leetcode.com" ，并返回 "leetcode.com"

Solution

双栈

class BrowserHistory {Stack<String> stack1;Stack<String> stack2;public BrowserHistory(String homepage) {stack1 = new Stack<String>();stack2 = new Stack<String>();stack1.push(homepage);}public void visit(String url) {stack1.push(url);if(!stack2.isEmpty()){stack2 = new Stack<String>();}}public String back(int steps) {if(steps > stack1.size()-1){steps = stack1.size()-1;}for(int i = 1; i <= steps; i++){String tmp = stack1.pop();stack2.push(tmp);}return stack1.peek();}public String forward(int steps) {if(steps > stack2.size()){steps = stack2.size();}for(int i = 1; i <= steps; i++){String tmp = stack2.pop();stack1.push(tmp);}return stack1.peek();}
}/*** Your BrowserHistory object will be instantiated and called as such:* BrowserHistory obj = new BrowserHistory(homepage);* obj.visit(url);* String param_2 = obj.back(steps);* String param_3 = obj.forward(steps);*/

5431. 给房子涂色 III

题目描述

在一个小城市里，有 m 个房子排成一排，你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n ）。有的房子去年夏天已经涂过颜色了，所以这些房子不需要被重新涂色。

我们将连续相同颜色尽可能多的房子称为一个街区。（比方说houses = [1,2,2,3,3,2,1,1]，它包含 5 个街区 [{1}, {2,2}, {3,3}, {2}, {1,1}]。）

给你一个数组 houses ，一个 m * n 的矩阵 cost 和一个整数 target ，其中：

• houses[i]：是第 i 个房子的颜色，0 表示这个房子还没有被涂色。
• cost[i][j]：是将第 i 个房子涂成颜色 j+1 的花费。

请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 target 个街区。如果没有可用的涂色方案，请返回 -1 。

示例1：

输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：9
解释：房子涂色方案为 [1,2,2,1,1]
此方案包含 target = 3 个街区，分别是 [{1}, {2,2}, {1,1}]。
涂色的总花费为 (1 + 1 + 1 + 1 + 5) = 9。

示例 2：

输入：houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：11
解释：有的房子已经被涂色了，在此基础上涂色方案为 [2,2,1,2,2]
此方案包含 target = 3 个街区，分别是 [{2,2}, {1}, {2,2}]。
给第一个和最后一个房子涂色的花费为 (10 + 1) = 11。

示例 3：

输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
输出：5

示例 4：

输入：houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
输出：-1
解释：房子已经被涂色并组成了 4 个街区，分别是 [{3},{1},{2},{3}] ，无法形成 target = 3 个街区。

提示：

m == houses.length == cost.length
n == cost[i].length
1 <= m <= 100
1 <= n <= 20
1 <= target <= m
0 <= houses[i] <= n
1 <= cost[i][j] <= 10^4

Soluion

三维动态规划

参考题解

• 状态定义：dp[i][j][k]代表第i个房子涂成j颜色，有k个街区的最小花费

• 边界：

  对第一个房子:

  • 如果已经涂色，即houses[0] != 0,则相应花费为0
  • 如果没有涂色，houses[0] == 0,则有n种颜色可以涂

class Solution {public int minCost(int[] houses, int[][] cost, int m, int n, int target) {//dp[i][j][k] 第i个房子涂成j颜色，有k个街区的最小花费int[][][] dp = new int[m][n][target+1];for(int i=0; i<m; i++) {for(int j=0; j<n; j++) {Arrays.fill(dp[i][j], -1);}}//base case, 第1个房子if(houses[0] != 0) {//如果已经涂色，则不用增加花费dp[0][houses[0]-1][1] = 0;} else {for(int i=0; i<n; i++) {dp[0][i][1] = cost[0][i];}}for(int i=1; i<m; i++) {for(int k=1; k<=i+1 && k<=target; k++) {//已经涂色，则只需要求解dp[i][c][k]，其他的均为-1if(houses[i] != 0) {int c = houses[i]-1; //颜色号-1//默认为int最大值dp[i][c][k] = dp[i-1][c][k] == -1 ? Integer.MAX_VALUE : dp[i-1][c][k];for(int j=0; j<n; j++) {//dp[i-1][j][k-1] 可达，才能从 dp[i-1][j][k-1] 跳转过来if(j != c && dp[i-1][j][k-1] != -1) {//已经涂色的，不需要增加费用dp[i][c][k] = Math.min(dp[i-1][j][k-1], dp[i][c][k]);}}//没有有效值的话，说明不可达，设置为-1if(dp[i][c][k] == Integer.MAX_VALUE) {dp[i][c][k] = -1; }continue; }//需要涂色for(int j=0; j<n; j++) {dp[i][j][k] = dp[i-1][j][k] == -1 ? Integer.MAX_VALUE : dp[i-1][j][k] + cost[i][j];for(int t=0; t<n; t++) {if(t != j && dp[i-1][t][k-1] != -1) {dp[i][j][k] = Math.min(dp[i-1][t][k-1]+cost[i][j], dp[i][j][k]);}}//不可达,设置为-1if(dp[i][j][k] == Integer.MAX_VALUE) {dp[i][j][k] = -1;}}}  }int ans = Integer.MAX_VALUE;for(int i=0; i<n; i++) {if(dp[m-1][i][target] != -1) {ans = Math.min(dp[m-1][i][target], ans);}         }//不可达，返回-1return ans == Integer.MAX_VALUE ? -1 : ans;}
}