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

目录

第1题：移除重复节点

第2题：FizzBuzz

第3题：根据数字二进制下1的数目排序

第4题：最小差值1

第5题：斐波那契数

第6题：数组的相对排序

第7题：解码字母到整数映射

第8题：最长特殊序列1

第9题：单值二叉树

第10题：查找常用字符

力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。

第1题：移除重复节点

试题要求如下：

回答（C语言）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* removeDuplicateNodes(struct ListNode* head){
  char *map = malloc(20001);
  memset(map, 0, 20001);
  
  struct ListNode *pre;
  struct ListNode *cur = head;
  
  while(cur){
    if(map[cur->val] == 0){
      map[cur->val] = 1;
      pre = cur;
    }
    else {
      pre->next = cur->next;  // 删除这个重复的节点
    }
    
    cur = cur->next;
  }
  
  free(map);

  return head;
}

运行效率如下所示：

第2题：FizzBuzz

试题要求如下：

回答（C语言）：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char ** fizzBuzz(int n, int* returnSize){
    char** res = (char**)malloc(sizeof(char*)*n);
    char* s;

    for(int i = 0,m = 0;i < n;i++)
    {
        m = i+1;
        if(m%3==0 && m%5!=0)
        {
            s = (char*)malloc(sizeof(char)*5);
            strcpy(s,"Fizz");
            res[i] = s;
        }
        else if(m%3!=0 && m%5==0)
        {
            s = (char*)malloc(sizeof(char)*5);
            strcpy(s,"Buzz");
            res[i] = s;
        }
        else if(m%3==0 && m%5==0)
        {
            s = (char*)malloc(sizeof(char)*9);
            strcpy(s,"FizzBuzz");
            res[i] = s;
        }
        else
        {
            s = (char*)malloc(sizeof(char)*11);
            sprintf(s,"%d",m);
            res[i] = s;
        }
    }
    
    *returnSize = n;
    return res;
}

运行效率如下所示：

第3题：根据数字二进制下1的数目排序

试题要求如下：

回答（C语言）：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int onefigure(int num){
    int fi = 0;

    while(num != 0){
        if((num & 1) == 1){
            fi++;
        }
        num >>= 1;
    }
    
    return fi;
}

int cmp(const void * a, const void * b){
    int c = *(int *)a,d = *(int*)b;
    int f1 = 0, f2 = 0;

    f1 = onefigure(c);
    f2 = onefigure(d);
    if(f1 == f2){
        return c - d;
    }

    return f1 - f2;
}

int* sortByBits(int* arr, int arrSize, int* returnSize){
    *returnSize = arrSize;
    qsort(arr,arrSize,sizeof(int), cmp);

    return arr;
}

运行效率如下所示：

第4题：最小差值1

试题要求如下：

回答（C语言）：

int smallestRangeI(int* A, int ASize, int K){
    int min,max,aver;
    min=max=A[0];

    for(int i=0;ival);
}

运行效率如下所示：

第10题：查找常用字符

试题要求如下：

回答（C语言）：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char ** commonChars(char ** A, int ASize, int* returnSize)
{
    char** ret = (char**)malloc(101 * sizeof(char*));
    int q = 0;

    for (int i = 0; i < 101; i++) {
        ret[i] = (char*)malloc(2 * sizeof(char));
        memset(ret[i], 0, 2);
    }

    int hash[100][128] = {0};  // 用于统计所有单词的字母出现情况

    for (int i = 0; i < ASize; i ++) {
        int j = 0;
        
        while (A[i][j]) {
            hash[i][A[i][j]]++;
            j++;
        }
    }

    for (int j = 0; j < 128; j++) {
        int min = hash[0][j];
        if (min == 0) {
            continue;
        }

        for (int i = 0; i < ASize; i++) {
            if (hash[i][j] < min) {
                min = hash[i][j];
            }
        }

        while (min) {
            ret[q++][0] = j;
            min--;
        }
    }

    *returnSize = q;
    return ret;
}

运行效率如下所示：