415, 34, Add Strings, Find First and Last Position of Element in Sorted Array

415. Add Strings

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

1. The length of both num1 and num2 is < 5100.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. 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;
    }
}