2023.08.14 算法

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。

示例1:

 输入："aabcccccaaa"
 输出："a2b1c5a3"

示例2:

 输入："abbccd"
 输出："abbccd"
 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。

代码

class Solution {
    public String compressString(String S) {
        
        // 判断字符串是否为空
        if(S.length() == 0){
            return S;
        }

        // 使用StringBuilder存储修改后的字符串
        StringBuilder stringBuilder = new StringBuilder();

        // 设置左右指针和字母出现次数
        int left = 0,right = 0;
        int count = 0;

        // 判断右指针是否超出字符串的长度
        while(right < oldLength){
            // 判断左右指针是否相同，相同则右指针向右移一位，并给当前字符出现次数加1
            if(S.charAt(left) == S.charAt(right)){
                right++;
                count++;
            }else{
                // 如果不相同，则将当前左指针的字符存入stringBuilder里，并在字符后面添加出现次数
                stringBuilder.append(S.charAt(left));
                stringBuilder.append(count);
                // 将出现次数归零，并将左指针移向右指针的位置
                count = 0;
                left = right;
            }
        }

        // 右指针到头时，会结束循环，当前的字符和次数无法存进stringBuilder中
        // 在最后，将左指针内容和次数存到stringBuilder中
        stringBuilder.append(S.charAt(left));
        stringBuilder.append(count);

        // 判断新字符串和旧字符串长度，并返回字符串
        if(stringBuilder.length() < S.length()){
            return stringBuilder.toString();
        } else{
            return S;
        }
        
        /*
        // 返回字符串另一种方法
         return stringBuilder.length() < oldLength ? stringBuilder.toString() : S;
        */

    }
}

**题目：**RSA加密算法在网络安全世界中无处不在，它利用了极大整数因数分解的难度，数据越大，安全系数越高，给定一个32位整数，请对其进行因数分解，找出是哪两个素数的乘积。

输入描述：

一个正整数num
0 < num <= 2147483647

输出描述

如果成功找到，以单个空格分隔，从小到大输出两个素数，分解失败，请输出-1 -1

示例1

输入 
15
输出
3 5
说明
因数分解后，找到两个素数3和5，使得3*5=15，按从小到大排列后，输出3 5

示例2

输入 
27
输出
-1 -1
说明
通过因数分解，找不到任何素数，使得他们的乘积为27，输出-1 -1

代码

public class Main{
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        // 获取输入的数字
        int n = sc.nextInt();
 
        // 设置获取的两个因数
        int factor_num = primeNumber(n);
        int factor_sun = 0;
        
        // 判断是否为-1
        if(factor_num == -1){
            factor_sun = -1;
        }else{
            factor_sun = n / factor_num;
        }
        
        // 按照排序返回
        if(factor_num <= factor_sun){
            System.out.print(factor_num + " " +factor_sun);
        }else{
            System.out.print(factor_sun + " " +factor_num);
        }
        
        // 不要忘记关闭输入流
        sc.close();
    }
    
    
    static int primeNumber(int num){
        for(int i = 2;i <= Math.sqrt(num); i++){
            // 判断是否为素数
            if(isPrime(i)){
                if(num % i == 0){
                    // 当获取到第一个素数时，再判断一下另一个是否为素数
                    if(isPrime(num / i)){
                        return i;
                    }
                }
            }
        }
        return -1;
    }

    // 判断是否为素数
    static boolean isPrime(int s) {
        if (s < 2) return false;
        // Math.sqrt(s)平方根
        for (int i = 2; i <= Math.sqrt(s); i++){
            if (s % i == 0) {
                return false;
            }
        }
        return true;
    }
    
}