1046. Last Stone Weight
We have a collection of rocks, each rock has a positive integer weight.
Each turn, we choose the two heaviest rocks and smash them together. Suppose the stones have weights
xandywithx <= y. The result of this smash is:
- If
x == y, both stones are totally destroyed;- If
x != y, the stone of weightxis totally destroyed, and the stone of weightyhas new weighty-x.At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)
Example 1:
Input: [2,7,4,1,8,1] Output: 1 Explanation: We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then, we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then, we combine 2 and 1 to get 1 so the array converts to [1,1,1] then, we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.
Note:
1 <= stones.length <= 301 <= stones[i] <= 1000
Approach #1: Brute Force. [Java]
class Solution {
public int lastStoneWeight(int[] stones) {
Comparator c = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if((int)o1<(int)o2)
return 1;
else return -1;
}
};
List<Integer> list = new ArrayList<Integer>();
for (int s : stones) list.add(s);
while (list.size() >= 2) {
list.sort(c);
int num1 = list.get(0);
int num2 = list.get(1);
list.remove(0);
list.remove(0);
if (num1 > num2) list.add(num1 - num2);
}
return list.isEmpty() ? 0 : list.get(0);
}
}
1047. Remove All Adjacent Duplicates In String
Given a string
Sof lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.We repeatedly make duplicate removals on S until we no longer can.
Return the final string after all such duplicate removals have been made. It is guaranteed the answer is unique.
Example 1:
Input: "abbaca" Output: "ca" Explanation: For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".
Note:
1 <= S.length <= 20000Sconsists only of English lowercase letters.
Approach #1: Brute Force. [Java]
class Solution {
public String removeDuplicates(String S) {
List<Character> list = new ArrayList<>();
for (int i = 0; i < S.length(); ++i) {
if (i < S.length() - 1 && S.charAt(i) == S.charAt(i+1)) {
i++;
continue;
}
list.add(S.charAt(i));
}
while (haveDuplicates(list)) {
}
String ret = "";
for (int i = 0; i < list.size(); ++i)
ret += list.get(i);
return ret;
}
public boolean haveDuplicates(List<Character> list) {
for (int i = 1; i < list.size(); ++i) {
if (list.get(i) == list.get(i-1)) {
list.remove(i);
list.remove(i-1);
return true;
}
}
return false;
}
}
1048. Longest String Chain
Given a list of words, each word consists of English lowercase letters.
Let's say
word1is a predecessor ofword2if and only if we can add exactly one letter anywhere inword1to make it equal toword2. For example,"abc"is a predecessor of"abac".A word chain is a sequence of words
[word_1, word_2, ..., word_k]withk >= 1, whereword_1is a predecessor ofword_2,word_2is a predecessor ofword_3, and so on.Return the longest possible length of a word chain with words chosen from the given list of
words.
Example 1:
Input: ["a","b","ba","bca","bda","bdca"] Output: 4 Explanation: one of the longest word chain is "a","ba","bda","bdca".
Note:
1 <= words.length <= 10001 <= words[i].length <= 16words[i]only consists of English lowercase letters.
Approach #1: HashMap + DP. [Java]
class Solution {
public int longestStrChain(String[] words) {
if (words == null || words.length == 0) return 0;
int ans = 0;
Map<String, Integer> map = new HashMap<>();
Arrays.sort(words, new Comparator<String>() {
public int compare(String str1, String str2) {
return str1.length() - str2.length();
}
});
for (String word : words) {
if (map.containsKey(word)) continue;
map.put(word, 1);
for (int i = 0; i < word.length(); ++i) {
StringBuilder sb = new StringBuilder(word);
sb.deleteCharAt(i);
String next = sb.toString();
if (map.containsKey(next) && map.get(next) + 1 > map.get(word)) {
map.put(word, map.get(next) + 1);
}
}
if (map.get(word) > ans) ans = map.get(word);
}
return ans;
}
}
1049. Last Stone Weight II
We have a collection of rocks, each rock has a positive integer weight.
Each turn, we choose any two rocks and smash them together. Suppose the stones have weights
xandywithx <= y. The result of this smash is:
- If
x == y, both stones are totally destroyed;- If
x != y, the stone of weightxis totally destroyed, and the stone of weightyhas new weighty-x.At the end, there is at most 1 stone left. Return the smallest possible weight of this stone (the weight is 0 if there are no stones left.)
Example 1:
Input: [2,7,4,1,8,1] Output: 1 Explanation: We can combine 2 and 4 to get 2 so the array converts to [2,7,1,8,1] then, we can combine 7 and 8 to get 1 so the array converts to [2,1,1,1] then, we can combine 2 and 1 to get 1 so the array converts to [1,1,1] then, we can combine 1 and 1 to get 0 so the array converts to [1] then that's the optimal value.
Note:
1 <= stones.length <= 301 <= stones[i] <= 100
Approach #1: DP. [Java]
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
int n = stones.length;
for (int stone : stones)
sum += stone;
int total_sum = sum;
sum /= 2;
boolean[][] dp = new boolean[sum+1][n+1];
for (int i = 0; i <= n; ++i)
dp[0][i] = true;
int max = Integer.MIN_VALUE;
for (int i = 1; i <= sum; ++i) {
for (int j = 1; j <= n; ++j) {
if (dp[i][j-1] == true || (i >= stones[j-1] && dp[i-stones[j-1]][j-1])) {
dp[i][j] = true;
max = Math.max(max, i);
}
}
}
return total_sum - max * 2;
}
}
Reference: