Weekly Contest 138
1051. Height Checker
Students are asked to stand in non-decreasing order of heights for an annual photo.
Return the minimum number of students not standing in the right positions. (This is the number of students that must move in order for all students to be standing in non-decreasing order of height.)
Example 1:
Input: [1,1,4,2,1,3]
Output: 3
Explanation:
Students with heights 4, 3 and the last 1 are not standing in the right positions.
Note:
1 <= heights.length <= 1001 <= heights[i] <= 100
Approach #1: [Java]
class Solution {
public int heightChecker(int[] heights) {
int[] copy = new int[heights.length];
for (int i = 0; i < heights.length; ++i) {
copy[i] = heights[i];
}
Arrays.sort(heights);
int ret = 0;
for (int i = 0; i < heights.length; ++i) {
if (copy[i] != heights[i])
ret++;
}
return ret;
}
}
1052. Grumpy Bookstore Owner
Today, the bookstore owner has a store open for
customers.lengthminutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute,
grumpy[i] = 1, otherwisegrumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.The bookstore owner knows a secret technique to keep themselves not grumpy for
Xminutes straight, but can only use it once.Return the maximum number of customers that can be satisfied throughout the day.
Example 1:
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes.
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.
Note:
1 <= X <= customers.length == grumpy.length <= 200000 <= customers[i] <= 10000 <= grumpy[i] <= 1
Approach #1: [Java]
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
int s = 0, e = 0;
int getFromX = 0;
int res = 0;
for (int i = 0; i <= grumpy.length - X; ++i) {
int temp = 0;
for (int j = i; j < i + X; ++j) {
if (grumpy[j] == 1) {
temp += customers[j];
}
}
if (temp > getFromX) {
getFromX = temp;
s = i;
e = i + X;
}
}
for (int i = 0; i < s; ++i) {
if (grumpy[i] == 0)
res += customers[i];
}
for (int i = s; i < e; ++i) {
res += customers[i];
}
for (int i = e; i < grumpy.length; ++i) {
if (grumpy[i] == 0)
res += customers[i];
}
return res;
}
}
1053. Previous Permutation With One Swap
Given an array
Aof positive integers (not necessarily distinct), return the lexicographically largest permutation that is smaller thanA, that can be made with one swap (A swap exchanges the positions of two numbersA[i]andA[j]). If it cannot be done, then return the same array.
Example 1:
Input: [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.Example 2:
Input: [1,1,5]
Output: [1,1,5]
Explanation: This is already the smallest permutation.Example 3:
Input: [1,9,4,6,7]
Output: [1,7,4,6,9]
Explanation: Swapping 9 and 7.Example 4:
Input: [3,1,1,3]
Output: [1,3,1,3]
Explanation: Swapping 1 and 3.
Note:
1 <= A.length <= 100001 <= A[i] <= 10000
Approach #1: [Java]
class Solution {
public int[] prevPermOpt1(int[] A) {
int len = A.length;
int left = len - 2, right = len - 1, tmp;
while (left >= 0 && A[left] <= A[left+1]) left--;
if (left < 0) return A;
while (A[left] <= A[right]) right--;
while (A[right-1] == A[right]) right--;
tmp = A[left];
A[left] = A[right];
A[right] = tmp;
return A;
}
}
1054. Distant Barcodes
In a warehouse, there is a row of barcodes, where the
i-th barcode isbarcodes[i].Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.
Example 1:
Input: [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]Example 2:
Input: [1,1,1,1,2,2,3,3]
Output: [1,3,1,3,2,1,2,1]
Note:
1 <= barcodes.length <= 100001 <= barcodes[i] <= 10000
Approach #1: PriorityQueue [Java]
class Solution {
public int[] rearrangeBarcodes(int[] barcodes) {
Map<Integer, Integer> memo = new HashMap<>();
for (int i : barcodes) {
memo.put(i, memo.getOrDefault(i, 0) + 1);
}
Queue<Integer> pq = new PriorityQueue<>((a, b)->(memo.get(b) - memo.get(a)));
for (int i : memo.keySet()) {
pq.add(i);
}
int[] ans = new int[barcodes.length];
int k = 0;
int count = 0;
Queue<Integer> wait = new LinkedList<>();
while (!pq.isEmpty()) {
while (!pq.isEmpty() && count < 2) {
int first = pq.poll();
ans[k++] = first;
memo.put(first, memo.get(first) - 1);
wait.add(first);
count++;
}
while (!wait.isEmpty() && wait.size() != 1) {
if (memo.get(wait.peek()) > 0) {
pq.add(wait.poll());
} else {
wait.poll();
}
}
count = 0;
}
return ans;
}
}
Reference:
https://docs.oracle.com/javase/9/docs/api/java/util/PriorityQueue.html
最新文章
- sha512散列(C语言)
- 【工匠大道】将项目同时托管到Github和Git@OSC
- Java开发之JSP行为
- MySQL基础（二）——DDL语句
- WebSockets基础
- How to set up a basic working Appium test environment
- QT中QWidget、QDialog QMainWindow
- 修改FFMpeg源码—捕获丢包
- C# Exception的子类Serializable警告
- JS中(function(){xxx})(); 这种写法是什么意思？
- FloatingActionButton 完全解析[Design Support Library(2)]
- C语言入门（4）——常量、变量与赋值
- 阿里云ECS每天一件事D7：安装tomcat8.0
- SpringMVC(八)：使用Servlet原生API作为Spring MVC hanlder方法的参数
- 盘点：2016中国百强地产CIO高峰论坛的8大看点
- skipfish web Scrabble
- MySQL经典练习题
- OpenCV教程(43) harris角的检测(1)
- <sdoi2017>树点涂色
- Ireport第一张web项目报表。