当前位置：首页 > article >正文

LeetCode 算法笔记-第 04 章基础算法篇

article 2024/9/19 20:33:17

1.枚举

采用枚举算法解题的一般思路如下：

确定枚举对象、枚举范围和判断条件，并判断条件设立的正确性。
一一枚举可能的情况，并验证是否是问题的解。
考虑提高枚举算法的效率。

我们可以从下面几个方面考虑提高算法的效率：

抓住问题状态的本质，尽可能缩小问题状态空间的大小。
加强约束条件，缩小枚举范围。
根据某些问题特有的性质，例如对称性等，避免对本质相同的状态重复求解。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    // Allocate memory for the result (2 integers)
    int* result = (int*)malloc(2 * sizeof(int));
    
    // Iterate through the array to find two numbers that sum to the target
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[i] + nums[j] == target) {
                result[0] = i; // Store the first index
                result[1] = j; // Store the second index
                *returnSize = 2; // Set the size of the result array
                return result; // Return the result array
            }
        }
    }

    *returnSize = 0; // If no solution found, set returnSize to 0
    return NULL; // Return NULL if no solution is found
}

什么是质数：大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

int st[10000000]={0};
int pr[10000000]={0};
int cunt=0;

void pre(int n){
    cunt=0;
    for(int i=2;i<n;i++){
        if(!st[i]) pr[cunt++]=i;
        for(int j=0;pr[j]<=n/i;j++){
            st[pr[j]*i]=1;
            if(i%pr[j]==0) break;
        }
    }
}
int countPrimes(int n) {
    pre(n);
    return cunt;
}

int countTriples(int n) {
    int sun=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int a=1;a<=n;a++){
                if(i*i+j*j==a*a) sun++;
            }
        }
    }
    return sun;
}