search

Linjiayu6 / LeetCode

[2019+] CS Fundamentals: Algorithms and Data structures
0 stars 0 forks source link

[其他] #9

Open Linjiayu6 opened 4 years ago

Linjiayu6 commented 4 years ago

剑指 Offer 66. 构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
思路
1. forward正向 [占位1, 1, 1 * 2, 1 * 2 * 3, 1 * 2 * 3 * 4]
2. backward反向 [占位1, 5, 5 * 4, 5 * 4 * 3, 5 * 4 * 3  * 2][::-1]
3. forward[0] * backward[0],  forward[1] * backward[1], ....... 
class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
        if len(a) == 0: return []
        if len(a) == 1: return a
        if len(a) == 2: return a[::-1] # [3, 2] return [2, 3]

        # [1, 2, 3, 4]
        # forward = 正向推理一次 [占位1, 1, 1 * 2, 1 * 2 * 3]
        # backward = 反向推理一次 [4 * 3 * 2 ,4 * 3, 4, 占位1]
        # forward[0] * backward[0], forward[1] * backward[1], forward[2] * backward[2] ....

        forward, backward = [1], [1]
        tmp = 1
        for i in range(0, len(a) - 1):
            tmp *= a[i]
            forward.append(tmp)
        tmp = 1
        for j in range(len(a) - 1, 0, -1):
            tmp *= a[j]
            backward.append(tmp)
        backward = backward[::-1]

        result = []
        for i in range(len(a)): result.append(forward[i] * backward[i])
        return result
Linjiayu6 commented 4 years ago

剑指 Offer 57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

image

# 滑动窗口概念
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
Linjiayu6 commented 4 years ago

剑指 Offer 45. 把数组排成最小的数

image 快速排序

# 其实是个 快速排序
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)
Linjiayu6 commented 4 years ago

剑指 Offer 16. 数值的整数次方

同 50. Pow(x, n)

1 - 分治思想 / 二分法 + 递归

思路:
myPow(3, 7) 
[3, 3, 3, 3, 3, 3, 3] len = 7

答:
新的值: 3 * 3 = 9
新的分组: 分成 7 // 2 = 3
因为是奇数, 多出来部分 * 3
myPow(9, 3) * 3 (因为是奇数, 所以多出来一个3)
# 二分法 + 递归 => 分治思想
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

image

Linjiayu6 commented 4 years ago

🔥 剑指 Offer 62. 圆圈中最后剩下的数字 未独立解题

约瑟夫环问题

题目:
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，
则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

引用来自Leetcode

这个解释到位: 换个角度举例解决约瑟夫环

从后往前推理, 找到本来的位置
余数的意义: 被剩下的意思

解题思路:
删除第三个数
[a, b, c] 被删除的是 c
=> [a, b] 删除的是a
=> [b]

从后往前推
b index = 0,  往上找在数组长度为2的时候, 他的位置是? 1  (0 + 2) % 3 = 1 b 在[a, b] 时候位置为1
[a, b] (1 + 3) % 3 = 1 在[a, b, c] 时候位置为1
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
Linjiayu6 commented 4 years ago

🔥 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, 先一步步缩小区间;

13 
1. 区间 [1, 13]
   13 - 1 // 2 + 1 = 7  => 7 * 7 > 36    所以 [1, 6]
2.区间 [1, 7]
   7 - 1 // 2 + 1 = 4 => 4 * 4 > 13   所以 [1, 4]
3. 区间 [1, 4]
   4 - 1 // 2 + 1 = 2 =>  2 * 2 < 13  所以 [2, 4 ]
4. 区间 [2, 4]
   4 - 2 // 2 + 2= 3 => 3 * 3 < 9 所以 [3, 4]
5. 区间[3, 4]
最后锁定了3
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)
Linjiayu6 commented 4 years ago

125. 验证回文串 TODO

var 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
};
Linjiayu6 commented 4 years ago

模板渲染

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)
Linjiayu6 commented 4 years ago

手写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))
Linjiayu6 commented 4 years ago

快手 阿里 - 拆解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')
Linjiayu6 commented 4 years ago

执行结果改造 🔥🔥🔥🔥🔥🔥🔥

forEach是不会等待异步执行的，所以是同步

// 一起输出 1, 4, 9
const list = [1, 2, 3]
const square = num => {
  return new Promise((resolve, reject) => {
    setTimeout(() => {
      resolve(num * num)
    }, 1000)
  })
}

function test() {
  list.forEach(async x=> {
    const res = await square(x)
    console.log(res)
  })
}
test()

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()
Linjiayu6 commented 4 years ago

LRU Least Recently Used 最近最少被访问 🔥

146. LRU缓存机制

应用: 

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)
        }
    }
}