深圳网站关键词优化公司哪家好,wordpress新用户默认角色设置,有免费做推广的网站吗,湖北正规网站建设质量保障废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【字符串相加】#xff0c;使用【字符串】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为喊一句号子鼓励自己程序员永不失业程序员走向架构本篇Blog的主题是【字符串相加】使用【字符串】这个基本的数据结构来实现这个高频题的站点是CodeTop筛选条件为目标公司最近一年出现频率排序由高到低的去牛客TOP101去找只有两个地方都出现过才做这道题CodeTop本身汇聚了LeetCode的来源确保刷的题都是高频要面试考的题。
名曲目标题后附上题目链接后期可以依据解题思路反复快速练习题目按照题干的基本数据结构分类且每个分类的第一篇必定是对基础数据结构的介绍。
字符串相加【EASY】
感觉很多数据结构都有要相加或合并的计算逻辑
题干 解题思路
算法流程 设定 ij 两指针分别指向 num1num2 尾部模拟人工加法
计算进位 计算 carry tmp / 10代表当前位相加是否产生进位添加当前位 计算 tmp n1 n2 carry并将当前位 tmp % 10 添加至 res 头部索引溢出处理 当指针 i或j 走过数字首部后给 n1n2 赋值为 0相当于给 num1num2 中长度较短的数字前面填0以便后续计算。当遍历完 num1num2 后跳出循环并根据 carry 值决定是否在头部添加进位 1最终返回 res 即可。
复杂度分析
时间复杂度 O(max(M,N))其中 MN 为 数字长度按位遍历一遍数字以较长的数字为准空间复杂度 O(1)指针与变量使用常数大小空间。
代码实现
给出代码实现基本档案 基本数据结构字符串 辅助数据结构无 算法迭代 技巧无 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** 计算两个数之和* param s string字符串 表示第一个整数* param t string字符串 表示第二个整数* return string字符串*/public String solve (String s, String t) {int i s.length() - 1;int j t.length() - 1;int cnt 0;StringBuilder res new StringBuilder();while (i 0 || j 0) {// 1 计算当前总和,如果其中一个字符串用完了则补0int n i 0 ? s.charAt(i) - 0 : 0;int m j 0 ? t.charAt(j) - 0 : 0;int curSum n m cnt;// 2 计算进位值cnt (curSum) / 10;// 3 设置当前位值res.append(curSum % 10);// 4 移动指针i--;j--;}// 字符串都用完后发现还有进位值则再补充1if (cnt 0) {res.append(1);}return res.reverse().toString();}
}复杂度分析
时间复杂度 O(N)遍历了两个字符串ON阶 空间复杂度 O(1)只用到常量
