LeetCode：题目记录

[isaaxite]

大纲

01. 删列造序 02. 键盘行 03. 数组拆分 I 04. N叉树的最大深度 05. 最小差值 I 06. 将有序数组转换为二叉搜索树 07. 重复 N 次的元素 08. 斐波那契数列 09. 单值二叉树 10. 两个数组的交集 11. 反转字符串中的单词 III 12. 转置矩阵 13. Excel表列序号 14. 按奇偶排序数组 II 15. 独特的电子邮件地址 16. 车的可用捕获量 17. 字符的最短距离 18. 各位相加 19. 链表翻转 20. 棒球比赛 21. 查找常用字符 22. 子域名访问计数 23. 杨辉三角 24. 二进制表示中质数个计算置位 25. 岛屿的周长 26. 修剪二叉搜索树 27. 最长特殊序列 Ⅰ 28. 只出现一次的数字 29. 二叉树的层次遍历 II 30. 二叉树的层平均值 31. N叉树的层序遍历 32. 分糖果 33. 数组的相对排序 34. 写字符串需要的行数 35. 链表的中间结点 36. 特殊等价字符串组 37. 重塑矩阵 38. 三维形体投影面积 39, 托普利茨矩阵 40. 整数反转 41. 回文数 42. 罗马数字转整数 43. 最长公共前缀 44. 有效的括号 45. 合并两个有序链表

[isaaxite]

回到顶部

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

第一版

这道题用动态规划的思路并不难解决，比较难的是后文提出的用分治法求解，但由于其不是最优解法，所以先不列出来

• 动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
• 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
• 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
• 每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果
• 时间复杂度：O(n)O(n)

/*
 * @lc app=leetcode.cn id=53 lang=javascript
 *
 * [53] 最大子序和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
  let ans = nums[0];
  let sum = 0;
  for (const num of nums) {
    if (sum > 0) {
      sum += num;
    } else {
      sum = num;
    }
    ans = Math.max(sum, ans);
  }
  return ans;
};

• 202/202 cases passed (72 ms)
• Your runtime beats 85.85 % of javascript submissions
• Your memory usage beats 6.41 % of javascript submissions (36 MB)

[bilibiliou]

回到顶部

键盘行

给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。

示例：

输入: ["Hello", "Alaska", "Dad", "Peace"] 输出: ["Alaska", "Dad"]  

注意：

你可以重复使用键盘上同一字符。 你可以假设输入的字符串将只包含字母。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/keyboard-row 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

尝试用正则实现

var regs = [/q|w|e|r|t|y|u|i|o|p/i, /a|s|d|f|g|h|j|k|l/i, /z|x|c|v|b|n|m/i]
var input = ["Hello", "Alaska", "Dad", "Peace"]

var map = {}
for (var k = 0; k < regs.length; k++) {
    var reg = regs[k]
    map[k] = []
    for (var i = 0; i < input.length; i++) {
      var str = input[i]
      var belong = true

      for (var j = 0; j < str.length; j++) {
        var w = str[j]
        var isBelong = !reg.test(w)
        if (isBelong) {
          belong = false
          break
        }
      }
      if (belong) {
        map[k].push(str)
      }
    }
}

var result = []
for (var key in map) {
  var r = map[key]
  result = result.concat(r)
}

result // ["Alaska", "Dad"]

[bilibiliou]

回到顶部

N叉树的最大深度

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

例如，给定一个 3叉树 :

我们应返回其最大深度，3。

说明:

树的深度不会超过 1000。 树的节点总不会超过 5000。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一种基于广度遍历，非递归的解决方案

/**
  function Node (v, childs) {
    this.v = v
    this.childs = childs
  }
*/

function maxDepth (root) {
  if (!root) {
    return 0
  }

  const stack = [{node: root, deep: 1}]
  let result = 1
  while (stack.length > 0) {
    let currentNode = stack.pop()
    let { node, deep } = currentNode
    let children = node.childs
    result = Math.max(result, deep)
    if (children && children.length) {
      for (let i = 0; i < children.length; i++) {
        let child = children[i]
        stack.push({node: child, deep: deep + 1})
      }
    }
  }
  return result
}

maxDepth ({
  v: 'A',
  childs: [{
    v: 'B',
    childs: [{
      v: 'E',
      childs: [{
        v: 'G'
      }]
    }]
  }, {
    v: 'C',
    childs: [{
      v: 'F',
      childs: [{
        v: 'H',
        childs: [{
          v: 'J',
          childs: [{
            v: 'K'
          }]
        }]
      }]
    }]
  }, {
    v: 'D'
  }]
})

[bilibiliou]

回到顶部

字符的最短距离

给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。

示例 1:

输入: S = "loveleetcode", C = 'e'
输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

说明:

字符串 S 的长度范围为 [1, 10000]。
C 是一个单字符，且保证是字符串 S 里的字符。
S 和 C 中的所有字母均为小写字母。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shortest-distance-to-a-character 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一种低效 O(n)²，但是便于理解的解决方案

var reverse = function( str ){
  var newStr = '', i = str.length;
   for(; i >= 0; i--) {
        newStr += str.charAt(i);
   }
   return newStr;
}

function shortestToChar (S, C) {
  // 如果字符串中没有目标字符，则返回null
  if (S.indexOf(C) === -1) {
    return null
  }
  let result = []
  let len = S.length
  let pos = 0
  while (S[pos]) {
    if (S[pos] === C) {
      result.push(0)
      pos++
      continue
    }

    // 截取游标左边的逆序字符串 和 右边的正序字符串
    let prev = reverse(S.slice(0, pos))
    let next = S.slice(pos + 1, len)
    // 计算左边逆序字符串目标字符的距离 和 计算右边正序字符串的目标字符的距离
    let prevShort = prev.indexOf(C)
    let nextShort = next.indexOf(C)
    let psr = prevShort !== -1 ? prevShort : Infinity
    let nsr = nextShort !== -1 ? nextShort : Infinity
    result.push(Math.min(psr, nsr) + 1)
    pos++
  }
  return result
}

shortestToChar('loveleetcode', 'e')

[bilibiliou]

回到顶部

回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121
输出: true

示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶: 你能不将整数转为字符串来解决这个问题吗？

一种 O(log2 N) 的解决方案

var testPalindrome = function (s) {
    var i = 0
    var j = s.length - 1
    var flag = true
    while (j > i) {
        if (s[i] !== s[j]) {
           flag = false
           break
        }
        j--
        i++
    }

    return flag
}