个人学习编程(3-16) leetcode刷题

有多少小于当前数字的数字：

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

示例 1：

输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]
解释： 
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。 
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。 
对于 nums[3]=2 存在一个比它小的数字：（1）。 
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

示例 2：

输入：nums = [6,5,4,8]
输出：[2,1,0,3]

示例 3：

输入：nums = [7,7,7,7]
输出：[0,0,0,0]

#include <stdio.h>

void countSmallerNumbers(int nums[],int n,int result[]){
    //对每个元素nums[i]，遍历整个数组来计数
    for (int i = 0; i < n; i++)
    {
        int count = 0;
        for (int j = 0; j < n; j++)
        {
            if (nums[i] > nums[j])
            {
                count++;
            }
        }
    result[i] = count; //将结果存储在 result 数组中
        
    }
    
}

int main() {
    int nums[] = {8,1,2,2,3};
    int n = sizeof(nums) / sizeof(nums[0]);
    int result[n];

    countSmallerNumbers(nums,n,result);

    //打印结果数组
    printf("[");
    for (int i = 0; i < n; i++)
    {
        printf("%d",result[i]);
        if (i != n - 1)
        {
            printf(", ");
        }
    }
    printf("]\n");
    
    return 0;
}

设计 Goal 解析器：

请你设计一个可以解释字符串 command 的 Goal 解析器 。command 由 "G"、"()" 和/或 "(al)" 按某种顺序组成。Goal 解析器会将 "G" 解释为字符串 "G"、"()" 解释为字符串 "o" ，"(al)" 解释为字符串 "al" 。然后，按原顺序将经解释得到的字符串连接成一个字符串。

示例 1：

输入：command = "G()(al)"
输出："Goal"
解释：Goal 解析器解释命令的步骤如下所示：
G -> G
() -> o
(al) -> al
最后连接得到的结果是 "Goal"

示例 2：

输入：command = "G()()()()(al)"
输出："Gooooal"

示例 3：

输入：command = "(al)G(al)()()G"
输出："alGalooG"

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char* interpret(char* command) {
    //创建一个足够大的缓冲区来存储结果
    int len = strlen(command);
    char* result = (char*) malloc((len + 1) * sizeof(char)); //动态分配内存
    int idx = 0; //结果数组的索引

    for (int i = 0; i < len; i++){
        if (command[i] == 'G')
        {
            result[idx++] = 'G';
        }
        else if (command[i] == '(' && command[i + 1] == ')')
        {
            result[idx++] = 'o';
            i++; // 跳过 ')'
        }
        else if (command[i] == '(' && command[i + 1] == 'a' && command[i + 2] == 'l' && command[i + 3] == ')'){
            result[idx++] = 'a';
            result[idx++] = 'l';
            i += 3; // 跳过"al)"
        }
    }
    result[idx] = '\0';
    return result;
}

int main() {
    char command[] = "G()(al)(al)";
    char* result = interpret(command);
    printf("%s\n",result); //输出解析结果

    free(result);
    return 0;
}

仅替换一次字符串能否使得两个字符串相等：

给你长度相等的两个字符串 s1 和 s2 。一次 字符串交换 操作的步骤如下：选出某个字符串中的两个下标（不必不同），并交换这两个下标所对应的字符。

如果对 其中一个字符串 执行 最多一次字符串交换 就可以使两个字符串相等，返回 true ；否则，返回 false 。

数组：

#include <stdio.h>
#include <stdlib.h>
#include<bits/stdc++.h>


bool areStringEqualAfterOneSwap(char* s1,char* s2){
    int len = strlen(s1);
    if(strcmp(s1, s2) == 0){
        return true;
    }


    //找出不同的字符位置
    int diffIndexs[2];
    int diffCount = 0;

    for (int i = 0; i < len; i++)
    {
        if(s1[i] != s2[i]){
            if (diffCount == 2){
                return false;
            }
            diffIndexs[diffCount++] = i;
        }
    }

    //如果有两个不同的位置，检查交换后是否相等
    if (diffCount == 2){
        int i = diffIndexs[0];
        int j = diffIndexs[1];

        // 检查交换后的字符是否可以使两个字符串相等
        if(s1[i] == s2[j] && s1[j] == s2[i]){
            return true;
        }
    }
    return false;
}

int main() {
    char s1[101];
    char s2[101];
    scanf("%s",s1);
    scanf("%s",s2);

    //判断并输出结果
    if(areStringEqualAfterOneSwap(s1,s2)){
        printf("true\n");
    }else{
        printf("false\n");
    }

    return 0;
}

指针：

指针需要注意  首先是 

char* p = s1;

char* q = s2;

其次是在while循环的判断条件，已经当前走到多长了  ==>>  (p-s)

while (*p && *q) {

        if (*p != *q) {

            if (diffCount == 2) {

                return false;  // 超过两个不相等的字符，直接返回 false

            }

            diffIndices[diffCount++] = p - s1;  // 记录位置

        }

        p++;

        q++;

    }

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool areAlmostEqual(char* s1, char* s2) {
    // 如果两个字符串已经相等，直接返回 true
    if (strcmp(s1, s2) == 0) {
        return true;
    }

    // 指针初始化，遍历两个字符串
    char* p = s1;
    char* q = s2;
    
    // 存储不相等的位置
    int diffCount = 0;
    int diffIndices[2];  // 最多只有两个不同的位置
    
    // 遍历两个字符串
    while (*p && *q) {
        if (*p != *q) {
            if (diffCount == 2) {
                return false;  // 超过两个不相等的字符，直接返回 false
            }
            diffIndices[diffCount++] = p - s1;  // 记录位置
        }
        p++;
        q++;
    }

    // 如果不相等的位置有两个，检查是否可以交换这两个字符
    if (diffCount == 2) {
        int i = diffIndices[0];
        int j = diffIndices[1];
        
        // 判断交换后的字符是否能使得字符串相等
        if (*(s1 + i) == *(s2 + j) && *(s1 + j) == *(s2 + i)) {
            return true;
        }
    }
    
    return false;
}

int main() {
    char s1[101], s2[101];
    
    // 读取输入
    scanf("%s", s1);
    scanf("%s", s2);
    
    // 判断并输出结果
    if (areAlmostEqual(s1, s2)) {
        printf("true\n");
    } else {
        printf("false\n");
    }
    
    return 0;
}

 最大和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

给你一个整数数组 nums ，请你在所有可能的 子序列 中找到最长的和谐子序列的长度。

数组的 子序列 是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 1：

输入：nums = [1,3,2,2,5,2,3,7]

输出：5

解释：

最长和谐子序列是 [3,2,2,2,3]。

示例 2：

输入：nums = [1,2,3,4]

输出：2

解释：

最长和谐子序列是 [1,2]，[2,3] 和 [3,4]，长度都为 2。

示例 3：

输入：nums = [1,1,1,1]

输出：0

解释：

不存在和谐子序列。

 超时：

if (numsSize <= 1) return 0;

    // 使用一个哈希表来记录数字的频率
    int min = INT_MAX, max = INT_MIN;
    
    // 找到数组的最小值和最大值，用来确定哈希表的大小
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] < min) min = nums[i];
        if (nums[i] > max) max = nums[i];
    }

    // 数字的范围是 [min, max]，所以我们可以创建一个哈希表来存储频率
    int range = max - min + 1;
    int* freq = (int*)calloc(range, sizeof(int));  // 初始化频率数组
    
    // 统计每个数字的频率
    for (int i = 0; i < numsSize; i++) {
        freq[nums[i] - min]++;
    }

    int maxLength = 0;
    
    // 遍历频率表，检查每个数字和它的邻居 (num + 1) 的和谐子序列长度
    for (int i = 0; i < range - 1; i++) {
        if (freq[i] > 0 && freq[i + 1] > 0) {
            int length = freq[i] + freq[i + 1];
            if (length > maxLength) {
                maxLength = length;
            }
        }
    }
    
    return maxLength;  // 返回最大和谐子序列的长度

删除最外层括号：

有效括号字符串为空 ""、"(" + A + ")" 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。

• 例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。

如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。

对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。

示例 1：

输入：s = "(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

示例 2：

输入：s = "(()())(())(()(()))"
输出："()()()()(())"
解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3：

输入：s = "()()"
输出：""
解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。

#include <stdio.h>
#include <string.h>

char* removeOuterParentheses(char* s) {
    int n = strlen(s);
    char* result = (char*)malloc(n + 1); // 为结果分配足够的空间
    int index = 0; // 结果字符串的当前索引
    int level = 0; // 括号的嵌套层级

    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            if (level > 0) {  // 如果不是最外层括号
                result[index++] = s[i]; // 添加到结果中
            }
            level++; // 增加嵌套层级
        } else {
            level--; // 减少嵌套层级
            if (level > 0) { // 如果不是最外层括号
                result[index++] = s[i]; // 添加到结果中
            }
        }
    }

    result[index] = '\0'; // 确保字符串以 '\0' 结尾
    return result;
}

// 测试代码
int main() {
    char s[] = "(()())(())";
    char* result = removeOuterParentheses(s);
    printf("Output: %s\n", result);
    free(result); // 释放分配的内存
    return 0;
}