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

青衣

　　目录　　第1题：有序数组的平方
　　第2题：增减字符串匹配
　　第3题：数字的补数
　　第4题：Nim游戏
　　第5题：删除字符串中的所有相邻重复项
　　第6题：除数博弈
　　第7题：转换成小写字母
　　第8题：生成每种字符都是奇数个的字符串
　　第9题：按奇偶排序数组
　　第10题：转置矩阵
　　力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：有序数组的平方　　试题要求如下：

　　回答（C语言）：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int cmp (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}
int* sortedSquares(int* A, int ASize, int* returnSize){
  *returnSize=ASize;
  for(int i=0;i<ASize;i++){
    A[i]=A[i]*A[i];
  }
  qsort(A, ASize, sizeof(int), cmp);
  return A;
}

　　运行效率如下所示：

第2题：增减字符串匹配　　试题要求如下：

　　回答（C语言）：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* diStringMatch(char * S, int* returnSize)
{
  int N = strlen(S);
  int a=N;
  int b=0;
  int *ret = (int *)malloc(sizeof(int)*(N+1));
  *returnSize = N + 1;
  for (int i=0;i<N;i++){
    if (S[i] == 'I'){
      ret[i] = b;
      b++;
    }
    else{
      ret[i] = a;
      a--;
    }
  }
  ret[N] = b;
  
  return ret;
}

　　运行效率如下所示：

第3题：数字的补数　　试题要求如下：

　　回答（C语言）：

int findComplement(int num){
  long temp = 1;
  
  while (num >= temp){
    temp <<= 1;
  }
  return (temp - 1 - num);
}

　　运行效率如下所示：

第4题：Nim游戏　　试题要求如下：

　　回答（C语言）：

bool canWinNim(int n){
   return (n % 4 != 0); 
}

　　运行效率如下所示：

第5题：删除字符串中的所有相邻重复项　　试题要求如下：

　　回答（C语言）：

char * removeDuplicates(char * S){
  int i, cnt, len = strlen(S);
  for(i = 1, cnt = 0;i <= len;++i)
  {
    if(cnt == -1 || S[i] != S[cnt])
      S[++cnt] = S[i];
    else 
      --cnt;
  }
  return S;
}

　　运行效率如下所示：

第6题：除数博弈　　试题要求如下：

　　回答（C语言）：

bool divisorGame(int N){
  // 如果爱丽丝拿到奇数，则必输，
  // 因为奇数的因数必为奇数，则N-x必为偶数，
  // 鲍勃拿到偶数之后，只需要-1交还给爱丽丝，则爱丽丝再次拿到奇数，
  // 这样鲍勃永远拿到偶数，直到拿到2赢下比赛
  // 反过来，如果爱丽丝拿到偶数，只需要-1给鲍勃，那么鲍勃就必输。
  return N%2==0;
}

　　运行效率如下所示：

第7题：转换成小写字母　　试题要求如下：

　　回答（C语言）：

char * toLowerCase(char * str){
  for(int i=0;i<strlen(str);i++){
    if(str[i]>='A'&&str[i]<='Z')
      str[i]=str[i]+32;
  }
  return str;
}

　　运行效率如下所示：

第8题：生成每种字符都是奇数个的字符串　　试题要求如下：

　　回答（C语言）：

char * generateTheString(int n)
{
  char *ret=(char *)malloc(sizeof(char)*(n+1));
  ret[n]='\0';
  memset(ret,'a',n);
  ret[n-1]='a'+(n%2==0);
  
  return ret;
}

　　运行效率如下所示：

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

　　回答（C语言）：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortArrayByParity(int* A, int ASize, int* returnSize){
  int i=0,j=ASize-1;
  int temp=0;
  while(i<j){
    if(A[i]%2!=0 && A[j]%2==0){
      temp=A[j];
      A[j]=A[i];
      A[i]=temp;
    }
    if(A[i]%2==0)
      i++;
    if(A[j]%2!=0)
      j--;
  }
  *returnSize=ASize;
  return A;
}

　　运行效率如下所示：

第10题：转置矩阵　　试题要求如下：

　　回答（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** transpose(int** A, int ASize, int* AColSize, int* returnSize, int** returnColumnSizes){
  int** num=(int**)malloc(sizeof(int*)*(*AColSize));
  *returnColumnSizes=(int*)malloc(sizeof(int)*(*AColSize));
  *returnSize=*AColSize;
  //分配内存
  for(int i=0;i<*AColSize;i++){
    num[i]=(int*)malloc(sizeof(int)*ASize);
    returnColumnSizes[0][i] = ASize;
  }
  //矩阵转置
  for(int i=0;i<ASize;i++){
    for(int j=0;j<*AColSize;j++){
      num[j][i]=A[i][j];
    }
  }
  return num;
}

　　运行效率如下所示：