牛客-劍指offer題解第一階段
目錄- 牛客-劍指offer題解第一階段
- 考察點匯總
- 二維陣列中的查找
- 旋轉陣列的最小數字
- 調整陣列順序使奇數位于偶數前面
- 順時針列印矩陣
- 陣列中出現次數超過一半的數
- 連續子陣列的最大和
- 把陣列排成最小的數
- 陣列中的逆序對
- 數字在升序陣列中出現的次數
- 陣列中只出現過一次的兩個數字
- 陣列中的重復數字
- 構建乘積陣列
- 考察點匯總
考察點匯總
陣列，貪心，二分，歸并排序，動態規劃
二維陣列中的查找
題目
考察點：思路
class Solution {
public:
bool Find(int target, vector<vector<int> > 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<n&&j>=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<int> rotateArray) {
int left=0,right=rotateArray.size()-1;
while(left<right)
{
int mid=(left+right)/2;
if(rotateArray[mid]>rotateArray[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<int> reOrderArray(vector<int>& array) {
int n=array.size();
vector<int> 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<int> printMatrix(vector<vector<int> > matrix) {
vector<int> 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 <= right; i++)
res.push_back(matrix[up][i]);
up++;
if (up > down)
break;
for (int i = up; i <= down; i++)
res.push_back(matrix[i][right]);
right--;
if (left > 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<int> numbers) {
int n=numbers.size();
unordered_map<int,int> mp;
for(int i=0;i<n;i++)
{
mp[numbers[i]]++;
if(mp[numbers[i]]>n/2)
return numbers[i];
}
return 0;
}
};
連續子陣列的最大和
題目
考察點：動態規劃，貪心
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
int n = array.size();
vector<int> 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<int> numbers) {
string res="";
vector<string> 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<int>& data, vector<int>& 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<int> data) {
int n = data.size();
vector<int> temp(n);
return merge(0, n - 1, data, temp);
}
};
數字在升序陣列中出現的次數
題目
考察點：二分
class Solution {
public:
int find(vector<int>& data,double k){
int left=0;
int right=data.size()-1;
while(left<=right){
int mid=left+(right-left)/2;
if(data[mid]>k)
right=mid-1;
else
left=mid+1;
}
return left;
}
int GetNumberOfK(vector<int> 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<int> FindNumsAppearOnce(vector<int>& array) {
unordered_map<int,int> mp;
vector<int> 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<int>& numbers) {
set<int> res;
for(int i=0;i<numbers.size();i++)
if(!res.insert(numbers[i]).second) return numbers[i];
return -1;
}
};
構建乘積陣列
題目
考察點：思路
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> res(A.size(),1);
//前綴和
for(int i=1;i<A.size();i++)
res[i]=res[i-1]*A[i-1];
//后綴和
int ans=1;
for(int i=A.size()-1;i>=0;i--){
res[i]*=ans;
ans*=A[i];
}
return res;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/526844.html
標籤：其他
上一篇：2022.11.1每日一題