蓝桥杯刷题 Day1 高精度加法

蓝桥杯刷题 Day1

---

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

今天写牛客网模板题中的字符串模块

---

一、大数加法

原题地址: 高精度加法

1. 解题思路

1. 去除前导零：首先需要处理输入的字符串，去掉前导零。例如，输入可能是“00123”，我们需要将其转换为“123”。
2. 从右向左逐位相加：由于数字非常大，我们不能直接将其转换为整数进行计算。因此，我们将数字按字符逐位处理，从最低位（即字符串的末尾）开始相加。
3. 处理进位：每一步相加后可能会产生进位，需要将进位传递到下一位的计算中。
4. 构建结果字符串：将每一位的计算结果拼接到一个字符串中，并在最后反转得到正确的顺序。

2. 代码

2.1主函数

public static void main(String[] args){Scanner scanner = new Scanner(System.in);String A = scanner.next();String B = scanner.next();// 去除前导oA = 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进1carry = 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();// 去除前导oA = 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进1carry = sum / 10;}// sb.reverse()字符串本身反转，toString()转换为Sring对象(新对象)String result = sb.reverse().toString();return result;}
}

二、KMP字符串匹配

原题地址: KMP字符串匹配

0. 知识点速记

1. KMP算法：用于匹配字符串，可以智能地跳到某个位置匹配，避免穷举查找
2. 跳转规则：next数组

1. 解题思路

1. 去除前导零：首先需要处理输入的字符串，去掉前导零。例如，输入可能是“00123”，我们需要将其转换为“123”。
2. 从右向左逐位相加：由于数字非常大，我们不能直接将其转换为整数进行计算。因此，我们将数字按字符逐位处理，从最低位（即字符串的末尾）开始相加。
3. 处理进位：每一步相加后可能会产生进位，需要将进位传递到下一位的计算中。
4. 构建结果字符串：将每一位的计算结果拼接到一个字符串中，并在最后反转得到正确的顺序。

2. 代码