【NO.1 查看字符串是否为数组前缀】
解题思路
签到题，暴力连贯字符串查看是否相等即可。
代码展现
class Solution {
public boolean isPrefixString(String s, String[] words) {
String t = "";
for (var word : words) {
t += word;
if (s.equals(t)) {return true;}
}
return false;}
}
【NO.2 移除石子使总数最小】
解题思路
贪婪，每次移除最多的那一堆。
代码展现
class Solution {
public int minStoneSum(int[] piles, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> (b - a));
for (int p : piles) {heap.add(p);
}
for (int i = 0; i < k; i++) {heap.add((heap.poll() + 1) / 2);
}
return heap.stream().mapToInt(a -> a).sum();}
}
【NO.3 使字符串均衡的最小替换次数】
解题思路
统计出有多少不匹配的括号对，即没有左括号匹配的右括号。每次替换都能缩小 2 个不匹配的括号对。
代码展现
class Solution {
public int minSwaps(String s) {
int count = 0;
int left = 0;
for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '[') {left++;} else if (left != 0) {left--;} else {count++;}
}
return (count + 1) / 2;}
}
【NO.4 找出到每个地位为止最长的无效障碍赛跑路线】
解题思路
nlogn 的 LIS 算法，应用二分查找来优化 dp 递推过程，定义 dp[i] 示意长度为 i 的 LIS 的结尾最小值是多少，在 dp 上二分查找即可。
代码展现
class Solution {
int binarySearch(int[] v, int r, int key) {
int l = 0;
while (r - l > 1) {int m = (l + r) / 2;
if (v[m] <= key)
l = m;
else
r = m;
}
return v[r] <= key ? r : l;}
public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
int[] dp = new int[obstacles.length];
int[] result = new int[obstacles.length];
result[0] = 1;
dp[0] = obstacles[0];
int length = 1;
for (int i = 1; i < obstacles.length; i++) {if (obstacles[i] < dp[0]) {dp[0] = obstacles[i];
result[i] = 1;
} else if (obstacles[i] >= dp[length - 1]) {dp[length++] = obstacles[i];
result[i] = length;
} else {int idx = binarySearch(dp, length - 1, obstacles[i]);
dp[idx + 1] = Math.min(obstacles[i], dp[idx + 1]);
result[i] = idx + 2;
}
}
return result;}
}
杭州上岸算法网络科技有限公司
上岸算法网络科技有限公司是一家致力于用高质量，高互动性小班课程来帮忙学生更好的在待业市场中定位以及求职的公司。咱们以顶级的课程品质，高互动性的教学方式以及独特的小班教学模式来帮忙学生更快的跨过求职的鸿沟，用最高效，经济，正当的形式帮忙更多学生疾速找到梦寐以求的工作。