// 1827. Minimum Operations to Make the Array Increasing
class Solution {
public int minOperations(int[] nums) {
int len = nums.length;
int ans = 0;
int current = nums[0];
for (int i = 1; i < len; ++i) {
++current;
if (nums[i] < current) {
ans += current - nums[i];
} else {
current = nums[i];
}
}
return ans;
}
}学习笔记： 这是一道简单题，数组题。 就是需要一直递增，遇到大的就很自然，小的就要提升。
import java.util.Arrays;
// 1691. Maximum Height by Stacking Cuboids
class Solution {
public int maxHeight(int[][] cuboids) {
int n = cuboids.length;
for (int[] cuboid : cuboids) Arrays.sort(cuboid);
Arrays.sort(cuboids, (c1, c2) -> (c1[0] + c1[1] + c1[2]) - (c2[0] + c2[1] + c2[2]));
int ans = 0;
int[] maxHeights = new int[n];
for (int i = 0; i < n; ++i) {
maxHeights[i] = cuboids[i][2];
ans = Math.max(ans, maxHeights[i]);
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (cuboids[j][0] <= cuboids[i][0] && cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2]) {
maxHeights[i] = Math.max(maxHeights[i], maxHeights[j] + cuboids[i][2]);
}
}
ans = Math.max(ans, maxHeights[i]);
}
return ans;
}
}
学习笔记： 好家伙，两天简单题，之后直接今天来了一道困难题。 这是一道动态规划、排序的题目。 先要根据数学的理论一通推理，最优方案一定是把每个盒子最长边放在高上。 先把cuboids每个盒子内部排序，从短到长。 然后再整体排序，总长从短到长。 然后每一个盒子的状态转移方程式就是要找能放在他上面的最大的盒子高度。
// 1780. Check if Number is a Sum of Powers of Three
class Solution {
public boolean checkPowersOfThree(int n) {
while (n != 0) {
if (n % 3 == 2) {
return false;
}
n /= 3;
}
return true;
}
}
学习笔记： 今天竟然又是一道简单题。 其实就是用3进制的思想看这个数字里面有没有2。
// 1812. Determine Color of a Chessboard Square
class Solution {
public boolean squareIsWhite(String coordinates) {
return (coordinates.charAt(0) & 1) - (coordinates.charAt(1) & 1) != 0;
}
}
学习笔记： 这道题就是用模运算，一行就结束了。 之前9月1日做的，今天就懒得再做一遍了。
// 1775. Equal Sum Arrays With Minimum Number of Operations
class Solution {
public int minOperations(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length * 6 || nums2.length > nums1.length * 6) {
return -1;
}
int[] frequency1 = new int[7];
int[] frequency2 = new int[7];
int sum1 = 0;
int sum2 = 0;
for (int num : nums1) {
sum1 += num;
++frequency1[num];
}
for (int num : nums2) {
sum2 += num;
++frequency2[num];
}
if (sum1 < sum2) {
int t = sum2;
sum2 = sum1;
sum1 = t;
int[] te = frequency1;
frequency1 = frequency2;
frequency2 = te;
}
int ans = 0;
int change = 1;
while (sum1 > sum2) {
int diff = sum1 - sum2;
if (frequency1[7 - change] * (6 - change) < diff) {
int changeTimes = frequency1[7 - change];
frequency1[7 - change] = 0;
sum1 -= changeTimes * (6 - change);
ans += changeTimes;
} else {
int changeTimes = diff / (6 - change);
ans += changeTimes;
if (diff % (6 - change) != 0) {
++ans;
}
return ans;
}
diff = sum1 - sum2;
if (frequency2[change] * (6 - change) < diff) {
int changeTimes = frequency2[change];
frequency2[change] = 0;
sum2 += changeTimes * (6 - change);
ans += changeTimes;
} else {
int changeTimes = diff / (6 - change);
ans += changeTimes;
if (diff % (6 - change) != 0) {
++ans;
}
return ans;
}
++change;
}
return ans;
}
}
学习笔记： 这是一道计数、贪心算法的中等题。 先数出来，然后把小的一组的1变6，大的一组6变1，然后把小的一组2变6，大的一组5变1…… 方法特别容易想到，但是写成代码总是很麻烦要考虑很多东西，写得也很繁琐。
import java.util.HashSet;
// 1805. Number of Different Integers in a String
class Solution {
public int numDifferentIntegers(String word) {
HashSet<String> hashSet = new HashSet<>();
char[] charArray = word.toCharArray();
int len = charArray.length;
int i = 0;
int j = i;
OUTER:
while (i < len) {
while (charArray[i] > 57) {
++i;
if (i == len) {
break OUTER;
}
}
j = i;
while (charArray[i] < 58) {
++i;
if (i == len) {
break;
}
}
while (charArray[j] == '0' && j < i - 1) {
++j;
}
hashSet.add(word.substring(j, i));
}
return hashSet.size();
}
}
学习笔记： 这道题是简单题。 但是我觉得差不多有中等了，主要就是用双指针算法。 双指针切割字符串，存入集合可以去重算出数量。 麻烦的就是前导零，我本来打算是转int存set，发现不行。后来用long存set，竟然还是不行，里面有很长很离谱的数字。 好吧，最后就干存string了只好，但是得跑一下左指针把前导零去掉。
import java.util.ArrayDeque;
import java.util.Deque;
// 1687. Delivering Boxes from Storage to Ports
class Solution {
public int boxDelivering(int[][] boxes, int portsCount, int maxBoxes, int maxWeight) {
int n = boxes.length;
int[] ports = new int[n + 1];
int[] weight = new int[n + 1];
int[] neg = new int[n + 1];
long[] weightPrefixSums = new long[n + 1];
for (int i = 1; i <= n; ++i) {
ports[i] = boxes[i - 1][0];
weight[i] = boxes[i - 1][1];
if (i > 1) {
if (ports[i - 1] != ports[i]) {
neg[i] = neg[i - 1] + 1;
} else {
neg[i] = neg[i - 1];
}
}
weightPrefixSums[i] = weightPrefixSums[i - 1] + weight[i];
}
Deque<Integer> opt = new ArrayDeque<>();
opt.offerLast(0);
int[] minTrips = new int[n + 1];
int[] increment = new int[n + 1];
for (int i = 1; i <= n; ++i) {
while (i - opt.peekFirst() > maxBoxes || weightPrefixSums[i] - weightPrefixSums[opt.peekFirst()] > maxWeight) {
opt.pollFirst();
}
minTrips[i] = increment[opt.peekFirst()] + neg[i] + 2;
if (i != n) {
increment[i] = minTrips[i] - neg[i + 1];
while (!opt.isEmpty() && increment[i] <= increment[opt.peekLast()]) {
opt.pollLast();
}
opt.offerLast(i);
}
}
return minTrips[n];
}
}
学习笔记： 这是一道超级无敌困难的题目。 用到了单调栈，动态规划的点。我一开始怎么都想不出，看了官方题解和好几个题解自后终于慢慢从官方题解演算出过程来。真的太难了，没想到在我生日出这样的题目来刁难我。
// 1774. Closest Dessert Cost
class Solution {
int ans = Integer.MAX_VALUE;
int minDistanceToTarget = Integer.MAX_VALUE;
public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
for (int baseCost : baseCosts) {
addTopping(baseCost, 0, toppingCosts, target);
}
return ans;
}
private void addTopping(int cost, int index, int[] toppingCosts, int target) {
int distanceToTarget = Math.abs(cost - target);
if (distanceToTarget < minDistanceToTarget) {
ans = cost;
minDistanceToTarget = distanceToTarget;
} else if (distanceToTarget == minDistanceToTarget) {
if (cost < ans) {
ans = cost;
}
}
if (cost > target || index >= toppingCosts.length) {
return;
}
addTopping(cost, index + 1, toppingCosts, target);
addTopping(cost + toppingCosts[index], index + 1, toppingCosts, target);
addTopping(cost + toppingCosts[index] * 2, index + 1, toppingCosts, target);
}
}
学习笔记： 这是一道又去的题目，制作冰激凌。 用到了深度优先搜索，每一种配料就三种情况，不加，加一份，加两份。 就看最终价格最逼近的情况就可以了。
// 1796. Second Largest Digit in a String
class Solution {
public int secondHighest(String s) {
char[] charArray = s.toCharArray();
int len = charArray.length;
boolean[] digits = new boolean[10];
for (char c : charArray) {
if (c > 47 && c < 58) {
digits[c - 48] = true;
}
}
int kinds = 0;
for (int i = 9; i >= 0; --i) {
if (digits[i]) {
++kinds;
if (kinds == 2) {
return i;
}
}
}
return -1;
}
}
学习笔记： 这是一道简单的题目。 统计一下所有的数字是否有出现，然后找出第二大的种类，我选择建boolean数组然后从9开始遍历。
// 1769. Minimum Number of Operations to Move All Balls to Each Box
class Solution {
public int[] minOperations(String boxes) {
char[] charArray = boxes.toCharArray();
int n = charArray.length;
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
int c = charArray[i] - 48;
for (int j = 0; j < n; ++j) {
ans[j] += Math.abs(i - j) * c;
}
}
return ans;
}
}
学习笔记： 这是一道中等题，也没啥特别的算法分类。 这道题似乎没有啥特别的难点，就是双重循环计算然后把结果返回。