js解leetcode(53)-简单

1.用两个栈实现队列

题目：

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

思路：js因为数组的有shift和pop所以很简单，如果用java中的栈的话，思路大概是这样：

两个数组一个用于添加元素l1，一个用于删除元素l2。添加元素时，将所有元素都放进l1中，然后将元素入l1;删除元素时，所有元素出栈，推入l2，删除l2的栈顶元素。

var CQueue = function () {
  this.stack = [];
};

/**
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function (value) {
  this.stack.push(value);
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function () {
  if (!this.stack.length) {
    return -1;
  }
  return this.stack.shift();
};

2.斐波那契数列

题目：

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

思路：动态规划

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  const mod = Math.pow(10, 9) + 7;
  let v1 = 0;
  let v2 = 1;
  while (--n ) {
    [v1, v2] = [v2, (v1 + v2) % mod];
  }
  return v2;
};

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
  const list = new Array(n + 1);
  list[0] = 0;
  list[1] = 1;
  const mod = Math.pow(10, 9) + 7;
  for (let i = 2; i <= n; i++) {
    list[i] = (list[i - 1] + list[i - 2]) % mod;
  }
  return list[n];
};

3.旋转数组的最小数字

题目：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。  

思路：遍历或者递归均可

/**
 * @param {number[]} numbers
 * @return {number}
 */
var minArray = function(numbers) {
  const l = numbers.length;
  for (let i = 1; i < l; i++) {
    if (numbers[i] < numbers[i - 1]) return numbers[i];
  }
  return numbers[0];
};

4.二进制中1的个数

题目：

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2

思路：转换成字符串然后输出

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
      const s = n.toString(2);
  return [...s].filter((i) => i == "1").length;
};

5.打印从1到最大的n位数

题目：输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

思路：计算最大的数然后按顺序打印

/**
 * @param {number} n
 * @return {number[]}
 */
var printNumbers = function(n) {
  const max = Math.pow(10, n);
  const res = new Array(max - 1);
  for (let i = 0; i < max - 1; i++) {
    res[i] = i + 1;
  }
  return res;
};