开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结果,反思}的格式来记录,供日后复习和反思。题目的顺序按照leetcode给出的题目顺序,有些题目在并不是按照题目本身序号顺序排列的,也不是严格按照难易程度来排列的。
因此,这篇文章并不具有很强的归类总结性,归类总结性知识将会在其他文章记录,本篇重点在记录解题过程中的思路,希望能对自己有所启发。
class Solution {
public:
int maxArea(vector<int>& height) {
int area = 0;
int max_height = 0;
for(int i = 0; i < height.size(); ++i)
{
while(height[i]==0 && i < height.size())
++i;
for(int j = i+1 ; j < height.size(); ++j)
{
while(height[j]==0 && j < height.size())
++j;
if(j < height.size())
{
int a = (height[i] < height[j])? height[i]:height[j];
int tmp_area = a * (j - i);
if(tmp_area > area)
area = tmp_area;
}
}
if(height[i] > max_height)
max_height = height[i];
}
return area;
}
};
class Solution {
public:
int maxArea(vector<int>& height) {
int area = 0;
int max_height = 0;
for(int i = 0; i < height.size(); )
{
while(height[i]==0 && i < height.size())
++i;
int j = (area == 0)?(i+1):(i + area / height[i]);
for( ; j < height.size(); ++j)
{
while(height[j]==0 && j < height.size())
++j;
if(j < height.size())
{
int a = (height[i] < height[j])? height[i]:height[j];
int tmp_area = a * (j - i);
if(tmp_area > area)
area = tmp_area;
}
}
if(height[i] > max_height)
max_height = height[i];
int next_index = i+1;
while(next_index < height.size() && height[next_index] <= max_height)
++next_index;
i = next_index;
}
return area;
}
};
再加上距离优化的结果:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
if(nums.size()<2)
return result;
for(int i=0; i<nums.size(); ++i)
{
for(int j=i+1; j<nums.size(); ++j)
{
if(nums[i]+nums[j]==target)
{
result.push_back(i);
result.push_back(j);
break;
}
}
}
return result;
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
if(nums.size()<2)
return result;
vector<int> cpy(nums);
sort(cpy.begin(),cpy.end());
int start = 0, end = cpy.size() -1;
while(start < end)
{
int sum = cpy[start] + cpy[end];
if(sum < target)
++start;
else if(sum > target)
--end;
else
{
int a_indice = -1, b_indice = -1;
for(int i = 0; i < nums.size(); ++i)
{
if(nums[i] == cpy[start] || nums[i] == cpy[end])
result.push_back(i);
if(result.size() == 2)
return result;
}
}
}
}
};
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
if(nums.size()<=2)
return res;
set<vector<int>> tmp_res;
for(int i=0; i<nums.size(); ++i)
for(int j=i+1; j<nums.size(); ++j)
for(int k=j+1; k<nums.size(); ++k)
{
if(nums[i]+nums[j]+nums[k]==0)
{
vector<int> val{nums[i],nums[j],nums[k]};
sort(val.begin(),val.end());
tmp_res.insert(val);
}
}
res.insert(res.end(), tmp_res.begin(), tmp_res.end());
return res;
}
};
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> result;
int sz = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < sz - 2; ++i){
twoSum(nums, i + 1, 0 - nums[i], result);
while(nums[i] == nums[i + 1]) ++i;//这一步要注意,防止得出重复的vector
}
return result;
}
void twoSum(vector<int> & nums, int start, int value, vector<vector<int>> & ret)
{
int beg = start;
int end = nums.size()-1;
while (beg < end){
int sum = nums[beg] + nums[end];
if (sum < value)
beg++;
else if (sum > value)
end--;
else{
ret.push_back(vector<int>{nums[start - 1], nums[beg], nums[end]});
while (nums[beg + 1] == nums[beg]) beg++;//这一步的处理应该注意,防止出现相同的vector
while (nums[end - 1] == nums[end]) end--;
beg++, end--;
}
}
}
};
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
if(nums.size()<3)
return 0;
int sum = 0, dis = 99999;
for(int i=0; i<nums.size(); ++i)
for(int j=i+1; j<nums.size(); ++j)
for(int k=j+1; k<nums.size(); ++k)
{
int tmp_sum = nums[i]+nums[j]+nums[k];
int tmp_dis = 0;
if(target >= 0)
{
if(tmp_sum >= 0)
tmp_dis = (target >= tmp_sum)? (target-tmp_sum):(tmp_sum-target);
else tmp_dis = target - tmp_sum;
}
else
{
if(tmp_sum >= 0)
tmp_dis = tmp_sum - target;
else tmp_dis = (target < tmp_sum)? (tmp_sum - target):(target - tmp_sum);
}
if(tmp_dis < dis)
{
dis = tmp_dis;
sum = tmp_sum;
}
if(dis==0)
break;
}
return sum;
}
};
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int res = nums[0] + nums[1] + nums[2];
for(int i = 0; i < nums.size() - 2; i++){
int j = i + 1, k = nums.size() - 1;
while(j < k){
int num = nums[i] + nums[j] + nums[k];
if(abs(num - target) < abs(res - target)) res = num;
if(num < target) j++;
else k--;
}
}
return res;
}
};
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
if(nums.size()<4)
return res;
set<vector<int>> tmp_res;
for(int i=0; i<nums.size(); ++i)
for(int j=i+1; j<nums.size(); ++j)
for(int k=j+1; k<nums.size(); ++k)
for(int m=k+1; m<nums.size(); ++m)
{
if(nums[i]+nums[j]+nums[k]+nums[m]==target)
{
vector<int> val{nums[i],nums[j],nums[k],nums[m]};
sort(val.begin(),val.end());
tmp_res.insert(val);
}
}
res.insert(res.end(), tmp_res.begin(), tmp_res.end());
return res;
}
};
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
if(nums.size() < 4)
return result;
sort(nums.begin(),nums.end());
for(int i = 0; i < nums.size()-3; ++i)
{
threeSum(nums, i+1, target - nums[i], result, nums[i]);
while(nums[i]==nums[i+1])
++i;
}
return result;
}
void threeSum(vector<int>& nums, int start, int value, vector<vector<int>>& result, int pre_value)
{
for(int i = start; i < nums.size() - 2; ++i)
{
twoSum(nums, i+1, value - nums[i], result, pre_value);
while(nums[i]==nums[i+1])
++i;
}
}
void twoSum(vector<int>& nums, int start, int value, vector<vector<int>>& result, int pre_value)
{
int begin = start;
int end = nums.size() - 1;
while(begin < end)
{
int sum = nums[begin] + nums[end];
if(sum < value)
++begin;
else if(sum > value)
--end;
else
{
result.push_back(vector<int>{pre_value, nums[start-1], nums[begin], nums[end]});
while(nums[begin+1]==nums[begin])
++begin;
while(nums[end-1]==nums[end])
--end;
++begin;
--end;
}
}
}
};
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size()<2)
return nums.size();
int tail = nums.size();
for(int i=1; i<tail; )
{
int moved_nums = 0;
while(nums[i]==nums[i-1]&&i<tail)
{
++moved_nums;
++i;
}
tail -= moved_nums;
if(moved_nums!=0)
{
move(nums,i,moved_nums);
i = i-moved_nums;
}
else ++i;
}
return tail;
}
void move(vector<int>& nums, int start, int offset)
{
for(int j=start; j < nums.size(); ++j)
nums[j-offset]=nums[j];
}
};
#include<climits>
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() <= 1)
return nums.size();
int counter = 0;
int max_val = 0x7fffffff;
int last_pos = 0;
for(int i = 1; i < nums.size(); ++i)
{
if(nums[i]==nums[i-1])
{
nums[i-1]=max_val;
++counter;
}
}
if(counter!=0)
{
for(int i = 0; i < nums.size()-counter; ++i)
{
if(nums[i]==max_val)
{
if(last_pos < i)
last_pos = i;
last_pos = findNonNull(nums, last_pos, max_val);
if(last_pos < nums.size())
{
nums[i] = nums[last_pos];
nums[last_pos] = max_val;
}
else break;
}
}
}return nums.size()-counter;
}
int findNonNull(vector<int>& nums, int start, int& max_val)
{
while(start < nums.size())
{
if(nums[++start]!=max_val)
return start;
}
return start;
}
};
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int tail = nums.size();
for(int i=0; i<nums.size(); ++i)
{
if(nums[i]==val)
{
nums[i]=0x7fffffff;
--tail;
}
}
for(int i=0; i<tail; )
{
if(nums[i]==0x7fffffff)
{
for(int j=i+1; j<nums.size(); ++j)
nums[j-1]=nums[j];
}
else ++i;
}
return tail;
}
};
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int counter = 0;
for(int i = 0; i < nums.size(); ++i)
{
if(nums[i]==val)
{
++counter;
nums[i] = 0x7fffffff;
}
}
if(counter!=0)
{
int tail = nums.size()-1;
while(nums[tail]==0x7fffffff)
--tail;
for(int i=0; i<tail; ++i)
{
if(nums[i]==0x7fffffff)
{
nums[i]=nums[tail];
nums[tail]=0x7fffffff;
while(nums[tail]==0x7fffffff)
--tail;
}
}
}
return nums.size()-counter;
}
};
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int max = 0x7fffffff;
int counter = 0;
for(int i = 0; i < nums.size(); ++i)
{
if(nums[i]==val)
{
++counter;
nums[i] = max;
}
}
if(counter != 0)
sort(nums.begin(),nums.end());
return nums.size()-counter;
}
};
1,2,3
→ 1,3,2
3,2,1
→ 1,2,3
1,1,5
→ 1,5,1
class Solution {
public:
void nextPermutation(vector<int>& nums) {
if(nums.size()<2)
return ;
int start = nums.size() -2;
while(start >= 0)
{
if(post_check(nums, start)==true)
break;
else --start;
}
if(start<0)
sort(nums.begin(),nums.end());
}
bool post_check(vector<int>& nums, int start)
{
int next_index = -1;
for(int i=start+1; i<nums.size(); ++i)
{
if(nums[i]>nums[start])
{
if(next_index==-1)
next_index = i;
else if(nums[next_index]>nums[i])
next_index = i;
}
}
if(next_index==-1)
return false;
else
{
int tmp = nums[start];
nums[start]=nums[next_index];
nums[next_index]=tmp;
sort(nums.begin()+start+1, nums.end());
return true;
}
}
};
0 1 2 4 5 6 7
might become 4 5 6 7 0 1 2
).You are given a target value to search. If found in the array return its index, otherwise return -1.You may assume no duplicate exists in the array.class Solution {
public:
int search(vector<int>& nums, int target) {
for(int i=0; i<nums.size(); ++i)
if(nums[i]==target)
return i;
return -1;
}
};
[-1, -1]
.For example,
Given [5, 7, 7, 8, 8, 10]
and target value 8,
return [3, 4]
.class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res{-1,-1};
if(nums.size()==0)
return res;
int start=0, end=nums.size()-1;
int mid = 0;
while(start<=end)
{
mid = (start+end)/2;
if(nums[mid]==target)
break;
else if(nums[mid]>target)
end = mid-1;
else start = mid+1;
}
if(nums[mid]==target)
{
int left = mid-1, right = mid+1;
while(left>=0 && nums[left]==nums[left+1])
--left;
while(right<nums.size() && nums[right]==nums[right-1])
++right;
res[0]=left+1;
res[1]=right-1;
}
return res;
}
};