leetcode 953. Verifying an Alien Dictionary
class Solution {
public boolean isAlienSorted(String[] words, String order) {
int[] o = new int[26];
for (int i = 0; i < order.length(); ++i) {
o[order.charAt(i) - 'a'] = i;
}
for (int i = 0; i < words.length - 1; ++i) {
if (!inOrder(words[i], words[i + 1], o)) return false;
}
return true;
}
public boolean inOrder(String s1, String s2, int[] order) {
for (int i = 0; i < s1.length() && i < s2.length(); ++i) {
int l1 = order[s1.charAt(i) - 'a'];
int l2 = order[s2.charAt(i) - 'a'];
if (l1 > l2) return false;
else if (l1 < l2) return true;
}
if (s1.length() > s2.length()) return false;
else return true;
}
}
949. Largest Time for Given Digits
class Solution {
public String largestTimeFromDigits(int[] A) {
String ret = "";
int time = 0;
for (int i = 0; i < A.length; ++i) {
if (A[i] > 2) continue;
for (int j = 0; j < A.length; ++j) {
if (j != i) {
if (A[i] == 2 && A[j] > 3) continue;
for (int m = 0; m < A.length; ++m) {
if (m != i && m != j) {
if (A[m] > 5) continue;
int idx = 6 - i - j - m;
int t = (A[i] * 10 + A[j]) * 60 + (10 * A[m] + A[idx]);
if (t >= time) {
time = t;
ret = String.format("%02d:%02d", A[i] * 10 + A[j], 10 *A[m] + A[idx]);
}
}
}
}
}
}
return ret;
}
}
948. Bag of Tokens
Greedy solution:
Sort tokens first.
At each loop, first try to gain as many points as possible from the left of token array. In this way, points are gained with least points possibly.
Then exchange power using 1 point from the right of token array. In this way, we can get largest amount of power with 1 point. and continue to step 2 if possible.
class Solution {
public int bagOfTokensScore(int[] tokens, int P) {
Arrays.sort(tokens);
if (tokens.length == 0 || P < tokens[0]) return 0;
int l = 0, r = tokens.length - 1;
int ret = 0;
int c = 0;
while (l <= r) {
while (l <= r && P >= tokens[l]) {
c += 1;
ret = Math.max(ret, c);
P -= tokens[l];
l += 1;
}
//until cannot trade, gain power with least point and try again in next loop
if (r >= l && c > 0) {
P += tokens[r];
r -= 1;
c -= 1;
}
}
return ret;
}
}