开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结果,反思}的格式来记录,供日后复习和反思[注:有些题目的解法比较单一,就没有优化过程]。题目的顺序按照leetcode给出的题目顺序,有些题目在并不是按照题目本身序号顺序排列的,也不是严格按照难易程度来排列的。
因此,这篇文章并不具有很强的归类总结性,归类总结性知识将会在其他文章记录,本篇重点在记录解题过程中的思路,希望能对自己有所启发。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(nums.size()==0||target<nums.front())
return 0;
if(target>nums.back())
return nums.size();
int start=0, end=nums.size()-1, mid=0;
while(start<=end)
{
mid = (start+end)/2;
if(nums[mid]==target)
return mid;
else if(nums[mid]>target)
end = mid-1;
else start = mid+1;
}
return start;
}
};
For example, given candidate set [2, 3, 6, 7]
and target 7
,
A solution set is: [ [7], [2, 2, 3] ]
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> altered_candidates;
vector<vector<int>> res;
sort(candidates.begin(), candidates.end());
int tail=0;
while(candidates[tail]<=target&&tail<candidates.size())
++tail;
if(tail==0)
return res;
altered_candidates.insert(altered_candidates.end(), candidates.begin(), candidates.begin()+tail);
map<int, vector<vector<int>>> val_member;
find_res(altered_candidates, val_member, target);
res = val_member[target];
deduplicate(res);
return res;
}
void deduplicate(vector<vector<int>>& res)
{
set<vector<int>> set_res;
for(auto begin_iter=res.begin(); begin_iter!=res.end(); ++begin_iter)
{
sort(begin_iter->begin(), begin_iter->end());//排序有助于set自动对比和去重
set_res.insert(*begin_iter);
}
res.clear();
res.insert(res.end(), set_res.begin(), set_res.end());
}
void generate_new_val(map<int, vector<vector<int>>>& val_seq, int& target, int& new_target, int& val)
{
auto& seq_vec = val_seq[new_target];
for(auto seq_iter = seq_vec.begin(); seq_iter!=seq_vec.end(); ++seq_iter)
{
vector<int> val_tmp = *seq_iter;
val_tmp.push_back(val);
val_seq[target].push_back(val_tmp);
}
}
void find_res(vector<int>& nums, map<int, vector<vector<int>>>& val_seq, int target)
{
for(auto val:nums)
{
int new_target = target - val;//分解期望值
if(new_target==0)//如果恰好分解
{
val_seq[target].push_back(vector<int>{val});
continue;
}
if(new_target<nums.front())//如果分解值不在范围内
continue;
if(val_seq.find(new_target)!=val_seq.end())//已经求解过该期望值
generate_new_val(val_seq, target, new_target, val);
else //尚未求解该期望值
{
find_res(nums, val_seq, new_target);
generate_new_val(val_seq, target, new_target, val);
}
}
}
};
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
sort(candidates.begin(), candidates.end());
if(candidates.front() > target)
return res;
vector<int> index_result;
search_result(0, candidates, res, target, index_result);
return res;
}
void search_result(int index, vector<int>& candidates, vector<vector<int>>& res, int target, vector<int>& index_result)
{
while(index < candidates.size())
{
int val = candidates[index];
if(val > target)
break;
int times = target / val, rest = target % val;
while(times != 0)
{
vector<int> tmp_result(times, val);
tmp_result.insert(tmp_result.end(), index_result.begin(), index_result.end());
if(rest == 0)
res.push_back(tmp_result);
else
search_result(index+1, candidates, res, rest, tmp_result);
--times;
rest = target - times * val;
}
++index;
}
}
};
For example, given candidate set [10, 1, 2, 7, 6, 1, 5]
and target 8
,
A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> res;
sort(candidates.begin(),candidates.end());
if(candidates.front() > target)
return res;
vector<int> tmp;
search_result(0, target, candidates, tmp, res);
return res;
}
void search_result(int index, int target, vector<int>& candidates, vector<int>& index_result, vector<vector<int>>& res)
{
while(index < candidates.size())
{
int next_target = target - candidates[index];
if(next_target < 0)
return;
else if(next_target == 0)
{
vector<int> final_res(index_result);
final_res.push_back(candidates[index]);
res.push_back(final_res);
}
else
{
vector<int> tmp_result{index_result};
tmp_result.push_back(candidates[index]);
search_result(index+1, next_target, candidates, tmp_result, res);
}
while(index+1 < candidates.size() && candidates[index]==candidates[index+1])
++index;
++index;
}
}
};
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int N = matrix.size();
if(N == 0)
return;
for(int row = 0; row < N-1; ++row)
for(int col = 0; col < N-row-1; ++col)
{
int new_col = -1 * row + N - 1;
int new_row = -1 * col + N - 1;
swap(matrix[row][col], matrix[new_row][new_col]);
}
for(int col = 0; col < N; ++col)
{
int start_row = 0, end_row = N-1;
while(start_row < end_row)
{
swap(matrix[start_row][col], matrix[end_row][col]);
++start_row;
--end_row;
}
}
}
void swap(int& a, int& b)
{
int tmp = a;
a = b;
b = tmp;
}
};