天天看点
返回

leetcode刷题记录(8)-中等

1.解码方法

题目：

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1

'B' -> 2

...

'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

思路：动态规划，，判断后续的字符是否是合法。比如，字符数字大于26，则不作为条件。字符以0开头，也不能作为条件。前K个字符的解码数量，等于前K-1个字符的解码数量+前K-2个字符的解码数量。这个就很像斐波那契数列了

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function(s) {
  const l = s.length;
  let count = 0;
  const map = new Map();
  for (let i = 0; i < l; i++) {
    if (!i) {
        if(s[i]=='0')return 0
      count++;
    } else {

      if (s[i] == "0") {
          if(Number(s[i-1])>2)return 0
          if(s[i-1]=='0')return 0
          if(s[i-2]!='0'){
              
         count = map.get(i - 2) || 1;
          }
      } else if (s[i - 1] == "0") {
      } else {
        if (Number(`${s[i - 1]}${s[i]}`) > 26) {
        } else {
          count = (map.get(i - 1) || 0) + (map.get(i - 2) || 1);
        }
      }
    }
    map.set(i, count);
  }
  return count;
};
           
/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function(s) {
  const l = s.length;
  if (!l) return 0;
  if (s[0] === "0") return 0;

  const map = new Array(l).fill(0);
  map[0] = 1;
  for (let i = 1; i < l; i++) {
    if (s[i] == "0") {
      if (Number(s[i - 1]) > 2) return 0;
      if (s[i - 1] == "0") return 0;
      if (s[i - 2] != "0") {
        map[i] = map[i - 2] || 1;
      } else {
        map[i] = map[i - 1];
      }
    } else if (s[i - 1] == "0") {
      map[i] = map[i - 1];
    } else {
      if (Number(`${s[i - 1]}${s[i]}`) > 26) {
        map[i] = map[i - 1];
      } else {
        map[i] = (map[i - 1] || 0) + (map[i - 2] || 1);
      }
    }
  }
  return map[l - 1];
};

2.反转链表 II

题目：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

思路：首先明确，1-m和n之后的节点不需要反转，所以在m-n的时候，我们要切断链表，依次反转，最后连接上最后的节点。所以可以记录n之后的节点，记录m位置上的节点，反转之后连接m和最后的节点

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */
var reverseBetween = function(head, m, n) {
  if (m == n) return head;
  const p = new ListNode();
  p.next = head;
  let a = p;
  let index = 1;
  while (index < m) {
    head = head.next;
    a = a.next;
    index++;
  }
  let end;
  let start;

  const reverseNode = (head, n, index) => {
    if (!head) return head;
    if (index < n) {
      start = start || head;
      let next = head.next;
      const node = reverseNode(next, n, index + 1);
      head.next = null;
      next.next = head;
      return node;
    } else if (index == n) {
      end = head.next;
      return head;
    }
  };
    a.next = reverseNode(head, n, index);
  start.next = end;
  return p.next;
};

3.复原IP地址

题目：

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。

思路：和解码那题类似。从0开始遍历字符，记录上一次的结果，然后判断接下来三个字符转换成数字是否大于255，大于则取两个字符，小于则取3个。取了四次之后判断剩余字符，如果是空推入结果，不为空则不是有效的IP。然后判断一下非法的字符，即以0开头的

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
      const res = [];
  const restoreIpAddressesAA = (s, start, last) => {
    if (!s && start == 4) {
      res.push(last);
      return;
    } else if (start == 4) {
      return;
    } else {
      for (let i = 1; i < 4 && i < s.length + 1; i++) {
        const temps = s.slice(0, i);
        if (Number(temps) > 255) break;
        if (i > 1 && temps.startsWith("0")) break;
        const v = `${last}${!start ? "" : "."}${temps}`;
        restoreIpAddressesAA(s.slice(i), start + 1, v);
      }
    }
  };
  restoreIpAddressesAA(s, 0,'');
  return res;
};

4.二叉树的中序遍历

题目：给定一个二叉树，返回它的中序 遍历。

思路：首先明确二叉树的中序遍历的定义，对于一颗二叉树，先访问左节点，然后访问根节点，最后访问右节点，同时子树也满足这个条件。

先是递归，二叉树的四种遍历方式用递归都很简单

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  const res = [];
  const search = (root) => {
    if (!root) return;
    search(root.left);
    res.push(root.val);
    search(root.right);
  };
  search(root);
  return res;
};

迭代：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  const res = [];
  const stack = [root];
  while (stack.length) {
    const item = stack.pop();
    if (!item) continue;

    if (item.right) {
      stack.push(item.right);
      item.right = null;
    }
    if (!item.left && !item.right) {
      res.push(item.val);
    } else {
      const left = item.left;
      item.left = null;
      stack.push(item);
      stack.push(left);
    }
  }
  return res;
};

迭代的技巧，就是取出item，如果右节点非空，那么先把右子树推入栈，然后该节点right置为null。如果左节点非空，那么把当前的节点的left置为null，然后把当前节点推回栈，最后把左子树推入栈

5.不同的二叉搜索树

题目：给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。

思路：二叉搜索树的特点就是，左节点小于根节点小于右节点，且所有子树也满足这个条件。所以，所有可能的二叉树，就是遍历1-n，把当前的节点作为根节点，这个数左边的数生成二叉搜索树，右边的数也生成二叉搜索树，这样就能遍历完所有可能的结果。左边的数和右边的数又是一次新的遍历，所以用递归处理。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function(n) {
    if(!n)return []
  const res = [];
  const generateTreesAA = (min, max) => {
    if (min > max) return [null];
    if (min === max) return [new TreeNode(min)];
    const temp = [];
    for (let i = min; i <= max; i++) {
      const left = generateTreesAA(min, i - 1);
      const right = generateTreesAA(i + 1, max);

      for (let node1 of left) {
        for (let node2 of right) {
          let node = new TreeNode(i);
          node.left = node1;
          node.right = node2;
          temp.push(node);
        }
      }
    }
    return temp;
  };

  return generateTreesAA(1, n);
};
解码方法 反转链表 复原IP地址 二叉树的中序遍历 不同的二叉搜索树
上一篇: leetcode刷题记录(14)-简单
下一篇: 【DA】-【SQL】-【SQLZOO】-刷题记录

继续阅读