跳到主要内容

639.解码方法II

链接:639.解码方法II
难度:Hard
标签:字符串、动态规划
简介:给你一个字符串 s ,由数字和 '*' 字符组成,返回 解码 该字符串的方法 数目 。

题解 1 - typescript

  • 编辑时间:2021-09-28
  • 执行用时:152ms
  • 内存消耗:52.4MB
  • 编程语言:typescript
  • 解法介绍:dfs。
function pathSum(root: TreeNode | null, targetSum: number): number {
if (root === null) return 0;
let ans = 0;
dfs(root);
return ans;
function dfs(node: TreeNode | null, list: number[] = []) {
if (node === null) return;
const newList = list.map(v => v + node.val);
newList.push(node.val);
newList.forEach(v => {
if (v === targetSum) ans++;
});
dfs(node.left, newList);
dfs(node.right, newList);
}
}

题解 2 - typescript

  • 编辑时间:2021-09-28
  • 执行用时:88ms
  • 内存消耗:42.6MB
  • 编程语言:typescript
  • 解法介绍:dfs。
function pathSum(root: TreeNode | null, targetSum: number): number {
if (root === null) return 0;
let ans = 0;
dfs(root);
return ans;
function dfs(node: TreeNode | null, list: number[] = []) {
if (node === null) return;
const val = node.val;
const len = list.length;
if (val === targetSum) ans++;
for (let i = 0; i < len; i++) {
list[i] += val;
if (list[i] === targetSum) ans++;
}
list.push(val);
dfs(node.left, list);
dfs(node.right, list);
list.pop();
for (let i = 0; i < len; i++) {
list[i] -= val;
}
}
}