Leetcode之数组篇
1.从排序数组中删除重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
不需要考虑数组中超出新长度后面的元素。
解题思路：由于数组是有序的，所以只需要利用快慢指针对比新旧数组的尾部元素，如果旧数组和新数组的尾部元素则舍弃新数组尾部元素。
int removeDuplicate(int nums,int size)
{
if ( size <= 0) return 0;
int len = 0;//新数组长度
for(int i =1;i<size;i++)//i 是旧数组尾部遍历游标
{
if(nums[len] != nums[i])
{//如果新旧数组尾部元素不一致，证明此元素是需要添加到新元素尾部的
nums[++len] = nums[i];
}
//如果新旧尾部元素是一样的，证明旧的尾部元素需要被舍弃掉
}
return len+1;//len只是新数组尾部指针，返回的新数组长度就需要+1；
}
2. 买卖股票的最佳时机 II
解题思路：只要将所有波谷到波峰的值全部加起来就是最大的收益，并且波峰之后必定是波谷，波谷买进波峰卖出，从而达到收益最大化。波峰与波谷之间可能是两点之间也可能是多点之间，但是波峰到波谷中间所有段（连续两点之间的价格差）必定全部是下降状态，相反，波谷到波峰中间所有段必定是上升状态，从而演化成，求两点之间正收益的和。
int maxProfit(int* prices, int pricesSize){
if(1 >= pricesSize)//避免价值区间数组输入有误，保证程序的健壮性
return 0;
int sums = 0;//正收益的和
for (int i = 1; i< pricesSize ; i++)//i为下一值的游标，用于判断此区段升降状态
{
if (prices[i-1] < prices[i])//正收益状态，计算收益
sums += prices[i] -prices[i-1];
//如果是负收益状态，那么当前点即为卖出点，当前点和下一点的负收益不记录在收益内。
}
return sums;
}
3. 旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
解题思路：利用三次逆序法，向右移动k个单位，实际上就是数组分成两个部分 [0,size-k-1][size-k,size-1]，两部分前后颠倒，实际上就是全数组前后颠倒，颠倒后，再将两部分内部数组的顺序进行还原。可以得到最终的结果。值得注意的是k的数值需要对size取模，因为k=0 和k = size*n 都相当于数组没有移动。
void reverse (int *nums,int startIndex,int len)
{
int i = 0;
int endIndex = startIndex + len - 1;
while(i < len)
{
if( startIndex + i < endIndex -i)
{//利用异或运算对调两个数
nums[startIndex + i ] = nums[startIndex + i ] ^ nums[endIndex -i];
nums[endIndex -i] = nums[endIndex -i] ^ nums[startIndex + i ] ;
nums[startIndex + i ] = nums[endIndex -i] ^ nums[startIndex + i ] ;
}
else//当startIndex +i >= endIndex -i 时，前后两部分已经对调完毕
break;
i++;
}
}
void rotate(int *nums,int numsSize,int k)
{
if (0 >= numsSize ) return;//保证输入数组正确
int realK = k % numsSize;
if (realK == 0 ) return ;//原地没动无需执行
reverse(nums,0,numsSize);
reverse(nums,0,realK);
reverse(nums,realK,numsSize-realK);
}
4. 存在重复
给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
解题思路：思路一：通过创建一个哈希表，表下标和数组中的值为一一映射，然后表内值记录的是当前数组值出现的次数，当出现次数大于1时即可直接返回
思路二：破坏原有的数组结构，排序，然后顺序遍历，如果遇到两个相等的值，则返回。
bool containsDuplicate(int* nums, int numsSize) {
if (numsSize == 0)
return false；
int min = nums[0], max = nums[0], len;
// 确定哈希表范围。
for (int i = 1; i < numsSize; i++) {
if (nums[i] > max)
max = nums[i];
if (nums[i] < min)
min = nums[i];
}
// 哈希表。
len = max-min+1;
int* hash = (int *)malloc(sizeof(int)*len);
memset(hash,0 ,sizeof(int)*len);
for (int i = 0; i < numsSize; i++) {
// 判断元素是否已经出现过。
int hashIndex = nums[i]-min;
if (hash[hashIndex] == 1)
return true;
hash[hashIndex] ++;
}
return false;
}
5. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
解题思路：主要应用到异或的交换率和结合率，也就是说,a^b^c^d = a^ (b^c)^d= a^(b^d)^c，异或实际上是逻辑概念，可以抽象为数学中交集并集的概念，可转化为图形的交并集加以证明，详细证明请看异或操作的图形证明
，题中给出的是只有一个元素是一个，其余的都是成对出现的，如果对注数字做异或操作，那么就是这样的，a^b^c^d^b^a^c = d^(a^a)^(b^b)^(c^c)，一个数字异或自身一定为0，那么上面的那个公式最终得到的结果是d ,这样我们就找到了那个孤独的单身狗。
int singleNumber(int* nums, int numsSize){
if(0 >= numsSize) return -1;
if(1 == numsSize) return nums[0];
int result = 0;
for (int i = 0 ;i<numsSize ;i++)
{
result = result ^ nums[i];
}
return result;
}
6.两个数组的交集 II
给定两个数组，编写一个函数来计算它们的交集。
6.1有序数组情况
解题思路：依然可以利用扫描指针来挑选，第一个数组下标为index1，第二个数组下标为index2
1.*index1 == *index2 ，则取出，index1++，index2++
2.*index1 > *index2 ，index2++
3.*index1 < *index2，index1++
直至某一指针到达尾部为止。
vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
{
int index1 = 0;
int index2 = 0;
vector<int> result ;
while(index1<nums1.size() || index2<nums2.size() )
{
if( nums1[index1] == nums2[index2])
{
result.push_back(nums1[index1]);
++index2;
++index1;
break;
}
if( nums1[index1] > nums2[index2])
{
++index2;
break;
}
if( nums1[index1]< nums2[index2])
{
++index1;
break;
}
}
return result;
}
6.2 无序数组情况
解题思路：1.破坏数组，可以先将两个数组进行排序，然后按照6.1中的方法，挑选。2.利用一个MAP记录较短数组的每一个元素出现的值，然后再从较长数组中挑出，与MAP中存储的数据对应的值。
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
vector<int> result;
map<int,int> countMap;
if(nums1.size() < nums2.size())//找到长度最小的数组
{
swap(nums1,nums2);
}
//记录最小数组的包含元素及对应个数
for_each(nums2.begin(),nums2.end(),[&](int val)
{
if(countMap.count(val))
{
countMap[val]++;
}
else
{
countMap.insert(map<int,int>::value_type(val,1));
}
}
);
//在长数组中挑选重合的元素，每遇到重合的元素，就加入到结果数组中，然后对应元素的记录数字减1
for_each(nums1.begin(),nums1.end(),[&](int val)
{
if(countMap.count(val))
{
if(countMap[val]!=0)
{
result.push_back(val);
countMap[val]--;
}
}
}
);
return result;
}
7.加一
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
解题思路：需要考虑两点，1. 每一位的计算需要考虑低位的进位2.最高位进位，数字位数改变。
我们从后往前遍历原数组，分为三种情况：个位，中间位，最高位；
个位：原数+1
中间位：原数+进位 -> 此位有进位，重新调整当前位和进位，当前位插入结果数组中，进位留高位判断处理。
最高位：如果最高位存在进位，扩展数组
处理后的结果数组是逆向的，然后翻转数组，即得到真正的结果数组。
vector<int> plusOne(vector<int>& digits) {
vector<int> result;
if ( 0 == digits.size())
{
result.push_back(1);
return result;
}
int original = 0;
int carry = 0;
for(vector<int>::reverse_iterator rit = digits.rbegin(); rit != digits.rend();rit++)
{
if (rit == digits.rbegin())
{
original = *rit + 1;
}
else
{
original = *rit + carry;
}
if( 10 <= original)
{
original = original - 10;
carry = 1;
}
else
{
carry = 0;
}
result.push_back(original);
}
if (1 == carry) result.push_back(1);
reverse(result.begin(),result.end());
return result;
}
8. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
解题思路：很简单，顺序遍历数组，当遇到0时，记录0的个数，此后如果不是零，就将此数与最前面的0的交换位置，直至遍历结束。
void moveZeroes(vector<int>& nums) {
int zeroNum = 0;
for(int i = 0 ; i< nums.size() ; i++)
{
if( 0 != nums[i])//此位置不是0
{
if(zeroNum != 0)//如果前面有0，这将最前面的0和此位置的数交换
{
nums[i-zeroNum] = nums[i];
nums[i] = 0;
}
//如果前面没有0，不为零的位置不需要移动
}
else//此位置是0，零计数加一，然后接着遍历后边的位置
{
++zeroNum;
}
}
}
9. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
解题思路：这种关联型问题，肯定涉及到记录，涉及到记录的，并且可以实现线性查找的，基本上都会用到hash表，或者是c++中的unordered_map，先遍历一遍数组建立hash表，然后再遍历一遍数组找到配对信息。
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result(2);
if( 1 >= nums.size()) return result;
//建立hash表
unordered_multimap<int,int> hashMap;
for(int i = 0; i< nums.size();i++)
{
hashMap.insert({nums[i],i});
}
//遍历
for(int i = 0; i< nums.size();i++)
{
int part = target - nums[i];
auto search = hashMap.equal_range(part);
for(auto it = search.first;it != search.second;it++)
{
if (it->second != i)//当前并不是同一元素
{
result[0] = it->second;
result[1] = i;
return result;
}
}
}
return result;
}
10.有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
数独部分空格内已填入了数字，空白格用 '.' 表示。
解题思路：这个题遍历是免不了的，如果遍历，那么9*9的数组必然需要两层循环，遍历。但是这个题中即需要验证行还需要验证列，还需要验证宫，常规思维就是运行三次遍历，浪费时间，我们只需要考虑能不能将三次遍历融合成一次遍历呢？
两层循环中，外层循环的逻辑意义是，检验第几个块，行验证时i表示的是第i行，列验证时i表示的是第i列，宫验证时i表示的是第几个宫，j则表示第i个块中的第j个元素，所以我们只需要在循环体中利用i,j创造每个块中的实际坐标，即可
1.验证行时，array[i][j]，i代表行，j代表列
2.验证列时，array[j][i]，i在标列，j代表行
3.宫验证时，我们就需要找到每个宫的起始位置，然后根据每次j的加一操作，遍历一个方格，这个坐标是最难变换的
每个方格起始位置的row和col是下边的
row = (i/3)3
col = (i%3)3
j开始遍历一个方格时，不仅仅会影响到列，还会影响到行，所以最终公式应该是
row = (i/3)3 + j/3
col = (i%3)3 + j%3
以上是遍历方法，那么验证方法实际上就是老一套，记录每个数值在每个块中出现的个数，如果哪个块出现了同一个数值，则直接返回
bool isValidSudoku(vector<vector<char>>& board) {
if( 9 != board.size()) return false;
for(int i = 0 ;i<9;i++)
{
vector<int> row(9);
vector<int> col(9);
vector<int> cube(9,0);
for(int j=0;j<9;j++)
{
//行块验证
if(board[i][j] != '.')
{
int index = board[i][j] -'1';
if( row[index] != 0)
{
return false;
}
else
{
++row[index];
}
}
//列块验证
if(board[j][i] != '.')
{
int index = board[j][i] -'1';
if( col[index] != 0)
{
return false;
}
else
{
++col[index];
}
}
//根据逻辑下标计算数组实际下标
int rowIndex = 3*(i/3) + j/3;
int colIndex = j%3 +(i%3)*3;
//宫块验证
if(board[rowIndex][colIndex] != '.')
{
int index = board[rowIndex][colIndex] -'1';
if( cube[index] != 0)
{
return false;
}
else
{
++cube[index];
}
}
}
}
return true;
}
};
11. 旋转图像
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
解题思路：二维矩阵的旋转可以分割成层层回字型区域的旋转，每个单层回字型区域 ，即[i][j]->[i][n-1-j]->[n-1-j][n-1-j]->[n-1-j][j]这四个点围成的区域。
void rotate(vector<vector<int>>& matrix) {
if(0 >= matrix.size()) return;
int n = matrix.size();
int next = 0;
for(int i =0 ;i< n/2;i++)
{
int loopN = n - i*2;
for(int j=0 ;j<loopN-1;j++)
{
//将1位置变成被交换值的临时位置
//只要按照顺序与其依次交换即可得到最后的交换信息
swap(matrix[i][i+j],matrix[i+j][i+loopN-1]);
swap(matrix[i][i+j],matrix[i+loopN-1][i+loopN-1-j]);
swap(matrix[i][i+j],matrix[i+loopN-1-j][i]);
}
}
}
