- 312 Burst Balloons
输入：int数组
输出：int
题意：扎气球，最终得到的分数最大，每扎一个气球，得到的分数时该气球和旁边两个气球三个数字的乘积。
思路：分治法来进行动态规划。值得注意的是，动态规划中经常用到的从反方向来思考问题在这儿用到了。分治策略：因为最终得到的分数不受已经爆掉的气球的影响，因此我们按照最后爆掉的气球来进行情况划分。
class Solution {
public:
int maxCoins(vector<int>& nums) {
vector<int> ns;
ns.push_back(1);
for(auto a : nums) if(a > 0) ns.push_back(a);
ns.push_back(1);
int size = ns.size();
vector<vector<int>> dp(size + 1, vector<int>(size + 1, 0));
for(int k = 2;k < size;++ k){
for(int left = 0;left < size - k;++ left){
int right = left + k;
for(int i = left + 1;i < right;++ i){
int tmp = ns[left] * ns[i] * ns[right] + dp[left][i] + dp[i][right];
// cout<<tmp<<endl;
dp[left][right] = max(dp[left][right], tmp);
}
}
}
return dp[0][size - 1];
}
};
- 324 Wiggle Sort II
输入：int数组
输出：void
要求：摇摆排序，时间复杂度O(n)，空间复杂度O(1)。
思路：先求出中位数，然后将小于中位数的放在奇数位置，大于中位数的放在偶数位置。
值得注意的几个地方：
-
nth_element()函数的使用。 -
#define A(i) nums[(1 + 2 * (i)) % (size | 1)]可以用来更改索引顺序。
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int size = nums.size();
auto midptr = nums.begin() + size / 2;
nth_element(nums.begin(), midptr, nums.end());
int mid = *midptr;
// cout<<mid<<endl;
#define A(i) nums[(1 + 2 * (i)) % (size | 1)]
int index_odd = 0;
int index_even = size - 1;
int index = 0;
while(index <= index_even){
if(A(index) > mid){
swap(A(index_odd ++), A(index ++));
}else if(A(index) < mid){
swap(A(index), A(index_even --));
}else{
index ++;
}
}
}
};
-
335 Self Crossing
输入：int数组
输出：是否有自环
要求：从原点开始，逆时针走，按照北西南东的顺序。
思路：
情况分类图
class Solution {
public:
bool isSelfCrossing(vector<int>& x) {
int size = x.size();
if(size <= 3) return false;
for(int i = 3;i < size;++ i){
if(x[i] >= x[i - 2] && x[i - 1] <= x[i - 3]) return true;
if(i >= 4) if(x[i - 1] == x[i - 3] && (x[i] + x[i - 4]) >= x[i - 2]) return true;
if(i >= 5) if(x[i - 5] + x[i - 1] >= x[i - 3] && x[i] + x[i - 4] >= x[i - 2] && \
x[i - 2] >= x[i - 4] && x[i - 1] <= x[i - 3]) return true;
}
return false;
}
};
- 336 Palindrome Pairs
输入：字符串数组
输出：vector<vector<int>>
要求：返回能够构成回文串的各个字符串组
举例：
Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
思路：Hash Table
值得注意的地方：
-
is_palindrome中++和--的位置问题 - 对空串的处理：每次处理都会判断该word是不是整个字符串构成一个回文串，如果是的话，那就找一下有没有空串在map里边。
class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> ret;
map<string, int> tool;
for(int i = 0;i < words.size();++ i) tool[words[i]] = i;
for(int index = 0;index < words.size();++ index){
string word = words[index];
int size = word.size();
for(int i = 0;i <= size;++ i){
if(i > 0 && is_palindrome(word, 0, i - 1)){
string tmp = word.substr(i);
reverse(tmp.begin(), tmp.end());
if(tool.find(tmp) != tool.end() && tool[tmp] != index){
ret.push_back({tool[tmp], index});
}
}
if(is_palindrome(word, i,size - 1)){
string tmp = word.substr(0, i);
reverse(tmp.begin(), tmp.end());
if(tool.find(tmp) != tool.end() && tool[tmp] != index){
ret.push_back({index, tool[tmp]});
}
}
}
}
return ret;
}
bool is_palindrome(string& word, int begin, int end){
while(begin < end){
if(word[begin++] != word[end--]) return false;
}
return true;
}
};
- 365 Water and Jug Problem
输入：x和y是水壶的容量，z是要称量的水量
输出：bool（是否能称量出来）
思路：求取x和y的最大公约数，然后看z能不能整除该数字。
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
return z == 0 || (z <= x + y && z % gcd(x, y) == 0);
}
int gcd(int x, int y){
return y == 0 ? x : gcd(y, x % y);
}
};
- 381 Insert Delete GetRandom O(1) - Duplicates allowed
题意：构造题，以O(1)的时间复杂度来进行元素的增删和返回任意值
思路：因为允许重复元素的存在，因此我们需要将所有的重复元素出现的位置保存下来以供调用。因此需要两个数据结构。一个数组来存储数字，一个map来映射元素值和其位置。数组中存储的是pair，因为remove的过程中要修改相应位置上的值，我们需要知道需要修改的值对应的是m[val]中的第几个。
class RandomizedCollection {
public:
/** Initialize your data structure here. */
RandomizedCollection() {
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
bool insert(int val) {
auto ret = m.find(val) == m.end();
m[val].push_back(nums.size());
nums.push_back({val, m[val].size() - 1});
return ret;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
auto ret = m.find(val) != m.end();
if(ret){
auto last = nums.back();
m[last.first][last.second] = m[val].back();
nums[m[val].back()] = last;
m[val].pop_back();
nums.pop_back();
if(m[val].empty()) m.erase(val);
}
return ret;
}
/** Get a random element from the collection. */
int getRandom() {
return nums[rand() % nums.size()].first;
}
private:
vector<pair<int, int>> nums;//{val, index of val into m[val]}
unordered_map<int, vector<int>> m;//m[nums[i].first][nums[i].second] == i
};
/**
* Your RandomizedCollection object will be instantiated and called as such:
* RandomizedCollection obj = new RandomizedCollection();
* bool param_1 = obj.insert(val);
* bool param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/
