从零收集算法概念

[TinyScript]

从零收集算法概念

[TinyScript]

0x00 前缀和

1. 关键字：整数数组、中心下标、下标左侧之和等于右侧之和、求中心下标

题目： https://leetcode.cn/problems/find-pivot-index/description/
可使用前缀和进行计算：

• 前缀和基本公式

const arr = [1,2,3,4,5]
const n = arr.length;
const prefixSum = new Array(n); // 创建一个与原始数组相同长度的累加和数组

// 初始化累加和数组的第一个元素为原始数组的第一个元素
prefixSum[0] = arr[0];

// 使用循环计算累加和数组的其他元素
for (let i = 1; i < n; i++) {
  prefixSum[i] = prefixSum[i - 1] + arr[i];
}

console.log(prefixSum); // [1, 3, 6, 10, 15]

• 求右侧公式：

// 数组总和 - 前缀和 - 中心下标
// prefixSum === total - arr[i] - prefixSum

• 求中心下标公式推导：

// 只要在循环中满足以下公式，那么i就为中心下标，否则判断该数组不存在左右值相等的中心下标
// prefixSum === total - arr[i] - prefixSum
// => 2 * prefixSum + arr[i] === total

• 已知题目有中心下标，且左侧与右侧之和相等，那么只需遍历下标不断求左侧前缀和，再对右侧进行公式

const arr = [1, 7, 3, 6, 5, 6]; 
const total = arr.reduce((a,b) => a + b, 0);
let prefixSum = 0;
let i = 0;
// 求中心下标
for (; i < arr.length; i++) {
  if (2 * prefixSum + arr[i] === total) {
    break;
  }
  prefixSum += arr[i]
}
console.log(i); // 3

[TinyScript]

0x01 动态规划

1. 关键内容：

• 问题分解
  1. 定义状态
  2. 找到初始条件
  3. 状态转移方程：
  • 状态定义 + 状态之间的转移 + 中间结果的存储
  4. 存储中间结果
• 自底向上的计算
• 状态转移方程
• 存储中间结果
• 最优子结构性质
• 解决原问题