剑指offer 数组

剑指offer 数组

剑指offer 数组

• 1. 题目： 构建乘积数组
• • 解题1：
  • 解题2：
• 2.题目： 数组中重复的数字
• • 解法1：原始循环
  • 解法2
• 3.题目：数组中出现次数超过一半的数字
• • 解法1：哈希表
  • • map 与unordered_map
    • 红黑树
  • 解法2
• 4.题目：和为S的两个数字
• • 解法1：最原始的遍历方法for循环叠加查找
  • 解法2：双指针
• 5.题目：数字在排序数组中出现的次数
• • 解法1：直接解
  • 解法2：哈希
  • 解法3：二分法
• 6.题目： 调整数组顺序使奇数位于偶数前面
• • 解法1：两数组合并
  • 解法2：一数组直接累加
• 7.题目： 二维数组的查找
• • 解法1：直接上循环
  • 解法2：二分法
• 8. 题目：把数组排成最小的数
• • 解法1：全排列
  • 解法2：
• 9. 题目： 重建二叉树
• • 解法1：迭代
• 10.题目： 顺时针打印矩阵描述
• 11. 题目： 数组中的逆序对
• • 暴力法
  • 递归

** 知识点：数组 语言：C++

1. 题目： 构建乘积数组

题目描述
给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）
对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在

解题1：

思路：

把对应的第n个数视为1

可以左边相乘，再右边乘
left[1] = A[0]
right[1]= A[2]*A[3]*A[4]
B[1] = left[1]*right[1]

代码：

class Solution {
public:vector<int> multiply(const vector<int>& A) {vector<int> B(A.size(),1);//一定要写范围，否则出现段错误问题for(int i=1;i<A.size();i++)//left[i]{B[i] = B[i-1] * A[i-1];}int temp=1;//用变量代替right[i]for(int j=A.size()-2;j>=0;j--){temp = temp*A[j+1];B[j] =  B[j]*temp;// left[i]*right[i]}return B;                   }
};

疑问：for循环中–i 和i–，运行结果都是正确的。运行时间也一样，只有占用内存有微小差别。这是怎么回事？

解题2：

思路：直接把需要忽略的A[i]视为1，思路简单，但时间复杂度为n^2
for循环 1把A[i]赋值给一变量
for循环 2 A[i]视为1
for循环 3把变量重新赋值给A[i]

代码：

class Solution {
public:vector<int> multiply( vector<int>& A) {vector<int> B(A.size(),1);int temp=0;for(int i=0;i<A.size();i++){temp = A[i];A[i] = 1;B[i] = 1;for(int j=0;j<A.size();j++){B[i] = B[i] * A[j];}A[i] = temp;}return B;}
};

疑问：一开始 A[i] = 1；A[i] = temp;运行错误，显示 error: cannot assign to return value because function ‘operator[]’ returns a const value。但 B[i] = 1;就没有问题
查找后发现
将A值作为const向量传递。 这样，内部代码就可以读取索引i处的值，但不能回写新值。这个是程序自带的。而B是自己写的吗，没有带const。将A定义处的const删除即可。

2.题目： 数组中重复的数字

解法1：原始循环

最原始的循环，花费时间长

代码：

    if(numbers.size()==0){return -1;}for (int i=0; i<numbers.size(); i++){for (int j=i+1; j<numbers.size(); j++){if (numbers[i] == numbers[j]) return numbers[i];}}return -1;

注意：return -1；的位置，一定要在所有for之外
error： non-void function does not return a value in all control paths [-Werror,-Wreturn-type]
说明你还有情况没有考虑到

解法2

对数组中元素进行排序，有重复的参数会排在相邻位置

代码：

   if(numbers.size()==0){return -1;}sort(numbers.begin(), d());for(int i=0;i<numbers.size();i++){if(numbers[i] == numbers[i+1]){return numbers[i];}}return -1;
}

3.题目：数组中出现次数超过一半的数字

题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

解法1：哈希表

代码：

class Solution {
public:int MoreThanHalfNum_Solution(vector<int> numbers) {unordered_map<int, int> map;//哈希表for( int num : numbers) //对数组中数出现次数计数map[num]+=1;for( int num : numbers){if(map[num] > numbers.size()/2){return num;}      }return 0;}
};

注：map[i]不必赋初值，这里用到unordered_map

map 与unordered_map

红黑树

红黑树为非严格平衡二叉查找树

5条定义
1.节点颜色有红有黑
2.根节点一定为黑
3.叶子节点为黑
4.任意节点到叶子节点经过的黑色节点数目相同
5.不会有连续的红色节点

解法2

如果存在这样一个数，顺序排序后，它的位置一定大于数组的中位数

代码：

class Solution {
public:int MoreThanHalfNum_Solution(vector<int> numbers) {int k = numbers.size()/2; //数组的中位数int num=0; //计数变量sort(numbers.begin(), d()); //顺序排序for( int i=0;i<numbers.size();i++){if(numbers[k] == numbers[i])num++;}if(num > numbers.size()/2){return numbers[k];}return 0;}
};

4.题目：和为S的两个数字

题目描述：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
对应每个测试案例，输出两个数，小的先输出。

思路：数组本身就是递增的顺序排列，两数乘积最小的数值一定在数组的最边边。说明遍历此数组的话第一组符合条件的元素就是我们所求的。

解法1：最原始的遍历方法for循环叠加查找

代码：

class Solution {
public:vector<int> FindNumbersWithSum(vector<int> array,int sum) {int k = 0;vector<int> num;for(int i=0;i<array.size();i++){for(int j=i+1;j<array.size();j++) //遍历{if(array[i]+array[j] == sum){place_back (array[i]);place_back (array[j]);k++;break;}}if(k!=0) break; //加上 可限制个数为一对。否则输出所有}return num;//return 一般返回指针或变量}  };

解法2：双指针

一个指针指向头部，一个指向尾部

1. 如果arr[i] + arr[j] == sum , 说明是可能解
2. 否则如果arr[i] + arr[j] > sum, 说明和太大，所以–j
3. 否则如果arr[i] + arr[j] < sum, 说明和太小，所以++i

代码：

class Solution {
public:vector<int> FindNumbersWithSum(vector<int> array,int sum) {int i =0;//数组头部int j = array.size()-1;//数组尾部vector<int> num;while(i<j){if(array[i]+array[j]==sum)//两数之和为place_back(array[i]);place_back(array[j]);break;}else if(array[i]+array[j]<sum)//两数之和<sum{i++;}else j--;//两数之和>sum}return num;}
};

注：emplace_back和push_back一样都是可添加右值。emplace_back在空间优化上优于push_back。

5.题目：数字在排序数组中出现的次数

题目描述：统计一个数字在升序数组中出现的次数。

解法1：直接解

代码：

class Solution {
public:int GetNumberOfK(vector<int> data ,int k) {int count = 0;for (int val : data) {if (val == k)++count;}return count;}
};

解法2：哈希

class Solution {
public:int GetNumberOfK(vector<int> data ,int k) {unordered_map<int, int> mp;for(int i:data){mp[i]+=1;}for(int  i:data){if(i == k){return mp[i];}}  return 0;	//	如没有匹配值的情况
};

注：在此需要考虑如没有匹配值的情况，否则可能出现错误：
error: non-void function does not return a value in all control paths [-Werror,-Wreturn-type]
意思是不是所有分支都有返回值

解法3：二分法

一般有序且求次数的数组考虑二分法

本次采用lower_bound() ；upper_bound() 函数。其定义在头文件中。
upper_bound() 函数定义用于在指定范围内查找大于目标值的第一个元素。
语法格式：

//查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,const T& val);
//查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,const T& val, Compare comp);

注：其中，first 和 last 都为正向迭代器，[first, last) 用于指定该函数的作用范围；val 用于执行目标值；comp 作用自定义查找规则，此参数可接收一个包含 2 个形参（第一个形参值始终为 val）且返回值为 bool 类型的函数，可以是普通函数，也可以是函数对象。

代码：

class Solution {
public:int GetNumberOfK(vector<int> data,int k) {return upper_bound(data.begin(), d(), k) - lower_bound(data.begin(), d(), k);}
};

6.题目： 调整数组顺序使奇数位于偶数前面

解法1：两数组合并

思路：分别构造奇数组，偶数组再将他们合并
代码：

class Solution {
public:vector<int> reOrderArray(vector<int>& array) {int k=0,j =0;vector<int> odd,doub;for(int i=0;i<array.size();i++){if(array[i]%2 == 0){doub[j] =array[i];//偶数组++j;}else{odd[k] =array[i];//奇数组++k;}}odd.d(), doub.begin(),d());return odd;// write code here}
};

本来想用奇偶数组分别从0累加（如涉及到 数组+=1；数组变量++；），但此种方法需要初始化odd,doub数组范围。如果不确定会输出错误值或段错误
如：段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起
你的输出为:

所以采用emplace_back累加，insert合并数组。

class Solution {
public:vector<int> reOrderArray(vector<int>& array) {int k,j =0;vector<int> odd,doub,sum;for(int i:array){if(i%2 == 0)     	 //偶{place_back(i);}place_back(i);//奇}}odd.d(), doub.begin(),d());//合并return odd;}
};

解法2：一数组直接累加

这个新设了一个数组，直接加在后面。上面的算法新建了两个数组

//在下愚钝（哎），第一次见到这个。查了下目的是提高输入输出速度
static const auto io_sync_off = [](){// turn off syncstd::ios::sync_with_stdio(false);//主要作用是提高c++ cin cout 的速度，cin和cout原本的效率较低，涉及到要将输入输出存入缓存区// untie in/out streamsstd::cin.tie(nullptr);//主要作用是将cin和cout解除绑定，因为std :: cin默认是与std :: cout绑定的，所以每次操作的时候（也就是调用”<<”或者”>>”）都要刷新（调用flush），这样增加了IO的负担，通过tie(nullptr)来解除std :: cin和std :: cout之间的绑定，来降低IO的负担使效率提升
return nullptr;
}();
class Solution {
public:vector<int> reOrderArray(vector<int>& array) {vector<int> ans(array.size());int index =0;for(int i = 0; i < array.size(); ++i){if(array[i] % 2) ans[index++] = array[i];}for(int j  = 0; j< array.size(); ++j){if(array[j] % 2 == 0) ans[index++] = array[j];}return ans;}
};

7.题目： 二维数组的查找

题目：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
给定 target = 7，返回 true。

给定 target = 3，返回 false。

解法1：直接上循环

static const auto io_sync_off = [](){// turn off syncstd::ios::sync_with_stdio(false);//主要作用是提高c++ cin cout 的速度，cin和cout原本的效率较低，涉及到要将输入输出存入缓存区// untie in/out streamsstd::cin.tie(nullptr);//主要作用是将cin和cout解除绑定，因为std :: cin默认是与std :: cout绑定的，所以每次操作的时候（也就是调用”<<”或者”>>”）都要刷新（调用flush），这样增加了IO的负担，通过tie(nullptr)来解除std :: cin和std :: cout之间的绑定，来降低IO的负担使效率提升
return nullptr;
}();class Solution {
public:bool Find(int target, vector<vector<int> > array) {int conlum = array[0].size()-1;for(int i=0;i<array.size();i++){
//             if(array[i][0] <= target && array[i][conlum] >= target)
//             {for(int k=0;k<=conlum;k++){if(array[i][k]==target)return true;}}
//        }return false;}
};

有个问题：想判断target是否在首尾的范围内，加了句判断出现了段错误

if(array[i][0] <= target && array[i][conlum] >= target)//段错误
if(array[i][0] <= target)			//可以正常运行
if( array[i][conlum] >= target)		//可以正常运行
if(array[i][0] <= target & array[i][conlum] >= target)//可以正常运行

奇怪。。。

解法2：二分法

有序查找一般情况下会优先考虑二分法
不同的是在这里value应该设置在哪里。设在中间不好判断位置，又不能行列都除以2.既然行，列都是递增。可以从左下或右上判断，可以同时排除value所在的·行列。

代码：

static const auto io_sync_off=[](){ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return nullptr;
}();
class Solution {
public:bool Find(int target, vector<vector<int> > array) {int row = array.size();int column = array[0].size();if(row > 0 && column > 0){int i = 0;int j = column - 1;while(i < row && j >= 0){if(target == array[i][j]){return true;}else if(target < array[i][j]){j--;}else{i++;}}}return false;}
};

8. 题目：把数组排成最小的数

转载
题目描述：描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
示例1
输入：[3,32,321]
返回值：“321323”

其实看到输出的返回值就应该反应过来，这个肯是创建一个字符串变量

解法1：全排列

把所有的可能情况都排列出来，然后对他们比较大小获取题目要求的最小值。这里用到了全排列函数next_permutation

prev_permutation next_permutation 函数作用一致。不同的是如果字符串当前序列是a[n]，一个是a[n-1]，一个是a[n+1]
而且要注意的是在使用次函数之前，对其进行升序的排列。要不然他只会按顺序对此顺序之后的进行升序全排列。

class Solution {
public:string PrintMinNumber(vector<int> nums) {vector<string> str;for (int val : nums) {str.push_back(to_string(val));}   sort(str.begin(), d());string ret(nums.size(), '9');//有nums.size()那么多个位数的9.这里设为最大值9，到 ret = min(ret, tmp)比较时，获取的就是tmp。do {string tmp = "";for (string val : str)tmp += val;ret = min(ret, tmp);} while (next_permutation(str.begin(), d()));return ret;}
};

解法2：

最核心的思想:
比较两个字符串s1, s2大小的时候，先将它们拼接起来，比较s1+s2,和s2+s1那个大，如果s1+s2大，那说明s2应该放前面
这里用到了字符串变量的知识
1.对字符串变量的赋值
在定义了字符串变量后，可以用赋值语句对它赋予一个字符串常量，如

str = "China  ";

注意：stin是字符串变量，不是字符数组名，用字符数组时是不能这样做的，
如 定义字符数组

   char str [10];str=“kitty” ; /错误，str不是字符串变量而是参数组名//可以写成这种形式char arr[10] = “kitty”;

2.字符串连接直接用加号
3.字符串直接用运算关系符
如 ==，<,>,!=…

class Solution {
public:string PrintMinNumber(vector<int> nums) {vector<string> str;for (int val : nums) str.push_back(to_string(val));sort(str.begin(), d(), [](string a, string b)//这里用的是lambda{return a + b < b + a;});string ret = "";for (string s : str) ret += s;return ret;}
};

9. 题目： 重建二叉树

描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
示例1
输入：[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值：{1,2,5,3,4,6,7}

解法1：迭代

源文章链接：

/*** Definition for binary tree* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* reConstructBinaryTree(vector pre,vector vin) {int vinlen=vin.size();if(vinlen==0)return NULL;vector pre_left, pre_right, vin_left, vin_right;//创建根节点，根节点肯定是前序遍历的第一个数TreeNode* head = new TreeNode(pre[0]);//找到中序遍历根节点所在位置,存放于变量gen中int gen=0;for(int i=0;i<vinlen;i++){if(vin[i]==pre[0]){gen=i;break;}}//对于中序遍历，根节点左边的节点位于二叉树的左边，根节点右边的节点位于二叉树的右边// 左子树for(int i = 0; i < gen; i++){vin_left.push_back(vin[i]);pre_left.push_back(pre[i+1]);//先序第一个为根节点}// 右子树for(int i = gen + 1; i < vinlen; i++){vin_right.push_back(vin[i]);pre_right.push_back(pre[i]);}//递归，执行上述步骤，区分子树的左、右子子树，直到叶节点head->left = reConstructBinaryTree(pre_left, vin_left);head->right = reConstructBinaryTree(pre_right, vin_right);return head;}
};

10.题目： 顺时针打印矩阵描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
示例1
输入：
[[1,2],[3,4]]
返回值：
[1,2,4,3]

解法1：下标遍历
顺时针遍历，先在行上走到终点++，再在列上走到终点++。
从最大值走到最小值–。此为一个循环。如矩阵参数较大，就再多几个循环。可用迭代方法计算

class Solution {
public:void conclu(int conlumn,int row,int intitalx,int intitaly,vector<vector<int> > &matrix,vector<int> &resualt){for(int i =intitaly ;i<=conlumn;++i) resualt.push_back(matrix[intitalx][i]); //行增加for(int j =intitalx+1;j<=row;++j) resualt.push_back(matrix[j][conlumn]);//列增加int h = row - intitalx +1;if(h>1){for(int m =conlumn-1;m>=intitaly;--m) //行减小resualt.push_back(matrix[row][m]);}int w = conlumn -intitaly+1;if(w>1){for(int n = row-1;n>=intitalx+1;--n) resualt.push_back(matrix[n][intitaly]); //列减小}}vector<int> printMatrix(vector<vector<int> >&matrix){vector<int> resualt;pty()) return resualt;int row = matrix.size()-1, conlumn = matrix[0].size()-1;int intitalx=0,intitaly=0;while(intitalx<(row+1)&&intitaly<(conlumn+1))//知道要循环但不知道循环多少次就用while{conclu(conlumn--, row--, intitalx++, intitaly++, matrix, resualt); //迭代}return resualt;}
};

11. 题目： 数组中的逆序对

暴力法

class Solution {
public:int InversePairs(vector<int> data) {long long num=0;pty()) return 0;for(int i=1;i<data.size();i++){for(int j=0;j<i;j++){if(data[j]>data[i])num+=1;}}num =num%1000000007;return num;}
};

递归

class Solution {
public:int InversePairs(vector<int> data) {vector<int> r(data.begin(),d());long int count=0;mergeSort(data,r,0,data.size()-1,count);return count%1000000007;}void mergeSort(vector<int> &v,vector<int> &r,int begin,int end,long int &count){if(begin>=end)    return;int half=(begin+end)/2;mergeSort(v,r,begin,half,count);mergeSort(v,r,half+1,end,count);int i=begin,j=half+1,k=begin;while(i<=half && j<=end){if(v[i]<=v[j])    r[k++]=v[i++];else{r[k++]=v[j++];count+=half-i+1;}}//r[k++]=v[i++];while(i<=half){r[k++]=v[i++];//count+=end-half;}while(j<=end)    r[k++]=v[j++];i=begin;k=begin;while(i<=end)    v[i++]=r[k++];}
};