2019-02-21-算法-进化

怼烎@ 2022-03-17 01:10 136阅读 0赞

论代码能力：

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

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

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

示例：

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

**主方法为：addTwoNumbers**

自己最初的解题代码：

public class Test {
    	
    	public static void main(String[] args) throws InterruptedException {
    //		输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    //		输出：7 -> 0 -> 8
    //		原因：342 + 465 = 807
    //		[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
    //		[5,6,4]
    		ListNode aNode = initNode(new int[]{5});
    		ListNode bNode = initNode(new int[]{5});
    		ListNode cNode = addTwoNumbers(aNode, bNode);
    		System.out.println(JSONObject.toJSONString(cNode));
    	}
    	
    	public static ListNode initNode(int [] arr) {
    		ListNode head = new ListNode(arr[0]);
    		ListNode node = head;
    		for(int i=1;i<arr.length;i++) {
    			ListNode tNode = new ListNode(arr[i]);
    			node.next = tNode;
    			node = node.next;
    		}
    		return head;
    	}
    	
    	
    	public static class ListNode {
    		int val;
    		ListNode next;
    		public ListNode(int val) {
    			this.val = val;
    		}
    	}
    	
    	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    		List<Integer> arr1 = new ArrayList<Integer>();
    		List<Integer> arr2 = new ArrayList<Integer>();
    		ListNode t1 = l1;
    		ListNode t2 = l2;
    		while (t1!=null) {
    			arr1.add(t1.val);
    			t1 = t1.next;
    		}
    		while (t2!=null) {
    			arr2.add(t2.val);
    			t2 = t2.next;
    		}
    		
    		List<Integer> arr3 = null;
    		
    		arr3 = getResultList(arr1.size() > arr2.size()?arr1:arr2, arr1.size() > arr2.size()?arr2:arr1);
    		
    		ListNode head = new ListNode(arr3.get(0));
    		ListNode node = head;
    		for(int i=1;i<arr3.size();i++) {
    			ListNode tNode = new ListNode(arr3.get(i));
    			node.next = tNode;
    			node = node.next;
    		}
    		return head;
        }
    	
    	public static List<Integer> getResultList(List<Integer> longList, List<Integer> shortList) {
    		List<Integer> arr3 = new ArrayList<Integer>();
    		int jinJi = 0;
    		for(int i=0;i<longList.size();i++) {
    			int a = longList.get(i);
    			int b=0;
    			if(i<shortList.size()) {
    				b=shortList.get(i);
    			}
    			int count = a+b + jinJi;
    			if(count>9) {
    				jinJi = 1;
    			}else {
    				jinJi = 0;
    			}
    			arr3.add(count % 10);
    		}
    		if(jinJi != 0) {
    			arr3.add(jinJi);
    		}
    		return arr3;
    	}
    	
    }

参照标准答案重写的代码：

public class Test {
    	
    	public static void main(String[] args) throws InterruptedException {
    //		输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    //		输出：7 -> 0 -> 8
    //		原因：342 + 465 = 807
    //		[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
    //		[5,6,4]
    		ListNode aNode = initNode(new int[]{5});
    		ListNode bNode = initNode(new int[]{5});
    		ListNode cNode = addTwoNumbers(aNode, bNode);
    		System.out.println(JSONObject.toJSONString(cNode));
    	}
    	
    	public static ListNode initNode(int [] arr) {
    		ListNode head = new ListNode(arr[0]);
    		ListNode node = head;
    		for(int i=1;i<arr.length;i++) {
    			ListNode tNode = new ListNode(arr[i]);
    			node.next = tNode;
    			node = node.next;
    		}
    		return head;
    	}
    	
    	
    	public static class ListNode {
    		int val;
    		ListNode next;
    		public ListNode(int val) {
    			this.val = val;
    		}
    	}
    	
    	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    		//哑节点
    		ListNode yaNode = new ListNode(0);
    		ListNode head = yaNode;
    		
    		int jinJi = 0;
    		int benJi =0;
    		while (l1!=null || l2!=null) {
    			int temp = (l1 == null?0:l1.val) + (l2==null?0:l2.val) + jinJi;
    			jinJi = temp>9?1:0;
    			benJi = temp % 10;
    			ListNode node = new ListNode(benJi);
    			head.next = node;
    			head = head.next;
    			if(l1 != null) {
    				l1 = l1.next;
    			}
    			if(l2 != null) {
    				l2 = l2.next;
    			}
    		}
    		if(jinJi != 0) {
    			ListNode node = new ListNode(jinJi);
    			head.next = node;
    		}
    		
    		return yaNode.next;
        }

部分思路（按照人类解题，加法超过9进级的思路）是类似的，但是局部进行了优化（不用借助ArrayList，直接使用链表遍历即可）  
减少了内存占用，并且代码更加的简洁易懂，不易出错。继续努力吧！