wmshero / leetcode-javascript Goto Github PK

View Code? Open in Web Editor NEW

0.0 0.0 0.0 0 B

leetcode-javascript's People

Watchers

leetcode-javascript's Issues

题目

用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

数据范围： n\le1000n≤1000
要求：存储n个元素的空间复杂度为 O(n)O(n) ，插入与删除的时间复杂度都是 O(1)O(1)

示例1
输入：
["PSH1","PSH2","POP","POP"]
返回值：
1,2
 说明：
"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素，先进先出=>返回1
"POP“:代表删除一个元素，先进先出=>返回2

示例2
输入：
["PSH2","POP","PSH1","POP"]
返回值：
2,1

解答

let stack1=[]
let stack2=[]
function push(node)
{
   stack1.push(node)
}
function pop()
{
  if(!stack2.length){
      while(stack1.length){
          stack2.push(stack1.pop())
      }
  }
    return stack2.pop()
}
module.exports = {
    push : push,
    pop : pop
};

题目

const object = {
  a: [{ x: 2 }, { y: 4 }],
  b: 1
};
const other = {
  a: { z: 3 },
  b: [2, 3],
  c: 'foo'
};

转换为

 { a: [ { x: 2 }, { y: 4 }, { z: 3 } ], b: [ 1, 2, 3 ], c: 'foo'}

解答

使用 Array.reduce() 与 Object.keys(obj) 结合来遍历所有对象和键。使用 hasOwnProperty() 和 Array.concat() 为存在与多个对象中的键添加值。

const merge = (...objs) =>
  [...objs].reduce(
    (acc, obj) =>
      Object.keys(obj).reduce((a, k) => {
        acc[k] = acc.hasOwnProperty(k) ? [].concat(acc[k]).concat(obj[k]) : obj[k];
        return acc;
      }, {}),
    {}
  );
merge(object, other);

深度平铺数组

[1, 2, 3, [4, 5, [6, 7]]] 转成为[1, 2, 3, 4, 5, 6, 7]
使用递归。通过空数组[]使用 Array.concat() ，结合展开运算符 ... 来平铺数组。递归平铺每个数组元素。

const deepFlatten = (arr) =>
  [].concat(...arr.map((v) => (Array.isArray(v) ? deepFlatten(v) : v)));

题目

N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后，
要求：任何两个皇后不同行，不同列也不在同一条斜线上，
求给一个整数 n ，返回 n 皇后的摆法数。

数据范围: 1 \le n \le 91≤n≤9
要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n!)O(n!)

例如当输入4时，对应的返回值为2，
对应的两种四皇后摆位如下图所示：

解答

大概思路

n个皇后分别在1，2,3...n行的不同列处，列的下标用数组arr表示
要确定皇后的位置，其实就是确定列的位置，因为行已经固定了
进一步讲，也就是如何摆放数组arr [0,1,2,3,...,n-1]
如果没有【不在同一条斜线上】要求，这题其实只是单纯的全排列问题，代码很容易些出来
但是对于【不在同一条斜线上】要求，全排列得到的res结果有些并不能用，比如说皇后的列位置不能这样排列：[0,1,2,3...,n-1]
所以现在问题变成了，在全排列的基础上，根据N皇后的问题，去除一些结果
下面开始声明一些变量
arr n个皇后的列位置
res n皇后排列结果
ruler 记录对应的列位置是否已经占用（也是是否有皇后），如果有，那么设为1，没有设为0
setPos 哈希集合，标记正斜线（从左上到右下）位置，如果在相同正斜线上，坐标(x,y)满足 y-x 都相同
setCon 哈希集合，标记反正斜线（从y右上到左下）位置，如果在相同反斜线上，坐标(x,y)满足 x+y 都相同

大致的代码思路如下所示:

arr = [0,1,2,3,...,n-1]
res = []
ruler = [n]
setPos = new Set()
setPos = new Set()

backtrack(路径, arr):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表(arr):
        做选择
        backtrack(路径, arr)
        撤销选择
 return res.length

一些解释

首先，N 个皇后肯定得在不同行，不同列处（由题意 “任何两个皇后不同行，不同列” 可知）。
要实现这个方案，其实思路和全排列一样。把N个皇后的列坐标定义成数组arr = [0,1,2,...,n-1]。然后全排列该数组即可，得到的排列方式res的长度，就是排列方案的总数。
但是N皇后问题，还需要满足N 皇后不在同一条斜线上。这就更复杂了一点，需要对斜线位置进行判断。

怎么判断呢？
如果setPos里不包含正斜线位置，setCon里不包含反斜线位置，那么就是我们要的【满足结束条件】。
在回溯函数里，我们先确定第0排皇后的列位置，然后回溯递归，确定第1排的皇后的列位置。
所以每次回溯，坐标(x,y)其实是(row,i)

最终代码

     function Nqueen(n) {
            const arr = Array.from({ length: n }, (item, index) => index) // 列的位置
            let res = [];
            let ruler = new Array(n).fill(0);//用来记录num的皇后下落后，对角线位置，如果在对角线位置，那么为1，否则0
            let setPos = new Set();//标记正对角线
            let setCon = new Set();// 标记反对角线

            const backTrace = (row, path) => {
                if (path.length === n) {
                    res.push(path.slice());
                    return;
                }
                for (let i = 0; i < n; i++) {
                    // i表示列
                    if (ruler[i] == 0 && !setPos.has(i - row) && !setCon.has(i + row)) {
                        path.push(arr[i]);
                        ruler[i] = 1
                        setPos.add(i - row)
                        setCon.add(i + row)
                        backTrace(row + 1, path);
                        path.pop();
                        ruler[i] = 0;
                        setPos.delete(i - row)
                        setCon.delete(i + row)
                    }
                }
            }
            backTrace(0, [])
            return res.length;

        }

跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
示例1

输入：
2
返回值：
2
说明：
青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2

示例2

输入：
7
返回值：
21

思路

一只青蛙一次可以跳1阶或2阶，直到跳到第n阶，也可以看成这只青蛙从n阶往下跳，到0阶，按照原路返回的话，两种方法事实上可以的跳法是一样的——即怎么来的，怎么回去！
当青蛙在第n阶往下跳，它可以选择跳1阶到n-1，也可以选择跳2阶到n-2，即它后续的跳法变成了f(n-1)+f(n-2)，这就变成了斐波那契数列。因此可以按照斐波那契数列的做法来做：即输入n，输出第n个斐波那契数列的值，初始化0阶有1种，1阶有1种。

step 1：低于2项的数列，直接返回n。
step 2：初始化第0项，与第1项分别为0，1.
step 3：从第2项开始，逐渐按照公式累加，并更新相加数始终为下一项的前两项。

解答

function jumpFloor(number) {
  if (number <= 0) return -1;
  if (number <= 2) return number;
  return jumpFloor(number - 1) + jumpFloor(number - 2);
}

将数字转化为千分位格式

使用toLocaleString()将浮点数转换为 Decimal mark 格式。将整数部分转化为用逗号分隔的字符串。

const toDecimalMark = num => num.toLocaleString('en-US');
toDecimalMark(12305030388.9087); // "12,305,030,388.909"

解析网址参数

将http://url.com/page?name=Adam&surname=Smith转换为{name: 'Adam', surname: 'Smith'}

const getURLParameters = (url) =>  url
.match(/([^?=&]+)(=([^&]*))/g)
.reduce(
  (a, v) => (
    (a[v.slice(0, v.indexOf("="))] = v.slice(v.indexOf("=") + 1),a)
  ),
  {}
);
console.log(getURLParameters("http://url.com/page?name=Adam&surname=Smith"));

没有重复项的全排列

题目

给出一组数字，返回该组数字的所有排列
例如：

输入
[1,2,3]
输出
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].

（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

数据范围：数字个数 0 < n \le 60<n≤6
要求：空间复杂度 O(n!)O(n!) ，时间复杂度 O(n!）O(n!）

解答

   function permute(nums) {
            const res = [], len = nums.length
            const traceTrack = (arr) => {
                if (arr.length ===len) {
                    res.push(arr.slice())
                    return
                }
                for (let i = 0; i < len; i++) {
                    if (arr.includes(nums[i])) continue
                    arr.push(nums[i])
                    traceTrack(arr)
                    arr.pop()
                }
            }

            traceTrack([])
            return res
        }

合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

解答

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    const prehead = new ListNode(-1);
    let prev = prehead;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            prev.next = l1;
            l1 = l1.next;
           
        } else {
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;
        
    }

    // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
    prev.next = l1 === null ? l2 : l1;
    return prehead.next;
};

题解

我们的 while 循环每次比较 l1 和 l2 的大小，把较小的节点接到结果链表上

反转链表

题目

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0\leq n\leq10000≤n≤1000
要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。

如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

示例1

输入：
{1,2,3}
返回值：
{3,2,1}

示例2

输入：
{}
返回值：
{}
说明：
空链表则输出空

解答

function ReverseList(pHead)
{
    if(!pHead || !pHead.next) return pHead;
      
    let newhead = ReverseList(pHead.next);
    pHead.next.next = pHead;
    pHead.next = null;
      
    return newhead;
}

括号生成

题目

数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

解答

    const generateParenthesis = (n) => {
              const target = []
              dfs(0, 0, '', target, n)
              return target
          }
          const dfs = (startCount, endCount, str, target, n) => {
              if (str.length === 2 * n) {
                  target.push(str)
                  return str
              }
              if (startCount < n) dfs(startCount + 1, endCount, str + '(', target, n)
              if (endCount < startCount) dfs(startCount, endCount + 1, str + ')', target, n)
          }

无重复字符的最长子串

题目：

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解答

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const arr=s.split('')
    let l=0,r=0,maxLen=0,obj={}
    while(l<arr.length&&r<arr.length){
        if(!obj[arr[r]]){
            obj[arr[r]]=1
            r++
        }else{
            obj[arr[l]]=0
            l++
        }
        maxLen=Math.max(maxLen,r-l)
    }
    return maxLen
};

包含min函数的栈

题目

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素

数据范围：操作数量满足 0 \le n \le 300 \0≤n≤300 ，输入的元素满足 |val| \le 10000 \∣val∣≤10000
进阶：栈的各个操作的时间复杂度是 O(1)\O(1) ，空间复杂度是 O(n)\O(n)

示例:
输入:    ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
输出:    -1,2,1,-1
解析:
"PSH-1"表示将-1压入栈中，栈中元素为-1
"PSH2"表示将2压入栈中，栈中元素为2，-1
“MIN”表示获取此时栈中最小元素==>返回-1
"TOP"表示获取栈顶元素==>返回2
"POP"表示弹出栈顶元素，弹出2，栈中元素为-1
"PSH1"表示将1压入栈中，栈中元素为1，-1
"TOP"表示获取栈顶元素==>返回1
“MIN”表示获取此时栈中最小元素==>返回-1

解答

let stack = []
let stackMin = []


function push(node) {
    if (stack.length === 0) {
        stackMin.push(node)
    } else {
        if (node <= stackMin[stackMin.length - 1]) {
            stackMin.push(node)
        } else {
            stackMin.push(stackMin[stackMin.length - 1])
        }
    }
    stack.push(node)

}
function pop() {
    if (stack.length) {
        stackMin.pop()
        return stack.pop()
    } else {
        return null
    }
}
function top() {
    if (stack.length) {
        return stack[stack.length - 1]
    } else {
        return null
    }

}
function min() {
    return stackMin[stackMin.length-1]
}
module.exports = {
    push: push,
    pop: pop,
    top: top,
    min: min
};

括号生成

题目

数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

解答

    const generateParenthesis = (n) => {
              const target = []
              dfs(0, 0, '', target, n)
              return target
          }
          const dfs = (startCount, endCount, str, target, n) => {
              if (str.length === 2 * n) {
                  target.push(str)
                  return str
              }
              if (startCount < n) dfs(startCount + 1, endCount, str + '(', target, n)
              if (endCount < startCount) dfs(startCount, endCount + 1, str + ')', target, n)
          }

两数之和

题目

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

输入：
[3,2,4],6
返回值：
[2,3]
说明：
因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2,3]

输入：
[20,70,110,150],90
返回值：
[1,2]
说明：
20+70=90

解答

/**
 *
 * @param numbers int整型一维数组
 * @param target int整型
 * @return int整型一维数组
 */
function twoSum(numbers, target) {
   let res=new Array(2)
   const map=new Map();
    for(let i=0;i<numbers.length;i++){
        if(map.has(target-numbers[i])){
            res=[map.get(target-numbers[i])+1,i+1]
            break;
        }else{
            map.set(numbers[i],i)
        }
    }
    return res
}

顺次数-1291

我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。

请你返回由 [low, high] 范围内所有顺次数组成的有序列表（从小到大排序）。

示例 1：

输出：low = 100, high = 300
输出：[123,234]

示例 2：

输出：low = 1000, high = 13000
输出：[1234,2345,3456,4567,5678,6789,12345]

解答

/**
 * @param {number} low
 * @param {number} high
 * @return {number[]}
 */
 let sequentialDigits = function (low, high) {
    let lowLen = `${low}`.length
    let highLen =  `${high}`.length
    let lens = []
    for (let i = lowLen; i <= highLen; i++) {
      lens.push(i)
    }
  
    let res = []
    for (let i = 0; i < lens.length; i++) {
      let len = lens[i]
      for (let start = 1; start <= 10 - len; start++) {
        let num = start
      
        for (let n = start + 1; n < start + len; n++) {
          num = 10 * num + n
        }
        if (num <= high && num >= low) {
          res.push(num)
        }
      }
    }
  
    return res
  }

跳水板-面试题 16.11

你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。

返回的长度需要从小到大排列。

示例 1

输入：
shorter = 1
longer = 2
k = 3
输出： [3,4,5,6]
解释：
可以使用 3 次 shorter，得到结果 3；使用 2 次 shorter 和 1 次 longer，得到结果 4 。以此类推，得到最终结果。

解答

/**
 * @param {number} shorter
 * @param {number} longer
 * @param {number} k
 * @return {number[]}
 */
var divingBoard = function (shorter, longer, k) {
    if (k === 0) return []
    if (shorter === longer) return [k * shorter]
    let arr = []
    for (let i = 0; i <= k; i++) {
        arr.push(longer * i + shorter * (k - i))
    }
    return arr
};

112. 路径总和

题目

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点是指没有子节点的节点。

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径

解答

/**
 * 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 {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
    if(root==null) return false
    if(root.left!=null) root.left.val+=root.val;
    if(root.right!=null) root.right.val+=root.val
    if(root.left==null&&root.right==null) return root.val==targetSum
    return hasPathSum(root.left,targetSum)|| hasPathSum(root.right,targetSum)
};