day4：283-912-剑指offer45
283.移动0
class Solution {
public:
void moveZeroes(vector<int>& nums) {
//每遇到为0的数就将后面的数前移。没有减少操作次数
int n=nums.size();
int k=n-1,i=0,j;
while(i<k)
{
if(nums[i]==0)
{
j=i+1;
do{
nums[j-1]=nums[j];
}while((j++)<k);
nums[k]=0;
k--;
}
if(nums[i]!=0)i++;
}
}
};
912.排序数组(待改)
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
q_sort(nums,0,nums.size()-1);
return nums;
}
void q_sort(vector<int>&s,int l,int r)
{
int pos;
pos=part(s,l,r);
q_sort(s,l,pos);
q_sort(s,pos+1,r);
}
int part(vector<int>&s,int l,int r)
{
int v=s[l];
int j=l;
for(int i=l+1;i<s.size();i++)
{
if(s[i]<v)
{
j++;
if(i!=j)
{
swap(s[i],s[j]);
}
}
}
s[l]=s[j];s[j]=v;
return j;
}
};
剑指offer45
只通过了209/222后续再改
class Solution {
public:
string minNumber(vector<int>& nums) {
//数字转换为string，比较大小，排序
//数字转换为string，string转换为int:atoi
//快排
//if(nums.empty()) return 0;
if(nums.size()>1)
Quicksort(nums,0,nums.size()-1);
string s="";
for(int i=0;i<nums.size();i++)
s+=to_string(nums[i]);
return s;
}
void Quicksort(vector<int>&number,int left,int right)
{
if(left<right)
{
int pos=Quick(number,left,right);
Quicksort(number,left,pos-1);
Quicksort(number,pos+1,right);
}
}
int Quick(vector<int>&number,int left,int right)
{
int j=left,pos_value=number[left];
for(int i=left+1;i<=right;i++)
{
int a=atoi((to_string(number[i])+to_string(number[left])).c_str());
int b=atoi((to_string(number[left])+to_string(number[i])).c_str());
if(a<b)
{
j++;
if(i!=j)
{
int temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
}
number[left]=number[j];
number[j]=pos_value;
return j;
}
string to_string(int n)
{
//n>0
char s[100],ss[100];
int i=0,j=0;
while(n)
{
s[i++]=n%10+'0';
n/=10;
}
//s[i]='/0';
while(i)
{
ss[j++]=s[--i];
}
ss[j]='\0';
return ss;
}
};
第5天：506-面试题10.1合并排序的数组
506
class Solution {
public:
vector<string> findRelativeRanks(vector<int>& score) {
vector<string> res(score.size());
map<int, int> worker;
for (int i = 0; i < score.size(); ++i)
worker.insert({score[i], i});
int i = 0;
for (auto it = worker.rbegin(); it != worker.rend(); ++it, ++i) {
switch(i) {
case 0: res[it->second] = "Gold Medal";
break;
case 1: res[it->second] = "Silver Medal";
break;
case 2: res[it->second] = "Bronze Medal";
break;
default: res[it->second] = to_string(i + 1);
}
}
return res;
}
};
面试题10.1合并排序数组
class Solution {
public:
void merge(vector<int>& A, int m, vector<int>& B, int n) {
vector<int>tmp(A);
int i,j=n-1;
for(i=m;i<m+n;i++)
{
tmp[i]=B[j--];
}
j=n+m-1;
i=0;
for(int k=0;k<A.size();k++)
{
if(tmp[i]<=tmp[j])
{
A[k]=tmp[i++];
}else{
A[k]=tmp[j--];
}
}
}
};
第6天：75-215
75class Solution {
public:
void sortColors(vector<int>& nums) {
int n=nums.size();
int j=-1;
for(int i=0;i<n;i++)
{
//把0换到前面
if(nums[i]==0)
{
j++;
if(i!=j)
swap(nums[i],nums[j]);
}
}
for(int i=j+1;i<n;i++)
{
//把1换到前面
if(nums[i]==1)
{
j++;
if(i!=j)
swap(nums[i],nums[j]);
}
}
}
};
215数组中的第k最大元素
暂时略
第7天-1122-908
1122数组的相对排序
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
unordered_map<int, int> rank;
for (int i = 0; i < arr2.size(); ++i) {
rank[arr2[i]] = i;
}
sort(arr1.begin(), arr1.end(), [&](int x, int y) {
if (rank.count(x)) {
return rank.count(y) ? rank[x] < rank[y] : true;
}
else {
return rank.count(y) ? false : x < y;
}
});
return arr1;
}
};
908最下差值I
class Solution {
public:
int smallestRangeI(vector<int>& nums, int k) {
int min = nums[0], max = nums[0];
for (int x: nums) {
min = (min<=x)?min:x;
max = (max>=x)?max:x;
}
return (0<=max - min - 2*k)?max-min-2*k:0;
}
};
