写点什么

力扣 (LeetCode) 刷题,简单题 (第 14 期)

发布于: 2021 年 03 月 24 日
力扣(LeetCode)刷题,简单题(第14期)

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


第 1 题:配对交换


试题要求如下:



解答思路:


分别取出 num 的偶数位与奇数位


然后让偶数位右移一位奇数位左移一位


让移位后的偶数与奇数异或即可得最终结果


回答(C 语言):


int exchangeBits(int num){    int even_number = 0xaaaaaaaa;    //1010 1010 ...... 取出偶数    int uneven_number = 0x55555555;  //0101 0101 ...... 取出奇数     even_number = num & even_number;    uneven_number = num & uneven_number;     even_number = even_number >> 1;    uneven_number = uneven_number << 1;     return even_number | uneven_number;}
复制代码


运行效率如下所示:





第 2 题:比较字符串最小字母出现频次


试题要求如下:



解答思路:


回答(C 语言):


/** * Note: The returned array must be malloced, assume caller calls free(). */#define NUM 26int QureySmallWord (char *str, int *hash){    memset(hash, 0, NUM * sizeof(int));    int len = strlen(str);    int res = 0;    for (int i = 0; i < len; i++) {        // 统计字符串中各个字符出现的频次,已默认是字典序        hash[str[i] - 'a']++;    }    for (int i = 0; i < NUM; i++) {        // 获取字符串中最小字母的出现频次,即hash表中第一个非零值        if (hash[i] > 0) {            res = hash[i];            break;        }    }    //printf("res %d\n", res);    return res;}int* numSmallerByFrequency(char ** queries, int queriesSize, char ** words, int wordsSize, int* returnSize){    int *array_q = (int *)malloc(queriesSize * sizeof(int));    int *array_w = (int *)malloc(wordsSize * sizeof(int));    int *hash = (int *)malloc(NUM * sizeof(0));    // queries各个字符串(按字典序比较)最小字母的出现频次    for (int i = 0; i < queriesSize; i++) {        array_q[i] = QureySmallWord(queries[i], hash);    }    // words各个字符串(按字典序比较)最小字母的出现频次    for (int i = 0; i < wordsSize; i++) {        array_w[i] = QureySmallWord(words[i], hash);    }    // 依次查找queries中字符串满足f(queries[i]) < f(W[0..j])的个数    int *res = (int *)malloc(queriesSize * sizeof(int));    int count = 0;    for (int i = 0; i < queriesSize; i++) {        int temp = 0;        for (int j = 0; j < wordsSize; j++) {            //printf("array_q[%d] %d  array_w[%d] %d", i, array_q[i], j, array_w[j]);            if (array_q[i] < array_w[j]) {                temp++;            }        }        res[count++] = temp;    }    *returnSize = count;    return res;}
复制代码


运行效率如下所示:





第 3 题:交替位二进制


试题要求如下:



解答思路:


每次用 n&1 位运算取出最后一位,并与上一次取出的最后一位比较,一样的话返回 false。


回答(C 语言):


bool hasAlternatingBits(int n){    int pre = n & 1;     n >>= 1;     while (n != 0) {        if ((n & 1) == pre) {            return false;        }        pre = n & 1;        n >>= 1;    }        return true;}
复制代码


运行效率如下所示:





第 4 题:二进制间距


试题要求如下:



解答思路:


1、利用 1 与数字 N 进行 &运算检查二进制第一位是否为 1;


2、逐步将数字二进制值向右移动一位:N = N>>1;


3、N <= 0 时终止。


回答(C 语言):


int binaryGap(int N){    int distance = 0, max = 0,distanceon = 0;      while (N > 0){        if((N & 1) != 0){            distanceon = 1;             if(distance > max){                max = distance;            }             distance = 0;        }         distance+=(distanceon);        N = N >> 1;    }        return max;}
复制代码


运行效率如下所示:





第 5 题:最后一块石头的重量


试题要求如下:



解答思路:


1、5 个石头撞四次 6 个石头撞 5 次 N 个石头撞 N-1 次;


2、降序,撞前两个。得到的新石头放回去,空缺位置置 0;


3、重复第二步;


4、最后剩下一个,就是答案。


回答(C 语言):


int Cmp(const void* a, const void* b){    return *(int*)b - *(int*)a;} int lastStoneWeight(int* stones, int stonesSize){    int time = stonesSize - 1;    int buf[30] = {0};    memcpy(buf, stones, stonesSize * sizeof(int));     while (time > 0) {        qsort(buf, 30, sizeof(int), Cmp);        buf[0] -= buf[1];        buf[1] = 0;        time--;    }        return buf[0];}
复制代码


运行效率如下所示:





第 6 题:旋转数字


试题要求如下:



解答思路:


遍历从 1 到 N 的每个数字 X,判断 X 是否为好数。如果 X 中存在 3、4、7 这样的无效数字,则 X 不是一个好数。如果 X 中不存在 2、5、6、9 这样的旋转后会变成不同的数字,则 X 不是一个好数。否则,X 可以旋转成一个不同的有效数字。


回答(C 语言):


/** 函数功能:检测是否是好数;是好数返回1,否则返回0 * 函数输入:当前检测的数num* 函数返回值:0或1*/int CheckDigits(int num){    int rest;    int flag = 0;     while(num > 0) {        rest = num % 10;        /* 遇到垃圾数直接返回0 */        if (rest == 3 || rest == 4 || rest == 7) {            return 0;        }        /* 遇到有可能存在的好数先标记一下 */        if (rest == 2 || rest == 5 || rest == 6 || rest == 9) {            flag = 1;        }        num = num / 10;    }        /* 如果不存在垃圾数,且有好数则统计加1 */    if (flag == 1) {        return 1;    }     return 0;}int rotatedDigits(int N){    int ret = 0;    for (int i = 1; i <= N; i++) {        /* 逐个检测,好数就加1 */        ret += CheckDigits(i);    }    return ret;}
复制代码


运行效率如下所示:





第 7 题:十进制整数的反码


试题要求如下:



解答思路:


举个例子 6 是 110 那么他的反码是他与 111 异或得到的 001。所以找到比 N 大的每位都为 1 的数,与 N 进行异或。


回答(C 语言):


int bitwiseComplement(int N){    int num = 1;     while(num < N){        num = (num << 1) + 1;    }        return N ^ num;}
复制代码


运行效率如下所示:





第 8 题:连续子数组的最大和


试题要求如下:



解答思路:


动态规划:



回答(C 语言):


int maxSubArray(int* nums, int numsSize){    int sum=nums[0],max=nums[0];        for(int i=1;i<numsSize;i++)    {        sum=(sum>0)?(sum+nums[i]):nums[i];        max=(max>sum)?max:sum;       }     return max;}
复制代码


运行效率如下所示:





第 9 题:有序数组中出现次数超过 25%的元素


试题要求如下:



回答(C 语言):


int findSpecialInteger(int* arr, int arrSize){    int i = 1,cou = 0;    int temp = arr[0];     while(i < arrSize){        if(temp == arr[i]){            cou++;             if(cou*4 >= arrSize){                break;            }        }         else{            cou = 0;        }         temp = arr[i];        i++;    }     return temp;}
复制代码


运行效率如下所示:





第 10 题:数组中字符串匹配


试题要求如下:



解答思路:


C 语言使用 strstr 库函数来进行子字符串匹配。strstr(str1,str2) 函数用于判断字符串 str2 是否是 str1 的子串。如果是,则该函数返回 str1 字符串从 str2 第一次出现的位置开始到 str1 结尾的字符串;否则,返回 NULL。


回答(C 语言):


char ** stringMatching(char ** words, int wordsSize, int* returnSize){    if ((words == NULL) || (wordsSize <= 0)) {        *returnSize = 0;        return NULL;    }     char** res = (char**)malloc(sizeof(char*) * wordsSize);    int index = 0;     for (int i = 0; i < wordsSize; i++) {        for (int j = 0; j < wordsSize; j++) {            if (i != j) {                if (strstr(words[j], words[i])) {                    res[index] = (char*)malloc(sizeof(char) * (strlen(words[i]) + 1));                    memcpy(res[index], words[i], strlen(words[i]) + 1);                    index++;                    break;                }            }        }    }     *returnSize = index;    return res; }
复制代码


运行效率如下所示:



发布于: 2021 年 03 月 24 日阅读数: 8
用户头像

【研究方向】物联网、嵌入式、AI、Python 2018.02.09 加入

【公众号】美男子玩编程

评论

发布
暂无评论
力扣(LeetCode)刷题,简单题(第14期)