leetcode137Contest

  1. Last Stone Weight3
  2. Remove All Adjacent Duplicates In String4
  3. Longest String Chain6
  4. Last Stone Weight II

1. Last Stone Weight3

a collection of rocks with each one has positive weight. Each turn, we choose two heaviest rocks and smash them together.
logic：
sort them in increase order, and push back the last two elements, and smash and push the remain back to the vector.

solution：

1
2
3
4
5
6
7
8
9
10
11
12
public: 
	int lastStoneWeight(vector<int>& a){
		while(a.size()>1){
			sort(a.begin(), a.end());
			int n = a.size();
			int x = a[n-1] - a[n-2];
			a.pop_back();
			a.pop_back();
			a.push_back(x);
		}
		return a[0];
	}

2. Remove All Adjacent Duplicates In String4

Given a String S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.
Repeatly doing the removement until we no longer can. return the final string.

example: inputs: “abbaca”
outputs: “ca”
Solution Logic: using stack, check the top of the stack, if equal to current element, then pop it out.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public:
	string removeDuplicates(string S){
		vector<char> a;
		for(auto& c: S){
			if(a.size() && a.back()==c){
				a.pop_back();
			}else{
				a.push_back(c);
			}
		}
		string ret;
		for(auto& it: a) ret += it;
		return ret;
	}

3. Longest String Chain6

Given a list of words, each word consists of English lowercase letters.
Let’s say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, “abc” is a predecessor of “abac”.
Return the longest possible length of a word chain with words chosen from the given list of words.
Example 1:

1
2
3
Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".

Solution:
Per inolving in state transfer: Dynamic programming is needed.
sort the word based on the length; then loop through all the possible string by missing one letter. if one string got seen before, we update the longest chain for current string.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class solution{
	//static attached to class
	static bool compare(const string &s1, const string &s2){
		return s1.length() < s2.length();
	}
public:
	int longestStrChain(vector<string>& words){
		sort(words.begin(), words.end(), compare);
		unordered_map<string,int> dp;
		for(string w: words){
			int max_idx = 0;
			for(int i = 0; i < w.length(); i++){
				string word = w.substr(0, i) + w.substr(i+1);
				max_idx = max(max_idx, dp[word]+1);
			}
			dp[w] = max_index;
		}
		int result = 0;
		for(auto m: dp){
			result  = max(result, m.second);
		}
		return result;
	}
}

4. Last Stone Weight II

Follow up of the first one: not the biggest two stones anymore, but the smash strategy become:

1
2
3
4
5
Each turn, we choose any two rocks and smash them together.  
Suppose the stones have weights x and y with x <= y.  The result of this smash is:

If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

So, there are a lot of choices! ===> Knapsacks problem!

###Tips: Think in the way of real scenarios, and how you get it done first.
Then connect the logic with data structure and algorithm.