算法优化遍历不回头的场景

忘是亡心i 2024-03-27 16:05 86阅读 0赞

### 开方操作 ###

#### HJ6 质数因子 ####

/**
     * 收集质数因子
     */
    private static List<Long> getPrimes(Long num) {
        
        List<Long> res = new ArrayList<>();
        // Math.sqrt(num)两数相乘最大的也就是平方，再往后就是重复值了
        double sqrt = Math.sqrt(num);
        for (long i = 2L; i <= sqrt; i++) {
        
            while (num % i == 0) {
        
                res.add(i);
                num = num / i;
            }
        }
        // num==1说明全部整除开了，num!=1说明余下本身为素数
        if (num != 1) {
        
            res.add(num);
        }
        return res;
    }

#### 判断是否为素数之积 ####

/**
     * 判断是否为素数之积
     */
    private static List<Integer> getIntegers(int num) {
        
        List<Integer> res = new ArrayList<>();
        double sqrt = Math.sqrt(num); // 讨巧算法，两个数相乘最大的也就是平方
        for (int i = 2; i <= sqrt; i++) {
         // 求素数之积,要跳过1的特殊场景,所以从2开始查找
            if (!isPrime(i)) {
        
                continue; // 第一个因数不为素数则处理下个数
            }
            if (num % i != 0) {
        
                continue; // 不能整除则处理下个数
            }
            if (!isPrime(num / i)) {
        
                continue; // 第二个因数不为素数则处理下个数
            }
            res.add(i);
            res.add(num / i);
        }
        return res;
    }

#### 判断是不是素数 ####

/**
     * 判断是不是素数
     */
    public static boolean isPrime(int num) {
        
        // 2,3
        if (num < 4) {
        
            return num > 1;
        }
        double sqrt = Math.sqrt(num);
        for (int i = 2; i <= sqrt; i++) {
        
            if (num % i == 0) {
         // 模为0说明整除了
                return false;
            }
        }
        return true;
    }
    
    /**
     * 有点高级需要理解，先保存
     */
    public boolean isPrime(int num) {
        
        for (int i = 2; i * i <= num; i++) {
        
            if (num % i == 0) {
          // 模为0说明整除了
                return false;
            }
        }
        return true;
    }

### i 和 i+1 ###

#### NC61 两数之和 ####

private static int[] getIntegers(int[] numbers, int target) {
        
        int[] res = new int[2];
        for (int i = 0; i < numbers.length; i++) {
        
            if (numbers[i] > target) {
        
                continue;
            }
            // 这种判断存在的场景时不存在回头路的，有回头也是前面收集过的，所以j=i+1
            for (int j = i + 1; j < numbers.length; j++) {
        
                if (numbers[i] + numbers[j] == target) {
        
                    res[0] = i + 1;
                    res[1] = j + 1;
                    return res;
                }
            }
        }
        return res;
    }

### 递归 ###

#### 是否有长度大于2的相同子串 （注：其他符号不含空格或换行）（HJ20 密码验证合格程序） ####

if (hasSameSubStr(str, 0, 3)) {
        
        return "NG";
    }
     
    /**
     * 是否有长度大于2的相同子串 （注：其他符号不含空格或换行）
     */
    private static boolean hasSameSubStr(String str, int l, int r) {
        
        // 最优化应该是如果截取3位的话应该是r>=str.length()-2,n位应该是r>=str.length()-(n-1)
        if (r >= str.length()) {
        
            return false;
        }
        // 母串
        String sourceStr = str.substring(r);
        // 子串
        String targetStr = str.substring(l, r);
        // 母串是否包含子串
        if (sourceStr.contains(targetStr)) {
        
            return true;
        } else {
        
            return hasSameSubStr(str, l + 1, r + 1);
        }
    }