上岸算法 I LeetCode Weekly Contest 244解题报告
No.1判断矩阵经轮转后是否一致解题思路模拟矩阵的旋转即可。代码展示class Solution {public boolean findRotation(int[][] mat, int[][] target) {
for (int i = 0; i < 4; i++) {
if (equal(mat, target)) {
return true;
}
mat = rotate(mat);
}
return false;
}
private int[][] rotate(int[][] mat) {
int[][] r = new int.length];
for (int i = 0, y = 0; i < mat.length; i++, y++) {
for (int j = 0, x = mat.length - 1; j < mat.length; j++, x--) {
r = mat;
}
}
return r;
}
boolean equal(int[][] mat, int[][] target) {
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat.length; j++) {
if (mat != target) {
return false;
}
}
}
return true;
}
}上岸算法公开课，毫无保留地将业界面试核心知识免费传授给大家，并配有课前课后习题以及标准答案集以方便大家学习。长达近30小时的核心课程帮助大家掌握所有面试必备知识，在一个月内有效突破算法面试认知，从而有自信面对FAANG的挑战。联系上岸小年糕，领取课件及视频No.2 使数组元素相等的减少操作次数解题思路简单暴力地，从大到小依次处理每个元素即可。使用 TreeMap 的代码非常简洁，或者可以使用链表，速度更快。代码展示class Solution {
public int reductionOperations(int[] nums) {
TreeMap<Integer, Integer> count = new TreeMap<>();
for (var num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
int result = 0;
while (count.size() > 1) {
var largest = count.pollLastEntry();
var nextLargest = count.lastEntry();
result += largest.getValue();
count.put(nextLargest.getKey(), nextLargest.getValue() + largest.getValue());
}
return result;
}
}No.3 使二进制字符串字符交替的最少反转次数解题思路枚举类型 1 操作执行的次数即可。执行完类型 1 的操作之后，需要执行的类型 2 的操作次数是固定的。我们只需要知道奇数下标上 0 和 1 的数量、偶数下标上 0 和 1 的数量就可以计算出类型 2 的操作次数。每执行一次类型 1 的操作，奇数下标上 0 和 1 的数量、偶数下标上 0 和 1 的数量的变化都可以 O(1) 地计算出来。代码展示class Solution {
public int minFlips(String s) {
char[] str = s.toCharArray();
// count 表示偶数下标上 0 和 1 的数量
// count 表示奇数下标上 0 和 1 的数量
int[][] count = new int;
for (int i = 0; i < str.length; i++) {
count - '0']++;
}
int result = Math.min(count + count, count + count);
for (int i = 0; i < str.length - 1; i++) {
count - '0']--;
int tmp = count;
count = count;
count = tmp;
tmp = count;
count = count;
count = tmp;
count[(str.length - 1) % 2] - '0']++;
result = Math.min(result, Math.min(count + count, count + count));
}
return result;
}
}No.4 装包裹的最小浪费空间解题思路二分查找。对所有的包裹和供应商的盒子都排序，然后依次枚举每个供应商即可。计算一个供应商的盒子的浪费空间时，从小到大使用每种盒子，每种盒子尽可能多装包裹即可，使用前缀和数组和二分查找可以快速计算结果。代码展示class Solution {
public int minWastedSpace(int[] packages, int[][] boxes) {
Arrays.sort(packages);
long[] preSum = new long;
preSum = packages;
for (int i = 1; i < preSum.length; i++) {
preSum = preSum + packages;
}
long result = -1;
for (int[] box : boxes) {
Arrays.sort(box);
long t = waste(packages, preSum, box);
if (t != -1 && (result == -1 || t < result)) {
result = t;
}
}
return (int) (result % 1000000007L);
}
private long waste(int[] packages, long[] preSum, int[] boxes) {
int start = 0;
long result = 0;
for (int box : boxes) {
if (box < packages) {
continue;
}
int index = binarySearch(packages, box);
// 之间的包裹使用 box 装
result += (long) box * (index - start + 1) - preSum;
if (start != 0) {
result += preSum;
}
start = index + 1;
if (start >= packages.length) {
return result;
}
}
return -1;
}
private int binarySearch(int[] arr, int target) {
int l = 0, r = arr.length - 1;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (arr <= target) {
l = mid;
} else {
r = mid;
}
}
return arr <= target ? r : l;
}
}
页:
[1]