Hanlin Shi

从空slice开始append会有因为capacity被超过导致多余的allocation以及copy。更简洁的做法是直接按照row size来allocate: ```golang func generate(numRows int) (res [][]int) { res = make([][]int, numRows) for k := 1; k

ASCII一共256个字符，其中数值为0的ASCII是Null char是不可被打印的，不用担心它会意外地出现在 `s` 或 `t` 中。 ```golang func isIsomorphic(s string, t string) bool { dict, used := [256]byte{}, [256]bool{} for i, c := range s { if dict[c] == 0...

二分的时候，中点可能落在3种情况中: 1. `nums[l]`, `nums[m]`, `nums[r]`单调递增 2. `nums` 大小会发生突变。`nums[m]` 在突变点左侧，即`nums[l]`< `nums[m]` 3. `nums` 大小会发生突变。`nums[m]` 在突变点右侧，即`nums[l]`> `nums[m]` 我们考虑要去除左半边的情况。对于 1, 3, 如果满足 `nums[m] < target = rv && (target > mv || target

第一层循环遍历不重复的节点，由于我们要在单链表里删除重复的节点，所以我们让慢指针指向前一个节点，遍历他的下一个元素。第二层循环遍历快指针，让他指向链表中上一层被遍历的元素与他值相同最后一个元素。O(n)时间 O(1)空间： ```golang func deleteDuplicates(head *ListNode) *ListNode { dummy := &ListNode{Next: head} for slow, fast := dummy, head; slow.Next != nil; { for fast = slow.Next; fast.Next != nil &&...

判断是不是等于lowbit： ```golang func isPowerOfTwo(n int) bool { if n

可以BFS直接套用102题的代码，改一下每层加入返回值数组的节点顺序即可，用了滚动数组时间也是beat 100%的: ```golang func zigzagLevelOrder(root *TreeNode) (res [][]int) { if root == nil { return } levels := [2][]*TreeNode{} levels[0] = []*TreeNode{root} for len(levels[len(res)%2]) != 0 { curr := len(res)...

这道题后来补充说要设计一个小于 `O(n)` 复杂度的算法，所以是要利用完全二叉树的性质的。 ``` Design an algorithm that runs in less than O(n) time complexity. ``` 我是通过比较二叉树最左和最右节点是不是在同一个level上，如果是的话利用完全二叉树性质就可以直接返回大小 `2^h-1`，如果不是的话再各自递归。 ```golang /** * Definition for a binary tree node. * type TreeNode...

Follow up里要求O(n logn)的解，可以用前缀和+二分来做: ```golang func minSubArrayLen(target int, nums []int) int { sum := make([]int, len(nums) + 1) for i, num := range nums { sum[i+1] = sum[i] + num }...

对于子串是不是回文可以用DP来加速。DP遍历子串的方式感觉面试不一定能想对或者解释清楚，于是可以用记忆化搜索。最后用DFS来收集结果。 ```golang const ( NotEvaluated = iota IsPalindrome NotPalindrome ) func partition(s string) (res [][]string) { dp := make([][]int8, len(s)) for i := range dp { dp[i] = make([]int8, len(s)...

借鉴了下思路，beat 100 100： ```golang import ( "bytes" "math" "sort" "strconv" ) func largestNumber(nums []int) string { sort.Slice(nums, func(i, j int) bool { v1, v2 := float64(nums[i]), float64(nums[j]) if v1 ==...