算法(硬币，两数和等)

Question

function getCoinCount(datas: number[], amount: number) {
  if(amount < 1) {
    return;
  }
  const amountList: number[] = [];
  amountList.length = amount + 1;
  amountList.fill(Infinity);
  amountList[0] = 0;
  for(let a = 1; a < amountList.length; a++) {
    for(let c = 0; c < datas.length; c++) {
      const currCoin = datas[c];
      const offset = a - currCoin;
      if(offset >= 0) {
        amountList[a] = Math.min(amountList[a], amountList[offset] + 1);
      }
    }
  }
  if(amountList[amount] === Infinity) {
    return -1;
  }
  return amountList[amount];
}

function getValsIdx(datas: number[], target: number) {
  const valIdxMap = new Map();
  for(let i = 0; i < datas.length; i++) {
    const offset = target - datas[i];
    if(valIdxMap.has(offset)) {
      return [valIdxMap.get(offset), i];
    }
    valIdxMap.set(datas[i], i);
  }
  return -1;
}

function getRepeatStrLength(str: string) {
  const charMap = new Map();
  let L:number = 0; // 滑动窗口左边界
  let maxLength = 0;// 记录找到的最大长度
  // R(右边界)不断向右移动，遍历整个字符串
  for(let R = 0; R< str.length; R++) {
    const char: string = str[R];
    if(charMap.has(char)) {
      const lastIndex = charMap.get(char);
      // 如果 charMap 中记录的索引 (lastIndex) 在当前窗口 L 的右侧或等于 L，
      // 说明该重复字符位于当前窗口内。
      // 此时必须收缩窗口 L，将其移动到重复字符的下一位，即 max(L, lastIndex + 1)。
      // 使用 max(L, lastIndex + 1) 是为了防止 L 回退（如果 lastIndex 在 L 的左侧，则 L 不动）。
      L = Math.max(L, lastIndex + 1);
    }
    charMap.set(char, R);
    maxLength = Math.max(maxLength, R-L+1);
  }
  return maxLength;
}

function main() {
  // console.log(getCoinCount([5, 2, 7, 10], 12));
  // console.log(getValsIdx([10, 2, 4, 6, 8], 18));
  console.log(getRepeatStrLength("abbcfgeee"));
}
main();

/**
 * 合并两个有序数组 (原地操作)
 * @param nums1 目标数组，空间足够
 * @param m nums1中有效元素的数量
 * @param nums2 源数组
 * @param n nums2中元素的数量
 */
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    // p1: nums1 最后一个有效元素指针
    let p1 = m - 1; 
    // p2: nums2 最后一个有效元素指针
    let p2 = n - 1; 
    // p: 合并后要放置元素的位置指针 (nums1 的末尾)
    let p = m + n - 1;

    // 当 nums2 中还有元素未处理时，继续比较
    while (p2 >= 0) {
        // 如果 p1 还有元素，并且 nums1[p1] 大于 nums2[p2]
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            // 将 nums1[p1] 放在末尾
            nums1[p] = nums1[p1];
            p1--; // 移动 p1
        } else {
            // 否则（p1 耗尽 或 nums2[p2] >= nums1[p1]），放置 nums2[p2]
            nums1[p] = nums2[p2];
            p2--; // 移动 p2
        }
        p--; // 移动放置指针
    }
    // 循环结束后，如果 nums1[p1] 还有剩余（即它们都比 nums2 的所有元素小），
    // 它们已经处于正确位置，无需额外操作。
}


/**
 * 动态规划求解最长递增子序列的长度
 * @param nums 无序整数数组
 * @returns 最长递增子序列的长度
 */
function lengthOfLIS(nums: number[]): number {
    if (nums.length === 0) {
        return 0;
    }

    // 1. 状态数组：dp[i] 表示以 nums[i] 结尾的 LIS 长度
    const dp: number[] = new Array(nums.length).fill(1);
    let maxLen = 1;

    // 2. 遍历数组，填充 dp 数组
    for (let i = 1; i < nums.length; i++) {
        // 向前遍历所有 j < i 的元素
        for (let j = 0; j < i; j++) {
            // 如果 nums[i] 比前面的 nums[j] 大 (满足递增条件)
            if (nums[i] > nums[j]) {
                // 状态转移方程：dp[i] 挑战历史最长值
                // dp[j] + 1 表示将 nums[i] 接在以 nums[j] 结尾的 LIS 后面
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
      
        // 3. 更新全局最大值
        maxLen = Math.max(maxLen, dp[i]);
    }

    return maxLen;
}

算法(硬币，两数和等)

0 Answers