欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

计算不限定大小的两个数相加

程序员文章站 2022-12-17 21:10:58
前言int类型数据是有一定大小范围的,在32位机子下:[-2147483648, 2147483647]。如何进行超出范围的计算呢?解题思路将数字转换为String类型,再转换为char[]数组进行模拟人算:进位法。以leetcode第二题为例值得注意的是,2->4->3,其实便于理解可以看作是 3 < 4 < 2: 3 < 4 < 2 4 < 6 < 4—————————————————— 8 &......

前言

int类型数据是有一定大小范围的,在32位机子下:[-2147483648, 2147483647]。如何进行超出范围的计算呢?

解题思路

将数字转换为String类型,再转换为char[]数组进行模拟人算:进位法。以leetcode第二题为例

值得注意的是,2->4->3,其实便于理解可以看作是  3  <  4  <  2:

  3  <  4  <  2
  4  <  6  <  4
——————————————————
  8  <  0  <  7

    进1

题目

2. 两数相加

难度中等5303

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

 代码

 public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
	    	
	    	int is_Ten = 0;
	    	int l1Num , l2Num , tempSum;
	    	ListNode resutListNode = null , tempListNode = null;
	    	
	    	
	    	//99999不停进位
	    	while (l1!=null || l2!=null) {
	 
	    		//使之尾部不多一个节点
	    		if (resutListNode == null) {
					resutListNode = new ListNode();
					tempListNode = resutListNode;
				}else {
					tempListNode.next = new ListNode();	//先创建空间才能往后延不断掉节点
					tempListNode = tempListNode.next;
				}
	    		
	    		//判断是否有对应的两数对应位数可相加
				l1Num = l1==null ? 0 : l1.val;
				l2Num = l2==null ? 0 : l2.val;
				
				//进位和当前位数补充结果
				tempSum = l1Num + l2Num + is_Ten;
				is_Ten = tempSum /10;
				tempListNode.val = tempSum %10;

				//null.next = null 会报空指针错误,而不是指的是l1.next = null有问题,所以这里判断的是l1/l2 != null
				if (l1 != null) {
					l1 = l1.next;
				}
				
				if (l2 != null) {
					l2 = l2.next;	
				}

			}
	    	
	    	//超出所以长度一位的进位
	    	if (is_Ten == 1) {
	    		tempListNode.next = new ListNode();	//先创建空间才能往后延不断掉节点
				tempListNode = tempListNode.next;
				tempListNode.val = is_Ten;
			}
	    	
	    	
			return resutListNode;
 
	    }

标准输入输出代码

输入字符串输出字符串(可转换)。为了输出为正常顺序,采用StringBuffer的result.insert(0, char);来记录结果集;

for循环的i为倒数第几个,因为模拟计算是从字符串的最右边开始的。

	    //标准输入
	    public StringBuffer addTwoNumbers3(String l1, String l2) {
			StringBuffer result = new StringBuffer();
			
			char[] l1Chars = l1.toCharArray();
			char[] l2Chars = l2.toCharArray();
			
			int maxLength = l1Chars.length > l2Chars.length ? l1Chars.length : l2Chars.length;
			int l1TempNum=0 , l2TempNum=0 , tempSum=0 , is_Ten=0;
			
			//倒数第几个
			for (int i = 1; i <= maxLength; i++) {
				
				if (i > l1Chars.length) {
					l1TempNum = 0;
				}else {
					l1TempNum = l1Chars[l1Chars.length - i] -'0';
				}
				if (i > l2Chars.length) {
					l2TempNum = 0;
				}else {
					l2TempNum = l2Chars[l2Chars.length - i] -'0';
				}
								
				
				tempSum = l1TempNum + l2TempNum + is_Ten;
				result.insert(0, tempSum %10);
				is_Ten = tempSum/10;
				
			}
			
	    	//超出所以长度一位的进位
	    	if (is_Ten == 1) {
	    		result.insert(0, '1');
			}
			
			
			return result;
	   }

测试结果:
计算不限定大小的两个数相加

原本代码

递归转化,但是有int范围限制。

计算不限定大小的两个数相加

// 1999999999  9999999991越界错误,要每个位数增加
	   public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

	    	StringBuffer l1Num = new StringBuffer();
	    	StringBuffer l2Num = new StringBuffer();
	    	l1Num = getSourceNumber(l1, l1Num);
	    	l2Num = getSourceNumber(l2, l2Num);
	    	//int reultNum = Integer.valueOf(l1Num.toString()) + Integer.valueOf(l2Num.toString());
	    	//char[] resultChar = String.valueOf(reultNum).toCharArray();
	    	char[] resultChar = add(l1Num, l2Num);
	    	
			ListNode resultListNode = new ListNode();
			ListNode tempListNode = resultListNode;
			

	    	for (int i = resultChar.length - 1 ; i >= 0; i--) {
	    	
				tempListNode.val = resultChar[i] - '0';
				tempListNode.next = i == 0 ? null : new ListNode();	//去除最后一个情况不再添加
				tempListNode =  tempListNode.next;				
			}

			return resultListNode;	        
	    }
	    
	    static StringBuffer getSourceNumber(ListNode n , StringBuffer result) {
	    	
	    	if (n == null) {
				return result;
			}
	    	getSourceNumber(n.next, result);

	    	return  result.append(String.valueOf(n.val));
	    }
	    
	    char[] add(StringBuffer l1Num ,StringBuffer l2Num) {
	    
			return null;
	    	
	    }

 

本文地址:https://blog.csdn.net/qq_37334150/article/details/110224753