算法题（一）

var s = new String('abc');

s.charAt(1) // "b"
s.charAt(s.length - 1) // "c"

for (var i = 0; i < arr.length; i++) {
  if (arr[i] === 2) break;
  console.log(arr[i]);
}
//1

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        dp = [0] * (k + 1)
        m = 0
        while dp[k] < n:
            m += 1
            for i in range(k, 0, -1):
                # print(m, k)
                dp[i] = dp[i - 1] + dp[i] + 1
        return m

class Solution:
   def uniquePaths(self,m:int,n:int)->int:
       dp = [[0]*n for _ in range(m)]
       for i in range(m)
           dp[i][0] = 1
       for i in range(n)
           dp[0][i] = 1
       for i in range(1,m)
           for j in range(1,n)
               dp[i][j] = dp[i][j-1] + dp[i-1][j]
       return dp[m-1][n-1]

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        dp = [[0] * len(grid[0])] * len(grid)
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i > 0 and j > 0:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
                elif i > 0:
                    dp[i][j] = dp[i - 1][j] + grid[i][j]
                elif j > 0:
                    dp[i][j] = dp[i][j - 1] + grid[i][j]
                else:
                    dp[i][j] = grid[i][j]
        return dp[-1][-1]

class Solution:
   def minCut(self,s:str)->int:
       if s == s[::-1]:
          return 0
       
       for i in range(1,len(s)+1);
           if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]
              return 1
       
       dp[i-1 for i in range(len(s)+1)]
       for i in range(1,len(s)+1):
           for j in range(i)
               if s[j:i] == s[i:j][::-1]
                  dp[i] = min(dp[i],dp[j]+1)
       return dp[-1]

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)#三角形行数
        if n==1: return triangle[0][0]
        dp = [[0]*n for i in range(n)]
        
        for i in range(n-1,-1,-1):
            for j in range(len(triangle[i])):
                if i==n-1:
                    dp[i][j]=triangle[i][j]
                else:
                    dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]#(i,j)到达最后一行的最小路径 = min((i+1,j), (i+1,j+1))+triangle[i][j]
        return dp[0][0]

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
      	res = [0 for _ in range(amount + 1)]
        
        for i in range(1, amount + 1):
            cost = float('inf')
            for c in coins:
                if i - c >= 0:
                    cost = min(cost, res[i - c] + 1)
            res[i] = cost
        
        if res[amount] == float('inf'):
            return -1
        else:
            return res[amount]

class Solution:
    def rob(self, nums: List[int]) -> int:
        n=len(nums)
        if n==0:return 0
        if n==1:return nums[0]
        if n==2:return max(nums[0],nums[1])
        
        dp=[0]*n
        dp[0]=nums[0]
        dp[1]=max(nums[0],nums[1])
        
        for i in range(2,n):
            dp[i]=max(dp[i-1],dp[i-2]+nums[i])
        
        return dp[-1]

class Solution:
    def rob(self, nums: List[int]) -> int:
      if (n := len(nums)) == 0:
        return 0
      if n == 1:
        return nums[0]
      result1 = self.robRange(nums, 0, n - 2)
      result2 = self.robRange(nums, 1, n - 1)
      return max(result1 , result2)

    def robRange(self, nums: List[int], start: int, end: int) -> int:
      if end == start: return nums[start]
      dp = [0] * len(nums)
      dp[start] = nums[start]
      dp[start + 1] = max(nums[start], nums[start + 1])
      for i in range(start + 2, end + 1):
        dp[i] = max(dp[i -2] + nums[i], dp[i - 1])
      return dp[end]

class Solution:
    def rob(self, root: TreeNode) -> int:
        if root is None:
            return 0
        if root.left is None and root.right  is None:
            return root.val
        # 偷父节点
        val1 = root.val
        if root.left:
            val1 += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right:
            val1 += self.rob(root.right.left) + self.rob(root.right.right)
        # 不偷父节点
        val2 = self.rob(root.left) + self.rob(root.right)
        return max(val1, val2)

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # If null return ""
        if len(strs) == 0:
            return ""

        prefix = strs[0]

        for i in range(1, len(strs)):
            while(strs[i].find(prefix) != 0):
                prefix = prefix[:-1]
                if len(prefix) == 0:
                    return ""

        return prefix

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
				if len(strs) == 0:
            return ""

        for i in range(len(strs[0])):
            for j in range(1, len(strs)):
                if i == len(strs[j]) or strs[0][i] != strs[j][i]: # i==len must be put at the front
                    return strs[0][:i]

        return strs[0]

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n1, n2 = len(text1), len(text2)
        pre = [0 for _ in range(n2 + 1)]
        dp = [0 for _ in range(n2 + 1)]
        for i in range(n1):
            for j in range(1, n2 + 1):
                if text1[i] == text2[j-1]:
                    dp[j] = pre[j-1] + 1
                else:
                    dp[j] = max(pre[j], dp[j-1])
                pre[j-1] = dp[j-1]
            pre[j] = dp[j]
        return dp[-1]

class Solution:
   def numMatchingSubseq(self,s:str,words:List)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]
        for j in range(len(dp[0])):
            dp[0][j] = j
        for i in range(len(dp)):
            dp[i][0] = i
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(1 + dp[i][j-1], 1 + dp[i-1][j], 1 + dp[i-1][j-1])
        return dp[-1][-1]

class Solution:
    def maximumProduct(self,nums:List[int])->int:
        nums.sort()
        return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])

class Solution:
    def largestDivisibleSubset(self,nums:List[int])->List[int]:
        if not nums: return nums
        if len(nums) == 1: return nums
        l = len(nums)
        nums.sort()
        
        dp = [[i] for i in nums]
        
        for i in range(1,l):
            for j in range(i-1,-1,-1):
                if nums[i]%nums[j] == 0:
                   dp[i] = max(dp[j] + nums[i],dp[i],key = len)
                    
        return max(dp,key=len)

class Solution:
    def maxArea(self, height: List[int]) -> int:
      """
        :type height: List[int]
        :rtype: int
        """
        left = 0
        right = len(height) - 1
        maxArea = 0
        while left < right:
            b = right - left
            if height[left] < height[right]:
                h = height[left]
                left += 1
            else:
                h = height[right]
                right -= 1
            area = b*h
            if maxArea < area:
                maxArea = area
        return maxArea

f(6)
//递
=>6*f(5)
=>6*(5*f(4))
=>6*(5*(4*f(3)))
=>6*(5*(4*(3*f(2))))
=>6*(5*(4*(3*(2*f(1)))))
//归
=>6*(5*(4*(3*(2*1))))
=>6*(5*(4*(3*2)))
=>6*(5*(4*6))
=>6*(5*24)
=>6*120
=>720

//直接执行
def fabonacci(n)
    return fabonacci(n-1)+fabonacci(n-2)
//赋值给变量再执行，错误
def fabonacci(n)
    n = n-1
    m = n-2
    return fabonacci(n)+fabonacci(m)

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

class Solution:
    def letterCombinations(self, digits: str) -> list:
        KEY = {'2': ['a', 'b', 'c'],
               '3': ['d', 'e', 'f'],
               '4': ['g', 'h', 'i'],
               '5': ['j', 'k', 'l'],
               '6': ['m', 'n', 'o'],
               '7': ['p', 'q', 'r', 's'],
               '8': ['t', 'u', 'v'],
               '9': ['w', 'x', 'y', 'z']}
        if digits == '':
            return []
        ans = ['']
        for num in digits:
            ans = [pre+suf for pre in ans for suf in KEY[num]]
        return ans

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        if len(s) == 0:
            return [[]]
        if len(s) == 1:
            return [[s]]
        tmp = []
        for i in range(1,len(s)+1):
            left = s[:i]
            right = s[i:]
            if left ==left[::-1]: #如果左侧不是回文的，则舍弃这种尝试
                right = self.partition(right)
                for i in range(len(right)):
                    tmp.append([left]+right[i])
        return tmp

class Solution:
    def search(self, nums: List[int], target: int) -> int:
      	left, right = 0, len(nums) - 1
        
        while left <= right:
            middle = (left + right) // 2

            if nums[middle] < target:
                left = middle + 1
            elif nums[middle] > target:
                right = middle - 1
            else:
                return middle
        return -1

def search(self, nums: List[int], target: int) -> int:
  	lo,hi = 0, len(nums) - 1
    while lo <= hi:
      	mid = (lo + hi) >> 1
        if nums[mid] == target:
          	return True
        while lo < mid and nums[lo] == nums[mid]:
          	lo += 1
        if nums[lo] <= nums[mid]:
          	if nums[lo] <= target < nums[mid]:
              	hi = mid - 1
            else:
              	lo = mid + 1
        else:
    				if nums[mid] < target <= nums[hi]:
              	lo = mid + 1
            else:
              	hi = mid - 1
    return False

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
              return False
        r, c = len(matrix), len(matrix[0])
        get_value = lambda i: matrix[i // c][i % c]

        left, right = 0, r * c - 1
        while left <= right:
            middle = left + (right - left) // 2
            if get_value(middle) == target:
               return True
            elif get_value(middle) < target:
               left = middle + 1
            else:
               right = middle - 1
        return False

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity=capacity
        self.cache={}


    def get(self, key: int) -> int:
        if key in self.cache:
            v=self.cache.pop(key)
            self.cache[key]=v  #保证经常使用的在后面，不常使用的在前面
            return v
        return -1


    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.pop(key)
        self.cache[key]=value   #先放「密钥/数据值」，之后再判断是否达到上限
        if len(self.cache)>self.capacity:
            x=list(self.cache.keys())[0]    #取出最久未使用的密钥
            self.cache.pop(x)

class LFUCache:

    def __init__(self, capacity: int):
        self.c, self.__count = capacity, 0
        self.keys = {}  # {key: int, value = [value, fre, time]}

    def get(self, key: int) -> int:
        self.__count += 1

        if key in self.keys:
            self.keys[key][1] += 1
            self.keys[key][2] = self.__count
            return self.keys[key][0]
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        self.__count += 1

        if self.c == 0:
            return
        #  如果key不存在
        if key not in self.keys:
            if len(self.keys) >= self.c:
                #  寻找使用次数最少的key
                min_keys = []
                min_fre = self.keys[min(self.keys, key=lambda x:self.keys[x][1])][1]
                for k in self.keys:
                    if self.keys[k][1] == min_fre:
                        min_keys.append(k)
                #  在使用次数最少的key中寻找最近没有使用的
                min_time, least_key = 1e8, 0
                for k in min_keys:
                    if self.keys[k][2] < min_time:
                        min_time = self.keys[k][2]
                        least_key = k
                #  删除the least frequently used key
                del self.keys[least_key]
            self.keys[key] = [value, 1, self.__count]
        #  如果key存在
        else:
            self.keys[key][0] = value
            self.keys[key][1] += 1
            self.keys[key][2] = self.__count

var Solution = function(w) {
  this.rates = []
  const sum = w.reduce((sum, item) => sum + item, 0)
  let temp = 0
  for (let i = 0; i < w.length; i++) {
    let rate = (w[i] / sum)
    temp += rate
    this.rates.push(temp.toFixed(2) * 1)
    rate = null
  }
};

Solution.prototype.pickIndex = function() {
  const num = Math.random().toFixed(2) * 1
  for (let i = 0; i < this.rates.length; i++) {
    if (num <= this.rates[i]) {
      return i
    }
  }
};