力扣(LeetCode)刷题，简单题(第11期)

江南才子

　　目录　　第1题：二进制表示中质数个计算置位
　　第2题：消失的数字
　　第3题：最小绝对差
　　第4题：按奇偶排序数组II
　　第5题：主要元素
　　第6题：逐步求和得到正数的最小值
　　第7题：找不同
　　第8题：魔术索引
　　第9题：托普利茨矩阵
　　第10题：下一个更大元素1
　　力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：二进制表示中质数个计算置位　　试题要求如下：

　　回答（C语言）：

// 判断是否为质数
bool isPrime(int num){
  if (num < 2) return false;
  int i;
  for(i = 2; i * i <= num; i++) {
    if (num % i == 0) return false;
  }
  return true;
}
int getOneCount(int num){
  int count = 0;
  while (num != 0) {
    num &= (num - 1);
    count++;
  }
  return count;
}
// 算出含有1的个数m，m是否为素数
int countPrimeSetBits(int L, int R){
  int i,num,count = 0;
  for (i = L; i <= R; i++) {
    num = getOneCount(i);
    if (isPrime(num)) count++;
  }
  return count;
}

　　运行效率如下所示：

第2题：消失的数字　　试题要求如下：

　　回答（C语言）：

int missingNumber(int* nums, int numsSize){
  int i=0;
  int* data_buf=(int*)malloc(sizeof(int)*(numsSize+1));
  memset(data_buf,0,sizeof(int)*(numsSize+1));
  for(i=0;i<numsSize;i++){
    data_buf[nums[i]]++;
  }
  for(i=0;i<numsSize;i++){
    if(data_buf[i]==0){
      break;
    }
  }
  data_buf[numsSize]='\0';
  return i;
}

　　运行效率如下所示：

第3题：最小绝对差　　试题要求如下：

　　回答（C语言）：

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int cmp(const void* num, const void* num2){
  return *(int*)num - *(int*)num2;
}
int** minimumAbsDifference(int* arr, int arrSize, int* returnSize, int** returnColumnSizes){
   
  qsort(arr,arrSize,sizeof(int),cmp);
  int **returnarra = malloc(sizeof(int*)*arrSize), count = 0;
  int *ColumnSizes = (int*)malloc(sizeof(int)* arrSize);
  assert(returnarra!=NULL && ColumnSizes!=NULL);
  int different, min = abs(arr[0]-arr[arrSize-1]);
  for(int i = 1; i < arrSize;i++){
    if((different = abs(arr[i] - arr[i-1])) < min){
      min = different;
    }
  }
  for(int i = 1; i < arrSize; i++){
    different = abs(arr[i] - arr[i-1]);
    if(different == min){
      int *pair = malloc(sizeof(int) * 2);
      pair[0] = arr[i-1];
      pair[1] = arr[i];
      returnarra[count] =pair;
      ColumnSizes[count++] = 2;
    }
  }
  
  *returnSize = count;
  *returnColumnSizes = ColumnSizes;
  return returnarra; 
}

　　运行效率如下所示：

第4题：按奇偶排序数组II　　试题要求如下：

　　回答（C语言）：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortArrayByParityII(int* A, int ASize, int* returnSize){
  //int* arr = (int*)malloc(sizeof(int) * ASize);
  *returnSize = ASize;
  int odd = 1;
  for (int i = 0; i < ASize; i += 2) {
    if (A[i] % 2 != 0) {
      while (A[odd] % 2 == 1) {
        odd += 2;
      }
      int tmp = A[odd];
      A[odd] = A[i];
      A[i] = tmp;
    }  
  }
  return A;
}

　　运行效率如下所示：

第5题：主要元素　　试题要求如下：

　　回答（C语言）：

int majorityElement(int* nums, int numsSize){
  int cur;
  int counter = 0;
  for (int i = 0; i < numsSize; i++) {
    if (counter == 0) {
      counter = 1;
      cur = nums[i];
    } else if (cur != nums[i]) {
      counter--;
    } else {
      counter++;
    }     
  }
  if(counter > 0)
    return cur;
  else
    return -1; 
}

　　运行效率如下所示：

第6题：逐步求和得到正数的最小值　　试题要求如下：

　　回答（C语言）：

int minStartValue(int* nums, int numsSize)
{
  int min = nums[0], count = 0;
  for (int i = 0; i < numsSize; i ++)
  {
    count += nums[i];
    min = min < count ? min : count;
  }
  min = 1 - min;
  
  return min > 0 ? min : 1;
}

　　运行效率如下所示：

第7题：找不同　　试题要求如下：

　　回答（C语言）：

char findTheDifference(char * s, char * t){
  int sum_s = 0,sum_t = 0;
  for(int i = 0;i < strlen(t);i++){
    if(i < strlen(t)-1){
      sum_s +=s[i];
    }
    sum_t +=t[i];
  }
  
  return sum_t-sum_s;
}

　　运行效率如下所示：

第8题：魔术索引　　试题要求如下：

　　回答（C语言）：

int findMagicIndex(int* nums, int numsSize){
  for(int i = 0;i < numsSize;i++){
    if(nums[i] == i){
      return i;
    }
  }
  return -1;
}

　　运行效率如下所示：

第9题：托普利茨矩阵　　试题要求如下：

　　回答（C语言）：

//(r1, c1) (r2, c2)满足对角线的特点 r1 - c1 == r2 - c2
bool isToeplitzMatrix(int** matrix, int matrixSize, int* matrixColSize){
  for(int i = 1;i < matrixSize;++i)
  {
    for(int j = 1;j < matrixColSize[0];++j)
    {
      if(matrix[i-1][j-1] != matrix[i][j])
        return false;
    }
  }
  return true;
}

　　运行效率如下所示：

第10题：下一个更大元素1　　试题要求如下：

　　回答（C语言）：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
  int* res = (int*)malloc(sizeof(int) * nums1Size);
  int flag = 0;
  int i,j;
  
  for(i = 0; i < nums1Size; i++) {
    for(j = 0; j < nums2Size; j++) {
      if(nums1[i] == nums2[j]) {
        flag = 1;
        continue;
      } 
      else if(nums1[i] < nums2[j] && flag == 1) {
        res[i] = nums2[j];
        break;
      } 
    }
    if(j == nums2Size) {
      res[i] = -1;
    }
    flag = 0;
  }
  *returnSize = nums1Size;
  return res;
}

　　运行效率如下所示：