蓝桥杯刷题-Day1-高精度加法
目录
蓝桥杯刷题 Day1 高精度加法
蓝桥杯刷题 Day1
提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档
前言
今天写牛客网模板题中的字符串模块
一、大数加法
原题地址:
1. 解题思路
- 去除前导零：首先需要处理输入的字符串，去掉前导零。例如，输入可能是“00123”，我们需要将其转换为“123”。
- 从右向左逐位相加：由于数字非常大，我们不能直接将其转换为整数进行计算。因此，我们将数字按字符逐位处理，从最低位（即字符串的末尾）开始相加。
- 处理进位：每一步相加后可能会产生进位，需要将进位传递到下一位的计算中。
- 构建结果字符串：将每一位的计算结果拼接到一个字符串中，并在最后反转得到正确的顺序。
2. 代码
2.1主函数
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String A = scanner.next();
String B = scanner.next();
// 去除前导o
A = deleteZeros(A);
B = deleteZeros(B);
// 两个大数相加
String result = addNum(A,B);
//输出
System.out.println(result);
}2.2 去除前导0
// 去除前导0，处理全为0的情况
public static String deleteZeros(String num){
int i = 0;
while(i < num.length() && num.charAt(i) == '0'){
i++;
}
if(i == num.length()){
return "0";
}
return num.substring(i);// 提取字符,[i,num末尾）
}2.3 大数相加
// 大数相加
public static String addNum(String A, String B){
// StringBuilder修改字符串本身
StringBuilder sb = new StringBuilder();
// 索引
int i = A.length() - 1;
int j = B.length() - 1;
// 进位
int carry = 0;
while(i >= 0 || j >= 0 || carry > 0){
int sum = carry;
if(i >= 0){
// -'0' 将字符串转化成整数
sum += A.charAt(i) - '0';
i--;
}
if(j >= 0){
sum += B.charAt(j) - '0';
j--;
}
// 当前位
sb.append(sum % 10);
// 10进1
carry = sum / 10;
}2.4 完整代码
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String A = scanner.next();
String B = scanner.next();
// 去除前导o
A = deleteZeros(A);
B = deleteZeros(B);
// 两个大数相加
String result = addNum(A,B);
//输出
System.out.println(result);
}
// 去除前导0，处理全为0的情况
public static String deleteZeros(String num){
int i = 0;
while(i < num.length() && num.charAt(i) == '0'){
i++;
}
if(i == num.length()){
return "0";
}
return num.substring(i);// 提取字符,[i,num末尾）
}
// 大数相加
public static String addNum(String A, String B){
// StringBuilder修改字符串本身
StringBuilder sb = new StringBuilder();
// 索引
int i = A.length() - 1;
int j = B.length() - 1;
// 进位
int carry = 0;
while(i >= 0 || j >= 0 || carry > 0){
int sum = carry;
if(i >= 0){
// -'0' 将字符串转化成整数
sum += A.charAt(i) - '0';
i--;
}
if(j >= 0){
sum += B.charAt(j) - '0';
j--;
}
// 当前位
sb.append(sum % 10);
// 10进1
carry = sum / 10;
}
// sb.reverse()字符串本身反转，toString()转换为Sring对象(新对象)
String result = sb.reverse().toString();
return result;
}
}二、KMP字符串匹配
原题地址:
0. 知识点速记
- KMP算法：用于匹配字符串，可以智能地 跳到 某个位置匹配，避免穷举 查找
- 跳转规则：next数组
1. 解题思路
- 去除前导零：首先需要处理输入的字符串，去掉前导零。例如，输入可能是“00123”，我们需要将其转换为“123”。
- 从右向左逐位相加：由于数字非常大，我们不能直接将其转换为整数进行计算。因此，我们将数字按字符逐位处理，从最低位（即字符串的末尾）开始相加。
- 处理进位：每一步相加后可能会产生进位，需要将进位传递到下一位的计算中。
- 构建结果字符串：将每一位的计算结果拼接到一个字符串中，并在最后反转得到正确的顺序。