[其他] #9
Comments
剑指 Offer 57 - II. 和为s的连续正数序列
# 滑动窗口概念
class Solution(object):
def findContinuousSequence(self, target):
"""
:type target: int
:rtype: List[List[int]]
"""
result = []
half = target // 2
halfList = [x for x in range(1, half + 1)]
if target % 2 == 1: result.append([half, half + 1])
slide = 3
while slide < half: # 滑块长度 一定是从3开始, 因为相邻两个数相加 一定是个奇数
if sum(halfList[0: slide]) <= target:
i = 0
while i < half:
if sum(halfList[i: i + slide]) == target:
result = [halfList[i: i + slide]] + result
break
elif sum(halfList[i: i + slide]) > target: break
i += 1
slide += 1
else:
break
return result |
剑指 Offer 45. 把数组排成最小的数
# 其实是个 快速排序
class Solution:
def minNumber(self, nums: List[int]) -> str:
_len = len(nums)
if _len == 0: return ''
if _len == 1: return str(nums[0])
strList = [str(i) for i in nums] # [9,3,30,2,5] # 所有都转为字符串
"""
3, 30 比较 330 vs 303 则 [30, 3]
3, 2 比较 32 vs 23 则[2,3] 2 再和30比较 230 和 320 则[2, 30, 3]
最后 [5, 9]
"""
for i in range(1, _len):
x, y = i - 1, i
while x >= 0:
prev, next = strList[x], strList[y]
if int(prev + next) > int(next + prev): # 后面的小则换位置
strList[x], strList[y] = next, prev
x -= 1
y -= 1
else:
break
return ''.join(strList) |
剑指 Offer 16. 数值的整数次方同 50. Pow(x, n)1 - 分治思想 / 二分法 + 递归# 二分法 + 递归 => 分治思想
class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0: return 1
if n == 1: return x
if n < 0:
x = 1 / x
n = - n
if n % 2 == 1: # 奇数
return self.myPow(x * x, n // 2) * x
else:
return self.myPow(x * x, n // 2)2 - 位运算方法 TODO
|
🔥 剑指 Offer 62. 圆圈中最后剩下的数字 未独立解题约瑟夫环问题这个解释到位: 换个角度举例解决约瑟夫环class Solution:
def lastRemaining(self, n: int, m: int) -> int:
if n == 0 and n == 1: return 0
result = 0
# 从后往前推
for i in range(2, n + 1):
result = (m + result) % i
return result |
🔥 69. x 的平方根 TODO 牛顿法# 我想出来的，但并不好 利用 x^2 + 2x + 1 = value
class Solution(object):
def mySqrt(self, x):
if x == 0: return 0
if x == 1: return 1
n = 1
prev = n * n
while prev + 2 * n + 1 <= x:
prev += 2 * n + 1
n += 1
return n🔥 二分法解决 - 去找区间left * left < x < right * right, 先一步步缩小区间; class Solution(object):
def select(self, left, right, target):
if left + 1 == right:
if left * left <= target and right * right > target:
return left
else:
return right
half = (right - left) // 2 + left
# 区间选择 [half, x]
if half * half < target:
return self.select(half, right, target)
# 区间选择 [1, half]
elif half * half > target:
return self.select(left, half, target)
else:
return half
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x == 0: return 0
if x == 1: return 1
return self.select(1, x, x)
|
125. 验证回文串 TODOvar isPalindrome = function(s) {
// 正则去掉不是数字和字母的
s = s.replace(/[^0-9a-zA-Z]/g, '').toLowerCase()
// 双指针
i = 0
j = s.length - 1
while (i < s.length) {
if (s[i] !== s[j]) { return false }
i += 1
j -= 1
}
return true
}; |
模板渲染1 - 硬写 /**
* var template = "{{name}}很厉害，才{{age}}岁"
* var context = { name: "bottle", age: "15" }
* 输入: template context
* 输出: bottle很厉害，才15岁
*/
function fn (template, context) {
var arr = []
template.split('{{').map(item => {
arr = arr.concat(item.split('}}'))
})
var result = ''
arr.forEach(item => result += context[item] ? context[item] : item)
return result
}2 - 正则表达式 🔥🔥🔥🔥🔥🔥 var template = "{{name}}很厉害，才{{age}}岁, {{ name }}"
var context = { name: "周杰伦", age: "18" }
function fn (template, context) {
var match = /{{(.*?)}}/g
// val = {{ name }}, key = ' name '
var result = template.replace(match, (val, key) => {
return context[key.trim()]
})
return result
}
fn(template, context) |
手写async await// 异步
var getData = delay => new Promise(resolve => {
setTimeout(() => resolve(delay + 1000), delay)
})
// generator 使用 * + yield
function* fn (init) {
var data1 = yield getData(init)
console.log('data1', data1)
var data2 = yield _async(data1)
console.log('data2', data2)
var data3 = yield _async(data2)
console.log('data3', data3)
return data3
}
// 问题是: generator 不能自动推进下去, 必须是手动执行
// 1. 先去初始化执行一次
var start = fn(2000)
// { value: <Promise>, done: false }
// console.log(start.next())
// 2. start.next().value ... 调用
start.next().value.then(data1 => {
console.log(data1) // 1000
// 3. start.next(xxx).value ... 调用
start.next(data1).value.then(data2 => {
console.log(data2) // 2000
// 4. start.next(xxx).value ... 调用
start.next(data2).value.then(data3 => {
console.log(data3) // 3000
start.next(data3).value // 最后结尾部门
})
})
})co 实现function co (generatorFn, ...init_args) {
// promise 一定要在外面
return new Promise(resolve => {
var executor = generatorFn(...init_args) // 初始化执行
function NEXT (...args) {
// xxx.next(xxx).value.then(xx => ...)
var g = executor.next(...args)
if (g.done === true) { // 已经完成了
resolve(g.value) // 把最后值输出
return
}
return g.value.then((...data) => NEXT(...data))
}
NEXT()
})
}
co(fn, 1000).then(data => console.log('最终值: ', data)) |
快手 阿里 - 拆解URL参数中queryString硬写 // 快手面试题: 拆解URL参数中 queryString
// const url = 'http://sample.com/?a=1&b=2&c=xx&d=2#hash'
// const result = {a: "1", b: "2", c: "xx", d: "2"}
function fn (url) {
var [, querystring] = url.split('?')
if (querystring.length === 0) return {}
var result = {}
// querystring.split('#').shift(): a=1&b=2&c=xx&d=2
querystring.split('#')[0].split('&').forEach(item => {
var [key, val] = item.split('=')
result[key] = decodeURIComponent(val)
})
return result
}
fn('http://sample.com/?a=1&b=2&c=xx&d=2#hash')正则匹配过滤掉 一部分信息 function fn (url) {
// 匹配的是我要留下的内容
var arr = url.match(/([\w]+)=([\w]+)/g) // ["a=1", "b=2", "c=xx", "d=2"]
var result = {}
arr.forEach(item => {
var [key, val] = item.split('=')
result[key] = val
})
return result
}
fn('http://sample.com/?a=1&b=2&c=xx&d=2#hash') |
执行结果改造 🔥🔥🔥🔥🔥🔥🔥
forEach是不会等待异步执行的，所以是同步 1 - 用for 或 for of 他们会等 async function test () {
for (var i = 0; i < list.length; i++) {
var x = list[i]
var res = await square(x)
console.log(res)
}
}
test()async function test () {
for (x of list) {
var res = await square(x)
console.log(res)
}
}
test()2 - promise 链式调用 function test () {
var p = Promise.resolve()
list.forEach((x) => {
// p必须赋值, 要不然不对
p = p.then(() => square(x)).then(console.log)
})
}
test() |
LRU Least Recently Used 最近最少被访问 🔥
应用:
// 实现组件缓存, 组件切换时, 不会对组件进行卸载。
<keep-alive><component :is="view"></component></keep-alive>
keep-alive里有max设定, 当缓存数据大到一定程度，就开始执行LRU策略，将长久不用的组件通过key值标记，就释放掉了。Map常用api
- map = new Map()
- map.get(key)
- map.set(key, value)
- map.has(key)
- map.size() // length
- map.keys() // 返回是个迭代器
map.keys().next().value // 最少使用当前那个值class LRUCache {
constructor (capacity) {
this.capacity = capacity
this.cache = new Map()
}
get (key) {
// 有值则返回, 并删除后重新放入, 因为有顺序问题
if (this.cache.has(key)) {
var value = this.cache.get(key)
this.cache.delete(key)
this.cache.set(key, value)
return value
}
return -1
}
put(key, value) {
// 如果里面已经有了key值, 则覆盖重新进map
if (this.cache.has(key)) {
this.cache.delete(key)
this.cache.set(key, value)
} else if (this.cache.size < this.capacity) {
this.cache.set(key, value)
} else {
// 释放最少用的, 类似链表迭代器
// var keys = Array.from(this.cache.keys())
// var oldkey = keys[0]
var oldkey = this.cache.keys().next().value
this.cache.delete(oldkey)
this.cache.set(key, value)
}
}
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
剑指 Offer 66. 构建乘积数组
The text was updated successfully, but these errors were encountered: