leetcode笔记

心得

• 在for里面加入if的全体退出判断要慎重。小概率的if退出，放在for循环结束后再判断，成本更低。

js

定义一个全为0的数组

let data = new Array(26)
for (let i = 0; i < 26; i++) {
  data[i] = 0
}

• 规定大小能比直接令为[]，少一些内存，虽然就0.1mb的样子

• 用for循环来填充是最快的

sort()排序

nums.sort((a, b) => a - b);

sort()设计出来，就是为了字符串的排序。输入number会先转换为string，即25会大于100

而sort()接受一个compareFunction(a, b)，如果返回值小于0，那么a被排到b的前面；大于0则相反；等于0就不变。 因此从小到大的比较函数，可以写为(a, b)=> a-b，从大到小就可以是(a, b)=> b-a

数组第一层深拷贝

let new = old.slice()

~~

有个更加简单的方法来取地板

~~()

就是前面加两个波浪号。就是两次按位非。

也不知道为啥，反正能把小数点都扔掉。

不仅如此，还能把字符串变成数字，如果不是数字还能变成0

~~"word"  // 0
~~"123" // 123
~~123.32 //123

image-20191029105822104

go

for循环

for i := 1; i < 5; i++ {
    sum += i
}

for i, s := range strings {
    fmt.Println(i, s)
}

转换

int转string

string:=strconv.Itoa(int)

int64转string

string:=strconv.FormatInt(int64,10)

string转int

int,err:=strconv.Atoi(string)

string转int64

int64, err := strconv.ParseInt(string, 10, 64)

排序

sort.Ints(intList)
sort.Slice(sArr, func(i, j int) bool {
  return sArr[i] < sArr[j]
})

// 2d
sort.Slice(n, func(i, j int) bool {
  for x := range n {
    if n[i][x] == n[j][x] {
      continue
    }
    return n[i][x] < n[j][x]
  }
  return false
})

json序列化和反序列化

value := "{\"FailTime\":1571909067,\"FailReason\":\"2\"}"

var failsInfo FailsInfo
err := json.Unmarshal([]byte(value), &failsInfo)
if err != nil {
  return nil, err
}

failsInfo.FailTime

深拷贝

before := []int{2, 1, 2}
new := make([]int, len(before))
copy(new, before)

pop

x, a = a[len(a)-1], a[:len(a)-1]

python

排序

mylist.sort()

逆序for

for i in range(len(nums)-1, -1, -1):
  ...

一些算法

清除二进制位中最右边的1

n &= n - 1

如，统计二进制有多少个1

func count1(n int) int {
    var res int
    for n != 0 {
        n &= n - 1
        res++
    }
    return res
}

位运算判断奇偶

(number & 1) == 0
// 0: 偶数，1: 奇数

交换两个变量的值

a = a ^ b
b = a ^ b
a = a ^ b

两分法

var searchInsert = function(nums, target) {
  const length = nums.length;
  if (nums[length - 1] < target) {
    return length;
  } else if (length === 0) {
    return 0;
  }
  let left = 0;
  right = length - 1;
  while (left < right) {
    let mid = (left + right) >>> 1;
    if (target > nums[mid]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return right;
};

def binary_search(array, target):
    low = 0
    high = len(array)-1
    while low < high:
        mid = (low+high) >> 1
        if target > array[mid]:
            low = mid+1
        else:
            high = mid
    return high

mid = (left+right)>>1

即使left+right整型溢出，变成负数，无符号右移，能得到正数的正确结果。

mid另一种求法：

mid = left + (right-left)//2

或者用右移：

mid = left + ((right-left)>>1)，记得要加括号，加减优先级比右移要高，不加要出问题。

异或

三项判断，如果知道不可能均为真/假，如何判断是两项为真，还是一项为真

用异或，把判断结果连起来

两项真，异或结果为假；一项真，异或结果为真

中序遍历

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        p = root
        count = 0
        while p is not None or stack:
            while p is not None:
                stack.append(p)
                p = p.left
            p = stack.pop()
            count += 1
            if count == k:
                return p.val
            p = p.right

回溯

主要是，剩余路径+已经走过的路径

image-20191221095220049