刷题笔记I

发表于 分类于 本文字数： 2.1k 阅读时长 ≈ 2 分钟

刷题笔记I

统计N以内的素数

素数:只能被1和自身整除的数，0、1除外

  • 解法一：暴力算法
    直接从2开始遍历，判断是否能被2到自身之间的数整除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int countPrimes(int n) {
    int ans = 0;
    for (int i = 2; i < n; ++i) {
        ans += isPrime(i) ? 1 : 0;
}
return ans; }
//i如果能被x整除，则x/i肯定能被x整除，因此只需判断i和根号x之中较小的即可 public boolean isPrime(int x) {
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            return false;
        }
}
    return true;
}
  • 解法2:埃氏筛

    利用合数的概念(非素数)，素数*n必然是合数，因此可以从2开始遍历，将所有的合数做上标记

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public static int eratosthenes(int n) {
        boolean[] isPrime = new boolean[n];
        int ans = 0;
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) {
                ans += 1;
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = true;
    } }
    }
    return ans

    将合数标记为true，j = i * i 从 2 * i 优化而来，系数2会随着遍历递增(j += i，相当于递增了系数2)， 每一个合数都会有两个比本身要小的因子(0,1除外)，2 * i 必然会遍历到这两个因子
    当2递增到大于根号n时，其实后面的已经无需再判断(或者只需判断后面一段)，而2到根号n、实际 上在 i 递增的过程中已经计算过了，i 实际上就相当于根号n

例如:n = 25 会计算以下
24 = 8
34 = 12
但实际上8和12已经标记过，在n = 17时已经计算了 3 * 4，2 * 4

寻找数组的中心索引

数组中某一个下标，左右两边的元素之后相等，该下标即为中心索引
思路:先统计出整个数组的总和，然后从第一个元素开始叠加
总和递减当前元素，叠加递增当前元素，知道两个值相等

1
2
3
4
5
6
7
8
9
10
11
public static int pivotIndex(int[] nums) {
    int sum1 = Arrays.stream(nums).sum();
    int sum2 = 0;
    for(int i = 0; i<nums.length; i++){
        sum2 += nums[i];
        if(sum1 == sum2){
return i; }
        sum1 = sum1 - nums[i];
    }
return -1;
}

x的平方根

在不使用 sqrt(x) 函数的情况下，得到 x的平方根的整数部分

  • 解法一:二分查找
    x的平方根肯定在0到x之间，使用二分查找定位该数字，该数字的平方一定是最接近x的，m平方值如果 大于x、则往左边找，如果小于等于x则往右边找
    找到0和X的最中间的数m，
    如果m * m > x，则m取x/2到x的中间数字，直到m * m < x，m则为平方根的整数部分
    如果m * m <= x，则取0到x/2的中间值，知道两边的界限重合，找到最大的整数，则为x平方根的整数 部分
    时间复杂度:O(logN)
1
2
3
4
5
6
7
8
9
10
11
12
public static int binarySearch(int x) {
    int l = 0, r = x, index = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if ((long) mid * mid <= x) {
index = mid;
            l = mid + 1;
        } else {
r = mid - 1; }
}
    return index;
}
  • 解法二:牛顿迭代
    假设平方根是 i ，则 i 和 x/i 必然都是x的因子，而 x/i 必然等于 i ，推导出 i + x / i = 2 * i，得出 i = (i + x / i) / 2
    由此得出解法，i 可以任选一个值，只要上述公式成立，i 必然就是x的平方根，如果不成立， (i + x / i) / 2得出的值进行递归，直至得出正确解
1
2
3
4
5
6
7
8
9
10
11
12
public static int newton(int x) {
    if(x==0) return 0;
    return ((int)(sqrts(x,x)));
}
public static double sqrts(double i,int x){
    double res = (i + x / i) / 2;
    if (res == i) {
        return i;
    } else {
        return sqrts(res,x);
    }
}