算法(十八)

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

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

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

示例：

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

class ListNode{
//    ListNode next = null;
//    int val;
//    public ListNode(int x){
//        val = x;
//    }
//}

public static void main(String[] args) {
        int[] a = new int[]{9,9};
        int[] b = new int[]{1,2,3,4};
        int i = 0;
        ListNode head = new ListNode(0);
        ListNode p = head;
        while (i < a.length) {
            ListNode newNode = new ListNode(a[i]);
            p.next = newNode;
            p = p.next;
            i++;
        }
        i = 0;
        ListNode head2 = new ListNode(0);
        ListNode p2 = head2;
        while (i < b.length) {
            ListNode newNode = new ListNode(b[i]);
            p2.next = newNode;
            p2 = p2.next;
            i++;
        }

        ListNode p1 = head.next;
        System.out.print("链表a为: ");
        while (p1 != null) {
            System.out.print(p1.val + " ");
            p1 = p1.next;
        }
        System.out.println();
        ListNode p22 = head2.next;
        System.out.print("链表b为: ");
        while (p22 != null) {
            System.out.print(p22.val + " ");
            p22 = p22.next;
        }
        ListNode resNode = addTwoNumbers(head.next, head2.next);
        System.out.println();
        System.out.print("相加后链表为: ");
        if(resNode != null){
            while (resNode != null) {
                System.out.print(resNode.val + " ");
                resNode = resNode.next;
            }
        }else{
            System.out.println("错误！");
        }
    }

    private static ListNode addTwoNumbers(ListNode head, ListNode head2) {
        ListNode newHead = new ListNode(0);
        ListNode p = head, q=head2, cur = newHead;
        int carry = 0;
        while (p!=null || q!=null){
            int x = (p!=null)?p.val:0;
            int y = (q!=null)?q.val:0;
            int sum = carry+x+y;
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            if(p!=null) p=p.next;
            if(q!=null) q=q.next;
        }
        if(carry>0){
            cur.next = new ListNode(carry);
        }
        return newHead.next;
    }

}

2、编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"
示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

• 水平扫描法

public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++)
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
return prefix;
}

时间复杂度：O(S)；S 是所有字符串中字符数量的总和。

空间复杂度：O(1)。我们只需要使用常数级别的额外空间。

• 分治法

public static void main(String[] args) {
        String[] strs = new Strin***ower","flow","flight"};
        String res = longestCommonPrefix(strs);
        System.out.println(res);
    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        return longestCommonPrefix(strs, 0 , strs.length - 1);
    }

    private static String longestCommonPrefix(String[] strs, int l, int r) {
        if (l == r) {
            return strs[l];
        }
        else {
            int mid = (l + r)/2;
            String lcpLeft =   longestCommonPrefix(strs, l , mid);
            String lcpRight =  longestCommonPrefix(strs, mid + 1,r);
            return commonPrefix(lcpLeft, lcpRight);
        }
    }

    static String commonPrefix(String left, String right) {
        int min = Math.min(left.length(), right.length());
        for (int i = 0; i < min; i++) {
            if ( left.charAt(i) != right.charAt(i) )
                return left.substring(0, i);
        }
        return left.substring(0, min);
    }

时间复杂度：O(S)O(S)，SS 是所有字符串中字符数量的总和，S=m*n。

空间复杂度：O(m \cdot log(n))。

内存开支主要是递归过程中使用的栈空间所消耗的。 一共会进行 log(n)log(n) 次递归，每次需要 mm 的空间存储返回结果，所以空间复杂度为 O(m\cdot log(n))。