Coding Problems & Solutions

• Coding Problems & Solutions
  • cheatsheet
    • if none
    • while
    • generate list
  • Problems & Solutions
  • solution:

---

Coding Problems & Solutions

ᐕ)⁾⁾ como estas~~~~ bien~~~~ y tu?~~~~ yes

---

cheatsheet

if none

return stack == []

if len(stack) == 0:
  return True
return False


if s in d: d[s] += 1 # --- II
else: d[s] = 1

d[s] = d.get(s,0) + 1

while

while i <n:
  i+=1

for i in range(n):

while cur.next and cur.next.val==cur.val:
  cur.next=cur.next.next
cur=cur.next

if cur.next and cur.next.val==cur.val:
  cur.next=cur.next.next
else:
  cur=cur.next

compare sum:

1. all negative -> no sum compare, if positive -> sum
2. if cur_sum < 0, cur_sum = 0, cur_sum += n, max(max, cur_sum)

# slow
if (root1, root2) == (None, None):

# fast
if root1 is None and root2 is None:

calculate specific step:

1. list all known step ```py if n in [1,2,3]: return n

n={1:1, 2:2} return n[i]

if(n<=2): return n

**Binary tree**

1. inorder:

```py
list = left_list + root + right_list

cur = root
stack.append(root)
while stack != []:
  if cur == None:
    out = stack.pop()
    ans.append(out.val)
    cur = cur.right
  else:
    stack.append(cur)
    cur = cur.left
ans.pop()

Sort Algorithms

best case:
[1,2,3,4,5] or [1,1,1,1,1,1]

generate list

self.sums = list([[0] * (m+1) ] * (n+1))  # nononononononono!!!!!!!

self.sums = [ [0 for j in range(m+1)] for i in range(n+1) ]

---

Problems & Solutions

Level	Title	Basic idea	⭐
—	—	slow fast 指针
Easy	26. Remove Duplicates from Sorted Array	slow fast 指针	✔️
Easy	27. Remove Element	slow fast 指针	✔️
Easy	283. Move Zeroes	slow fast 指针	✔️
Easy	83. Remove Duplicates from Sorted List	slow fast 指针	✔️
—	—	前缀和 sums = []
Medium	560. Subarray Sum Equals K	前缀和	✔️
Medium	304. Range Sum Query 2D - Immutable	前缀和,块状加减乘除	✔️
Easy	001.Two-Sum 挑两个和为 target 的数字	enumerate(), (index, value) 阅过放入dic，在看目标结果是否已在dic里 if target-num in dic: return [a[target - num], index]	✔️ py
Easy	007.Reverse-Integer	str[::-1]*-1	✔️
Medium	015.Three-Sum 3sum -> num + 2sum	num + 2 sum; 2sum -> dic, 阅过放入dic 2sum -> linea, 2 pointers left and right find target	✔️ py
Easy	020.Valid-Parentheses	扣除开闭和符号: 1.成组的replace 2.组成dic，一个个放入新list，成pair就扣除	✔️
Easy	021.merge-two-sorted-lists	listNode, head = dump, l1 l2 compare, dump.next = ?, l1/l2 = l1/l2.next, dump.next=l2/l1, return head.next	✔️
Easy	053.Maximum-Subarray 算连续sum最大的sub	1. compare i with pre_sum+i for starting point, add one by one for maxSum. 2. separate the negative and positive，if have positive 加currNum比大小 3. if cur_sum < 0, cur_sum = 0, cur_sum += n, max(max, cur_sum) 4. nums[i]=mac(当前sum+nums[i]，nums[i]) -> max(nums)	✔️ py
Medium	056.Merge-Intervals [[1,3],[2,6]] > [[1,6]]]	sorted(list, key), if outlist not empty or merged[-1][1] > interval[0], merge; other, outlist.append	✔️ py
Easy	094.binary-tree-inorder-traversal		✔️
Easy	[104.Maximum-Depth-of-Binary-Tree] 算🌲层数	if 最底层 root==null, 算一层。然后看左边，然后看右边。return 1+左边右边。	✔️
Medium	200.Number-of-Islands 1 是岛屿， 0 是水，计算有几个连着的岛屿	DFS 遍历每一个point，是1：把自己和另据都变成0.加一，然后遍历下一个	✔️ py
Easy	[206.Reverse-Linked-List] 1>2>3>Null to 3>2>1>Null	pre,curr,head 3 point iterate ; Recursion the rest and point to the head	✔️ py
Easy	[226.Invert-Binary-Tree] 🌲 把左右颠倒	if 最底层 root==null, 返回null，要不然左边等于右边。然后左边套算式迭代，右边套算式迭代。	✔️
Easy	242.Valid-Anagram 2个string，看字符是否相同 cat=tca cat！=car	py很快，return sorted(s1) == sorted(s2) 对比; java算 s.toCharArray(); charlist sorted，然后比较	✔️
Easy	[617.Merge-Two-Binary-Trees] 加法合并两个🌲	t1 往 t2 套，如果t2为null返回t1，否则就加t1.data。然后左边套算式迭代，右边套算式迭代。	✔️
Easy	[653.Two-Sum-IV-Input-is-a-BST] 找🌲里有没有数可以加成key	看key是否等于root，不等于，下层为null返回false，下层有数字则减去root继续往下算。每层迭代。	✔️
Easy	[938.Range-Sum-of-BST] 计算🌲里在key [L,R] 范围内的和	1.计算每个数字大小，在内部就加。 2.看数字是否在范围，然后看左边右边。左边套算式迭代，右边套算式迭代，+root大小。	✔️

Level	Title	Basic idea	⭐
Easy	[001.Trailing-zeros-in-factorial]	0s number = 5s number from int. one number at a time, calculate all.	✔️
Easy	[001.Numbers-factorials-end-with-zeros]	binarysearch find smallest number start x 0s，add 1 and calculate from the smallest one by one.	✔️

---

solution:

• 1
• 2
• 3
• 4
• 1
• 1
• 结构之法 算法之道
• 算法学习之路

Data Structure Visualizations:

• 1
• 2

---

:purple_heart: some link:

⭐ when the runestone error: use this link to access the text book