上岸算法 I LeetCode Weekly Contest 242解题报告
本帖最后由 上岸算法 于 2021-5-25 23:25 编辑No.1 哪种连续子字符串更长解题思路签到题。代码展示class Solution {
public boolean checkZeroOnes(String s) {
return check(s, '1') > check(s, '0');
}
private int check(String s, char c) {
int result = 0, count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == c) {
count++;
result = Math.max(result, count);
} else {
count = 0;
}
}
return result;
}
}
秋招将近，华大学长/斯坦福学姐联合组织了一场面向北美2021秋招的算法带刷公益活动。带刷内容源于Leetcode 原题/近期大厂算法面试真题。模拟面试+面试技巧分享，备战秋招！只要你熟练掌握一门计算机语言，比如：java/ python 等，即可免费参与本次刷题活动。https://seattler.io/upload/attach/202105/2021_05_26_13_57_50_68308活动时间：2021/6/1-2021/6/25No.2 准时到达的列车最小时速解题思路二分答案。对于给定车速计算通勤总耗时的时候，建议仅在最后一次运算使用浮点运算，其他均使用整型向上取整的除法。代码展示class Solution {
public int minSpeedOnTime(int[] dist, double hour) {
if (!check(dist, hour, (int) (1e7 + 1))) {
return -1;
}
int left = 1, right = (int) 1e7;
while (left + 1 < right) {
int mid = (left + right) / 2;
if (check(dist, hour, mid)) {
right = mid;
} else {
left = mid;
}
}
return check(dist, hour, left) ? left : right;
}
private boolean check(int[] dist, double hour, int speed) {
int cost = 0;
for (int i = 0; i < dist.length - 1; i++) {
cost += (dist + speed - 1) / speed;
}
return hour >= (double) cost + (1.0 * dist / speed);
}
}
No.3 跳跃游戏 VII解题思路类似于滑动窗口，使用队列维护可以跳跃到当前点的点集合。代码展示class Solution {
public boolean canReach(String s, int minJump, int maxJump) {
int n = s.length();
char[] str = s.toCharArray();
if (str == '1') {
return false;
}
LinkedList<Integer> queue = new LinkedList<>();
queue.add(0);
for (int i = 1; i < str.length; i++) {
while (!queue.isEmpty() && queue.getFirst() + maxJump < i) {
queue.pollFirst();
}
if (!queue.isEmpty() && str == '0' && queue.getFirst() + minJump <= i) {
if (i == str.length - 1) {
return true;
}
queue.add(i);
}
}
return false;
}
}No.4 石子游戏 VIII解题思路看似每次要重新放回去一个总和石子很复杂，但其实恰相反：放回去的石子必然被对手拿到，因此抵消了自己拿到的和。代码展示class Solution {
public int stoneGameVIII(int[] stones) {
int n = stones.length;
long[] sum = new long;
sum = stones;
for (int i = 1; i < n; i++) {
sum = sum + stones;
}
long[] dp = new long;
dp = sum;
long max = dp;
for (int i = n - 2; i > 0; i--) {
dp = sum - max;
max = Math.max(max, dp);
}
return (int) max;
}
}
页:
[1]