深圳网站设计公司设计,如何网上销售自己的产品,平台网站定制,网站定位广告文章目录 1. leetcode 2 两数之和1.1 解法一 1. leetcode 2 两数之和
1.1 解法一
题目及其相关实例如下 要做这个题,首先我们要学会模拟竖式的加法,我们知道即使是java基本数据中最大的long类型范围也是有限的,那如果超出范围了我们该怎么办呢,我们就需要用字符串来模拟这个… 文章目录 1. leetcode 2 两数之和1.1 解法一 1. leetcode 2 两数之和
1.1 解法一
题目及其相关实例如下 要做这个题,首先我们要学会模拟竖式的加法,我们知道即使是java基本数据中最大的long类型范围也是有限的,那如果超出范围了我们该怎么办呢,我们就需要用字符串来模拟这个加法的过程 思路分析: 1.将字符串转化为字符数组进行存储(toCharArray方法) 2.把字符数组逆序操作变为数字数组(逆序的原因是模拟竖式对齐) 3.创建一个ret数组用来保存逐个相加的结果 4.最后逆序输出ret数组就是最终的答案 代码实现如下
public static void addNumber(String s1,String s2){//这是我们的准备工作,先把字符串转换为字符数组,创建的arr1数组用来存放c1中的数字,arr2数组用来存放c2中的数字,创建一个返回数组用来输出结果char[] c1 s1.toCharArray();char[] c2 s2.toCharArray();int len1 c1.length;int len2 c2.length;int[] arr1 new int[len1];int[] arr2 new int[len2];int maxlen len1 len2 ? len1 : len2;int minlen len1 len2 ? len2 : len1;int[] ret new int[maxlen 1];//下面的工作是把字符串进行翻转并进行存储,用来模拟竖式相加对齐for(int i len1 - 1; i 0; --i){arr1[len1 - 1 -i] c1[i] - 0;}for(int i len2 - 1; i 0; --i){arr2[len2 - 1 - i] c2[i] - 0;}//下面我们模拟竖式的相加for(int i 0; i maxlen; i){if(i minlen){ret[i 1] (ret[i] arr1[i] arr2[i]) / 10;ret[i] (ret[i] arr1[i] arr2[i]) % 10;}else if(minlen len1){ret[i 1] (ret[i] arr2[i]) / 10;ret[i] (ret[i] arr2[i]) % 10;}else{ret[i 1] (ret[i] arr1[i]) / 10;ret[i] (ret[i] arr1[i]) % 10;}}//因为是逆序的,需要判断最后一个是不是0if(ret[ret.length - 1] 0) {ret Arrays.copyOf(ret, ret.length - 1);}for(int i 0; i ret.length / 2; i){int temp ret[i];ret[i] ret[ret.length - 1 - i];ret[ret.length - 1 -i] temp;}System.out.println(Arrays.toString(ret));}有了上面的铺垫,我们的两数相加其实就是这个原理,由于我们不知道具体链表的长度(可以整一个size方法,但是没必要),我们直接用顺序表来代替数组来进行操作,依然是模拟竖式相加,最后逐个new新节点进行串联即可(创建一个虚拟的节点进行连接) 代码实现如下
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {if(l1 null || l2 null){return null;}//我们通过创建一个集合类解决吧ListInteger list1 new ArrayList();ListInteger list2 new ArrayList();//开始遍历我们的链表ListNode cur l1;while(cur ! null) {int temp cur.val;list1.add(temp);cur cur.next;}ListNode curN l2;while(curN ! null) {int temp curN.val;list2.add(temp);curN curN.next;}//上面的那一步其实就相当于是把字符存入数组int len1 list1.size();int len2 list2.size();int maxlen len1 len2 ? len1 : len2;int minlen len1 len2 ? len2 : len1;int[] ret new int[maxlen 1];//跟上面的模拟不一样的这个是,这个本来就是逆序的,所以不用进行反转//开始模拟竖式相加的求和操作for(int i 0; i maxlen; i){if(i minlen){ret[i 1] (ret[i] list1.get(i) list2.get(i)) / 10;ret[i] (ret[i] list1.get(i) list2.get(i)) % 10;}else if(minlen len1){ret[i 1] (ret[i] list2.get(i)) / 10;ret[i] (ret[i] list2.get(i)) % 10;}else{ret[i 1] (ret[i] list1.get(i)) / 10;ret[i] (ret[i] list1.get(i)) % 10;}}//模拟竖式相加成功,现在看看最后一位是不是0(因为是倒叙求和的)if(ret[ret.length - 1] 0){ret Arrays.copyOf(ret,ret.length - 1);}//最后采用虚拟节点法把这ret中的节点都连接起来即可ListNode head new ListNode(-1);cur head;for(int i 0; i ret.length ; i){ListNode node new ListNode(ret[i]);cur.next node;cur cur.next;}//最后返回虚拟节点的下一个位置return head.next;}
}
