剑指offer之数组
数组
一、杂话：将剑指offer里的题目按 数据结构与算法里的知识点刷题总结
由于一开始不太会用这个编辑器，所以，格式上可能会有点乱，暂且不管了
接下来会按照数据结构后算法的顺序进行刷题总结
二、相关知识点：
①数组其实是线性表的顺序存储结构，形如 [1,2,3,4]
②声明一个数组：
int a[10];//并不会自动初始化a[i]=0,这种方法不使用
int a[10]={0};//初始化a[i]=0
int a[]={...};//已知元素，则可以不用预先给定数组长度
int *a=new int[n];//如数组长度是一个变量可以采用，但一般动态分配不用
注意：编程中常用vector来取代数组进行运算，因为其可动态分配空间，操作方便
③vector中常用函数：
push_back(num) 在向量后插入元素，但未预先给定向量大小时，不可用[i]调用，或插入元素，此时用push_back()
insert(pos,num) 在指定位置插入元素，指定位置常由begin()/end()计算得到
erase(first,last) 删除 [first,last)间的元素
empty() 判断向量是否为空
size() 判断向量长度
④数组的操作：
插入：插入后需要移动后面的元素，如在i处插入元素，则需将[i,size()-1]间的元素往后挪
---------实现方式是从[size(),i+1]依次由前面的数替代，a[i]=a[i-1]
删除：删除一个元素也需要移动后面的元素，如在i处插入元素，则需将[i+1,size()-1]间的元素往前挪
---------实现方式是从[pos,size()-1]依次由后面的数替代，a[i]=a[i+1]
④使用数组的注意事项：
1.首先，声明数组时，如未知所需大小，可将数组大小设为10 0000 0000，总之尽量设大
[限制其大小主要体现在下标范围。在C/C++中，数组下标的类型是std::size_t，因此数组的大小首先不能超过size_t所能表示的大小。这个数据类型是在库文件stdio.h中通过typedef声明的，对于32位程序它被定义为unsighed int，对于64位程序定义为unsigned long。前者能表示的最大大小为2^32-1，后者为2^64-1]
2.其次，注意数组下标由0开始，因此如果需要表示 1-n ，则应该设 MaxSize=n+1 ,然后让 [0]处为0或其他特殊值，合理忽略掉
3.再者，数组不支持赋值和拷贝，形如 int a[10]=arr;或int a[10];a=arr;的写法都是错误的
4.最后，最最最重要的是访问数组/向量时，注意千万不能越界，即注意两个边界，[0]和[MaxSize]
三、刷题
①JZ1 二维数组中的查找---较难:
图解如下：
代码如下：
bool Find(int target, vector<vector<int> > array) {
int n=array.size();
if(array.size()==0||array[0].size()==0) return 0;
int m=array[0].size();
if(array[n-1][m-1]<target) return 0;
for(int i=0;i<m;++i){
if(array[n-1][i]==target) return 1;
else if(array[n-1][i]>target){
for(int j=n-2;j>=0;--j){
if(array[j][i]==target) return 1;
else if(array[j][i]<target) break;
}
}
}
return 0;
}②JZ4 重建二叉树---中等
思路：
四个关键点：
1.前序遍历的首个元素即为根结点
2.中序遍历可以确定左右树元素和个数
3.前序遍历左右树先左后右排序
4.建树方法：采用前序遍历的方式建树,建树的条件是必须已知中序+前序/后序
前序遍历建树的方式---递归：
TreeNode *build(vector<int> v,int root_index,int left,int right){
if(left>right||v.size()==0) return nullptr;
TreeNode* root=new TreeNode(v[root_index])
root->left=bulid(v,left,root_index-1);
root->right=build(v,root_index+1,right);
return root;
}图解示意：
上述建树的方法，root_index==pre_left
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.size()==0||vin.size()==0||pre.size()!=vin.size()) return nullptr;
return rebuild(pre, 0, pre.size()-1, vin, 0, vin.size()-1);
}
TreeNode* rebuild(vector<int>pre,int pre_left,int pre_right,vector<int>vin,int vin_left,int vin_right){
if(pre_left>pre_right) return nullptr;
TreeNode * root=new TreeNode(pre[pre_left]);
for(int i=vin_left;i<=vin_right;++i){
if(vin[i]==root->val){
root->left=rebuild(pre, pre_left+1, i-vin_left+pre_left, vin,vin_left, i-1);
root->right=rebuild(pre,i-vin_left+pre_left+1,pre_right,vin,i+1,vin_right);
break;
}
}
return root;
}③J27 斐波那契数列---入门
关键点：
斐波那契数列的特点是从第3项开始，每一项等于前两项之和，形如 1 1 2 3 5 8 13 21......
因此，可以得到 a[0]=0,a[1]=a[2]=1, 在i>2时a[i]=a[i-1]+a[i-2]
为此可以有两种解法：递归或递推：
int Fibonacci(int n) {
/*法一：递归法*/
//递归回归点是：
if(n==0) return 0;
if(n==1||n==2) return 1;
//递推方程是：
return Fibonacci(n-1)+Fibonacci(n-2);
}int Fibonacci(int n){
/*法二：用数组递推*/
int *ans=new int[39];
if(n==0) return 0;
else if(n==1||n==2) return 1;
else{
ans[0]=0;ans[1]=1;ans[2]=1;
for(int i=3;i<=n;i++){
ans[i]=ans[i-1]+ans[i-2];
}
return ans[n];
}
}④JZ13 调整数组顺序使奇数位于偶数前面---较难
思路：
双指针遍历即可，注意一般双指针遍历可以在原数组上储存结果，也可以建立新的数组储存结果。但是本问题，因为要考虑保留各数的相对顺序，而在原数组上储存结果会导致另一边的数字顺序变乱。因此，本题用新数组储存。
/*双指针在原数组上储存会导致偶数乱序*/
vector<int> reOrderArray(vector<int>& array) {
if(array.size()<2) return array;
for(int i=0,j=0;i<array.size()&&j<array.size();++i){
if(array[i]%2!=0) swap(array[i],array[j++]);//j永远指向偶数
}
//问题是没法保证偶数也按原来顺序排列
return array;
//输入[1,2,3,4,5,6,7]结果为：[1,3,5,7,2,6,4]，偶数乱序了
}/*正确解法一：双指针用新数组储存*/
vector<int> reOrderArray(vector<int>& array) {
vector<int> reArray(array.size());
int head=0,tail=array.size()-1;
for(int i=0,j=array.size()-1;i<array.size()&&j>=0;i++,j--){
if(array[i]%2!=0) reArray[head++]=array[i];
if(array[j]%2==0) reArray[tail--]=array[j];
}
return reArray;
}/*正确解法二：冒泡排序，把偶数往后冒泡*/
vector<int> reOrderArray(vector<int>& array) {
vector<int> reArray(array);
bool changed=1;
for(int i=array.size()-1;i>0&&changed;i--){
changed=0;
for(int j=0;j<i;j++){
if(reArray[j]%2==0&&reArray[j+1]%2!=0){
changed=1;
int temp=reArray[j];
reArray[j]=reArray[j+1];
reArray[j+1]=temp;
}
}
}
return reArray;
}注意：在写for语句时中间的判断条件用','分隔表示的是 或，而非 与
⑤JZ19 顺时针打印矩阵==NC38 螺旋矩阵---较难
思路图解：
vector<int> spiralOrder(vector<vector<int> > &matrix) {
/*模拟旋转过程即可*/
if(matrix.size()==0) return {};
int m=matrix[0].size();
int n=matrix.size();
int up=0,down=n-1,left=0,right=m-1;
vector<int>v;
while(up<=down&&left<=right){//存在数
if(left<=right){//绿色线
for(int i=left;i<=right;++i){
v.push_back(matrix[up][i]);
}
}
if(up+1<down){//红色线
for(int i=up+1;i<down;++i){
v.push_back(matrix[i][right]);
}
}
if(up<down&&left<=right){//蓝色线
for(int i=right;i>=left;--i){
v.push_back(matrix[down][i]);
}
}
if(left<right&&up+1<down){//紫色线
for(int i=down-1;i>=up+1;--i){
v.push_back(matrix[i][left]);
}
}
++left;--right;
++up;--down;
}
return v;
}⑥JZ28 数组中出现次数超过一半的数字---简单
思路：该题比较简单，只要统计各数字出现次数，然后判断是否大于一半数组长度即可。注意点是，可以用向量/数组或哈希表来统计次数，但是，用向量/数组的话，因为是数字对应下标，下标对应值才是次数，因此会造成很大的空间浪费，而且若数过大时，下标可能承受不了。所以本题用哈希表存储次数。
int MoreThanHalfNum_Solution(vector<int> numbers) {
//统计每个数出现的次数，用哈希表或者数组（向量）记录皆可
//哈希表记录
map<int,int>hashTable;
int n=numbers.size();
for(int i=0;i<n;++i){
if(hashTable.count(numbers[i])==0) hashTable[numbers[i]]=1;
else ++hashTable[numbers[i]];
if(hashTable[numbers[i]]>n/2)//统计完再判断是否满足要求
return numbers[i];
}
return 0;
}⑦JZ32 把数组排成最小的数---较难
思路：有两种方法
（1）方法一：穷举法，涉及到使用全排列
介绍全排列：
全排列的思想是：
1.将一个已有的排列，每次将[i]处的数与[left]处的数交换，形成一个新的排列
2.然后缩小排列范围，从[left+1]到[right],进行全排列
3.[i]处的数与[left]处的数换回来
4.不断重复以上步骤，直到最后排列只剩一个数，即left==right
代码实现：
void perm(vector<int>&v,int left,int right){
if(left==right){
//得到一个排列
for(int i=0;i<v.size();++i) cout<<v[i];
}
return;
}
for(int i=left;i<=right;++i){
swap(v[i],v[left]);//交换第一个数，继续全排列
perm(v,left+1,right);//left之后的数全排列
swap(v[i],v[left]);//把第一个数换回来
}
}穷举法解这道题：不断的比较全排列中每种排列拼成的字符串，获得最小的字符串。因为字符串全为数字，数字在字符串中作为字符ascii码的大小关系与实际数字大小关系一致，且每种排列组成的字符串长度一样，所以可以直接进行数学比较，可用min()函数。
代码如下：
string PrintMinNumber(vector<int> numbers) {
/*方法一：暴力解法，即穷举*/
//利用自定义的全排列函数
/*string result(numbers.size(),'9');
perm(numbers,0,numbers.size()-1,result);
return result;*/
//利用STL自带的全排列函数
vector<string>strs;
for(auto &num:numbers){
strs.push_back(to_string(num));
}
sort(strs.begin(),strs.end());//第一个排列
string result(numbers.size(),'9');//此处不严谨
do{
string temp="";
for(auto str:strs){
temp+=str;
}
result=min(result,temp);
}while(next_permutation(strs.begin(),strs.end()));
return result;
}
//自定义的全排列函数
void perm(vector<int>&v,int left,int right,string &allsort){
if(left==right){
string temp="";
for(auto &num:v){
temp+=to_string(num);
}
allsort=min(allsort,temp);
return;
}
for(int i=left;i<=right;++i){
swap(v[i],v[left]);
perm(v,left+1,right,allsort);
swap(v[i],v[left]);
}
}方法一，全排列时间复杂度为O(n!)，而每次取最小值前都必须遍历数组拼成串，所以复杂度还要乘上n，因此方法一的时间复杂度为O(n!*n);空间复杂度为O(1)，因为只用了一个字符串来储存结果。另外，方法一的安全性不够，而且初始化result时并不严谨，因此不建议使用。
(2)方法二：贪婪算法
思路：要使拼成的数字最小，只需尽可能把小的数放在前面，因为如果使用默认的sort()函数对字符串排序的话，会出现[3,32]这种排序，因为3只有一个字符，所以会排在2个字符的32之前，而导致结果出错，我们想要的是323，而非332。为此，我们需要自定义排序原则。可以通过仿函数，lambda表达式，函数指针的方式定义排序原则。下面介绍这三种方式：
1.仿函数：定义一个结构，该结构只含一个bool类型的operator()(参数列表)函数
struct Prin{
bool operator()(string a，string b){
return a+b<b+a;//按a+b<b+a的次序排序
}
}2.lambda表达式：在sort第三个参数处写表达式，表达式的格式为：{函数体}，建议使用
//分两种，一种匿名lambda表达式，一种具名
//匿名：
sort(str.begin(),str.end(),[](string a,string b){
return a+b<b+a;
});
//具名
auto lam=[](string a,string b){
return a+b<b+a;
};
sort(str.begin(),str.end(),lam);3.函数指针：定义一个bool类型函数，传入sort就行
bool static Prin(string a,string b){
return a+b<b+a;
}
//加static的原因：类成员函数有隐藏的this指针,static 可以去this指针
sort(str.begin(), str.end(), Prin);于是，问题迎刃而解：
string PrintMinNumber(vector<int>numbers){
vector<string>v;
for(auto &num:numbers) v.push_back(to_string(num));
sort(v.begin(),v.end(),[](string a,string b){
return a+b<b+a;
});
string str="";
for(auto &s:v) str+=s;
return str;
}方法二采用了排序，时间复杂度为O(nlogn),
需要一个字符串向量大小为n，所以空间复杂度为O(n)
⑧JZ35 数组中的逆序对---困难
思路：
1.按常规想法，从左到右计算每个数的逆序对，然后累加起来。显然时间复杂度是O(n^2)，当n很大时，便会超时。因此，得采用其他方法。这里有一个小知识点，归并排序可以分成两段，一前一后，而逆序对恰好与前后有关。举个例子：[2 3] [1 0] 逆序对有(2,1),(2,0),(3,1),(3,0)
如果将两区间元素有序化：[2 3] [0 1],逆序对为(2,0),(2,1),(3,0),(3,1)。可以看出，在两个区间中，不管区间元素是否有序，逆序对一样。
2.归并排序：
思路是递归：将序列递推分为两段，直至只剩一个元素，再回归合并。归并排序需要两个函数，一个是分段的递归函数，一个是合并函数。其中，分段递归函数中最后一步调用合并函数。
代码如下：
//归并排序之合并,合并时排序
void merge(vector<int>&arr,vector<int> &temp,int left,int mid,int right,int &result){
int i=left,j=mid+1,k=0;
while(i<=mid&&j<=right){
if(arr[i]>arr[j]){
temp[k++]=arr[j++];
//当已升序的前区，出现元素[i]比后区的元素[j]大时，则前区该元素[i]后的元素也比后区该元素[j]大
result+=(mid-i+1);
result%=1000000007;
}
else temp[k++]=a[i++];
}
while(i<=mid) temp[k++]=arr[i++];
while(j<=right) temp[k++]=arr[j++];
for(k=0,i=left;i<=right;++i,++k)
arr[i]=temp[k];
}
//归并排序之分段递归
void mergeSort(vector<int>&arr,vector<int> &temp,int left,int right,int &result){
if(left>=right) return;//回归点
//分区
int mid=left+((right-left)>>1);
mergeSort(arr,temp,left,mid,result);
mergeSort(arr,temp,mid+1,right,result);
//按序合并
merge(arr,temp,left,mid,right,result);
}//解决本题
int InversePairs(vector<int> data){
int result=0;
vector<int>temp(data.size());
mergeSort(data,temp,0,data.size()-1,result);
return result;
}⑨JZ37 数字在升序数组中出现的次数---中等
思路：这个题其实很简单，利用已有的条件，题目说是个升序数组，所以只要左边i找到k，右边j找到k,[i,j]之间的数就只能全是k，因此就很好统计数量了,即为 j-i+1。
注意：首先，while循环必须包括i==j，因为可能只存在一次。其次，在while(i<=j)循环内，当i，j都找到k了，就得break，不然会循环超时。最后，要记得判断该数存在不。
代码如下：
int GetNumberOfK(vector<int> data ,int k) {
//双指针很好解决这一问题
int i=0,j=data.size()-1;
while(i<=j){
if(data[i]!=k) ++i;
if(data[j]!=k) --j;
if(data[i]==k&&data[j]==k) break;
}
return i<=j? j-i+1:0;
} ⑩JZ42 和为S的两个数字---中等
思路：这个题有点类似两数之和的题，但又不同，有暴力解法，即遍历，也有哈希表解法，还有双指针解法。这里提下后两种。建议使用第二种。因为时间复杂度都为O(n),但哈希解法需要O(n)的空间复杂度，而双指针空间复杂度为O(1)。
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
//特殊情况：
if(array.size()<2) return {};
//哈希解法：
unordered_set<int>hashTable;
for(int i=0;i<array.size();++i){
if(hashTable.count(array[i])==0){
hashTable.insert(array[i]);
}
else{
if((array[i]>>1)==sum) return {array[i],array[i]};
}
}
for(int i=0;i<array.size();++i){
if(hashTable.count(sum-array[i])!=0){
return {array[i],sum-array[i]};
}
}
return {};
} vector<int> FindNumbersWithSum(vector<int> array,int sum) {
//特殊情况：
if(array.size()<2) return {};
//双指针解法
int left=0,right=array.size()-1;
while(left<right){
int ans=array[left]+array[right];
if(ans==sum) break;
else if(ans<sum) ++left;
else --right;
}
if(left<right) return {array[left],array[right]};
else return {};
}⑪JZ50 数组中重复的数字---简单
思路：问题比较简单，只要返回有重复的数就行了
提供两种方法，哈希表法，耗空间但省时间，排序判断法省空间但排序耗时间。
具体代码如下：
//哈希表解法
int duplicate(vector<int>& numbers) {
// write code here
//特殊情况
if(numbers.size()<2) return -1;
/*unordered_set<int>hashTable;
for(int i=0;i<numbers.size();++i){
if(hashTable.count(numbers[i])!=0) return numbers[i];
else hashTable.insert(numbers[i]);
}
return -1;*/
}//排序判断
int duplicate(vector<int>& numbers) {
// write code here
//特殊情况
if(numbers.size()<2) return -1;
sort(numbers.begin(),numbers.end());
for(int i=0;i<numbers.size()-1;++i){
if(numbers[i]==numbers[i+1])
return numbers[i];
}
}⑫JZ51 构建乘积数组---简单
思路：
1.双指针解法：左边i右边j只要没找到该位置，就累积。代码如下:
vector<int> multiply(const vector<int>& A) {
//特殊情况
if(A.size()<2) return {};
//双指针
vector<int>result(A.size());
for(int k=0;k<A.size();++k){
int i=0,j=A.size()-1;
int sum=1;
while(i!=k&&j!=k){
sum*=(A[i++]*A[j--]);
}
while(i!=k) sum*=A[i++];
while(j!=k) sum*=A[j--];
result[k]=sum;
}
return result;
}2.前缀积解法，以空间换时间
vector<int> multiply(const vector<int>& A) {
//特殊情况
if(A.size()<2) return {};
//前缀积
vector<int>accumulate1(A.size());
vector<int>accumulate2(A.size());
vector<int>result(A.size());
accumulate1[0]=A[0];accumulate2[A.size()-1]=A[A.size()-1];
for(int i=1;i<A.size();++i){
accumulate1[i]=accumulate1[i-1]*A[i];
}
for(int i=A.size()-2;i>=0;--i){
accumulate2[i]=accumulate2[i+1]*A[i];
}
for(int i=0;i<A.size();++i){
int num=1;
if(i==0) num=accumulate2[i+1];
else if(i==A.size()-1) num=accumulate1[i-1];
else num=accumulate1[i-1]*accumulate2[i+1];
result[i]=num;
}
return result;
}⑬JZ66 机器人的运动范围---较难
插曲：一开始想着用数学推导的方式去做，好不容易算出了公式，却又发现忘了考虑给定行数列数对答案的影响，最后还是没能解答出来。这也警示我，对于编程题实际上不能依赖数学推导，不适合用数学方式直接去推导，要利用编程思想，去减少计算。自认为，目前算法编程能力上不去的主要原因是没能够利用一些算法去解决子问题，很多题目并非考的推导，而是方法。
待解：该题涉及到图的遍历，但目前还没学到，因此，先留着，之后学习了再回来解答......
试题链接：
①二维数组中的查找
②重建二叉树
③斐波那契数列
④调整数组顺序使奇数位于偶数前面
⑤顺时针打印矩阵
⑥数组中出现次数超过一半的数字
⑦把数组排成最小的数
⑧数组中的逆序对
⑨数字在升序数组中出现的次数
⑩和为S的两个数字
⑪数组中重复的数字
⑫构建乘积数组
⑬机器人的运动范围
四、参考博客：
关于数组最多能多大
