天天看點
傳回

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】-刷題記錄

繼續閱讀