// 最大子集
// function maxSubArray(A) {
// var maxSoFar = A[0], maxEndingHere = A[0];
// var arr = [];
// for (var i = 1; i < A.length; ++i) {
// maxEndingHere = Math.max(maxEndingHere + A[i], A[i]);
// maxSoFar = Math.max(maxSoFar, maxEndingHere);
// arr = [maxSoFar - A[i], A[i]];
// }
// return arr;
// }
// console.log(maxSubArray([1, -2, 5, 2, -3, 2]))
// 爬楼问题 LeetCode 70
// 假设你正在爬楼梯，需要 n 阶你才能到达楼顶。
// 每次你可以爬 1 或 2 个台阶，你有多少种不同的方法可以爬到楼顶呢？
// function climbStairs(n) {
// // if (n == 1) {
// // return 1;
// // }
// // var dp = new Array(n + 1);
// // dp[0] = 0;
// // dp[1] = 1;
// // dp[2] = 2;
// // for (let i = 3; i <= n; i++) {
// // dp[i] = dp[i - 1] + dp[i - 2];
// // }
// // return dp[n];
// var f0 = 1, f1 = 1, i, f2;
// for (i = 2; i <= n; i++) {
// f2 = f0 + f1;
// f0 = f1;
// f1 = f2;
// }
// return f1;
// }
// console.log(climbStairs(12));
// 使用最小花费爬楼梯 ，第 i个阶梯对应着一个非负数的体力花费值
// 输入: cost = [10, 15, 20]
// 输出: 15
// 解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
// var minCostClimbingStairs = function (cost) {
// if (!cost || cost.length < 1) return 0;
// let dp = [];
// dp[0] = cost[0];
// dp[1] = cost[1];
// for (let i = 2; i < cost.length; i++) {
// dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
// }
// return Math.min(dp[dp.length - 1], dp[dp.length - 2]);
// };
// console.log(minCostClimbingStairs([10, 15, 20]))
// Given an integer array nums, find the contiguous subarray(containing at least one number) which has the largest sum and return its sum.
// function maxSubArray(arr) {
// var dp = new Array(arr.length);
// dp[0] = arr[0];
// var result = dp[0];
// for (var i = 1; i < arr.length; i++) {
// dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
// result = Math.max(result, dp[i]);
// }
// return result;
// }
// console.log(maxSubArray([1, -2, 5, 2, -3, 2]))
// 打家劫舍 LeetCode 198
// function rob(arr) {
// var n = arr.length;
// if (n == 0) {
// return 0;
// }
// var dp = new Array(n + 1);
// dp[0] = 0;
// dp[1] = arr[0];
// for (var i = 1; i < arr.length; i++) {
// dp[i + 1] = Math.max(dp[i - 1] + arr[i], dp[i]);
// }
// return dp[n];
// }
// console.log(rob([1, -2, 5, 4, -3, 2]))
// 斐波那切
// function Fibonacci(n) {
// if (n <= 0) return n;
// var Memo = new Array(n + 1);
// for (var i = 0; i <= n; i++) {
// Memo[i] = -1;
// }
// return fib(n, Memo);
// }
// function fib(n, Memo) {
// if (Memo[n] != -1) return Memo[n];
// //如果已经求出了fib（n）的值直接返回，否则将求出的值保存在Memo备忘录中。
// if (n <= 2) {
// Memo[n] = 1;
// } else {
// Memo[n] = fib(n - 1, Memo) + fib(n - 2, Memo);
// }
// return Memo[n];
// }
// function fib(n) {
// if (n <= 0)
// return n;
// var Memo = new Array(n + 1);
// Memo[0] = 0;
// Memo[1] = 1;
// for (var i = 2; i <= n; i++) {
// Memo[i] = Memo[i - 1] + Memo[i - 2];
// }
// return Memo[n];
// }
// console.log(fib(10))
// 插入排序
// function insertionSort(A) {
// for (var j = 1; j < A.length; j++) {
// let key = A[j];
// let i = j - 1;
// while (i >= 0 && A[i] > key) {
// A[i + 1] = A[i];
// i = i - 1;
// A[i + 1] = key;
// }
// }
// return A;
// }
// 插入排序复杂度为O^2
// function insertionSort(A) {
// let temp;
// for (var i = 1; i < A.length; i++) {
// temp = A[i]; // 提前先记录下后面一位的值（j循环过程中交换了位置后A[i]引用就变了）
// let j = i - 1; // j记录前一位要比较的数的下标
// while (j >= 0 && A[j] > temp) {
// A[j + 1] = A[j];
// j = j - 1; // 位数减1 继续向前比较
// }
// A[j + 1] = temp; // 交换
// }
// return A;
// }
// console.log(insertionSort([1, 5, 3, 1, 4, 5, 1, 6, 2, 9]));
// function insertionSort(A) {
// var temp;
// for (var i = 1; i < A.length; i++) {
// var j = i - 1;
// temp = A[i];
// while (j >= 0 && A[j] > temp) {
// A[j + 1] = A[j];
// j--;
// }
// A[j + 1] = temp;
// }
// return A;
// }
// console.log(insertionSort([3, 1, 4, 5, 1, 6, 2, 9]));
// 分治法 归并排序 复杂度为 nlg(n)
// function merge(left, right) {
// var result = [];
// while (left.length > 0 && right.length > 0) {
// if (left[0] < right[0]) {
// result.push(left.shift());
// } else {
// result.push(right.shift());
// }
// }
// return result.concat(left).concat(right);
// }
// function mergeSort(items) {
// if (items.length == 1) {
// return items;
// }
// var middle = Math.floor(items.length / 2),
// left = items.slice(0, middle),
// right = items.slice(middle);
// return merge(mergeSort(left), mergeSort(right));
// }
// function mergeSort(A) {
// if (A.length == 1) {
// return A;
// }
// let middle = A.length / 2;
// let left = A.slice(0, middle);
// let right = A.slice(middle, A.length);
// return marge(mergeSort(left), mergeSort(right))
// }
// function marge(left, right) {
// let result = [];
// while (left.length > 0 && right.length > 0) {
// if (left[0] < right[0]) {
// result.push(left.shift())
// } else {
// result.push(right.shift())
// }
// }
// return result.concat(left).concat(right);
// }
// console.log(mergeSort([3, 1, 4, 5, 1, 6, 2, 9]))
// 快排 相比与归并 不稳定
// function quickSort(arr, left = 0, right = arr.length - 1) {
// var partitionIndex;
// if (left < right) {
// partitionIndex = partition(arr, left, right);
// quickSort(arr, left, partitionIndex - 1);
// quickSort(arr, partitionIndex + 1, right);
// }
// return arr;
// }
// function partition(arr, left, right) { // 分区操作
// var pivot = left, // 设定基准值（pivot）
// index = pivot + 1;
// for (var i = index; i <= right; i++) {
// if (arr[i] < arr[pivot]) {
// swap(arr, i, index);
// index++;
// }
// }
// swap(arr, pivot, index - 1);
// return index - 1;
// }
// function swap(arr, i, j) {
// var temp = arr[i];
// arr[i] = arr[j];
// arr[j] = temp;
// }
// console.log(quickSort([2, 5, 7, 2, 1, 8, 4, 2, 5]))
// 判断一个数是不是质数
// function isPrime(num) {
// if (num <= 0) return false;
// if (num === 1 || num === 2) return true;
// if (num % 6 !== 1 && num % 6 !== 5) return false;
// const sqrt = Math.sqrt(num);
// if (num % sqrt === 0) return false;
// for (let i = 5; i <= sqrt; i += 6) {
// if (num % i == 0 || num % (i + 2) == 0) {
// return false;
// }
// }
// return true;
// }
// console.log(isPrime(133))
// 棋盘 求不同路径
// 在一个m x n 的棋盘上 从 0,0 点 走到 m,n 点一共有多少种路径 斐波那切 + 动态规划
// var uniquePaths = function (m, n) {
// let dp = new Array(m);
// dp.fill(new Array(n));
// for (let i = 0; i < m; i++) {
// for (let j = 0; j < n; j++) {
// if (i == 0 || j == 0)
// dp[i][j] = 1;
// else {
// dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
// }
// }
// }
// return dp[m - 1][n - 1];
// };
// console.log(uniquePaths(3, 7))
// 有障碍棋盘 求不同路径
// function uniquePathsWithObstacles(obstacleGrid) {
// let m = obstacleGrid.length;
// let n = obstacleGrid[0].length;
// if (obstacleGrid[0][0] == 1) {
// return 0;
// }
// obstacleGrid[0][0] = 1;
// // 边界也可视为障碍
// for (let i = 1; i < m; i++) {
// obstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) ? 1 : 0;
// }
// for (let i = 1; i < n; i++) {
// obstacleGrid[0][i] = (obstacleGrid[0][i] == 0 && obstacleGrid[0][i - 1] == 1) ? 1 : 0;
// }
// for (let i = 1; i < m; i++) {
// for (let j = 1; j < n; j++) {
// if (obstacleGrid[i][j] == 0) {
// obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
// } else {
// obstacleGrid[i][j] = 0;
// }
// }
// }
// return obstacleGrid[m - 1][n - 1];
// }
// const arr = [
// [0, 0, 1, 0],
// [0, 0, 0, 0],
// [0, 0, 1, 0],
// [0, 0, 0, 0]
// ];
// console.log(uniquePathsWithObstacles(arr))
// 最大子序列和
// function maxSubArray(nums) {
// let ans = nums[0];
// let sum = 0;
// for (let num of nums) {
// if (sum > 0) {
// sum += num;
// } else {
// sum = num;
// }
// ans = Math.max(ans, sum);
// }
// return ans;
// }
// function maxSubArray(nums) {
// let res = nums[0];
// let sum = 0;
// for (let num of nums) {
// if (sum > 0) {
// sum += num;
// } else {
// sum = num;
// }
// res = Math.max(sum, res);
// }
// return res;
// }
// console.log(maxSubArray([1, 3, 0, 4, -14, 2, 3, 4, 5, 6]))
// 买卖股票最佳时机 仅一次交易
// 对应的交易状态为: [买入, 卖出]
// function maxProfit(prices) {
// let maxprofit = 0;
// for (let i = 0; i < prices.length - 1; i++) {
// for (let j = i + 1; j < prices.length; j++) {
// maxprofit = Math.max(maxprofit, prices[j] - prices[i]);
// }
// }
// return maxprofit;
// }
// 买卖股票最佳时机 1次
// 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
// function maxProfit(prices) {
// // let n = prices.length;
// // let dp_i_0 = 0, dp_i_1 = -Number.MAX_VALUE;
// // let dp_pre_0 = 0; // 代表 dp[i-2][0]
// // for (let i = 0; i < n; i++) {
// // let temp = dp_i_0;
// // dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
// // dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
// // dp_pre_0 = temp;
// // }
// // return dp_i_0;
// let n = prices.length;
// let dp = new Array(n);
// dp.fill(new Array(2));
// for (let i = 0; i < n; i++) {
// if (i - 1 == -1) {
// dp[i][0] = 0; // 没有持有
// dp[i][1] = -prices[i]; // 花费prices[i]买入
// continue;
// }
// dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
// dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
// }
// return dp[n - 1][0];
// }
// 买卖股票最佳时机 不限交易次数
// function maxProfit(prices) {
// let n = prices.length;
// let dp = new Array(n);
// dp.fill(new Array(2));
// for (let i = 0; i < n; i++) {
// if (i - 1 == -1) {
// dp[i][0] = 0; // 没有持有
// dp[i][1] = -prices[i]; // 花费prices[i]买入
// continue;
// }
// dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
// dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])
// }
// return dp[n - 1][0];
// }
// 买卖股票最佳时机 不限交易次数 但每次 sell 之后要等一天才能继续交易（冷冻期）
// function maxProfit(prices) {
// if (!prices || prices.length < 2) return 0;
// let n = prices.length;
// let dp = [];
// for (let i = 0; i < n; i++) {
// dp[i] = [];
// if (i - 1 == -1) {
// dp[i][0] = 0; // 没有持有
// dp[i][1] = -prices[i]; // 花费prices[i]买入
// continue;
// }
// dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
// dp[i][1] = Math.max(dp[i - 1][1], (i < 2 ? 0 : dp[i - 2][0]) - prices[i])
// }
// return dp[n - 1][0];
// }
// console.log(maxProfit([1, 2, 4]))
// 买卖股票最佳时机 不限交易次数 每次交易要支付手续费
// function maxProfit(prices, fee) {
// let n = prices.length;
// let dp = new Array(n);
// dp.fill(new Array(2));
// for (let i = 0; i < n; i++) {
// if (i - 1 == -1) {
// dp[i][0] = 0; // 没有持有
// dp[i][1] = -prices[i]; // 花费prices[i]买入
// continue;
// }
// dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
// dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])
// }
// return dp[n - 1][0];
// }
// 买卖股票最佳时机 限制交易次数max_k=2
// 一次
// function maxProfit_k_inf(prices) {
// let n = prices.length;
// let dp_i_0 = 0, dp_i_1 = -Number.MAX_VALUE;
// for (let i = 0; i < n; i++) {
// let temp = dp_i_0;
// dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
// dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
// }
// console.log('maxProfit_k_inf')
// return dp_i_0;
// }
// // // 限制次数为k todo 此处有问题
// function maxProfit(prices, k) {
// if (!prices || prices.length == 0) return 0;
// let n = prices.length;
// if (k > n / 2) return maxProfit_k_inf(prices);
// let dp = Array.from(Array(n)).map(() => Array(k + 1).fill(Array(2).fill(1)))
// for (let i = 0; i < n; i++)
// for (let _k = k; _k > 1; _k--) {
// if (i - 1 == -1) {
// dp[i][_k][0] = 0;
// dp[i][_k][1] = -prices[i];
// continue;
// }
// dp[i][_k][0] = Math.max(dp[i - 1][_k][0], dp[i - 1][_k][1] + prices[i]);
// dp[i][_k][1] = Math.max(dp[i - 1][_k][1], dp[i - 1][_k - 1][0] - prices[i]);
// }
// return dp[n - 1][k][0];
// }
// console.log(maxProfit([3, 2, 6, 5, 0, 3, 11, 4, 1, 13, 10, 1, 20], 5));
// 编码方法问题
// function numDecodings(s) {
// if (s == null || s.length == 0) {
// return 0;
// }
// const dp = Array(s.length + 1).fill(0);
// dp[0] = 1;
// dp[1] = s[0] !== "0" ? 1 : 0;
// for (let i = 2; i < s.length + 1; i++) {
// const one = +s.slice(i - 1, i);
// const two = +s.slice(i - 2, i);
// if (two >= 10 && two <= 26) {
// dp[i] = dp[i - 2]; // 等同关系
// }
// if (one >= 1 && one <= 9) {
// dp[i] += dp[i - 1];
// }
// }
// return dp[dp.length - 1];
// }
// console.log(numDecodings('1201'))
// 最长回文字符串 未通过
// function longestPalindrome(s) {
// let total = s.length;
// // 储存上面表格值的数组
// let isPalindromic = Array.from(Array(total)).map(() => Array(total).fill(false))
// let start = 0, end = 0, len = 0, maxLen = 0;
// // j 是子串的起始位置，i 是结束位置
// for (let i = 0; i < total; ++i) {
// for (let j = 0; j <= i; ++j) {
// if (j == i) {
// isPalindromic[j][i] = true;
// } else if (i - j == 1) {
// isPalindromic[j][i] = s[i] == s[j];
// } else if (i - j > 1) {
// isPalindromic[j][i] = s[i] == s[j] && isPalindromic[j + 1][i - 1];
// }
// len = i - j + 1;
// if (isPalindromic[j][i] && len > maxLen) {
// // 只有当该子串是回文，且长度大于上一个回文串的长度时才更新变量
// maxLen = len;
// start = j;
// end = i;
// }
// }
// }
// return s.substr(start, end - start + 1);
// }
// console.log(longestPalindrome('cabearddrcfdc'))
// 区域和检索 - 数组不可变
// var NumArray = function (nums) {
// this.nums = nums;
// this.dp = [] // fill填充数组存在问题
// };
// NumArray.prototype.sumRange = function (i, j) {
// if (this.dp && this.dp[i] && this.dp[i][j]) return this.dp[i][j];
// let res = 0;
// for (let n = i; n <= j; n++) {
// res += this.nums[n];
// }
// this.dp[i] = [];
// this.dp[i][j] = res;
// return this.dp[i][j];
// };
// var obj = new NumArray([-2, 0, 3, -5, 2, -1])
// console.log(obj.sumRange(0, 2))
// console.log(obj.sumRange(2, 5))
// console.log(obj.sumRange(0, 5))
// 不同的二叉搜索树
// var numTrees = function (n) {
// let dp = new Array(n + 1).fill(0);
// dp[0] = 1;
// dp[1] = 1;
// for (let i = 2; i <= n; ++i) {
// for (let j = 1; j <= i; ++j) {
// dp[i] += dp[j - 1] * dp[i - j];
// }
// }
// console.log(dp)
// return dp[n];
// };
// console.log(numTrees(3))
// 最小路径和
// var minPathSum = function (grid) {
// // let m = grid.length;
// // let n = grid[0].length;
// // let dp = new Array(n);
// // for (let i = m - 1; i >= 0; i--) {
// // for (let j = n - 1; j >= 0; j--) {
// // if (i == m - 1 && j != n - 1)
// // dp[j] = grid[i][j] + dp[j + 1];
// // else if (j == n - 1 && i != m - 1)
// // dp[j] = grid[i][j] + dp[j];
// // else if (j != n - 1 && i != m - 1)
// // dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]);
// // else
// // dp[j] = grid[i][j];
// // }
// // }
// // return dp[0];
// let m = grid.length;
// let n = grid[0].length;
// let dp = new Array(m).fill(new Array(n));
// for (let i = m - 1; i >= 0; i--) {
// for (let j = n - 1; j >= 0; j--) {
// if (i == m - 1 && j != n - 1)
// dp[i][j] = grid[i][j] + dp[i][j + 1];
// else if (j == n - 1 && i != m - 1)
// dp[i][j] = grid[i][j] + dp[i + 1][j];
// else if (j != n - 1 && i != m - 1)
// dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
// else
// dp[i][j] = grid[i][j];
// }
// }
// return dp[0][0];
// };
// console.log(minPathSum([
// [1, 3, 1],
// [1, -1, 1],
// [1, 1, 9]
// ]))
// 三角形最小路径和
// 例如，给定三角形：
// [
// [2],
// [3, 4],
// [6, 5, 7],
// [4, 1, 8, 3]
// ]
// 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
// var minimumTotal = function (triangle) {
// for (let i = triangle.length - 2; i >= 0; i--)
// for (let j = 0; j < triangle[i].length; j++)
// triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
// return triangle[0][0];
// };
// console.log(minimumTotal([
// [-1],
// [2, 3],
// [1, -1, -3]]))
