If you sort the array and just walk through it and update the min distance along the way then it passed all test cases.
public static long carParkingRoof(List<Long> cars, int k) {
// Write your code here
if (cars.size() == 0 || k < 0) {
return 0;
}
Collections.sort(cars);
long minDist = Long.MAX_VALUE;
for (int i = 0; i <= cars.size() - k; i++) {
minDist = Math.min(minDist, cars.get(i + k - 1) - cars.get(i));
}
return minDist + 1;
}
I passed 12/14 test cases. The failing 2 say “Your code did not execute within the time limits”. Is there a way to optimize my code?
Thanks!
What I’m doing is basically expanding left and right from current character until I find the same character, and get its index. I always go left first because you want the smaller index. Unless your current index is the smallest then you go right.
public static List<Integer> closest(String s, List<Integer> queries) {
// Write your code here
List<Integer> result = new ArrayList<Integer>();
if (queries.size() == 0) {
return result;
}
char[] strToChar = s.toCharArray();
for(int i = 0; i < queries.size(); i++) {
int currIndx = queries.get(i); // target character index
if (currIndx < 0 || currIndx >= strToChar.length) { // invalid index from query
result.add(-1);
continue;
}
char c = strToChar[queries.get(i)];
int checkAway = 1;
boolean found = false;
// check left and right from current index and find closest index of same character
while(currIndx - checkAway >= 0 || currIndx + checkAway < strToChar.length) {
int moveLeft = currIndx - checkAway;
int moveRight = currIndx + checkAway;
if(moveLeft >=0 && c == strToChar[moveLeft]){
result.add(moveLeft);
found = true;
break;
} else if(moveRight < strToChar.length && strToChar[moveRight] == c){
result.add(moveRight);
found = true;
break;
}
checkAway++;
}
if(!found){
result.add(-1);
}
}
return result;
}
可以看下 https://leetcode.com/problems/shortest-distance-to-target-color/
public static List<Integer> closest(String s, List<Integer> queries) {
Map<Character, List<Integer>> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
map.computeIfAbsent(s.charAt(i), (k) -> new ArrayList<>()).add(i);
}
List<Integer> result = new ArrayList<>(queries.size());
for (int query : queries) {
List<Integer> indexes = map.getOrDefault(s.charAt(query), Collections.emptyList());
result.add(binarySearch(indexes, query));
}
return result;
}