t1.统计包含给定前缀的字符串
题目描述思路
模拟
Python实现Java实现 t2.使两字符串互为字母异位词的最少步骤数
题目描述思路
统计
Python实现Java实现 t3.完成旅途的最少时间
题目描述思路
二分查找
Python实现Java实现 t4.完成比赛的最少时间
题目描述思路
动态规划
Python实现Java实现
t1.统计包含给定前缀的字符串 题目描述
统计包含给定前缀的字符串
思路 模拟根据题意模拟即可。
Python实现class Solution:
def prefixCount(self, words: List[str], pref: str) -> int:
ans = 0
for word in words:
if word.startswith(pref):
ans += 1
return ans
Java实现
class Solution {
public int prefixCount(String[] words, String pref) {
int ans = 0;
for (String word : words) {
if (word.startsWith(pref)) {
ans += 1;
}
}
return ans;
}
}
t2.使两字符串互为字母异位词的最少步骤数 题目描述
使两字符串互为字母异位词的最少步骤数
思路 统计统计两个字符串各个字母出现个数，做差找出两个字符串之间的差别即可。
Python实现class Solution:
def minSteps(self, s: str, t: str) -> int:
cnt1, cnt2 = Counter(s), Counter(t)
cnt1.subtract(cnt2)
ans = 0
for key, value in cnt1.items():
ans += abs(value)
return ans
Java实现
class Solution {
public int minSteps(String s, String t) {
Map sMap = new HashMap<>();
Map tMap = new HashMap<>();
for (char c : s.toCharArray()){
sMap.put(c,sMap.getOrDefault(c,0)+1);
}
for (char c : t.toCharArray()){
tMap.put(c,tMap.getOrDefault(c,0)+1);
}
int res = 0 ;
for (char c:sMap.keySet()){
if (tMap.containsKey(c) && tMap.get(c).equals(sMap.get(c)))continue;
if (!tMap.containsKey(c)){
tMap.put(c,sMap.get(c));
res+=sMap.get(c);
}
if (tMap.containsKey(c)){
res += Math.abs(tMap.get(c) - sMap.get(c));
}
}
for (char c : tMap.keySet()){
if (!sMap.containsKey(c)){
sMap.put(c,tMap.get(c));
res+=tMap.get(c);
}
}
return res;
}
}
t3.完成旅途的最少时间 题目描述
完成旅途的最少时间
思路 二分查找
使用二分法，对完成至少totalTrips旅途所需要花费的最少时间进行枚举。
二分查找的上下界分别为min(time)和min(time)*totalTrips。
class Solution:
def minimumTime(self, time: List[int], totalTrips: int) -> int:
l, r = min(time), min(time)*totalTrips
while l < r:
mid = l + (r-l) // 2
total = 0
for t in time:
total += mid // t
if total >= totalTrips:
r = mid
else:
l = mid+1
return l
Java实现
class Solution {
public long minimumTime(int[] time, int totalTrips) {
Arrays.sort(time);
long l = time[0], r = 1L*time[0]*totalTrips;
while (l < r) {
long mid = l + (r-l) / 2;
long trip = 0;
for (int t : time) {
if (mid < t) {
break;
}
trip += mid / t;
}
if (trip >= totalTrips) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}
t4.完成比赛的最少时间 题目描述
完成比赛的最少时间
思路 动态规划
根据题意，连续使用同一个轮胎耗时是指数增长的，且每种轮胎都有无数个，所以连续使用同一个轮胎i跑x圈，则第x圈的耗时不用超过changeTime+fi，否则直接更换轮胎更好。
所以动态规划上界为changeTime+fi，即
f
i
∗
r
i
(
x
−
1
)
<
=
c
h
a
n
g
e
T
i
m
e
+
f
i
fi*ri^(x-1) <= changeTime+fi
fi∗ri(x−1)<=changeTime+fi。
具体实现时，先预处理出连续使用同一个轮胎跑x圈的最小耗时，记为minSec[x]，可以通过遍历每个轮胎计算出来。然后定义f[i]表示跑i圈的最小耗时。为方便计算，初始值f[0]=-changeTime。最后一个轮胎连续跑j圈，可以从f[i-j]转移过来。
class Solution:
def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
minSec = [float("inf")] * 18
for f, r in tires:
x, time, sum = 1, f, 0
while time <= changeTime + f:
sum += time
minSec[x] = min(minSec[x], sum)
time *= r
x += 1
f = [0] * (numLaps + 1)
f[0] = -changeTime
for i in range(1, numLaps+1):
f[i] = changeTime + min(f[i-j] + minSec[j] for j in range(1, min(18, i+1)))
return f[numLaps]
Java实现
class Solution {
public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
List[] bestLap = new List[tires.length];
int maxLap = 0;
for (int i = 0; i < tires.length; ++i) {
int f = tires[i][0], r = tires[i][1];
int maxTime = f + changeTime;
int t = f, cost = f;
bestLap[i] = new ArrayList<>();
bestLap[i].add(cost);
while ((t *= r) < maxTime) {
cost += t;
bestLap[i].add(cost);
}
maxLap = Math.max(maxLap, bestLap[i].size());
}
int[] dp = new int[numLaps + 1];
for (int i = 1; i < numLaps + 1; ++i) {
int minTime = Integer.MAX_VALUE;
if (i <= maxLap) {//全程不用换胎
for (List oneTire : bestLap) {
if (i <= oneTire.size()) minTime = Math.min(minTime, oneTire.get(i - 1));
}
}
for (int j = 1; j < i; j++) {
minTime = Math.min(minTime, dp[j] + dp[i - j] + changeTime);
}
dp[i] = minTime;
}
return dp[numLaps];
}
}
