Valid Anagram – Java

   public class Solution {
    /**
     * @param s: The first string
     * @param t: The second string
     * @return: true or false
     */
    public boolean anagram(String s, String t) {
        // write your code here
        if (s == null || t == null) {
            return false;
        }
        
        int[] cntS = new int[256];
        int[] cntT = new int[256];
        
        for (char c : s.toCharArray()) {
            cntS[c]++;
        }
        
        for (char c : t.toCharArray()) {
            cntT[c]++;
        }
        
        //Arrays.equals()
        for (int i = 0; i < 256; i++) {
            if (cntS[i] != cntT[i]) {
                return false;
            }
        } 
        return true;
    }
}

Time O(n). Space O(1).

LintCode 8 Rotate String – Python 3 ( Week 11 – 11)

 class Solution:
    """
    @param str: An array of char
    @param offset: An integer
    @return: nothing
    """
    def rotateString(self, s, offset):
        # write your code here
        if len(s) < 2 or offset % len(s) == 0:
            return s
            
        offset = offset % len(s)
        
        self.reverse(s, 0, len(s) - 1 - offset)
        self.reverse(s, len(s) - offset, len(s) - 1)
        self.reverse(s, 0, len(s) - 1)
        return s
        
        
        
    def reverse(self, s, start, end):
        while start < end:
            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1

Time O(n). Space O(1).

Recover Rotated Sorted Array – Python 3 ( Week 11 – 10)

Solution 1

   class Solution:
    """
    @param nums: An integer array
    @return: nothing
    """
    def recoverRotatedSortedArray(self, nums):
        # write your code here
        if not nums:
            return []
            
        minIndex = self.findMinimum(nums)
        if minIndex == 0:
            return nums
        #print(minIndex)
        self.reverseArray(nums, 0, minIndex - 1 )
        #print(nums[:minIndex])
        self.reverseArray(nums, minIndex, len(nums) - 1)
        #print(nums[minIndex:])
        self.reverseArray(nums, 0, len(nums) - 1)
        #print(nums)
        return nums
      
    
    def findMinimum(self, nums):
        minIndex = 0
        minmum = nums[0]
        for i in range(len(nums) - 1):
           if nums[i] < minmum:
               minmum = nums[i]
               minIndex = i
        return minIndex
        

    def reverseArray(self, nums, start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

Time O(n). Space O(1).

Median of two Sorted Arrays – Python 3 ( Week 11 – 09)

Solution 1

class Solution:
    def findMedianSortedArrays(self, A: List[int], B: List[int]) -> float:
        l = len(A) + len(B)
        if l % 2 == 0:
            return (self.findKth(A, 0, B, 0, l // 2) + self.findKth(A, 0, B, 0, l // 2 + 1)) / 2
        else:
            return self.findKth(A, 0, B, 0, l // 2 + 1)
            
        
    def findKth(self, A, astart, B, bstart, k):
        if astart >= len(A):
            return B[bstart + k - 1]
        if bstart >= len(B):
            return A[astart + k - 1]
            
        if k == 1:
            return min(A[astart], B[bstart])
            
        a = A[astart + k // 2 - 1] if astart + k // 2 - 1 < len(A) else None
        b = B[bstart + k // 2 - 1] if bstart + k // 2 - 1 < len(B) else None
        
        if b is None or (a is not None and a < b):
            return self.findKth(A, astart + k // 2, B, bstart, k - k // 2 )
        return self.findKth(A, astart, B, bstart + k // 2, k - k // 2 )

Time O(logmn). Space O(1).

Solution 2

class Solution:
    """
    @param: A: An integer array
    @param: B: An integer array
    @return: a double whose format is *.5 or *.0
    """
    def findMedianSortedArrays(self, A, B):
        # write your code here
        n = len(A) + len(B)
        if n % 2 == 0:
            return (self.findKth(A, B, n // 2) + self.findKth(A, B, n // 2 + 1) ) / 2.0
        return self.findKth(A, B, n // 2 + 1)
      
    #find Kth of A and B    
    def findKth(self, A, B, k):
        n = len(A)
        m = len(B)
        if n == 0:
            return B[k - 1]
        if m == 0:
            return A[k - 1]
        
        #binary search
        
        start = min(A[0], B[0])
        end = max(A[n - 1], B[m - 1])
        #T = end - start
        
        #log(end - start) times
        #O(logT * log(n+m))
        while start + 1 < end:
            mid = start + (end - start) // 2
            num = self.count_small_or_equal(A, mid) + self.count_small_or_equal(B, mid)
            #Time O(log(n+m))
            if num < k:
                start = mid
            else:
                end = mid
        
        if self.count_small_or_equal(A, start) + self.count_small_or_equal(B, start) == k:
            return start
        return end
        
    def count_small_or_equal(self, arr, target):
            
        start = 0
        end = len(arr) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if arr[mid] <= target:
                start = mid
            else:
                end = mid
        
        if arr[start] > target:
            return start
        elif arr[end] > target:
            return end
        return len(arr)

Time O(logT *log(m+n))

Merge Sorted Array – Python 3 ( Week 11 – 08)

   class Solution:
    """
    @param: A: sorted integer array A which has m elements, but size of A is m+n
    @param: m: An integer
    @param: B: sorted integer array B which has n elements
    @param: n: An integer
    @return: nothing
    """
    def mergeSortedArray(self, A, m, B, n):
        # write your code here
        
        t = m + n - 1
        i, j = m - 1, n - 1 
        
        while i >= 0 or j >= 0:
            if j < 0 or (i >= 0 and A[i] >= B[j]):
                A[t] = A[i]
                i -= 1 
            else:
                A[t] = B[j]
                j -= 1
            t -= 1 
            
        return A

Time O(n + m). Space O(1).

Remove Duplicates from Sorted Array II – Python 3 ( Week 11 – 07)

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        
        if len(nums) <= 1:
            return 1 
        
        index, ans, first = 0, 0, 0
        
        while first < len(nums):
            i = 1
            while first + i < len(nums) and nums[first] == nums[first + i]:
                i += 1
                
            if i == 1:
                nums[index] = nums[first]
                ans = index
                index += 1
                first += 1
            else:
                nums[index] = nums[first]
                nums[index + 1] = nums[first]
                ans = index + 1
                index += 2
                first += i
            
        return ans + 1

Time O(n). Space O(1).

Find Minimum in Rotated Sorted Array II – Python 3 ( Week 11 – 06)

class Solution:
    def findMin(self, nums: List[int]) -> int:
        min_num = nums[0]
        
        start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid] < nums[end]:
                end = mid
            elif nums[mid] > nums[end]:
                start = mid
            else:
                end = end - 1
        
        if nums[start] < nums[end]:
            return nums[start]
        else:
            return nums[end]

Time O(logn). Space O(n).

Search in Rotated Sorted Array – Python 3 ( Week 11 – 04)

Solution 1: One BS

   class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        
        start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            mid = int(start + (end - start) / 2)

            if nums[mid] >= nums[start]:
                if nums[start] <= target <= nums[mid]:
                    end = mid
                else:
                    start = mid            
            else:
                if  nums[mid] <= target <= nums[end]:
                    start = mid
                else:
                    end = mid
                    
        if nums[start] == target:
            return start
        elif nums[end] == target:
            return end
        
        return - 1

Time O(logn). Space O(1).

Solution 2: 2 BF

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        
        min_index = self.find_min_index(nums)
        
        if target <= nums[-1]:
            return self.find_target_index(nums[min_index:], target, min_index)
        else:
            return self.find_target_index(nums[:min_index], target, 0)
        
        
    def find_min_index(self, nums: List[int]) -> int:
        start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[start] > nums[end] and nums[start] < nums[mid]:
                    start = mid
            else:
                    end = mid
        
        if nums[start] < nums[end]:
            return start
        else:
            return end
    
    def find_target_index(self, nums, target, index) -> int:
        if not nums:
            return -1
        
        start = start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid] > target:
                end = mid
            else:
                start = mid
            
        if nums[start] == target:
            print(start)
            return index + start
        elif nums[end] == target:
            return index + end
        else:
            return -1

Add Digits – Python 3 (Week 11 – 03)

Solution 1

class Solution:
    def addDigits(self, num: int) -> int:
        
        ans = num
        
        while num > 9:
            ans = 0
            while num > 0:
                ans += num % 10
                num = num // 10
            num = ans
            
        return ans

Solution 2

  class Solution:
    def addDigits(self, num: int) -> int:
        
        if num == 0:
            return 0

        return (num - 1) % 9 + 1

Time complexity: O(n), assume n is the # of digits in the input. Space O(1).

Design a site like this with WordPress.com
Get started