算法储备-练习笔记(一)

Posted on | In
算法储备笔记
  1. 有序数组求等于某个数k的长度(k可能不存在于数组中)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function find(list = [], k, startIndex, endIndex) {
	if (startIndex === endIndex) return [-1]
	const mid = Math.floor((startIndex + endIndex)/2)
	const midNum = list[mid]
	const prevIndex = mid - 1
	const nextIndex = mid + 1
	const prev = list[prevIndex]
	const next = list[nextIndex]
	if (midNum === k && (prev < midNum || next > midNum)) {
		return [ mid ]
	}
	return [ ...find(list, k, startIndex, prevIndex), ...find(list, k, nextIndex, endIndex)].filter(el => el)
}
a = [1,2,3,3,3,3,4]
const idx = find(a, 3, 0, a.length - 1)
const { startIndex = 0, endIndex = 0 } = idx
console.log(idx.length === 1 ? 1: endIndex-startIndex )
  1. 二叉树深度
1
2
3
4
5
6
7
8
function getTreeDepth(tree) {
	if (!tree) return 0
	const leftDepth = getTreeDepth(tree.left)
	const rightDepth = getTreeDepth(tree.right)
	return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1
}

3.

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function addTwoNodeList(l1, l2) {
	return recursion(l1, l2, 0)
}
function recursion(l1, l2, isAdd) {
	const { isAdd: needAdd, value } = computeValue(l1, l2, isAdd)
	if (!l1.next && !l2.next && !isAdd) { 
		return { value, next: null }
	}
	return { value, next: recursion(l1.next, l2.next, needAdd) }
}
function computeValue(l1, l2, isAdd) {
	const l1Value = l1 ? l1.value || 0 : 0
	const l2Value = l2 ? l2.value || 0 : 0
	return { value: (l1Value + l2Value + isAdd) % 10, isAdd: l1Value + l2Value + isAdd > 9 ? 1 : 0 }
}