目录
一、周赛战况
? ? ? ? 前2题半个小时，第三题由于未考虑精度的问题，卡了好久，超时未解出来，后续给补上了。
二、题目列表
一共4道题，分值对应是3,4,5,6，由易到难。
1.? 字母在字符串中的百分比(简单)
给你一个字符串?s?和一个字符?letter?，返回在?s?中等于?letter?字符所占的?百分比?，向下取整到最接近的百分比。
示例 1：
输入：s = "foobar", letter = "o" 输出：33 解释： 等于字母 'o' 的字符在 s 中占到的百分比是 2 / 6 * 100% = 33% ，向下取整，所以返回 33 。示例 2：
输入：s = "jjjj", letter = "k" 输出：0 解释： 等于字母 'k' 的字符在 s 中占到的百分比是 0% ，所以返回 0 。提示：
1 <= s.length <= 100s?由小写英文字母组成letter?是一个小写英文字母
解题思路
? ? ? ? 1) 找出有多少个与letter字符相同的字符。
? ? ? ? 2) 计算百分比时乘以100。
完整代码
package leetcode100.weeks.date20220522;
public class PercentageLetter6074 {
public int percentageLetter(String s, char letter) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == letter) {
count++;
}
}
return count * 100 / s.length();
}
public static void main(String[] args) {
PercentageLetter6074 percentageLetter6074 = new PercentageLetter6074();
int result = percentageLetter6074.percentageLetter("12412321", '1');
System.out.println("result=" + result);
}
}
时间复杂度与空间复杂度
? ? ? ? 时间复杂度为O(N)，空间复杂度为O(1)。
2. 装满石头的背包最大数量(中等)
????????现有编号从?0?到?n - 1?的?n?个背包。给你两个下标从?0?开始的整数数组?capacity?和?rocks?。第?i?个背包最大可以装?capacity[i]?块石头，当前已经装了?rocks[i]?块石头。另给你一个整数?additionalRocks?，表示你可以放置的额外石头数量，石头可以往 任意 背包中放置。
请你将额外的石头放入一些背包中，并返回放置后装满石头的背包的?最大?数量。
示例 1：
输入：capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2 输出：3 解释： 1 块石头放入背包 0 ，1 块石头放入背包 1 。 每个背包中的石头总数是 [2,3,4,4] 。 背包 0 、背包 1 和 背包 2 都装满石头。 总计 3 个背包装满石头，所以返回 3 。 可以证明不存在超过 3 个背包装满石头的情况。 注意，可能存在其他放置石头的方案同样能够得到 3 这个结果。示例 2：
输入：capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100 输出：3 解释： 8 块石头放入背包 0 ，2 块石头放入背包 2 。 每个背包中的石头总数是 [10,2,2] 。 背包 0 、背包 1 和背包 2 都装满石头。 总计 3 个背包装满石头，所以返回 3 。 可以证明不存在超过 3 个背包装满石头的情况。 注意，不必用完所有的额外石头。
解题思路
? ? ? ? 1)? 先计算出每个背包中的剩余容量，这样能知道哪些背包已经满了，哪些背包还能继续放。
int[] leftCapacity = new int[capacity.length];
for (int i = 0; i < capacity.length; i++) {
leftCapacity[i] = capacity[i] - rocks[i];
}
Arrays.sort(leftCapacity);? ? ? ? 2)? 将背包的剩余容量从大到小进行排序，这样在装填的时候从差的最少的背包来放。
? ? ? ? 3)? 依次按照剩余容量的大小进行装填，装满了继续装下一个，这样就能达到最大装填数。
? ? ? ? 4)? 如果当前背包的剩余容量大于可用的石头数，那么表示再也填不满一个背包了。
for (int j = 0; j < leftCapacity.length; j++) {
if (leftCapacity[j] == 0) {
//如果满了
maxNum++;
continue;
}
// 开始放石头
if (leftCapacity[j] > additionalRocks) {
// 没有多余的石头够放一个背包了。
break;
} else {
additionalRocks -= leftCapacity[j];
maxNum++;
}
}完整代码
package leetcode100.weeks.date20220522;
import java.util.Arrays;
public class MaximumBags6075 {
/**
* @param capacity 各背包的容量
* @param rocks 已经装了多少个
* @param additionalRocks 还有多少个石头
* @return
*/
public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
int maxNum = 0;
// 剩余背包容量排序
int[] leftCapacity = new int[capacity.length];
for (int i = 0; i < capacity.length; i++) {
leftCapacity[i] = capacity[i] - rocks[i];
}
Arrays.sort(leftCapacity);
for (int j = 0; j < leftCapacity.length; j++) {
if (leftCapacity[j] == 0) {
//如果满了
maxNum++;
continue;
}
// 开始放石头
if (leftCapacity[j] > additionalRocks) {
// 没有多余的石头够放一个背包了。
break;
} else {
additionalRocks -= leftCapacity[j];
maxNum++;
}
}
return maxNum;
}
public static void main(String[] args) {
MaximumBags6075 maximumBags6075 = new MaximumBags6075();
int[] capacity = {3, 5, 6, 8};
int[] rocks = {1, 1, 1, 1};
int additionalRock = 2;
int maxPackage = maximumBags6075.maximumBags(capacity, rocks, additionalRock);
System.out.println("最大背包数量: " + maxPackage);
}
}
时间复杂度与空间复杂度
? ? ? ? 时间复杂度为O(N)，空间复杂度为O(1)。
3. 表示一个折线图的最少线段数
????????给你一个二维整数数组?stockPrices?，其中?stockPrices[i] = [dayi, pricei]?表示股票在?dayi?的价格为?pricei?。折线图?是一个二维平面上的若干个点组成的图，横坐标表示日期，纵坐标表示价格，折线图由相邻的点连接而成。比方说下图是一个例子：
请你返回要表示一个折线图所需要的?最少线段数?。
示例 1：
输入：stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]] 输出：3 解释： 上图为输入对应的图，横坐标表示日期，纵坐标表示价格。 以下 3 个线段可以表示折线图： - 线段 1 （红色）从 (1,7) 到 (4,4) ，经过 (1,7) ，(2,6) ，(3,5) 和 (4,4) 。 - 线段 2 （蓝色）从 (4,4) 到 (5,4) 。 - 线段 3 （绿色）从 (5,4) 到 (8,1) ，经过 (5,4) ，(6,3) ，(7,2) 和 (8,1) 。 可以证明，无法用少于 3 条线段表示这个折线图。
示例 2：
输入：stockPrices = [[3,4],[1,2],[7,8],[2,3]] 输出：1 解释： 如上图所示，折线图可以用一条线段表示。
提示：
1 <= stockPrices.length <= 105stockPrices[i].length == 21 <= dayi, pricei?<= 109- 所有?
dayi?互不相同?。
题目链接：?https://leetcode.cn/contest/weekly-contest-294/problems/minimum-lines-to-represent-a-line-chart/
解题思路?
? ? ? ? 1)? 题目要求我们判断三点是否在一条直线上，如果不是，那么线段数+1。
? ? ? ? 2)? 节点之间两两判断斜率是否相等，即判断(x1-x2)/(y1-y2)==(x1-x3)/(y1-y3)是否成立;
踩坑指南
? ? ? ? 1)? 定先要将二维数组中的x坐标先按照大小进行排序，如果不排序，那么可能会出现会"回连"的情况，就不符合题意。
? ? ? ? 2)? 不要用除法!!! 除法会有精度问题，用double玩了半天，发现还是有精度问题，最后换成了乘法，用long类型就不会有问题了!!!
完整代码
package leetcode100.weeks.date20220522;
import java.util.Arrays;
import java.util.Comparator;
public class MinimumLines6076 {
/**
* 设点A（x1，y1），B（x2，y2），C（x3，y3）
* <p>
* 要判断三点共线，只需证明斜率相等即可。
* <p>
* 即：(x1y2-x2y1)+(x2y3-x3y2)+(x3y1-y3x1)==0
*
* @param stockPrices
* @return
*/
public int minimumLines(int[][] stockPrices) {
if (stockPrices.length <= 2) {
return Math.abs(stockPrices.length - 1);
}
int result = 1;
// 先按照大小排序一下，要不然连线的时候会出现“回连”的情况
Arrays.sort(stockPrices, Comparator.comparingInt(o -> o[0]));
//在一条线上
Point p1 = new Point(stockPrices[0]);
Point p2 = new Point(stockPrices[1]);
for (int i = 2; i < stockPrices.length; i++) {
Point p3 = new Point(stockPrices[i]);
// 判断point2节点是否和前面的节点成一条线
long r1 = (p3.y - p1.y) * (p2.x - p1.x);
long r2 = (p2.y - p1.y) * (p3.x - p1.x);
if (r1 != r2) {
// 如果不在，那么就数量+1
//不在一条直线上
result++;
System.out.println("不相等: " + r1 + "," + r2);
} else {
System.out.println("相等: " + r1 + "," + r2);
}
p1 = new Point(stockPrices[i - 1]);
p2 = new Point(stockPrices[i]);
}
return result;
}
class Point {
long x;
long y;
public Point(int[] stockPrice) {
this.x = stockPrice[0];
this.y = stockPrice[1];
}
public long getX() {
return x;
}
public void setX(long x) {
this.x = x;
}
public long getY() {
return y;
}
public void setY(long y) {
this.y = y;
}
}
public static void main(String[] args) {
MinimumLines6076 minimumLines6076 = new MinimumLines6076();
String arr = "[[72,98],[62,27],[32,7],[71,4],[25,19],[91,30],[52,73],[10,9],[99,71],[47,22],[19,30],[80,63],[18,15],[48,17],[77,16],[46,27],[66,87],[55,84],[65,38],[30,9],[50,42],[100,60],[75,73],[98,53],[22,80],[41,61],[37,47],[95,8],[51,81],[78,79],[57,95]]";
int[][] stockPrices = new int[][]{{72, 98}, {62, 27}, {32, 7}, {71, 4}, {25, 19}, {91, 30}, {52, 73}, {10, 9}, {99, 71}, {47, 22}, {19, 30}, {80, 63}, {18, 15}, {48, 17}, {77, 16}, {46, 27}, {66, 87}, {55, 84}, {65, 38}, {30, 9}, {50, 42}, {100, 60}, {75, 73}, {98, 53}, {22, 80}, {41, 61}, {37, 47}, {95, 8}, {51, 81}, {78, 79}, {57, 95}};
// int[][] stockPrices = new int[][]{{1, 1}, {500000000, 499999999}, {1000000000, 999999998}};
int result = minimumLines6076.minimumLines(stockPrices);
System.out.println(result);
}
}
时间复杂度和空间复杂度?
? ? ? ? 时间复杂度为O(N), 空间复杂度为O(1)。
