Given two non-negative integers
num1
and num2
represented as string, return the sum of num1
and num2
.
Note:
- The length of both
num1
andnum2
is < 5100. - Both
num1
andnum2
contains only digits0-9
. - Both
num1
andnum2
does not contain any leading zero. - You must not use any built-in BigInteger library or convert the inputs to integer directly.
class Solution { public String addStrings(String num1, String num2) { int carry = 0; StringBuilder sb = new StringBuilder(); for (int i = 0; i < num1.length() || i < num2.length(); i++) { int n1 = 0, n2 = 0; if (i < num1.length()) n1 = num1.charAt(num1.length() - 1 - i) - '0'; if (i < num2.length()) n2 = num2.charAt(num2.length() - 1 - i) - '0'; sb.append((n1 + n2 + carry) % 10); carry = (n1 + n2 + carry) / 10; } if (carry > 0) sb.append(carry); return sb.reverse().toString(); } }
34. Find First and Last Position of Element in Sorted Array
Given an array of integers
nums
sorted in ascending order, find the starting and ending position of a given target
value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return
[-1, -1]
.
Example 1:
Input: nums = [5,7,7,8,8,10]
, target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10]
, target = 6
Output: [-1,-1]
----------------------------用2分找开头跟结尾
class Solution { public int[] searchRange(int[] nums, int target) { int[] rt = new int[2]; rt[0] = findStart(nums, 0, nums.length - 1, target); if (rt[0] == -1) { rt[1] = -1; }else { rt[1] = findEnd(nums, rt[0], nums.length - 1, target); } return rt; } private int findStart(int[] nums, int left, int right, int target) { while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) { if (mid == 0 || (mid > 0 && nums[mid - 1] != nums[mid])) { return mid; } right = mid - 1; } else if (nums[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } private int findEnd(int[] nums, int left, int right, int target) { while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) { if (mid == nums.length - 1 || (mid < nums.length - 1 && nums[mid + 1] != nums[mid])) { return mid; } left = mid + 1; }else if (nums[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } }
No comments:
Post a Comment