力扣(LeetCode)刷题，简单题(第14期)_力扣题目 统计字符串字符个数

目录

第1题：配对交换

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

第3题：交替位二进制

第4题：二进制间距

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

第6题：旋转数字

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

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

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

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

---

力扣(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 26
int 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;
 
}

运行效率如下所示：