数据结构刷题实战

class Solution:  
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:  
        dict = {}  
        for num in nums:  
            if num not in dict:  
                dict[num] = 1  
            dict[num] = dict[num] + 1  
        sorted_items = sorted(dict.items(), key=lambda item: item[1], reverse=True)  
        #keys = [item[0] for item in sorted_items[:k]]  
        return sorted_items

# 这个题目是偏算法，但是具体实现的时候会考察到对数组的遍历操作
from typing import List

def productArrayOfSelf(list: List[int]) -> List[int]:
    # 1,2,3,4 
    # prefix: 1 1 2 6
    # suffix: 24  12  4  1
    n = len(list)
    prefix_result = [1] * n
    suffix_result = [1] * n
    for i in range(n-1):
        prefix_result[i+1] = list[i] * prefix_result[i]

    for i in reversed(range(1,len(list))):
        suffix_result[i-1] = list[i] * suffix_result[i]

    result = [1] * n
    for i in range(n):
        result[i] = prefix_result[i] * suffix_result[i]
    return result

productArrayOfSelf([1,2,3,4])

from typing import List  
  
class Solution:  
    def productExceptSelf(self, nums: List[int]) -> List[int]:  
        n = len(nums)  
        prefix_prduct = 1  
        postfix_product = 1  
        result = [0] * n  
        for i in range(n):  
            result[i] = prefix_prduct  
            prefix_prduct *= nums[i]  
  
        for i in range(n-1, -1, -1):  
            result[i] *= postfix_product  
            postfix_product *= nums[i]  
  
  
        return result  
  
print(Solution().productExceptSelf([1,2,3,4]))  # 输出: [24, 12, 8, 6]

class Solution:  
    def isValidSudoku(self, board: List[List[str]]) -> bool:  
        rows = [{} for _ in range(9)]  
        columns = [{} for _ in range(9)]  
        boxes = [{} for _ in range(9)]  
  
        for i in range(9):  
            for j in range(9):  
                num = board[i][j]  
                if num != '.':  
                    num = int(num) 
                    box_index = (i // 3 ) * 3 + j // 3  
                    rows[i][num] = rows[i].get(num, 0) + 1  
                    columns[j][num] = columns[j].get(num, 0) + 1  
                    boxes[box_index][num] = boxes[box_index].get(num, 0) + 1  
  
                    if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:  
                        return False       
        return True

//模版1: 3*3方格
//notInBox(row - (row % 3), col - (col % 3), board)
function notInBox(startRow, startCol, board) {
  let st = new Set();
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      let cur = board[startRow + i][startCol + j];

      if (st.has(cur)) {
        return false;
      }
      if (cur !== ".") {
        st.add(cur);
      }
    }
  }
  return true;
}

class Solution:  
    def longestConsecutive(self, nums: List[int]) -> int:  
        nums_set = set(nums)  
        longest = 1  
        for i in nums_set:  
            if i - 1 not in nums_set:  
                current_len = 1  
                current_num = i + 1  
                while current_num in nums_set:  
                    current_num += 1  
                    current_len = current_len + 1  
                longest = max(longest, current_len)  
        return longest  
  
Solution().longestConsecutive([100, 100,4,200,1,3,2])

class Solution:  
    def threeSum(self, nums: List[int]) -> List[List[int]]:  
        res = set()  
        n, p, z = [], [], []  
        for i in nums:  
             if i > 0:  
                 p.append(i)  
             elif i < 0:  
                 n.append(i)  
             else:  
                 z.append(i)  
        N, P = set(n), set(p)  
        if z:  
            for i in P:  
                if -1*i in N:  
                    res.add((-1*i, 0, i))  
  
        if len(z) >= 3:  
            res.add((0,0,0))  
  
        for i in range(len(n)):  
            for j in range(i+1, len(n)):  
                target = -1*(n[i]+n[j])  
                if target in P:  
                    res.add(tuple(sorted([n[i], n[j], target])))  
  
        for i in range(len(p)):  
            for j in range(i+1, len(p)):  
                target = -1*(p[i]+p[j])  
                if target in N:  
                    res.add(tuple(sorted([p[i],p[j], target])))  
  
        return res

arr = [-2, -3, 4, -1, -2, 1, 5, -3]

7

function maxSubArraySum(arr: number[]): number {
  // 初始化变量
  const maxint = Math.pow(2, 53); // JavaScript 中的最大安全整数
  let maxSoFar = -maxint - 1;     // 全局最大和，初始值设为最小值
  let maxEndingHere = 0;          // 当前子数组的最大和

  // 遍历数组
  for (let index = 0; index < arr.length; index++) {
    maxEndingHere = maxEndingHere + arr[index]; // 更新当前子数组和

    // 如果当前子数组和大于全局最大和，则更新全局最大和
    if (maxSoFar < maxEndingHere) {
      maxSoFar = maxEndingHere;
    }

    // 如果当前子数组和小于 0，则重新开始计算子数组
    if (maxEndingHere < 0) {
      maxEndingHere = 0;
    }
  }

  return maxSoFar; // 返回全局最大和
}

// 测试用例
const arr = [-2, -3, 4, -1, -2, 1, 5, -3];
console.log(maxSubArraySum(arr)); // 输出: 7

const mergeSort = (data, p, r) => {
    // 如果只剩一个元素，结束递归
    if (p >= r) return;

    // 分割点
    let q = Math.floor((p + r) / 2);

    // 分解
    mergeSort(data, p, q);
    mergeSort(data, q + 1, r);

    // 合并
    merge(data, p, q, r);
};

const merge = (data, p, q, r) => {
    const temp = new Array(r - p + 1);
    let i = p;
    let j = q + 1;
    let k = 0;

    // 比较两个数组的元素，按升序写入临时数组
    while (i <= q && j <= r) {
        if (data[i] <= data[j]) {
            temp[k++] = data[i++];
        } else {
            temp[k++] = data[j++];
        }
    }

    // 将剩余元素写入临时数组
    let start = i;
    let end = r;
    if (j > r) {
        end = q;
    } else {
        start = j;
    }
    while (start <= end) {
        temp[k++] = data[start++];
    }

    // 将临时数组内容复制回原数组
    for (let i = 0; i < r - p + 1; i++) {
        data[p + i] = temp[i];
    }
    return data;
};

export const ms_test_function = () => {
    const data = [11, 8, 3, 9, 7, 1, 2, 3];
    mergeSort(data, 0, data.length - 1);
    return true;
};

// Step 1: Divide the file into smaller partitions based on order amounts
function partitionFile(inputFilePath, outputDirPath, callback) {
    const partitions = {};
    // Read the input file sequentially
    const readStream = fs.createReadStream(inputFilePath, { encoding: 'utf8' });
    readStream.on('data', (chunk) => {
        const orders = chunk.split('\n');
        orders.forEach((order) => {
            // Extract the order amount from the order entry
            const amount = parseFloat(order.split(',')[1]);
            // Determine the partition for the order based on its amount
            const partition = Math.floor(amount / 100);
            // Create a writable stream for the partition file if it doesn't exist
            if (!partitions.hasOwnProperty(partition)) {
                const partitionFilePath = `${outputDirPath}/partition_${partition}.txt`;
                partitions[partition] = fs.createWriteStream(partitionFilePath, { flags: 'a' });
            }
            // Write the order to the appropriate partition file
            partitions[partition].write(`${order}\n`);
        });
    });
    readStream.on('end', () => {
        // Close all partition files
        for (const partition in partitions) {
            partitions[partition].end();
        }
        callback();
    });
}

// Step 2: Sort each partition individually
function sortPartitions(inputDirPath, outputDirPath, callback) {
    fs.readdir(inputDirPath, (err, files) => {
        if (err) {
            throw err;
        }
        files.forEach((file) => {
            const filePath = `${inputDirPath}/${file}`;
            const sortedFilePath = `${outputDirPath}/sorted_${file}`;
            // Read the orders from the partition file
            const orders = fs.readFileSync(filePath, { encoding: 'utf8' }).split('\n');
            // Sort the orders using an efficient algorithm (e.g., merge sort)
            const sortedOrders = orders.sort((a, b) => {
                const amountA = parseFloat(a.split(',')[1]);
                const amountB = parseFloat(b.split(',')[1]);
                return amountA - amountB;
            });
            // Write the sorted orders to the sorted partition file
            fs.writeFileSync(sortedFilePath, sortedOrders.join('\n'), { encoding: 'utf8' });
        });
        callback();
    });
}

// Step 3: Merge the sorted partitions
function mergePartitions(inputDirPath, outputFilePath) {
    // Step 1: Perform merge sort on an array of numbers
    function mergeSort(arr) {
        if (arr.length <= 1) {
            return arr;
        }
        const mid = Math.floor(arr.length / 2);
        const left = arr.slice(0, mid);
        const right = arr.slice(mid);
        return merge(mergeSort(left), mergeSort(right));
    }

    // Step 2: Merge two sorted arrays
    function merge(left, right) {
        let merged = [];
        let i = 0;
        let j = 0;
        while (i < left.length && j < right.length) {
            // 读取文件标题后面的数字
            if (parseFloat(left[i].split(',')[1]) <= parseFloat(right[j].split(',')[1])) {
                merged.push(left[i]);
                i++;
            } else {
                merged.push(right[j]);
                j++;
            }
        }
        while (i < left.length) {
            merged.push(left[i]);
            i++;
        }
        while (j < right.length) {
            merged.push(right[j]);
            j++;
        }
        return merged;
    }

    const filePointers = [];
    let mergedOutput = '';
    fs.readdir(inputDirPath, (err, files) => {
        if (err) {
            throw err;
        }
        // Open all sorted partition files and initialize file pointers
        files.forEach((file) => {
            const filePath = path.join(inputDirPath, file);
            const fileData = fs.readFileSync(filePath, 'utf8').trim();
            const partitionData = fileData.split('\n');
            filePointers.push(partitionData);
        });
        // Merge the sorted partitions
        const sortedOutput = mergeSort(filePointers.flat());
        // Format the sorted output
        mergedOutput = sortedOutput.join('\n') + '\n';
        // Write the merged output to the final sorted file
        fs.writeFileSync(outputFilePath, mergedOutput, { encoding: 'utf8' });
    });
}

/**
 * 双11凑单问题
 * @param {number[]} items 商品价格数组
 * @param {number} n 商品个数
 * @param {number} w 凑单金额
 */
function double11advance(items, n, w) {
    // 初始化状态表
    let states = new Array(n);
    for (let i = 0; i < n; i++) {
        states[i] = new Array(3 * w + 1).fill(false);
    }

    // 初始状态
    states[0][0] = true; // 不选第一个商品
    if (items[0] <= 3 * w) {
        states[0][items[0]] = true; // 选第一个商品
    }

    // 动态规划填表
    for (let i = 1; i < n; i++) {
        // 不选择第 i 件商品
        for (let j = 0; j <= 3 * w; j++) {
            if (states[i - 1][j] === true) {
                states[i][j] = states[i - 1][j];
            }
        }

        // 选择第 i 件商品
        for (let j = 0; j <= 3 * w - items[i]; j++) {
            if (states[i - 1][j] === true) {
                states[i][j + items[i]] = true;
            }
        }
    }

    // 找到最接近满减金额的总价
    let j;
    for (j = w; j < 3 * w + 1; j++) {
        if (states[n - 1][j] === true) {
            break;
        }
    }

    // 如果找不到满足条件的组合
    if (j === 3 * w + 1) {
        console.log("无法找到满足条件的商品组合");
        return;
    }

    // 回溯找出具体选择了哪些商品
    for (let i = n - 1; i >= 1; i--) {
        if (j - items[i] >= 0 && states[i - 1][j - items[i]] === true) {
            console.log(items[i]); // 打印已选商品
            j -= items[i];
        }
    }

    // 检查是否选择了第 0 件商品
    if (j !== 0) {
        console.log(items[0]);
    }
}

const items = [2, 2, 4, 6, 3];
const n = items.length;
const w = 10;

double11advance(items, n, w);

6
4

/**
 * 计算两个字符串的编辑距离
 * @param {string} a 字符串A
 * @param {number} n 字符串A的长度
 * @param {string} b 字符串B
 * @param {number} m 字符串B的长度
 * @returns {number} 最小编辑距离
 */
function lwstDP(a, n, b, m) {
    // 初始化二维数组 minDist
    const minDist = new Array(n + 1);
    for (let i = 0; i < n + 1; i++) {
        minDist[i] = new Array(m + 1);
        minDist[i][0] = i; // 将空字符串转换为a[0...i-1]的编辑距离
    }
    for (let j = 0; j < m + 1; j++) {
        minDist[0][j] = j; // 将空字符串转换为b[0...j-1]的编辑距离
    }

    // 动态规划填表
    for (let i = 1; i < n + 1; i++) {
        for (let j = 1; j < m + 1; j++) {
            if (a[i - 1] === b[j - 1]) {
                // 字符相等，无需操作
                minDist[i][j] = minOfThree(
                    minDist[i - 1][j] + 1, // 删除
                    minDist[i][j - 1] + 1, // 插入
                    minDist[i - 1][j - 1]  // 不操作
                );
            } else {
                // 字符不等，取最小操作
                minDist[i][j] = minOfThree(
                    minDist[i - 1][j] + 1, // 删除
                    minDist[i][j - 1] + 1, // 插入
                    minDist[i - 1][j - 1] + 1 // 替换
                );
            }
        }
    }

    return minDist[n][m]; // 返回最终结果
}

/**
 * 辅助函数：返回三个数中的最小值
 * @param {number} n1 第一个数
 * @param {number} n2 第二个数
 * @param {number} n3 第三个数
 * @returns {number} 最小值
 */
function minOfThree(n1, n2, n3) {
    return Math.min(n1, Math.min(n2, n3));
}

const a = "mitcmu";
const b = "mtacnu";
const n = a.length;
const m = b.length;

console.log(lwstDP(a, n, b, m)); // 输出：3

3

arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}

3

arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

10

function miniJumpsToEnd(arr) {
  const n = arr.length;

  // 如果数组长度为 1 或更小，无需跳跃
  if (n <= 1) return 0;

  // 如果起点为 0 且数组长度大于 1，无法跳跃
  if (arr[0] == 0) return -1;

  let maxReach = arr[0]; // 当前能够到达的最远索引
  let step = arr[0];     // 当前剩余的步数
  let jumps = 1;         // 总跳跃次数

  for (let i = 1; i < n; i++) {
    // 如果当前索引已经到达或超过终点
    if (i == n - 1) {
      return jumps;
    }

    // 更新能够到达的最远索引
    maxReach = Math.max(maxReach, i + arr[i]);

    // 消耗一步
    step--;

    // 如果当前剩余步数为 0，需要进行一次跳跃
    if (step == 0) {
      jumps++;

      // 如果当前索引已经超过最大可达范围，说明无法到达终点
      if (i >= maxReach) {
        return -1;
      }

      // 更新剩余步数为新的最大可达范围减去当前索引
      step = maxReach - i;
    }
  }

  return -1; // 如果循环结束仍未返回结果，说明无法到达终点
}

arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}

3

arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

10

class Solution:  
    def isPalindrome(self, s: str) -> bool:  
        start = 0  
        end = len(s) - 1  
        while start < end:  
            if not s[start].isalnum():  
                start += 1  
                continue  
            if not s[end].isalnum():  
                end -= 1  
                continue  
            if s[start].lower() != s[end].lower():  
                return False  
            start += 1  
            end -= 1  
        return True

class Solution:  
    def twoSum(self, numbers: List[int], target: int) -> List[int]:  
        start = 0  
        end = len(numbers) - 1  
        while start < end:  
            sum = numbers[start] + numbers[end]  
            if sum == target:  
                return [start, end]  
            elif sum < target:  
                start += 1  
            else:  
                end -= 1  
        return []

# min(LMin, RMax) - h(i) 
class Solution:  
    def maxArea(self, height: List[int]) -> int:  
        n = len(height)  
        l, r = 0, n - 1  
        ans = 0  
        while l <= r:  
            ans = max(ans, (r-l)*min(height[l], height[r]))  
            if height[l] < height[r]: l += 1  
            else:  r -= 1  
        return ans

# min(LMin, RMax) - h(i) 
class Solution:  
    def maxArea(self, height: List[int]) -> int:  
        if not height:  
            return 0  
        l, r = 0, len(height) - 1  
        lMax, rMax = height[0], height[-1]  
        res = 0  
  
        while l < r:  
            if lMax < rMax:  
                l += 1  
                lMax = max(lMax, height[l])  
                res += lMax - height[l]  
            else:  
                r -= 1  
                rMax = max(rMax, height[r])  
                res += rMax - height[r]  
  
        return res

"forgeeksskeegfor"

"geeksskeeg"

"Geeks"

"ee"

function longestPalindrome(str: string): string {
  const n = str.length;
  if (n === 0) return "";

  let maxLength = 1; // 最长回文子串的长度
  let start = 0;     // 最长回文子串的起始位置

  for (let index = 0; index < n; index++) {
    let low = index - 1;
    let high = index + 1;

    // 跳过右侧重复字符
    while (high < n && str[high] === str[index]) {
      high++;
    }

    // 跳过左侧重复字符
    while (low >= 0 && str[low] === str[index]) {
      low--;
    }

    // 中间部分是回文，继续向外扩展
    while (low >= 0 && high < n && str[low] === str[high]) {
      low--;
      high++;
    }

    // 计算当前回文子串的长度
    const length = high - low - 1;
    if (maxLength < length) {
      maxLength = length;
      start = low + 1;
    }
  }

  // 返回最长回文子串
  return str.substring(start, start + maxLength);
}

class Solution:  
    def isValid(self, s: str) -> bool:  
        stack = list()  
        dict = { "(": ")", "{": "}", "[": "]" }  
        for char in s:  
            if len(stack) > 0 and stack[-1] not in dict:  
                return False  
            if len(stack) == 0 or dict[stack[-1]] != char:  
                stack.append(char)  
                continue  
            stack.pop()  
        return len(stack) == 0

class MinStack:  
    def __init__(self):  
        self.list = []  
        self.min = []  
    def push(self, val: int) -> None:  
        self.list.append(val)  
        self.min.append(val if not self.min else min(val, self.min[-1]))  
    def pop(self) -> None:  
        self.list.pop()  
        self.min.pop()  
    def top(self) -> int:  
        return self.list[-1]  
    def getMin(self) -> int:  
        return self.min[-1]

class Solution:  
    def evalRPN(self, tokens: List[str]) -> int:  
        stack = []  
        ops = ['+', '-', '*', '/']  
        for token in tokens:  
            if token in ops:  
                a = stack.pop()  
                b = stack.pop()  
                if token == '+':  
                    result = int(b) + int(a)  
                elif token == '*':  
                    result = int(b) * int(a)  
                elif token == '/':  
                    result = int(b) / int(a)  
                else:  
                    result = int(b) - int(a)  
                stack.append(int(result))  
                continue  
            stack.append(int(token))  
        return stack[-1]

# 单调递减堆栈存储信息
class Solution:  
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:  
        stack = [] # pair: temp, index  
        res = [0] * len(temperatures)  
        for i, v in enumerate(temperatures):  
            while stack and v > stack[-1][0]:  
                stackT, stackIndex = stack.pop()  
                res[stackIndex] = (i - stackIndex)  
            stack.append([v, i])  
        return res

arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, K = 3

3 3 4 5 5 5 6

function getMaxK(arr, k) {
  if (!arr) return;
  if (arr.length <= k) {
    return Math.max(...arr);
  }
  for (let index = 0; index <= arr.length - k; index++) {
    let result = Math.max(arr[index], arr[index + 1], arr[index + 2]);
    console.log(result + " ");
  }
}

function getMaxK(arr, k) {
  const res = [];
  const queue = [];
  let index = 0;

  // 初始化前 k 个元素
  for (; index < k; index++) {
    queue.push(arr[index]);
  }
  queue.sort((a, b) => b - a); // 排序以模拟 AVL 树
  res.push(queue[0]);

  // 滑动窗口处理剩余元素
  for (; index < arr.length; index++) {
    const element = arr[index];
    queue.push(element);
    queue.sort((a, b) => b - a); // 插入后重新排序
    res.push(queue[0]);
    queue.splice(arr[index - k + 1], 1); // 删除滑出窗口的元素
  }

  return res;
}

const s1 = []; // 滑动窗口
const s2 = []; // 临时窗口
const n = arr.length;

// 初始化
for (let index = 0; index < k - 1; index++) {
  insert(s2, arr[index]);
}

for (let i = 0; i <= n - k; i++) {
  // 更新窗口
  if (i - 1 >= 0) update(s1, s2);
  // 插入新元素
  insert(s2, arr[i + k - 1]);
  // 记录最大值
  res.push(Math.max(s1[s1.length - 1].max, s2[s2.length - 1].max));
}

思维误区
1、二分查找不是单纯找指定元素。它本质上可以**缩短范围**，只要你找到条件。这里比较的是当前行的最小和最大的元素，而不是两行的第一个元素。
2、迭代法和递归都是可以实现二分查找的

class Solution:  
    def search(self, nums: List[int], target: int) -> int:  
        def bs(low, high):  
            if low > high:  
                return -1  
            mid = low + (high - low) // 2  
            if nums[mid] < target:  
                return bs(mid + 1, high)  
            elif nums[mid] > target:  
                return bs(low, mid - 1)  
            else:  
                return mid  
        return bs(0, len(nums) - 1)

# 通过指针直接操作，不需要额外的数组存储
class Solution:  
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:  
        rows, cols = len(matrix), len(matrix[0])  
        top, bot = 0, rows - 1  
        targetRow = -1
        while top <= bot:  # = 表示获取最后一个值
            mid = bot + (top - bot) // 2  
            if target > matrix[mid][-1]:  
                top = mid + 1  
            elif target < matrix[mid][0]:  
                bot = mid - 1  
            else:  
                targetRow = mid
                break  # 找到当前行  
  
        l, r = 0, cols - 1  
        while l <= r:  
            m = l + (r - l) // 2  
            if target > matrix[row][m]:  
                l = m + 1  
            elif target < matrix[row][m]:  
                r = m - 1  
            else:  
                return True

class Solution:  
    def minEatingSpeed(self, piles: List[int], h: int) -> int:  
        l, r = 1, max(piles)  
        res = r  
        while l <= r:  
            k = l + (r - l) // 2  
            hours = 0  
            for p in piles:  
                hours += math.ceil(p / k)  
            if hours <= h:      
res = min(res, k)  
                r = k - 1  
            else:  
                l = k + 1  
        return res

class Solution:  
    def findMin(self, nums: List[int]) -> int:  
        res = nums[0]  
        l, r = 0, len(nums) - 1  
  
        while l <= r:  
            if nums[l] < nums[r]:  
                res = min(res, nums[l])  
                break  
  
            m = l + (r - l) // 2  
            res = min(res, nums[m])  
            if nums[m] >= nums[l]:  
                l = m + 1  
            else:  
                r = m - 1  
  
        return res

# 2 3 4 0 1 left sorted
# 3 4 0 1 2 right sorted
class Solution:  
    def search(self, nums: List[int], target: int) -> int:  
        l, r = 0, len(nums) - 1  
  
        while l <= r:  
            mid = l + (r - l) // 2  
            if nums[mid] == target:  
                return mid  
  
            # left sorted portion  
            if nums[l] <= nums[mid]:  
                if target > nums[mid] or target < nums[l]:  
                    l = mid + 1  
                else:  
                    r = mid - 1  
            # right sorted portion  
            else:  
                if target < nums[mid] or target > nums[r]:  
                    r = mid - 1  
                else:  
                    l = mid + 1  
        return -1

class TimeMap:  
    def __init__(self):  
        self.dict = {} # key: list of [value, timestamp]  
    def set(self, key: str, value: str, timestamp: int) -> None:  
        # already sorted  
        if key not in self.dict:  
            self.dict[key] = []  
        self.dict[key].append([value, timestamp])  
    def get(self, key: str, timestamp: int) -> str:  
        values = self.dict.get(key, [])  
        # find in binary search  
        l, r = 0, len(values) - 1  
        while l <= r: # equal to get last value  
            mid = l + (r - l) // 2  
            if values[mid][1] <= timestamp:  
                # 查找最后一个小于等于给定值的元素  
                if (mid == len(values) - 1) or values[mid + 1][1] > timestamp:  
                    return values[mid][0]  
                else:  
                    l = mid + 1  
            else:  
                r = mid - 1  
        return ''

class Solution:  
    def maxProfit(self, prices: List[int]) -> int:  
        l, r = 0, 1  
        maxP = 0  
        while r < len(prices):  
            if prices[l] < prices[r]:  
                profit = prices[r] - prices[l]  
                maxP = max(maxP, profit)  
            else:  
                l = r  
            r += 1  
        return maxP

class Solution:  
    def lengthOfLongestSubstring(self, s: str) -> int:  
        charSet = set()  
        l = 0  
        res = 0  
        for r in range(len(s)):  
            # 如果a已存在，则从左边移除 因为我们是要找到非重复子字符串
            while s[r] in charSet:  
                charSet.remove(s[l])  
                l += 1  
            charSet.add(s[r])  
            res = max(res, r - l + 1)  
        return res

class Solution:  
    def characterReplacement(self, s: str, k: int) -> int:  
        count = {}  
        res = 0  
        l = 0  
        for r in range(len(s)):  
            # add count of right char  
            count[s[r]] = 1 + count.get(s[r], 0)  
            # not effective window  
            while (r - l + 1) - max(count.values()) > k:  
                count[s[l]] -= 1 # add count of left char  
                l += 1 # move the left cursor  
            # effective window            res = max(res, r - l + 1)  
        return res

# 寻找字符游戏，不关心顺序。
# 最简单：遍历两个数组，逐个对比，复杂度是n*m
# 优化：因为字符只有26个，可以建立一个hashmap，滑动窗口移动时，判断是否hashmap中存在，然后和数组a比较是否相等。复杂度是n
class Solution:  
    def checkInclusion(self, s1: str, s2: str) -> bool:  
        if len(s1) > len(s2): return False  
        # 初始化hashmap  
        s1Count, s2Count = [0] * 26, [0]*26  
        # 统计初始的出现次数  
        for i in range(len(s1)):  
            s1Count[ord(s1[i]) - ord('a')] += 1 # 统计出现次数  
            s2Count[ord(s2[i]) - ord('a')] += 1  
  
        # 如果找到匹配的应该是26，因为初始化其他的都是0  
  
        # 统计初始的匹配次数  
        matches = 0  
        for i in range(26):  
            matches += (1 if s1Count[i] == s2Count[i] else 0)  
  
        # 滑动窗口往右移动1位  
        l = 0  
        for r in range(len(s1), len(s2)): # 参数2是结束索引  
            if matches == 26: return True # 找到匹配字符  
  
            # 增加右邊字符判斷匹配情況  
            index = ord(s2[r]) - ord('a')  
            s2Count[index] += 1 # 匹配次數加1  
            if s1Count[index] == s2Count[index]:  
                matches += 1  
            elif s1Count[index] + 1 == s2Count[index]: # 因爲s2Count加了1，所以s1Count要+1進行比較  
                matches -= 1  
  
            # 移除左邊字符，計算匹配情況  
            index = ord(s2[l]) - ord('a')  
            s2Count[index] -= 1 # 匹配次數減1  
            if s1Count[index] == s2Count[index]:  
                matches += 1  
            elif s1Count[index] - 1 == s2Count[index]: # 應爲s2Count減了1，所以s1也要減1后比較  
                matches -= 1  
            l += 1 # 左邊指針移動  
        return matches == 26

# 滑动窗口指针只有i,
# The only thing we care about any particular substring in `s2` is having the same number of characters as in the `s1`. So we create a hashmap with the count of every character in the string `s1`. Then we slide a window over the string `s2` and decrease the counter for characters that occurred in the window. As soon as all counters in the hashmap get to zero that means we encountered the permutation.
class Solution:  
    def checkInclusion(self, s1: str, s2: str) -> bool:  
        def checkInclusion(self, s1: str, s2: str) -> bool:  
			# 初始不匹配都为1
            cntr, w = Counter(s1), len(s1)  
  
            for i in range(len(s2)):  
	            # 1 表示不匹配 0 表示匹配
                if s2[i] in cntr:  # 右边指针找到匹配 减1
                    cntr[s2[i]] -= 1  
                if i >= w and s2[i - w] in cntr: # 左边指针移出滑动窗口，不匹配加1
                    cntr[s2[i - w]] += 1  
				# 最后都为0说明找到匹配
                if all([cntr[i] == 0 for i in cntr]):
                    return True  
  
            return False

def test(s1, s2):
    s1_count = [0] * 26
    s2_count = [0] * 26
    len1 = len(s1)
    len2 = len(s2)
    if len1 > len2: 
        return False
    '''
        s1: ab
        s2: aefbaad

        s1_count:
        {
            1: 2, 'a'
            2: 1, 'b'
        }
        s2_count:
        {
            1: 2, 'a'
            8: 1, 'e'
        }
    '''
    for i in range(len1):
        s1_count[ord(s1[i]) - ord('a')] += 1
        s2_count[ord(s2[i]) - ord('a')] += 1
    
    for i in range(len2 - len1):  # 滑动距离0-4 
        if s1_count == s2_count: # 如果统计出来次数一样 就说明是子串
            return True
        # 移动窗口长度
        s2_count[ord(s2[i]) - ord('a')] -= 1 # 移除最左边的字符 数量-1
        s2_count[ord(s2[i + len1] - ord('a'))] += 1 # 添加右边的1个字符
    # 这个最后判断一下 ad
    return s1_count == s2_count

错误的做法：
1、一次操作移动两个指针
2、写法是错误的 curr.next = curr

# Definition for singly-linked list.  
# class ListNode:  
#     def __init__(self, val=0, next=None):  
#         self.val = val  
#         self.next = next  
# Definition for singly-linked list.  
# class ListNode:  
#     def __init__(self, val=0, next=None):  
#         self.val = val  
#         self.next = next
# 双指针法
# None <- a <- b 前面有一个None哨兵指针
class Solution:  
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:  
        prev, curr = None, head  
        while curr:  # 每次循环只修改一次指针
            next = curr.next  # 保存之前的指针，避免指针断开
            # 修改指针 curr.next = curr 这种写法是错误的
            curr.next = prev  
            # 指针往前移动
            prev = curr  
            curr = next  
        return prev

# Definition for singly-linked list.  
# class ListNode:  
#     def __init__(self, val=0, next=None):  
#         self.val = val  
#         self.next = next  
class Solution:  
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:  
        dummy = ListNode()  
        tail = dummy  
        while list1 and list2:  
            if list1.val < list2.val:  
                tail.next = list1  
                list1 = list1.next  
            else:  
                tail.next = list2  
                list2 = list2.next  
            tail = tail.next  
        if list1:  
            tail.next = list1  
        else:  
            tail.next = list2  
        return dummy.next

# slow, fast pointer and dummy node
class Solution:  
    def reorderList(self, head: Optional[ListNode]) -> None:  
        class Solution:  
            def reorderList(self, head: Optional[ListNode]) -> None:  
                # find middle  
                slow, fast = head, head.next  
                while fast and fast.next:  
                    slow = slow.next  
                    fast = fast.next.next  
  
                # reverse second half  
                second = slow.next  
                prev = slow.next = None  
                while second:  
                    tmp = second.next  
                    second.next = prev  
                    prev = second  
                    second = tmp  
  
                # merge tow half  
                first, second = head, prev  
                while second:  
                    tmp1, tmp2 = first.next, second.next  
                    first.next = second  
                    second.next = tmp1  
                    first, second = tmp1, tmp2

错误示范：
1、快慢指针不是说一定要同时移动的，可以一个先不动，fast指针先移动到指定位置

# slow, fast pointer and dummy node  
class Solution:  
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:  
        dummy = ListNode(0, head)  
        left = dummy  
        right = head  
        while n > 0 and right:  
            right = right.next  
            n -= 1  
  
        while right:  
            left = left.next  
            right = right.next  
  
        # delete  
        left.next = left.next.next  
  
        return dummy.next

# 通过先创建节点，再连线（创建hashmap建立两个链表的联系）
class Solution:  
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':  
        oldToCopy = { None : None }  
  
        # one pass  
        cur = head  
        while cur:  
            copy = Node(cur.val)  
            oldToCopy[cur] = copy  
            cur = cur.next  
  
        # two pass  
        cur = head  
        while cur:  
            copy = oldToCopy[cur]  
            copy.next = oldToCopy[cur.next]  
            copy.random = oldToCopy[cur.random]  
            cur = cur.next  
  
        return oldToCopy[head]

# 考虑 7 + 8 这样的边界case
class Solution:  
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:  
        dummy = ListNode()  
        cur = dummy  
        carry = 0  
        while l1 or l2 or carry:  
            v1 = l1.val if l1 else 0  
            v2 = l2.val if l2 else 0  
            # new digit  
            val = v1 + v2 + carry  
            carry = val // 10  
            val = val % 10  
            cur.next = ListNode(val) # create new node  
                        # update ptrs  
            cur = cur.next  
            l1 = l1.next if l1 else None  
            l2 = l2.next if l2 else None  
            return dummy.next

# 或者用快慢指针 
class Solution:  
    def hasCycle(self, head: Optional[ListNode]) -> bool:  
        cur = head  
  
        visited = {}  
        while cur:  
            if cur in visited: return True  
            visited[cur] = True  
            cur = cur.next  
  
        return False

class Solution:  
    def findDuplicate(self, nums: List[int]) -> int:  
        # 数组的值是[1,n] 0不在数组里面，可以把数组的值当做指针  
        # 本质上就是一个环，如果存在重复元素  
        # 如何找到最开始重复的元素：通过弗洛伊德算法 p(慢指针走到环开始节点需要的距离） = x（相交位置走到环开始需要的距离）  
        slow, fast = 0, 0  
        # 找到相交位置  
        while True:  
            slow = nums[slow]  
            fast = nums[nums[fast]]  
            if slow == fast:  
                break  
        # 弗洛伊德算法  
        slow2 = 0  
        while True:  
            slow = nums[slow] # 相交位置往前走  
            slow2 = nums[slow2] # 起始位置往前走  
            if slow == slow2:  
                return slow

class Node:  
    def __init__(self, key, val):  
        self.key, self.val = key, val  
        self.next = self.prev = None  # 是双向链表  
  
  
class LRUCache:  
  
    def __init__(self, capacity: int):  
        self.cap = capacity  
        self.cache = {}  # 快速找到节点的hashmap, 同时可以判断队列的长度  
        # left:LRU right:MRU  
        self.left, self.right = Node(0, 0), Node(0, 0)  # 指向左边第一个节点， 指向右边第一个节点，方便快速插入和删除，并且是双向链表  
        self.left.next = self.right  # 注意这里要更新前后指针  
        self.right.prev = self.left  
  
    # 从队列中删除一个元素  
    def remove(self, node):  
        prev, nxt = node.prev, node.next  # 这里先把前后节点弄出来  
        prev.next = nxt  
        nxt.prev = prev  
  
    # 插入队列尾部  
    def insert(self, node):  
        prev, nxt = self.right.prev, self.right  
        prev.next = nxt.prev = node  
        node.prev, node.next = prev, nxt  
  
    def get(self, key: int) -> int:  
        if key in self.cache:  
            # 将该元素从原先位置删除  
            self.remove(self.cache[key])  
            # 将该元素插入到最后  
            self.insert(self.cache[key])  
            return self.cache[key].val  # 注意这里是返回值  
        return -1  
  
    def put(self, key: int, value: int) -> None:  
        if key in self.cache:  # 注意这里是判断key是否存在，而不是self.cache[key]值是否存在  
            # 将该元素删除  
            self.remove(self.cache[key])  
        # 更新值，注意这里直接创建了新节点  
        self.cache[key] = Node(key, value)  
        # 将新的值插入到最后  
        self.insert(self.cache[key])  
  
        # 判断队列是否已满  
        if len(self.cache) > self.cap:  
            # 将左边最后一个元素删除  
            lru = self.left.next  
            self.remove(lru)  
            # 从缓存删除  
            del self.cache[lru.key]

错误的示范：
1、需要一个temp保存你要动的指针的值 否则，你把指针直接指到另一个地方了，原先的值你找不到了
2、可以先调换左右子树的，不是非得到叶子结点才能调换
3、递归调用一定是针对左右子树的，不能只递归左子树或者右子树

def test(root):
    if not root:
        return root
    temp = root.left
    root.left = root.right
    root.right = temp
    this.test(root.left)
    this.test(root.right)

class Solution:  
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:  
        if not root:  
            return root  
        temp = root.left  
        root.left = root.right  
        root.right = temp  
        self.invertTree(root.left)  
        self.invertTree(root.right)  
        return root

# DFS
class Solution:  
    def maxDepth(self, root: Optional[TreeNode]) -> int:  
        if not root:  
            return 0  
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

# 层序遍历，没有递归调用
"""
双端队列用来存放每一层的数据, 一开始push到队列里的是根节点，根节点弹出来的时候再推入左右子节点。 
上面做完刚好是level1 ，也就是**要先处理上一层节点再处理下一层节点**




q = deque([root])

while q: 
    for i in range(len(q)):
        node = q.popleft()
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)        

层序遍历也是BFS, 广度优先搜索



"""
class Solution:  
    def maxDepth(self, root: Optional[TreeNode]) -> int:  
        if not root:  
            return 0  
        q = deque([root])  # 双端队列
        level = 0  
        # 队列非空  
        while q:  
            # 要先处理上一层节点再处理下一层节点 
            for i in range(len(q)):  
                node = q.popleft()  
                if node.left:  
                    q.append(node.left)  
                if node.right:  
                    q.append(node.right)  
    
            level += 1  
  
        return level


# 迭代法，先序遍历
class Solution:  
    def maxDepth(self, root: Optional[TreeNode]) -> int:  
        if not root:  
            return 0  
        stack = [[root, 1]]  #
        res = 1  
        while stack:  # 最外层肯定是判断队列是否为空
            node, depth = stack.pop()  
            if node:  
                res = max(res, depth) 
                stack.append([node.left, depth + 1])  # 深度是上一个节点+1 
                stack.append([node.right, depth + 1])  
        return res

# 本质是和高度相关， 将高度和直径关联上, 从下到上开始遍历
# 暴力解法是从上到下时间复杂度是O(n) * n
class Solution:  
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:  
        if not root:  
            return -1  
  
        res = [0]  
  
        # 计算子树的高度  
        def dfs(root):  
            # nonlocal res 如果是用值的话 需要声明为nonlocal  
            if not root:  
                return -1  # 因为单个节点是0  
  
            left = dfs(root.left)  
            right = dfs(root.right)  
            res[0] = max(res[0], left + right + 2)  # left + right + 2是当前节点的直径或者说是最大边  
  
            return 1 + max(left, right)  
  
        dfs(root)  
        return res[0]

class Solution:  
    def isBalanced(self, root: Optional[TreeNode]) -> bool:  
        if not root:  
            return True  
  
        def dfs(root):  
            if not root:  
                return [True, -1]  
            left = dfs(root.left)  
            right = dfs(root.right)  
            balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1  # 注意这里同时要判断左右子树平衡，这样顶部的节点的平衡才代表了整棵树是否平衡  
            return [balanced, 1 + max(left[1], right[1])]  
  
        return dfs(root)[0]

class Solution:  
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:  
        # 比较单个节点的值是否相等，然后再比较叶子树（叶子树判断是否相等又变成相同的子问题了，可以递归调用判断）  
  
        # 比较单个节点  
        if not p and not q:  
            return True  
        if not p or not q or p.val != q.val:  
            return False  
  
        # 节点值相等，再判断叶子树（作为整体判断）  
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

from collections import deque

def isSameTree(tr1: TreeNode, tr2: TreeNode) -> bool:
    if not tr1 and not tr2:
        return True
    if not tr1 or not tr2:
        return False

    s = deque([(tr1, tr2)])

    while s:
        n1, n2 = s.popleft()

        # 当前节点值是否相同
        if n1.val != n2.val:
            return False

        # 检查左子树: 这里的思路可以简单点，如果一个为空，一个非空，肯定返回false。如果都为空，也不需要append
        if n1.left and not n2.left or not n1.left and n2.left:
            return False
        elif n1.left and n2.left:
            s.append((n1.left, n2.left))

        # 检查右子树
        if n1.right and not n2.right or not n1.right and n2.right:
            return False
        elif n1.right and n2.right:
            s.append((n1.right, n2.right))

    return True

class Solution:  
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:  
        if not subRoot: return True  
        if not root: return False  
  
        def isSameTree(p, q):  
            if not p and not q:  
                return True  
            if not p or not q or p.val != q.val:  
                return False  
  
                # 节点值相等，再判断叶子树（作为整体判断）    
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)  
  
        # 判断当前节点  
        if isSameTree(root, subRoot):  
            return True  
  
        # 递归判断左右子树是否是子树   
# 注意这里不是判断左右子树是否是sameTree，因为左右子树这个时候是同类子问题（递归地考虑问题）  
        return (self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot))

# 注意：这里说了是二叉搜索树， 所以不用考虑每个节点的路径问题  
# 直接一个指针往下判断就了事。 不一定都要遍历树
# 从问题出发，而不是从固有的思维出发
class Solution:  
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':  
        cur = root  
        while cur:  
            # [7,9]  
            if p.val > cur.val and q.val > cur.val:  
                cur = cur.right  
            # [0, 4]  
            elif p.val < cur.val and q.val < cur.val:  
                cur = cur.left   
            # [6, 7]     
else:  
                return cur

class Solution:  
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:  
        if not root:  
            return []  
        if not root.left and not root.right:  
            return [[root.val]]  
  
        dq = deque([root])  
  
        res = []  
        while dq:  
            levelArr = []  
            for i in range(len(dq)):  
                node = dq.popleft()  
                levelArr.append(node.val)  
                if node.left:  
                    dq.append(node.left)  
                if node.right:  
                    dq.append(node.right)  
            res.append(levelArr)  
  
        return res

class Solution:  
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:  
        if not root:  
            return None  
  
        dq = deque([root]) # ?? 
        res = []  
        while dq:  
            # level  
            rightSide = None  
            for i in range(len(dq)):  
                node = dq.popleft()  ## ?
                rightSide = node  # 用一个变量保存最后一个值，不用判断是否是最后一个元素因为for循环自动会执行到最后
                if node.left:  
                    dq.append(node.left)  
                if node.right:  
                    dq.append(node.right)  
            res.append(rightSide.val)  
        return res

class Solution:  
    def goodNodes(self, root: TreeNode) -> int:  
        # 一看就是要深度遍历，但是有一个点是先序遍历获得当前最大值的节点。如果后续的节点比它小，肯定不是good节点  
  
        def dfs(root, maxVal):  
            if not root:  
                return 0 # 空节点  
            res = 1 if root.val >= maxVal else 0   # 计算good nodes的个数  
            maxv = max(root.val, maxVal)  
            res += dfs(root.left, maxv) # 递归计算子树的good nodes的节点数  
            res += dfs(root.right, maxv)  
            return res  
  
        return dfs(root, root.val) # 根节点始终是good nodes

class Solution:  
    def isValidBST(self, root: Optional[TreeNode]) -> bool:  
        # 注意：仔细看边界case， 你会发现，不能单纯对比左右子树和父节点的关系。  
        # BST的定义是 右子树的所有节点都必须大于节点  
        # 所有右子树需要把节点当做 左区间  
  
        def dfs(root, left, right):  
            if not root:  
                return True  
            if not (root.val < right and root.val > left):  
                return False  
            return dfs(root.left, left, root.val) and dfs(root.right, root.val, right) #这里left是当前节点的左区间  
        return dfs(root, float('-inf'), float('inf'))

class Solution:  
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:  
        # 这里是BST，所以一定会想到中序遍历输出是刚好排序好的  
        # 因为有堆栈，这里可以用迭代法  
        stack = []  
        cur = root  
        num = 0  
        while cur or stack:  # 这里是or判断只要有一个存在  
            while cur:  
                stack.append(cur)  
                cur = cur.left  
  
            # 处理节点  
            cur = stack.pop()  # 这里pop出来是按照从小到大的  
            num += 1  
            if num == k:  
                return cur.val  
  
            cur = cur.right

class Solution:  
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:  
        # 先序遍历的节点一定是根节点。 然后通过中序遍历的划分左右子树  
  
        # 注意这里要判断空的情况  
        if not preorder or not inorder:  
            return None  
  
        # 创建根节点  
        root = TreeNode(preorder[0])  
        mid = inorder.index(preorder[0])  
        # 递归的思路创建左右子树  
        root.left = self.buildTree(preorder[1:mid + 1], inorder[:mid]) # 注意这里mid+1不包含。 这里是将中序和先序的节点做了划分  
        root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])  
        return root

// i is the root, n is the total nodes' number
const G = (i, n) => {
  return fn(i - 1) * fn(n - i);
};

// Get the total number of BST trees with n nodes.
const fn = (n) => {
  let _ = 0;
  if (n === 0 || n === 1) return 1;
  for (let i = 1; i <= n; i++) {
    _ += G(i, n);
  }
  return _;
};

console.log(fn(3)); // 输出: 5

f(3)
├── G(1,3) -> f(0) * f(2)
├── G(2,3) -> f(1) * f(1)
└── G(3,3) -> f(2) * f(0)

// get the total number of BST tress with i as the root node
const G = (i, n) => {
  return fn(i - 1) * fn(n - i);
};

const dp = [];
const fn = (n) => {
  let _ = 0;
  if (n === 0 || n === 1) return 1;
  if (dp[n]) {
    console.log("hit cache");
    return dp[n];
  }
  // loop all nodes
  for (let i = 1; i <= n; i++) {
    // add them all
    _ += G(i, n);
  }
  // cache result
  dp[n] = _;
  return _;
};

console.log(fn(3)); // 输出: 5

const getNumberOfBSTs = (n) => {
  const T = [];
  T[0] = 1; // Base case: 0 nodes -> 1 BST (empty tree)
  T[1] = 1; // Base case: 1 node -> 1 BST

  for (let i = 2; i <= n; i++) {
    T[i] = 0; // Initialize current value
    for (let j = 1; j <= i; j++) {
      // Calculate the number of BSTs with j as the root
      T[i] += T[j - 1] * T[i - j];
    }
  }

  return T[n]; // Return the result for n nodes
};

console.log(getNumberOfBSTs(3)); // 输出: 5
console.log(getNumberOfBSTs(4)); // 输出: 14