Leetcode每日刷题(五)

题目一： 搜索插入位置

描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

解法：二分法

public int searchInsert(int[] nums, int target) {
    int lIndex = 0;
    int hIndex = nums.length - 1;

    int index = 0;

    while (lIndex <= hIndex) {
        index = (lIndex + hIndex) >> 1;
        int i = nums[index];

        if (target < i) {
            hIndex = index - 1;
        } else if (target == i) {
            return index;
        } else {
            lIndex = index + 1;
        }
    }
    return lIndex;
}

• 时间复杂度： 其中 为数组的长度。二分查找所需的时间复杂度为 。
• 空间复杂度： 常数空间存放若干变量。

题目二：两数相加

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

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

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

示例：

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

解法：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0);
        ListNode temp = res;

        int lastSum = 0;
        while (l1 != null || l2 != null) {

            int sum = (l1 == null ? 0 : l1.val)
                    + (l2 == null ? 0 : l2.val)
                    + (lastSum >= 10 ? 1 : 0);

            temp.next = new ListNode(sum % 10 );

            temp = temp.next;
            lastSum = sum;
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        if (lastSum >= 10){
            temp.next = new ListNode(1);
        }
        return res.next;
    }
}

文章永久链接：https://tech.souyunku.com/26456