1. 二维数组查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：

1、可以考虑对每行进行二分查找

2、以右上或左下为起点，这里选择右上，依次向左扫描，如果当前值小于target，则row++（每行最后一个是该行最大的，如果它都小了，这一行都小了），如果大于，则col–（同理），直至扫描完。

代码1：以右上为起点

class Solution {
public:bool Find(int target, vector<vector<int> > array) {int row = array.size(), r = 0;//从第一行开始，注意array.size()是指vector中的向量个数，而 array[i].size()是指vector[i]中的向量个数。if(row == 0) return false;int col = array[0].size(),c = col -1;//从右上角开始即第一行最后一列while(r < row && c >= 0)//判断r和c的合理范围：r是每次++，所以其范围不能超过行数，c每次--，所以其范围不能小于0{if(array[r][c]== target) return true ;//找到目标数字if(array[r][c]<target) r++;//每行的最后一个元素都比目标数字小，说明该行的所有元素都要小于目标数字，故访问下一行的最后一个元素else  c--;//该行的最后一个元素大于目标数字，所以访问该行的倒数第二个元素，以此类推}return false;}
};

代码2：以左下为起点

class Solution {
public:bool Find(int target, vector<vector<int> > array) {int row = array.size()-1;int col = array[0].size()-1,  cl = 0;if(row < 0) return  false;while(row >= 0 && cl <= col){if(target == array[row][cl]) return true;else if (target > array[row][cl]) cl++;else   row--;}return false;}
};//代码3：二分查找，其时间复杂度为nlognpublic class Solution {public boolean Find(int [][] array,int target) {for(int i=0;i<array.length;i++){int low=0;int high=array[i].length-1;while(low<=high){int mid=(low+high)/2;if(target>array[i][mid])low=mid+1;else if(target<array[i][mid])high=mid-1;elsereturn true;}}return false;}
}

2. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路：（1）新开数组直接模拟，或者用插入排序等方法
代码1：

class Solution {
public:void reOrderArray(vector<int> &array) {vector<int> arr;for(int i = 0; i < array.size(); i++)if((array[i] & 1) == 1)arr.push_back(array[i]);for(int i = 0; i < array.size(); i++)if((array[i] & 1) == 0)arr.push_back(array[i]);for(int i = 0; i < arr.size(); i++)array[i] = arr [i];}
};

（2）首先，设置前指针指向第一个数，并且只向后移动；
然后，.设置第二个指针指向最后一个数，并且只向前移动；
最后，在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，我们就交换这两个数字。
测试不能通过！！！原来快排是不稳定的，而此题目要求相对位置不变！！！
其实，要想保证原有次序，则只能顺次移动或相邻交换。那么依然设置两个指针：
首先，begin从左向右遍历，找到第一个偶数；
然后，from从begin+1开始向后找，直到找到第一个奇数；
接着，将[begin,…,from-1]的元素整体后移一位；
最后将找到的奇数放入begin位置，然后begin++。
代码2：

class Solution {
public:void reOrderArray(vector<int> &array) {int begin = 0, end, tmp;while(begin < array.size()){//找到第一个偶数while(begin < array.size() && (array[begin] & 1) == 1)begin ++;end = begin + 1;//找到第一个奇数while(end < array.size() && (array[end] & 1) == 0)end ++;//将[begin,…,end-1]的元素整体后移一位if(end < array.size()){tmp = array[end];for(int i = end - 1; i >= begin; i--)array[i+1] = array[i];array[begin] = tmp;}else break;}}
};

3. 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.

思路：
把矩阵看成由若干个顺时针方向的圈组成，循环打印矩阵中的每个圈，每次循环打印一个圈。打印一圈通常分为四步，第一步从左到右打印一行；第二步从上到下打印一列；第三步从右到左打印一行；第四步从下到上打印一列。设置四个变量left，right，top，below，用于表示圈的方位，每一步根据起始坐标和终止坐标循环打印。

注意：最后一圈有可能不需要四步，有可能只有一行，只有一列，只有一个数字，因此我们要仔细分析打印每一步的前提条件：

打印第一步，第一步总是需要的。

打印第二步的前提条件是(top<below)

打印第三步的前提条件是(top<below && left<right)

打印第四步的前提条件是(top+1<below&&left<right)
`

class Solution {
public:vector<int> printMatrix(vector<vector<int> > matrix) {vector<int> res;if(matrix.empty()) return res;int row = matrix.size();int col = matrix[0].size();int top = 0, below = row - 1;int left = 0, right = col -1;while(left <= right && top <= below){for(int i=left; i<=right; ++i)res.push_back(matrix[top][i]);if(top < below)for(int i=top+1; i<=below; ++i)res.push_back(matrix[i][right]);if(top < below && left < right)for(int i=right-1; i>=left; --i)res.push_back(matrix[below][i]);if(top + 1 < below && left <right)for(int i=below-1; i>=top + 1; --i)res.push_back(matrix[i][left]);++ left; -- right; ++ top; --below;}return res;}
};

4. 数组中出现次数超过一半的数字

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

思路：
way1（王道）：数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。
（1）当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；
（2）如果下一个数字和我们之前保存的数字不同，则次数减1。
（3）如果次数为零，我们需要保存下一个数字，并把次数设为1。

代码：

class Solution {
public:int MoreThanHalfNum_Solution(vector<int> numbers) {if(numbers.size() == 0) return 0;int size = numbers.size();int res, count = 0;for(int i = 0; i < size; i++){if(count == 0){count ++;res = numbers[i];}else if(numbers[i] == res)//如果遍历的该元素和我们之前保存的res值相同，则count++count ++;else //否则count--count --;}//从头遍历，重新计算出现次数最多的元素的总次数count = 0;for(int i = 0; i < size; i++)if(numbers[i] == res) count ++;if(count > (size >> 1))  return res; //右移相当于除2，其时间效率要大于除法运算return 0;}
};

way2（利用快排）：数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。在随机快速排序算法中，我们先在数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小数字都排在它的左边，比选中的数字大的数字都排在它的右边。如果这个选中的数字的下标刚好是n/2，那么这个数字就是数组的中位数。如果它的下标大于n/2，那么中位数应该位于它的左边，我们可以接着在它的左边部分的数组中查找。如果它的下标小于n/2，那么中位数应该位于它的右边，我们可以接着在它的右边部分的数组中查找。

代码：

class Solution {
public:int MoreThanHalfNum_Solution(vector<int> numbers) {if(numbers.size() == 0) return 0;int start = 0, end = numbers.size()-1;int mid = numbers.size() >> 1; //右移一位等价于除2，其时间效率高于除法运算int p = Partition(numbers, start, end);while(p != mid){if(p > mid)end = p - 1;elsestart = p + 1;p = Partition(numbers, start, end);}int res = numbers[mid], count = 0;for(int i = 0; i < numbers.size(); i++)if(numbers[i] == res)count ++;if(count > mid) return res;return 0;}//快速排序算法：使得p左边数值小于p，p右边数值大于pint Partition(vector<int> a, int s, int e){int p = a[s];while(s < e){while(s < e && a[e] >= p) e--;if(s < e)  a[s] = a[e];while(s < e && a[s] <= p) s++;if(s < e)  a[e] = a[s];}a[s] = p;return s;}
};

5. 最小的k个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

思路：
（1）可以先创建一个大小为k的数据容器来存储最小的k个数字，从输入的n个整数中一个一个读入放入该容器中，如果容器中的数字少于k个，按题目要求直接返回空；
（2）如果容器中已有k个数字，而数组中还有值未加入，此时就不能直接插入了，而需要替换容器中的值。按以下步骤进行插入：
a. 先找到容器中的最大值；
b. 将待查入值和最大值比较，如果待查入值大于容器中的最大值，则直接舍弃这个待查入值即可；如果待查入值小于容器中的最大值，则用这个待查入值替换掉容器中的最大值；
c. 重复上述步骤，容器中最后就是整个数组的最小k个数字。
对于这个容器的实现，我们可以使用最大堆的数据结构，利用C++的标准模板（STL）的priority_queue来实现。

小知识 ：priority_queue（优先队列）
优先队列容器与队列一样，只能从队尾插入元素，从队首删除元素。但是它有一个特性，就是默认情况下队列中最大的元素总是位于队首，所以出队时，并非按照先进先出的原则进行，而是将当前队列中最大的元素出队。
priority_queue<int，vector, less > pq1; 　　　 // 使用递增less函数对象排序，大根堆（默认情况下为大根堆，即priority_queue q;）
priority_queue<int，vector, greater > pq2; 　　// 使用递减greater函数对象排序，小根堆

基本操作：

empty() 　　 如果队列为空，则返回真

pop()　　　　删除对顶元素，删除第一个元素

push() 　　 加入一个元素

size() 　　　 返回优先队列中拥有的元素个数

top() 　　　　返回优先队列对顶元素，返回优先队列中有最高优先级的元素

在默认的优先队列中，优先级高的先出队。在默认的int型中先出队的为较大的数。

代码：

class Solution {
public:vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {vector<int> res;if(input.size() < k || k <= 0) return res;priority_queue<int, vector<int>,less<int>> Q;//利用priority_queue来实现大根堆for(int i = 0; i < input.size(); i++){if(Q.size() < k)Q.push(input[i]);elseif(input[i] < Q.top()){Q.pop();Q.push(input[i]);}}while(!Q.empty()){res.push_back(Q.top());Q.pop();}return res;}
};

6. 连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

思路：分析计算连续子数组最大和的规律。下图是我们计算数组（1，-2，3，10，-4，7，2，-5）中子数组的最大和的过程。设置两个辅助变量，累加子数组和cur_sum、最大子数组和max_sum。初始的累加子数组和cur_sum为数组的第一个元素，初始的最大子数组和max_sum为数组的第一个元素。更新cur_sum方法：如果cur_sum>0，则继续累加；否则用下一个元素值替换累加的子数组和。更新max_sum方法：如果cur_sum >max_sum，则用累加的子数组和替换最大的子数组和。

代码：

class Solution {
public:int FindGreatestSumOfSubArray(vector<int> array) {if(array.size() == 0) return 0;int cursum = array[0], maxsum = array[0];//注意这里的赋值不能将其赋值为0，因为当出现数组元素为全为负数时，此时maxsum会一直为0，出现错误。for(int i = 1; i < array.size(); i++){if(cursum < 0) cursum = 0;cursum += array[i];if(cursum > maxsum) maxsum = cursum;}return maxsum;}
};

7.把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

思路：
（1）我们可以先思考只有两个数字的情况： [3,32] ，可以看出来 332>323 因此需要把数组改变为 [32,3] ；
（2）对于有三个数字的情况： [3,32,321] 我们两两进行比较， 332>323 于是，将 3 与 32 交换位置变成 [32,3,321] 而 3321>3213 于是将 3 与 321 继续交换位置到 [32,321,3] ；接着我们继续使用 32 进行比较，由于 32321>32132 将 32与321 进行位置交换为 [321,32,3] 此时，将数组链接起来变成 321323 即为最小的数。
具体思路：
（1）先将数字列表转化成字符串链表，这样便于在一个字符串后面直接加上另外一个字符串。也就是 “3”+“321”=“3321” 。
（2）构造一个比较函数，当 str1+str2>str2+str1 时我们认为字符串 str1>str2 。
（3）将字符串列表按照比较函数的规定进行冒泡排序（或其它方法排序），将定义为”大”的字符串放到最后。而”小”的字符串放在前面。最后将字符串列表链接起来，便是所求。对 sort() 函数进行比较函数cmp的传参，可以利用sort()函数直接对字符串列表进行排序。

代码：

class Solution {
public:string PrintMinNumber(vector<int> numbers) {string res;sort(numbers.begin(), numbers.end(), cmp);for(int i=0; i<numbers.size(); i++){res += to_string(numbers[i]);}return res;}static bool cmp(int a, int b){string sa = to_string(a);string sb = to_string(b);string ca = sa + sb;string cb = sb + sa;return ca < cb;//当ca小于cb，返回true，此时交换位置，如果返回为false，此时不交换位置，从而保证小 的字符串在前面}
};

8. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

思路：
先把数组分隔成子数组，统计出子数组内部的逆序对的数目，然后在统计出两个相邻子数组之间的逆序对的数目。合并完两个已排序的子数组后，要更新数组。
以数组{7,5,6,4}来分析统计逆序对的过程:


(a) P1 指向的数字大于P2指向的数字，表明数组中存在逆序对。P2 指向的数字是第二个子数组的第二个数字， 因此第二个子数组中有两个数字比7 小。把逆序对数目加2，并把7 复制到辅助数组，向前移动P1 和P3 。
(b) P1指向的数字小子P2指向的数字，没有逆序对。把P2指向的数字复制到辅助数组，并向前移动P2和P3
（c）P1 指向的数字大于P2指向的数字，因此存在逆序对。由于P2指向的数字是第二个子数组的第一个数字，子数组中只有一个数字比5 小。把逆序对数目加1 ，并把5复制到辅助数组，向前移动P1和P3。

代码：

class Solution {
public:int InversePairs(vector<int> data) {if(data.size() <= 1) return 0;vector<int> copy(data);//辅助数组,初始化构造拷贝，相当于将vector data数据复制一份给了vector copy。return Getcount(data, copy, 0, data.size()-1);}int Getcount(vector<int> &data, vector<int> &copy, int start, int end){if(start == end){copy[start] = data[start];return 0;}int count  = 0;int length = (end - start) / 2;int left = Getcount(copy, data, start, start+length)%1000000007; // 交换copy data，保证此时用的data是最新的，函数保证每轮copy为最新。int right = Getcount(copy, data, start+length+1, end)%1000000007;int i = start+length, j = end, index = end;while(i >= start && j >= start+length+1){if(data[i] > data[j]) {count += j - start - length;count = count % 1000000007;copy[index--] = data[i--];}else copy[index--] = data[j--];}while(i >= start) copy[index--] = data[i--];while(j >= start+length+1) copy[index--] = data[j--];return (count + left + right) % 1000000007;}
};

9. 在排序数组中查找数字

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

统计一个数字在排序数组中出现的次数。

思路：
比如：排序数组为{1,2,3,3,3,4,5}，那么数字3出现的次数就是3。
way1：遍历数组肯定就能知道某个数字的个数，此时的时间复杂度O(n)。

way2：除此之外，我们注意到，任务本质上是查找问题，而且是排序好的数组，可以尝试用二分查找算法，这样我们可以找到一个3，然后根据这个3向数组的两端遍历，找到所有的3，但是如果3是n个呢？这个算法本质上时间复杂度还是O(n)。

way3：.最后，我们发现在排序数组中，如果我们知道了第一个3和最后一个3出现的位置，那么其实也就知道了个数，那么我们能否在第一次使用二分查找之后，继续使用二分法，找到两端的3。

代码：

class Solution {
public:int GetNumberOfK(vector<int> data ,int k) {if(data.size() <= 0) return 0;int first = Findfirst(data, k, 0, data.size()-1);int last = Findlast(data, k, 0, data.size()-1);if(first != -1 && last != -1)return last - first + 1;return 0;//当k不在排序数组时则返回0，如果没有这一句话，则出现k不在数组中时，返回的则为1}int Findfirst(vector<int> data, int k, int begin, int end){if(begin > end) return -1;int mid = (begin + end) / 2;if(data[mid] == k){if(mid == 0 || data[mid -1] != k) return mid;//当中间值等于k时，如果中间值的左侧不等于k，则说明mid则为k值在数组中第一次出现的位置else end = mid -1;//否则，k值在数组中第一次出现的位置在mid的值的左侧。}else if(data[mid] > k) end = mid -1;else begin = mid + 1;return Findfirst(data, k, begin, end);}int Findlast(vector<int> data, int k, int begin, int end){if(begin > end) return -1;int mid = (begin + end) / 2;if(data[mid] == k){if(mid == data.size()-1 || data[mid + 1] != k) return mid;//当中间值等于k时，如果中间值的右侧不等于k，则说明mid则为k值在数组中最后一次出现的位置else begin = mid + 1;//否则，k值在数组中最后一次出现的位置在mid的值的右侧。}else if(data[mid] > k) end = mid - 1;else begin = mid + 1;return Findlast(data, k, begin, end);}
};

10. 数组中数字出现的次数

题目一：找出数组中只出现一次的两个数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路：异或运算符^：0与其他数字异或的结果是那个数字，相等的数字异或得0
从头到尾依次异或数组中的每一个数，那么最终的结果就是那个只出现一次的数字，比如下面这个例子
例子：2 3 4 2 3
所有数字依次异或运算：2 xor 3 xor 4 xor 2 xor 3 = (2 xor 2) xor (3 xor 3) xor 4= 0 xor 0 xor 4 = 4
最终结果4就是我们要找的那个只出现一次的数字。

数组里包含了两个只出现一次的数字，那么所有数字依次异或的结果就是这两个只出现一次的数字的异或结果。我们要想办法利用这个异或结果，把数组分为两个子数组，一个子数组包含一个只出现一次的数字，另一个数组包含另一个只出现一次的数字。由于这两个只出现一次的数字肯定不相等，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。我们在结果数字中找到第一个为1的位的位置，记为第N位。现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1，而第二个子数组的每个数字的第N位都为0。
举个栗子：1 2 3 4 2 3

 所有数字异或结果 = 1 xor 4二进制表示为：  001xor 100_______101异或结果的二进制位101，第一个为1的位的位置N=1。那么，数组所有数的二进制表示中，第N(N=1)位为1的的数为1 3 3，第N(N=1)位为0的的数为2 2 4.

class Solution {
public:void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {if(data.size() < 2)return ;int t = 0;for(int i = 0; i < data.size(); i++)t ^= data[i];//数组全部异或找出只出现一次的两个数字的异或结果，即1 xor 4（上述例子）int indexOf1 = 0;//找出异或结果中二进制位中两个数字不相同的那一位（要么为0，要么为1）while (((t & 1) == 0) && (indexOf1 < 32)){t = t >> 1;++ indexOf1;}*num1 = *num2 = 0;//以N位为1划分为两组，并进行异或。for(int i = 0; i < data.size(); i ++){if((data[i] >> indexOf1) & 1) *num1 ^= data[i];else*num2 ^= data[i];}}
};

题目二：在一个数组中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

代码：（不是太懂）

int findNum(int *arr, int n)
{int bit[32] = {0};for(int i = 0; i < n; i++){int b = 1;for(int j = 31; j >= 0; j--){int bv = arr[i]&b;if(bv != 0) bit[j]++;b <<= 1;}}int res = 0;for(int j = 0; j < 32; j++){res <<= 1;res += bit[j]%3;}return res;
}

11. 和为s的两个数字

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

思路：首先正常想的话，分别用一个跟其他所有比，时间复杂度过高。所以为了解决复杂度问题，这里采用st指向前部，ed指向后部，当a[st]+a[ed]小的时候，st++，大的时候ed–即可。因为题目要求乘数最小，根据数学计算，68<77,49<58，等等，所以可以保证该思路正确。

代码：

class Solution {
public:vector<int> FindNumbersWithSum(vector<int> array,int sum) {vector<int> res;int begin = 0, end = array.size()-1;while(begin < end){int cursum = array[begin] + array[end];if(cursum == sum){res.push_back(array[begin]);res.push_back(array[end]);break;}else if(cursum < sum)begin ++;elseend --;}return res;}
};

12. 数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

思路：
把这个数组叫做numbers，首先，这是一个无序的数组，但是所有的元素范围都在【0，n-1】
也就是说，如果这个数组是有序的，那么第i个位置的数就应该等于i，也就是numbers[i] = i 。那如果numbers[i]不等于i呢，比如下面的图,我们需要看numbers[i]和numbers[numbers[i]]的关系，分为两种情况：

代码：

bool duplicate(int numbers[], int length, int* duplication) {if(length <= 0 || numbers == nullptr)return false;for(int i = 0; i < length; i ++)if(numbers[i] > length - 1 || numbers[i] < 0)//不在范围return false;for(int i = 0; i < length; i ++){if(numbers[i] == i)continue;else {if (numbers[i] == numbers[numbers[i]]){*duplication = numbers[i];//获取重复的数字return true;}else {int tmp = numbers[i];numbers[i] = numbers[numbers[i]];numbers[numbers[i]] = tmp;}}}return false;}

13. 构建乘积数组

给定一个数组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];）

思路：
首先，仔细理解题意，B[i]是A数组所有元素的乘积，但是没有A[i]项，如果没有不能使用除法这一限制，我们可以直接将A数组的所有元素相乘，得到一个乘积，记为res，则使用公式B[i] = res/A[i]即可得到B这个乘积数组。

现在有不能使用除法的限制，只能使用其他办法，当然，一个最直观的办法是每次计算B[i]时，都计算A数组中n-1个数字的乘积，显然这需要O(n^2)的时间复杂度。

仔细分析可以发现，这种暴力解法有很多重复的计算，我们可以通过一个简单的改变来避免这些重复计算。具体如下：
我们可以把B[i]=A[0]*A[1]A[2]···*A[i-1]A[i+1]···*A[n-1]看成是两部分的乘积，第一部分是i之前的所有项，记为C[i]，即C[i]=A[0]*A[1]A[2]···A[i-1]，第二部分是i之后的所有项，记为D[i]，即D[i]=A[i+1]···*A[n-1]。
经过这样的分隔后，数组B就相当于可以用如下的矩阵来构建，B[i]为矩阵中第i行所有元素的乘积，即B[i] = C[i] *[i]。

首先B[i]=C[i]*D[i]，而C[i]可以通过自上而下的顺序进行计算，即C[0]=1,C[i]=C[i-1]*A[i-1],同理，D[i]可以通过自下而上的顺序进行计算，即
D[n-1]=1,D[i]=D[i+1]*A[i+1]。

代码：

class Solution {
public:vector<int> multiply(const vector<int>& A) {vector<int> B;if(A.size() <= 0) return B;int n = A.size();int *C = new int[n];int *D = new int[n];C[0] = 1; D[n-1] = 1;for(int i = 1; i < n; i ++)C[i] = C[i-1] * A[i-1];for(int i = n - 2; i >= 0; i --)D[i] = D[i+1] * A[i+1];for(int i = 0; i < n; i ++)B.push_back(C[i] * D[i]);return B;}
};

14.机器人运动范围

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

思路：
1.从(0,0)开始走，每成功走一步标记当前位置为true,然后从当前位置往四个方向探索，
返回1 + 4 个方向的探索值之和。
2.探索时，判断当前节点是否可达的标准为：
1）当前节点在矩阵内；
2）当前节点未被访问过；
3）当前节点满足limit限制。

代码：

class Solution {
public:int movingCount(int threshold, int rows, int cols){//vector标志每个节点是否有被访问过vector<int> vec(rows*cols, 0);return getCount(threshold, vec, 0, 0, rows, cols);}int getCount(int threshold, vector<int> &vec, int r, int c, int rows, int cols){int count = 0;//当前结点并且向四个方向探索if(r < rows && r >=0 && c >= 0 && c < cols && vec[r*cols+c] == 0 && (getSum(r)+getSum(c)) <= threshold){vec[r * cols + c] = 1;count = 1 + getCount(threshold, vec, r+1, c, rows, cols)+ getCount(threshold, vec, r-1, c, rows, cols)+ getCount(threshold, vec, r, c+1, rows, cols)+ getCount(threshold, vec, r, c-1, rows, cols);}return count;}//对行列坐标求位数和int getSum (int i){int sum = 0;while(i > 0){sum += (i % 10);i = i / 10;}return sum;}
};

15. 滑动窗口的最大值

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

思路：
采用双端队列，队列中的头节点保存的数据比后面的要大。
比如当前假如的数据比队尾的数字大，说明当前这个数字最起码在从现在起到后面的过程中可能是最大值
，而之前队尾的数字不可能最大了，所以要删除队尾元素。
此外，还要判断队头的元素是否超过size长度，由于存储的是下标，所以可以计算得到；
特别说明，我们在双端队列中保存的数字是传入的向量的下标；

代码：

class Solution {
public:vector<int> maxInWindows(const vector<int>& num, unsigned int size){vector<int> res;if(num.size() < size || size <= 0)return res;deque<int> Q;for(int i = 0; i < num.size(); i ++){////从后面依次弹出队列中比当前num值小的元素，同时也能保证队列首元素为当前窗口最大值下标while(!Q.empty() && num[i] > num[Q.back()])Q.pop_back();Q.push_back(i);////当当前窗口移出队首元素所在的位置，即队首元素坐标对应的num不在窗口中，需要弹出if(Q.front() + size <= i)Q.pop_front();///当滑动窗口首地址i大于等于size时才开始写入窗口最大值if(size <= i + 1)res.push_back(num[Q.front()]);}return res;}
};