牛客-剑指offer题解第一阶段目录
- 牛客-剑指offer题解第一阶段
- 考察点汇总
- 二维数组中的查找
- 旋转数组的最小数字
- 调整数组顺序使奇数位于偶数前面
- 顺时针打印矩阵
- 数组中出现次数超过一半的数
- 连续子数组的最大和
- 把数组排成最小的数
- 数组中的逆序对
- 数字在升序数组中出现的次数
- 数组中只出现过一次的两个数字
- 数组中的重复数字
- 构建乘积数组
- 考察点汇总
考察点汇总
数组，贪心，二分，归并排序，动态规划
二维数组中的查找
题目
考察点：思路
class Solution {public: bool Find(int target, vector<vector > array) { if(array.size()==0) return false; if(array[0].size()==0) return false; int n=array.size(); int m=array[0].size(); for(int i=0,j=m-1;i=0;) { if(target>array[i][j]) i++; else if(target<array[i][j]) j--; else return true; } return false; }};旋转数组的最小数字
题目
考察点：二分
class Solution {public: int minNumberInRotateArray(vector rotateArray) { int left=0,right=rotateArray.size()-1; while(leftrotateArray[right]) left=mid+1; else if(rotateArray[mid]<rotateArray[right]) right=mid; else right--; } return rotateArray[left]; }};调整数组顺序使奇数位于偶数前面
题目
考察点：思路
class Solution {public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型vector * @return int整型vector */ vector reOrderArray(vector& array) { int n=array.size(); vector array1(n); int odd=0; for(int i=0;i<n;i++) if(array[i]%2) odd++; int index1=0,index2=odd; for(int i=0;i<n;i++) { if(array[i]%2) array1[index1++]=array[i]; else array1[index2++]=array[i]; } return array1; }};顺时针打印矩阵
题目
考察点：思路
class Solution { public: vector printMatrix(vector<vector > matrix) { vector res; if (matrix.size() == 0) return res; int up = 0; int down = matrix.size() - 1; int left = 0; int right = matrix[0].size() - 1; while (up <= down && left <= right) { for (int i = left; i down) break; for (int i = up; i right) break; for (int i = right; i >= left; i--) res.push_back(matrix[down][i]); down--; if (up > down) break; for (int i = down; i >= up; i--) res.push_back(matrix[i][left]); left++; if (left > right) break; } return res; }};数组中出现次数超过一半的数
题目
考察点：哈希，思路
class Solution {public: int MoreThanHalfNum_Solution(vector numbers) { int n=numbers.size(); unordered_map mp; for(int i=0;in/2) return numbers[i]; } return 0; }};连续子数组的最大和
题目
考察点：动态规划，贪心
class Solution { public: int FindGreatestSumOfSubArray(vector array) { int n = array.size(); vector dp(n, 0); dp[0] = array[0]; int maxn=dp[0]; for (int i = 1; i < n; i++) { dp[i]=max(dp[i-1]+array[i],array[i]); maxn=max(maxn,dp[i]); } return maxn; }};把数组排成最小的数
题目
考察点：贪心，排序
class Solution {public: static bool cmp(string a,string b){ return a+b<b+a; } //C++11的话直接用to_string(int n) static string toString(int n){ if(n==0) return "0"; string str=""; int m; while(n){ m=n%10; n/=10; str+=('0'+m); } reverse(str.begin(),str.end()); return str; } string PrintMinNumber(vector numbers) { string res=""; vector strs; for(int i=0;i<numbers.size();i++) strs.push_back(toString(numbers[i])); sort(strs.begin(),strs.end(),cmp); for(int i=0;i<strs.size();i++) res+=strs[i]; return res; }};数组中的逆序对
题目
考察点：归并排序
class Solution { public: int mod = 1000000007; int merge(int left, int right, vector& data, vector& temp) { //终止条件 if (left >= right) return 0; //为防止left+right超出整形范围可以这样写left+(right-left)/2 int mid = (left + right) / 2; int res = merge(left, mid, data, temp) + merge(mid + 1, right, data, temp); res %= mod; int i = left, j = mid + 1; for (int k = left; k <= right; k++) temp[k] = data[k]; for (int k = left; k <= right; k++) { if (i == mid + 1) data[k] = temp[j++]; else if (j == right + 1 || temp[i] < temp[j]) data[k] = temp[i++]; else{ data[k] = temp[j++]; res += mid + 1 - i; } } return res%mod; } int InversePairs(vector data) { int n = data.size(); vector temp(n); return merge(0, n - 1, data, temp); }};数字在升序数组中出现的次数
题目
考察点：二分
class Solution {public: int find(vector& data,double k){ int left=0; int right=data.size()-1; while(leftk) right=mid-1; else left=mid+1; } return left; } int GetNumberOfK(vector data ,int k) { return find(data,k+0.5)-find(data,k-0.5); }};数组中只出现过一次的两个数字
题目
考察点：位运算，哈希
class Solution {public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型vector * @return int整型vector */ vector FindNumsAppearOnce(vector& array) { unordered_map mp; vector res; for(int i=0;i<array.size();i++) mp[array[i]]++; for(int i=0;i<array.size();i++) if(mp[array[i]]==1) res.push_back(array[i]); if(res[0]<res[1]) return res; return {res[1],res[0]}; }};数组中的重复数字
题目
考察点：思路
class Solution {public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param numbers int整型vector * @return int整型 */ int duplicate(vector& numbers) { set res; for(int i=0;i<numbers.size();i++) if(!res.insert(numbers[i]).second) return numbers[i]; return -1; }};构建乘积数组
题目
考察点：思路
class Solution {public: vector multiply(const vector& A) { vector res(A.size(),1); //前缀和 for(int i=1;i=0;i--){ res[i]*=ans; ans*=A[i]; } return res; }};