# 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.

## 542. 01 Matrix

https://leetcode.com/problems/01-matrix/

day31 0729

```
class Solution:
def updateMatrix(self, mat):
from collections import deque
m = len(mat)
n = len(mat[0])
maxsize = m*n
q = collections.deque()
def isBoundary(mat, i, j):
check = False
if i > 0:
check = check or mat[i-1][j] == 0
if j > 0:
check = check or mat[i][j-1] == 0
if i < (len(mat)-1):
check = check or mat[i+1][j] == 0
if j < (len(mat[0])-1):
check = check or mat[i][j+1] == 0
return check
for i in range(m):
for j in range(n):
if mat[i][j] == 0:
continue
elif isBoundary(mat, i, j):
q.append((i, j))
else:
mat[i][j] = maxsize
while(q):
(i, j) = q.popleft()
current_point = mat[i][j]
current_point_neighbor = [(i-1, j), (i, j-1), (i+1, j), (i, j+1)]
for (k, l) in current_point_neighbor:
# no need to change, out of mat or already zero
if (k not in range(m)) or (l not in range(n)):
continue
elif mat[k][l] == 0:
continue
elif mat[k][l] == maxsize:
q.append((k, l))
# in case there is already a smaller value
mat[k][l] = min(current_point+1, mat[k][l])
return mat
```

breadth first search. take care of the boundary.