My frustration and ugly codes

Being a bioinformatic student, I have no problem using other people’s software and plug in required data. I can also interpret data correctly for most of the cases. However, I am always nervous about not having a really solid training in quantitative skills. This is making me replaceble. It is easy to teach a software engineer biology knowledge but it is far more harder to let a biology researcher to acquire hardcore coding ability and adapt the best practice. The secret lies in the trained mindset and working memory capacity to organize those information in the brain.

tags: Poor solution: Review required. There is some way better solution to reduce the execution time and memory usage. not solved yet: The problem is not solved yet.

1004. Max Consecutive Ones III

https://leetcode.com/problems/max-consecutive-ones-iii/

day1 0629

It was suggested to use sliding window to find the consecutive ones. However the window size is dynamic.

In order to find the max consecutive ones, you actually have to collect all the zeroes.

236. Lowest Common Ancestor of a Binary Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

day2 0630

Recursive is the solution. Prepare some base case, and traverse both left and right, then prepare return.

89. Gray Code

https://leetcode.com/problems/gray-code/

day3 0701

class Solution:
    def grayCode(self, n: int) -> List[int]:
        return [ i^(i>>1) for i in range(2**n) ]

https://zh.wikipedia.org/wiki/%E6%A0%BC%E9%9B%B7%E7%A0%81

It is an old thing, even got an patent in 1953. There are two methods to generate gray code. To implement them, one by recursive, the other by bit operation.

658. Find K Closest Elements

https://leetcode.com/problems/find-k-closest-elements/

day4 0702

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        diff = [ abs(num - x) for num in arr ]
        print(diff)
        rank = [i[0] for i in sorted(enumerate(diff), key=lambda x:x[1])]
        print(rank)
        return sorted([ arr[id] for id in rank[0:k] ])

Easy to get correct answer. Utilize pointer and binary search to achieve better performance. Use lambda and enumerate to sort list and get the ranking.

363. Max Sum of Rectangle No Larger Than K (not solved yet)

https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/solution/

day5 0703

# This is still wrong! Some cases fail
class Solution:
    
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        if not matrix:
            return 0
        
        m = len(matrix)
        n = len(matrix[0])
        ans = -sys.maxsize
        
        for i in range(m):
            for j in range(n):
                matrix[i][j] += matrix[i][j-1]
        for i1 in range(n):
            for i2 in range(i1,n):
                for j1 in range(m):
                    for j2 in range(j1,m):
                        boxSum = matrix[j2][i2]
                        if i1>0: boxSum -= matrix[j1][i1]
                        # if boxSum == k:
                        #     return k
                        
                        if ((boxSum<k) and (abs(k-boxSum) < abs(k-ans))):
                            ans = boxSum
        return ans

Easy to get correct answer but might be very slow. Encountered Time Limit Exceeded. Use Prefix Sum. Some advance algo kadaneSum or squeezing col or row can further speed it up.

1220. Count Vowels Permutation

https://leetcode.com/problems/count-vowels-permutation/

day6 0704

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = [[1, 1, 1, 1, 1]]
# Each vowel 'a' may only be followed by an 'e'.
# Each vowel 'e' may only be followed by an 'a' or an 'i'.
# Each vowel 'i' may not be followed by another 'i'.
# Each vowel 'o' may only be followed by an 'i' or a 'u'.
# Each vowel 'u' may only be followed by an 'a'.        
        for i in range(1, n):
            dp.append([0, 0, 0, 0, 0])
            dp[i][0] = dp[i-1][1] + dp[i-1][2] + dp[i-1][4]
            dp[i][1] = dp[i-1][0] + dp[i-1][2]
            dp[i][2] = dp[i-1][1] + dp[i-1][3]
            dp[i][3] = dp[i-1][2]
            dp[i][4] = dp[i-1][2] + dp[i-1][3]
        return sum(dp[n-1])%(10**9 + 7)

Dynamic programming according to the hint. Gotta imagine the 2d array to simplify the question first.

566. Reshape the Matrix

https://leetcode.com/problems/reshape-the-matrix/

day7 0705

class Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:        
        m = len(mat)
        n = len(mat[0])
        if (m*n != r*c): return mat
        data = []
        for i in range(m):
            data.extend(mat[i])
        print(data)
        M = [[0 for i in range(c)] for j in range(r)]
        for sn, info in enumerate(data):
            M[int(sn/c)][sn%c]  = info
        print(M)
        return M

Looks pretty simple. Turn it to 1d and then recontruct to 2d. Could further reduce the time. Declare a 2 dimension list/matrix filled with zeroes correctly, without changing unexpected elements.

1338. Reduce Array Size to The Half

https://leetcode.com/problems/reduce-array-size-to-the-half/

day8 0706

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        accumulation = 0
        count = 0
        from collections import Counter
        l = len(arr)
        for k, v in {k: v for k, v in sorted(Counter(arr).items(), key=lambda item: item[1], reverse=True)}.items():
            accumulation += v
            count += 1
            if accumulation >= l/2:
                return count 

Took some time to understand the question. Not hard to follow the hints. Use the Counter from collections. Use lambda and Counter and items() to sort a dictionary accoding to the value.

378. Kth Smallest Element in a Sorted Matrix

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

day9 0707

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        arr = []
        for row in matrix:
            arr.extend(row)
        arr = sorted(arr)
        return arr[k-1]

While the input matrix is sort of sorted, seems don’t affect the algorithm very much. Use matrix.pop() to further shrink the memory usage. To sort a list, we can sorted(list) or list.sort().

718. Maximum Length of Repeated Subarray

https://leetcode.com/problems/maximum-length-of-repeated-subarray/

day10 0708

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        dp = [[0 for j in range(len(nums2))] for i in range(len(nums1))]
        answer = 0
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                if (i == 0 or j == 0):
                    if (nums1[i] == nums2[j]):
                        dp[i][j] = 0+1
                        answer = max(answer, 0+1)
                    else:
                        dp[i][j] = 0
                else:
                    if (nums1[i] == nums2[j]):
                        dp[i][j] = dp[i-1][j-1]+1
                        answer = max(answer, dp[i-1][j-1]+1)
                    else:
                        dp[i][j] = 0
        return answer

Poor solution. Dynamic programming. Check a pair of numbers each time. use max() for comparison. Could reduce the if/else.

300. Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/

day11 0709

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # dp store the length of subsequence
        dp = [1]*len(nums)
        # go from 1 to the end, 0th is base case 1
        for i in range(1, len(nums)):
            # check every possible subsequence so far
            for j in range(i):
                # check if it is increasing
                if nums[i] > nums[j]:
                    # then update the currect max
                    dp[i]=max(dp[j]+1,dp[i])
        return max(dp)  

Poor solution. Dynamic Programming. O(N^2). Should update to O(Nlog(N)).

639. Decode Ways II

https://leetcode.com/problems/decode-ways-ii/

day12 0710

class Solution:
    # modulo
    mod =  10**9 + 7
    # prepare a def for recursive
    def solve(self,dp,s,i):
        # base case
        if i==len(s):
            return 1
        # over the iteration
        if i> len(s):
            return 0
        
        # already assigned
        if dp[i] != -1:
            return dp[i]
        # hit a wrong 0
        if s[i] == "0":
            dp[i] =0
            return dp[i]
        
        # reading the next one digit
        one = 0
        if s[i] == '*':
            # all 9 choice
            one += (9*self.solve(dp,s,i+1))% self.mod
        else:
            # actual number
            one += self.solve(dp,s,i+1)
            
        # reading the next two digits
        two = 0
        # check the next two digits available
        if  i+1 < len(s):
            # if it ends with *
            if s[i+1]=='*':
                # start with * => **
                # could only be 11-19(9), 21-16(6) => 9+6 = 15
                if s[i]=='*':
                    two += (15*self.solve(dp,s,i+2))% self.mod
                # '1*' => 11-19 (9)
                elif s[i] <'2':
                    two += (9*self.solve(dp,s,i+2))% self.mod
                # "2*" => 21-26 (6)
                elif s[i] == '2':
                    two += (6*self.solve(dp,s,i+2))% self.mod
            # not ends with *
            else:
                # start with * and ends with some thing less than 7
                # could be 13/23, or 15/25 => 2 possibilities
                if s[i] == "*" and s[i+1]<'7':
                    two += (2*self.solve(dp,s,i+2))% self.mod
                # any none * containing numbers
                elif s[i] <'2' or (s[i] == '2' and s[i+1] <'7'):
                    two += self.solve(dp,s,i+2)
        # register the all possibilities of the current reading point
        dp[i] = ((one % self.mod + two % self.mod)%self.mod)
        return dp[i]
                
        
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [-1]*(n+1)
        return self.solve(dp,s,0)

poor solution. recursive and dynamic programing. breakdown each cases and form up the equation.

295. Find Median from Data Stream

https://leetcode.com/problems/find-median-from-data-stream/

day13 0711

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        import bisect
        self.pointer = 0
        self.median = 0
        self.len = 0
        self.isOdd = False
        self.num_list = []        

    def addNum(self, num: int) -> None:
        bisect.insort(self.num_list, num)
        self.len += 1
        self.isOdd = not self.isOdd
        
    def findMedian(self) -> float:
        # 3 -> 1, 13 -> 6
        # 4->2
        self.pointer = self.len//2
        # odd, get the number directly
        if self.isOdd:
            return self.num_list[self.pointer]
        # even, get the average of two nearest
        else:
            return (self.num_list[self.pointer] + self.num_list[self.pointer-1])/2

poor solution. statistics.median(list) could return median but cause Time Limit Exceeded. Insert element to a sorted list: import bisect and bisect.insort(num_list, num) should work. However, heap is a better way to solve this. need update.

205. Isomorphic Strings

https://leetcode.com/problems/isomorphic-strings/

day14 0712

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        map_st = dict(zip(s,t))
        map_ts = dict(zip(t,s))
        for i in range(len(s)):
            if map_st[s[i]] != t[i] or map_ts[t[i]] != s[i]:
                return False
        return True

Besure to check the both direction. Use zip() to produce tuple pairs from multiple iterables.

162. Find Peak Element

https://leetcode.com/problems/find-peak-element/

day15 0713

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        # binary style
        l,r = 0, len(nums)-1
        
        # get rid of some corner case
        if r==0 or nums[r] > nums[r-1]:
            return r
        if nums[0] > nums[1]:
            return 0
        
        # helper function
        def getMid(l,r):
            return (l+r)//2
        # recursive
        def findPeak(arr, l, r):
            
            mid = getMid(l,r)
            
            # base case
            if (arr[mid] > arr[mid-1]) and (arr[mid] > arr[mid+1]):
                return mid
            # might locate at right
            elif (arr[mid] < arr[mid+1]):
                return findPeak(arr, mid, r)
            # might locate at left
            else:
                return findPeak(arr, l, mid)
            
        return findPeak(nums, l, r)

to get the answer in O(log(n)), must use the divide and concour approach. recursive. binary search.

791. Custom Sort String

https://leetcode.com/problems/custom-sort-string/

day16 0714

class Solution:
    def customSortString(self, order: str, str: str) -> str:
        new_str = ""
        suffix = ""
        # prepare a ordered string holder
        order_dict = {}
        # initialize the dictionary from list or iterable
        for o in order:
            order_dict[o] = ""
        # collect all appeared char and those not in `order`
        for s in str:
            if s in order_dict:
                order_dict[s] += s
            else:
                suffix += s
        # put collected things to string
        for k, v in order_dict.items():
            new_str += v
        # make sure to add the suffix
        new_str += suffix
        return new_str

easy one, normal speed and large memory distribution. can use lambda to make it one line. can use collections.Counter() to make life easier. use for loop to initialize the dictionary using the elements from list as keys.

611. Valid Triangle Number

https://leetcode.com/problems/valid-triangle-number/

day17 0715

Fail: Time Limit Exceeded

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        import itertools
        count = 0
        for triplet in itertools.combinations(nums, 3):
            triplet = sorted(list(triplet))
            if (triplet[0] + triplet[1] > triplet[2]):
                count += 1
        return count

use itertools.combinations(list, size) to create all combination.

better one

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        counter = 0
        for i in range(2, len(nums)):
            short1, short2 = 0, i-1
            # keep checking until all combination, then increase i
            while short2 > short1:
                # the short2 is big enough so all the other larger than short1 can fit
                if nums[short1] + nums[short2] > nums[i]:
                    counter += short2 - short1
                    short2 -= 1
                # overall to small, increase the short1 to see if things get better
                else:
                    short1 += 1
        return counter

use pointer to check. presorted to increase speed so a bunch of number can be added under certain condition.

18. 4Sum

https://leetcode.com/problems/4sum/

day18 0716

Failed: Time Limit Exceeded

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        import itertools
        nums.sort()
        answer = [()]
        i =0
        
        for (a,b,c,d) in set([(a,b,c,d) for (a,b,c,d) in itertools.combinations(nums, 4)]):
            
            if target == a+b+c+d:
                answer.append((a,b,c,d))
        answer.pop(0)
        answer = list(set(answer))
        answer = [ list(quadruplets) for quadruplets in answer]
        return answer

use itertools.combinations(list, size) to create all combination.

Annotated answer from the solution tab

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        
        def kSum(nums: List[int], target: int, k: int) -> List[List[int]]:
            res = []
            # corner case, empty nums, all component too big, or target too big
            if len(nums) == 0 or nums[0] * k > target or target > nums[-1] * k:
                return res
            # base case
            if k == 2:
                return twoSum(nums, target)
            # no need to worry the offset at the end, catched by corner case
            for i in range(len(nums)):
                # skip the duplicate numbers
                if i == 0 or nums[i - 1] != nums[i]:
                    # recursive funciton to reduce the K
                    #   only sending the rest of the nums
                    #   the remaining value of target
                    #   and the reduced k
                    for set in kSum(nums[i + 1:], target - nums[i], k - 1):
                        res.append([nums[i]] + set)
            return res

        def twoSum(nums: List[int], target: int) -> List[List[int]]:
            res = []
            lo, hi = 0, len(nums) - 1
            while (lo < hi):
                sum = nums[lo] + nums[hi]
                # too small or already checked the lo
                if sum < target or (lo > 0 and nums[lo] == nums[lo - 1]):
                    lo += 1
                # too large or already checked the hi
                elif sum > target or (hi < len(nums) - 1 and nums[hi] == nums[hi + 1]):
                    hi -= 1
                # get an answer, march forward, check those pairs in between
                else:
                    res.append([nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
            return res
        
        nums.sort()
        return kSum(nums, target, 4)

First thing to do is sort the list. Use two functions, one to solve basic rules, the other use recursion to extend the case. pointer. Using triple loop can solve this question faster but cannot deal with different K. Sorting + pointer + fixed variable.

927. Three Equal Parts

https://leetcode.com/problems/three-equal-parts/

day19 0717

class Solution:
    def threeEqualParts(self, arr: List[int]) -> List[int]:
        # get the index of all ones
        ones = []
        for sn,i in enumerate(arr):
            if i == 1:
                ones.append(sn)
        n = len(ones)
        s = len(arr)
        print(ones)
        # check corner cases
        if n == 0:
            # not sure why but it requires this
            return [0,s-1]
        # eliminate possibilities
        if n%3 != 0:
            return [-1,-1]
        
        # make sure each part have equal number of ones
        a, b, c = ones[0], ones[n//3], ones[n*2//3]
        print(a, b, c)
        # start stepping forward until break
        while (c < s and arr[a] == arr[b] and arr[b] == arr[c]):
            a += 1
            b += 1
            c += 1
        # there is an offset so no need to minus 1
        if c == s:
            return [a-1,b]
        # just no way to find the three parts
        else:
            return [-1,-1]

poor solution. First get the index of value providers. Then devide value equally to each part. At last do some adjustment, this part could be further improve to speed it up.

25. Reverse Nodes in k-Group

https://leetcode.com/problems/reverse-nodes-in-k-group/

day20 0718

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        # base case
        if not head:
            return None
        # corner case
        if k == 1:
            return head
        # check if next recursion is needed
        kSizeChecker = head
        for i in range(k):
            if not kSizeChecker:
                return head
            kSizeChecker = kSizeChecker.next
        # start the business
        cur = head
        nxt = None
        # leave a None for the head
        prv = None
        count = 0
        # link the current to the previous node
        while cur and count < k:
            count += 1
            # get next
            nxt=cur.next
            # link the current to previous node
            cur.next=prv
            # move on, for the next loop, current become previous
            prv=cur
            # move on, for the next loop, next become current
            cur=nxt
        # if there is still something after the linked list
        if nxt:
            # the orginal head is now the last, link it to the next recursion returned value
            head.next=self.reverseKGroup(nxt,k)
        # return the last processed node, which is now at the beginning of the linked list
        return prv

Linked list is a tree, so we can use recursion to solve this problem. hard problem.

235. Lowest Common Ancestor of a Binary Search Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

day21 0719

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # base case and corner cases
        if root is None:
            return None
        if root.val == p.val or root.val is q.val:
            return root
        
        left = root.left
        right = root.right
        # traverse left and right
        left = Solution.lowestCommonAncestor(self, left, p, q)
        right = Solution.lowestCommonAncestor(self, right, p, q)
        
        # resolve the returned recursion value
        if left is not None and right is not None:
            return root
        if right is None:
            return left
        if left is None:
            return right

use the binary tree solution would work, but it is a binary search tree, so we can simple use the value to determine left or right

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        # Value of current node or parent node.
        parent_val = root.val

        # Value of p
        p_val = p.val

        # Value of q
        q_val = q.val

        # If both p and q are greater than parent
        if p_val > parent_val and q_val > parent_val:    
            return self.lowestCommonAncestor(root.right, p, q)
        # If both p and q are lesser than parent
        elif p_val < parent_val and q_val < parent_val:    
            return self.lowestCommonAncestor(root.left, p, q)
        # We have found the split point, i.e. the LCA node.
        else:
            return root

384. Shuffle an Array

https://leetcode.com/problems/shuffle-an-array/

day22 0720

class Solution:

    def __init__(self, nums: List[int]):
        self.original_nums = nums

    def reset(self) -> List[int]:
        """
        Resets the array to its original configuration and return it.
        """
        return self.original_nums

    def shuffle(self) -> List[int]:
        """
        Returns a random shuffling of the array.
        """
        new_list = self.original_nums[:]
        random.shuffle(new_list)
        return new_list     

random.shuffle(list) to shuffle a list. list.copy() to copy the value of a list instead of reference. can take some time to learn how to not use the shuffle() method with Fisher-Yates Algorithm.

838. Push Dominoes

https://leetcode.com/problems/push-dominoes/

day23 0721

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        # prepare the boundary so your don't need to worry about corner cases
        dominoes = f'L{dominoes}R'
        length = len(dominoes)
        new_str = ""
        last_direction = 0

        # make move until finding direction
        for i,d in enumerate(dominoes):
            # skip if dot
            if d == '.':
                continue

            # we have to update since hitting non dot

            # calculate the number of the dots
            chunk = i - last_direction - 1 # only the ...
            # first add the starting char
            if last_direction:
                new_str += dominoes[last_direction]
            # now deal with the dots
            if dominoes[last_direction] == dominoes[i]: # L...L or R...R
                new_str += dominoes[last_direction] * chunk
            elif dominoes[last_direction] == 'R' and dominoes[i] == 'L':    
                new_str += 'R' * (chunk//2)
                new_str += '.' * (chunk%2)
                new_str += 'L' * (chunk//2)
            else: # L...R
                new_str += f"{'.'* chunk}"
            last_direction = i
        return new_str

未知生焉知死 or not: forcing the boundaries to eliminate corner cases. two main approaches, one is like this one updating gradually, the other is base on force.

915. Partition Array into Disjoint Intervals

https://leetcode.com/problems/partition-array-into-disjoint-intervals/

day24 0722

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        left_max, global_max, ans = nums[0], nums[0], 0
        for i in range(1, len(nums)):
            if nums[i] < left_max:
                # only update left_max if the new element is smaller
                # we don't need to update left_max if the new element is larger everytime
                left_max = global_max
                ans = i
            # the new element is larger than left_max
            # but also larger than global_max
            elif nums[i] > global_max:
                # however, we are not sure if the global_max should be the left part
                global_max = nums[i]
        return ans+1

if one max is not enough, then get another max. only update the local max when things are still in control. even when things are out of control, we still need to keep track of the global max.

814. Binary Tree Pruning

https://leetcode.com/problems/binary-tree-pruning/

day25 0723

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        
        # check corner case and base case, the end of the tree
        if root is None:
            return None
        
        # traverse
        root.left = Solution.pruneTree(self, root.left)
        root.right = Solution.pruneTree(self, root.right)
        
        # resolve operation
        if (root.val == 0 and root.left is None and root.right is None):
            return None
        return root

standard divide and conquer, be careful about corner cases and the boolean value.

126. Word Ladder II

https://leetcode.com/problems/word-ladder-ii/

day26 0724

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        # corner case
        if beginWord == endWord: return [beginWord]
        
        # init
        alphabet = "abcdefghijklmnopqrstuvwxyz"
        wordList = set(wordList)
        q = collections.deque([[beginWord, []]])
        answer = []
        
        # find all shortest path
        while q:
            # unpack value, one by a time
            current_word, path = q.popleft()
            # eliminate duplication possibility
            if current_word in wordList:
                wordList.remove(current_word)
            # resolve cases
            if current_word == endWord:
                # add to answer: no answer yet, or also shortest
                if not answer or len(path)+1 == len(answer[0]):
                    answer.append(path + [current_word])
                # break for path being too long
                elif len(path)+1 > len(answer[0]):
                    break
            # process next word 
            for i in range(len(current_word)):
                for a in alphabet:
                    next_word = f"{current_word[:i]}{a}{current_word[i+1:]}"
                    if next_word in wordList:
                        # add to the queue, don't use append for multiple hits in wordList
                        q.append([next_word, path + [current_word]])
        return answer

poor solution (too slow). using deque from collections for append and pop operation. when things seems complicated, just prepare all solutions and see how would they fit in real cases.

600. Non-negative Integers without Consecutive Ones

https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/

day27 0725

class Solution:
    def findIntegers(self, n: int) -> int:
        count = 0
        for i in range(n+1):
            if ((i<<1) & i)==0:
                count += 1
        return count

fail one. time limit exceeded.

class Solution:
    def findIntegers(self, n: int) -> int:
        # first get the lengh of the digit
        l = len(format(n,'b'))
        # prepare fibonacci sequence
        fib = [0]*(l+1)
        fib[0] = 1
        fib[1] = 2
        for i in range(2,l+1):
            fib[i] = fib[i-1] + fib[i-2]
        print(fib)
        # init some variables
        isLastBitOne = False # keep track of status
        answer = 0
        bit = l - 1 # offset for the fib
        # accumulate all numbers without Consecutive Ones
        while bit >= 0: # *imagine covering the first digit progressively to fill up need of the longest number*
            if (n & 1<<bit)==0: # current digit not one, means no need to add to answer
                isLastBitOne = False
            else: # current digit is one, means there are some more values need to add to answer
                answer += fib[bit] # add to answer
                if isLastBitOne: # got consecutive ones, all following no matter
                    return answer
                isLastBitOne = True
            bit -= 1 # check next, *imagine covering the first digit*
        return answer+1 # include itself

too hard for me. need to turn the question into fibonacci sequence.

108. Convert Sorted Array to Binary Search Tree

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

day28 0726

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums) -> TreeNode:

        l = len(nums)
        # base cases
        if l == 1:
            return TreeNode(nums[0])
        elif l == 0:
            return None
        # traverse the two side
        left = Solution.sortedArrayToBST(self,nums[:l//2])
        right = Solution.sortedArrayToBST(self, nums[l//2+1:])
        # instantiate the current node
        currentNode = TreeNode(nums[l//2], left, right)

        return currentNode

basic problem. take care of the list index.

16. 3Sum Closest

https://leetcode.com/problems/3sum-closest/

day29 0727

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        diff = sys.maxsize
        answer = 0
        for i in range(len(nums)):
            j = i+1
            k = len(nums)-1
            while k>j:
                tmp = nums[i] + nums[j] + nums[k]
                if tmp == target: return target
                if abs(tmp-target) < diff:
                    diff = abs(tmp-target)
                    answer = tmp
                elif tmp > target:
                    k -= 1
                else:
                    j += 1
        return answer

modified 3 sum question, sort an array when ever possible, use pointer and narrow down the search range.

932. Beautiful Array

https://leetcode.com/problems/beautiful-array/

day30 0728

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        ans = [1]
        while len(ans)<n:
            tmp  =[]
            tmp.extend([i*2-1 for i in ans if (i*2-1)<=n])
            tmp.extend([i*2 for i in ans if (i*2)<=n])
            ans = tmp
        return ans

special math problem. get familiar with even and odd numbers.