初级算法 设计问题

打乱数组

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的

洗牌算法

var Solution = function (nums) {
  this.nums = nums;
  this.copy = JSON.parse(JSON.stringify(nums))
};


Solution.prototype.reset = function () {
  return this.copy
};

Solution.prototype.shuffle = function () {
  const arr = JSON.parse(JSON.stringify(this.copy))
  let len = arr.length;
  while (len) {
    let idx = parseInt(Math.random() * len);
    [arr[len - 1], arr[idx]] = [arr[idx], arr[len - 1]];
    len--;
  }
  return arr;
};

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

var MinStack = function () {
  this.stack = [];
  this.minIndex = -1;
};

MinStack.prototype.push = function (val) {
  if (this.stack.length == 0) {
    this.minIndex = this.stack.length;
  } else {
    if (val < this.stack[this.minIndex]) {
      this.minIndex = this.stack.length;
    }
  }
  this.stack.push(val);
};

MinStack.prototype.pop = function () {
  if (this.minIndex == this.stack.length - 1) {
    let min = Infinity;
    for (let i = 0; i < this.stack.length - 1; i++) {
      if (this.stack[i] < min) {
        min = this.stack[i];
        this.minIndex = i;
      }
    }
  }
  if (this.stack.length == 1) this.minIndex = -1;
  return this.stack.pop();
};

MinStack.prototype.top = function () {
  if (this.stack.length) {
    return this.stack[this.stack.length - 1];
  } else {
    return null;
  }
};

MinStack.prototype.getMin = function () {
  if (this.minIndex > -1) {
    return this.stack[this.minIndex];
  }
};