目錄
第1題:存在重複元素
第2題:2的幂
第3題:移動零
第4題:缺失數字
第5題:第一個錯誤的版本
第6題:按摩師
第7題:3的幂
第8題:求1+2+...+n
第9題:數值變為0的步數
第10題:有多少小于目前數字的數
力扣(LeetCode)定期刷題,每期10道題,業務繁重的同志可以看看我分享的思路,不是最高效解決方案,隻求互相提升。
試題要求如下:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5CO4EGZ0UDZiVWZwATZiZDOzQmN0AzY0QzYxAjZ2EjYk9CX5d2bs92Yl1iclB3bsVmdlR2LcNWaw9CXt92Yu4GZjlGbh5yYjV3Lc9CX6MHc0RHaiojIsJye.png)
int compare(const void *a, const void *b){
return *(int*)a - *(int*)b;
}
bool containsDuplicate(int* nums, int numsSize){
qsort(nums, numsSize, sizeof(int), compare);
for(int i = 0; i < numsSize - 1; i++){
if(nums[i] == nums[i+1]){
return true;
}
}
return false;
}
運作效率如下所示:
bool isPowerOfTwo(int n){
while(n%2==0&&n>1){
n=n/2;
}
if(n==1){
return true;
}
else{
return false;
}
}
void moveZeroes(int* nums, int numsSize){
for(int i=0,j = 0,temp=0; j < numsSize;++j) {
if(nums[j] != 0) {
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
++i;
}
}
}
int missingNumber(int* nums, int numsSize){
int ans = numsSize*(numsSize + 1)/2, i;
for(i = 0; i < numsSize; i++){
ans -= nums[i];
}
return ans;
}
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
int firstBadVersion(int n) {
long low=1;
long high=n;
while(low<high){
long mid=(low+high)/2;
if(!isBadVersion(mid)){
low=mid+1;
}
else{
high=mid;
}
}
return low;
}
//設dp[i]表示第i個房屋之前的最高金額,則求dp[numsSize-1]即可。
//狀态轉移方程:
//dp[0] = nums[0]
//dp[1] = max(nums[1], nums[0])
//dp[i] = max(dp[i-2] + nums[i], dp[i-1])(i>=2)
int massage(int* nums, int numsSize){
if(!nums || numsSize == 0)
return 0;
if(numsSize == 1)
return nums[0];
int *dp = (int*)malloc(sizeof(int) * numsSize);
dp[0] = nums[0];
dp[1] = fmax(nums[1], nums[0]);
for(int i = 2; i < numsSize; i++){
dp[i] = fmax(dp[i-2] + nums[i], dp[i-1]);
}
return dp[numsSize - 1];
}
bool isPowerOfThree(int n){
if (n == 0)
return false;
while(n%3==0){
n/=3;
}
if(n==1)
return true;
return false;
}
//(1)如果多個變量均非0(包括None、False等),那麼傳回最後一個變量的值。如3 and 2 and 'a'的傳回值為'a';
//(2)如果多個變量中存在0值,則傳回第一個0值。如1 and 'a' and 0 and None的傳回值為0。
int sumNums(int n){
int res = n;
n && (res += sumNums(n-1));
return res;
}
int numberOfSteps (int num){
int cou=0;
while(num!=0){
if(num%2==0){
num/=2;
}
else{
num-=1;
}
cou++;
}
return cou;
}
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize){
int* data_buf=(int*)malloc(sizeof(int)*(numsSize+1));
memset(data_buf,'\0',sizeof(int)*(numsSize+1));
for(int i=0;i<numsSize;i++){
for(int j=0;j<numsSize;j++){
if(nums[j]<nums[i])
data_buf[i]++;
}
}
data_buf[numsSize]='\0';
*returnSize=numsSize;
return data_buf;
}