#27 移除元素
思路
由于它实际调用接口的例子是图上这样，输出的限制就比较多。要求原地删除val，不能开新的数组来存进行删除操作后的数组，那么每次检测到val就把它后面的所有数前移一位。
遍历数组，每次检测到val就将之后的数前推一位，然后计数count加1。
nums.lenth-count=输出的数组长度lenth。
Case 1:没有相邻且等于val的数，那么正常运行
Case 2:最后一位数等于val,随着不断地进行这种粗糙的前移操作，会从最后一个数copy出很多个等于val的值。解决办法就是每次前移完成后将最后一位数覆盖为101（因为val是小于100的，不可能取到101）.
Case 3:存在两个以上相邻且等于val的数，这种时候由于将后一个数前移到当前操作的num[i]，导致会漏掉这个相连且重复的数，解决办法就是每次前移之后检查num[i]，如果还等于val，就从num[i]开始再执行一次前移操作（套娃）
代码
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int length,count=0;
for (int i = 0; i < nums.size(); i++) {
repeat: if (nums[i]==val)
{
count++;
for (int j=i; j<(nums.size()-1); j++)
{
nums[j]=nums[j+1];
}
//case 1:the last number is val
if (nums[nums.size()-1]==val)
{
nums[nums.size()-1]=101;
}
//case 2:more than 2 near numbers are all equal to val then do the delete operation again
//Actually I do not like "goto" ,it's dangerous ,but it's the first solution I thought out to deal with this
//Pardon me....
if (nums[i]==val)
{
goto repeat;
}
}
}
length=nums.size()-count;
return length;
}
};
反思
1.这种前移操作是非常粗糙的，会导致一些BUG，有优化的空间。在测试中我也遇到了尾数是val和有多个相连的val数的情况。由于我采用的是遍历式的for循环，针对这两种情况就只能见招拆招打补丁，而不能从结构设计上优雅地去避免这两种情况出错，有点尴尬。
2.针对多个等于val的数相连的情况，我采用的是每次前移之后都再次检查当前操作数，如果也为val，则再次执行前移，相当于是个套娃操作。为了减少代码量（图省事），虽然不情愿，我还是采用了"goto"语句，用起来倒是没什么问题。原谅我，goto真的很危险。。。。。。。
#977 有序数组的平方
思路
看到这个题之后的直接想法就是直接全部平方存到新数组里（操作)，然后再做一个排序，随便什么排序都能满足最基本的要求。
再看进阶要求，时间复杂度，平方操作是固定的，那么只能从这个排序方法上做文章。普通的排序复杂度在
，好一点的也要
，达不到要求。但是注意到本题是一个非降序数列，即使有正有负，那也有一个分界数，这让我联想到了归并排序里的Merge操作，所以我决定采用这种方法。
首先遍历找到分界数，然后从分界数的位置分割成两个数组。
然后将两个数组分别平方，一个从前往后，一个从后往前，两个数组元素比较大小，按顺序归并入新的数组。
代码
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int divide=0;
int leftcount=0;
int rightcount=0;
int leftindex=0;
int rightindex=0;
int count=0;
int i,j=0;
//To find the index of the divide number
for ( i=1 ; i<nums.size() ; i++ )
{
if ((nums[i]*nums[i-1])<=0)
{
divide=i-1;
break;
}
}
// all 0
if ((divide==0)&&(nums[nums.size()-1]<0))
{
divide=nums.size()-1;
}
// divide into two arrays
int left[nums.size()];
int right[nums.size()];
//initial left and right array
for ( i=0 ; i< divide;i++)
{
left[i]=0;
}
for ( i=0 ; i< nums.size()-divide-1;i++)
{
right[i]=0;
}
for ( j=divide; j>=0 ; j--)
{
left[leftindex]=nums[j]*nums[j];
leftindex++;
}
for ( i=divide+1 ; i<nums.size() ; i++)
{
right[rightindex]=nums[i]*nums[i];
rightindex++;
}
//Compare and merge
for ( i=0; i<nums.size() ; i++)
{
if (rightcount<rightindex)
{
if (leftcount<leftindex)
{
if (left[leftcount]<=right[rightcount])
{
nums[i]=left[leftcount];
leftcount++;
}
else
{
nums[i]=right[rightcount];
rightcount++;
}
}
else
{
nums[i]=right[rightcount];
rightcount++;
}
}
else
{
nums[i]=left[leftcount];
leftcount++;
}
}
cout<<count<<' '<<leftcount<<' '<<rightcount;
return nums;
}
};
反思
这个归并操作实现起来居然很艰难，主要是左右两个数组的边界情况把我绕晕了。
内存消耗没办法，如果是用最简单的平方加排序来做空间复杂度肯定会低很多。
不过我这个就属于空间换时间了。
总的来说花了快两个小时，写出来的代码比较烂，感觉归并的判断逻辑可以优化，数组的大小可以优化。。。
眼睛看花了，就这样吧先
先吃个海鲜焖面，拜拜
