given an ascending array of integers nums, and a target value target. Find the starting and ending positions in the array for the given target value.
your algorithm’s time complexity must be O(log n).
if there is no target value in the array, return [-1, -1].
example 1 :
enter : nums =,7,7,8,8,10 [5], target = 8
output: [3, 4]
sample 2 :
enter : nums =,7,7,8,8,10 [5], target = 6
output: [1, 1]
thought and code
O(log n) is the complexity of
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[] {-1, -1};
if (nums.length < 1) return res;
int firstIndex = search(nums, target - 1);
// 如果大于target-1 的第一个索引就超级界 或者 第一个索引的值不是target 那么就说明当前数组没有目标值
if (firstIndex == nums.length || nums[firstIndex] != target) return res;
else res[0] = firstIndex;
res[1] = search(nums, target) - 1;
return res;
}
public int search(int[] nums, int target) {
// 找到大于target值的第一个位置
int l = 0, r = nums.length;
while (l < r) {
int m = l + (r - l) / 2;
if (target >= nums[m]) l = m + 1;
else r = m;
}
return l;
}
}
The sum of the two numbers of leetcode
title: gives two non-empty linked lists to represent two non-negative integers. Their individual bits are stored in reverse order, and each of their nodes can only store one digit.
if we add these two Numbers together, a new linked list will be returned to represent their sum.
you can assume that neither number begins with 0, except for the number 0.
example:
method: simulate
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null, tail = null;
int carry = 0;
while (l1 != null || l2 != null) {
int n1 = l1 != null ? l1.val : 0;
int n2 = l2 != null ? l2.val : 0;
int sum = n1 + n2 + carry;
if (head == null) {
head = tail = new ListNode(sum % 10);
} else {
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
carry = sum / 10;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry > 0) {
tail.next = new ListNode(carry);
}
return head;
}
}
complexity analysis
time complexity: O(Max (m,n)), where m,n is the length of two linked lists. We’re going to go through all the places in both lists, and it only takes order (1) time to process each place.
space complexity: O(\ Max (m,n)). The length of the answer list is at most the length of the longer list +1.