5.4

剑指 Offer 09. 用两个栈实现队列

问题：只是删除时候返回了头节点，那怎么拿到这个queue呢

// 栈的特性是后进先出
// 队列的特性是先进先出
// 每次操作返回状态，如果没元素返回-1
var CQueue = function() {
    this.inStack = []
    this.outStack = []
};
/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function(value) {
    this.inStack.push(value)
};
/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    if (!this.outStack.length) {
        if (!this.inStack.length) {
            return -1
        }
        this.in2out()
    }
    return this.outStack.pop()
};
CQueue.prototype.in2out = function() {
    while(this.inStack.length) {
        this.outStack.push(this.inStack.pop())
    }
}
/**
 * Your CQueue object will be instantiated and called as such:
 * var obj = new CQueue()
 * obj.appendTail(value)
 * var param_2 = obj.deleteHead()
 */

207. 课程表

273. 整数转换英文表示

/**
 * @param {number} num
 * @return {string}
 */
const nt = ["Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve",
        "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"],
      tens = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"],
      bmt = ["Billion","Million","Thousand"],
      BILLION = 1000000000, MILLION = 1000000, THOUSAND = 1000;
var num2str = function(num) {
    const ans = [];
    if(num >= 100){
        ans.push(nt[Math.floor(num/100)]);
        ans.push("Hundred");
        num %= 100;
    }
    if(num >= 20){
        ans.push(tens[Math.floor(num/10)]);
        num %= 10;
    }
    if(num > 0){
        ans.push(nt[num]);
    }
    return ans.join(" ");
}
var numberToWords = function(num) {
    if(num == 0)
        return nt[num];
    const res = [];
    if(num >= BILLION){
        res.push(num2str(Math.floor(num/BILLION)));
        res.push(bmt[0]);
        num %= BILLION;
    }
    if(num >= MILLION){
        res.push(num2str(Math.floor(num/MILLION)));
        res.push(bmt[1]);
        num %= MILLION;
    }
    if(num >= THOUSAND){
        res.push(num2str(Math.floor(num/THOUSAND)));
        res.push(bmt[2]);
        num %= THOUSAND;
    }
    if(num > 0)
        res.push(num2str(num));
    return res.join(" ");
};

7. 整数反转

var reverse = function(x) {
    let res = 0;
    while(x){
        res = res * 10 + x % 10;
        if(res > Math.pow(2, 31) - 1 || res < Math.pow(-2, 31)) return 0;
        // 相当于 parseInt
        x = ~~(x / 10);
    }
    return res;
};

复原IP地址

const restoreIpAddresses = (s) => { 
  const res = [];
  // 复原从start开始的子串
  const dfs = (subRes, start) => {                 
    if (subRes.length == 4 && start == s.length) { // 片段满4段，且耗尽所有字符
      res.push(subRes.join('.'));                  // 拼成字符串，加入解集
      return;                     // 返不返回都行，指针已经到头了，严谨的说还是返回
    }
    // 这里为什么return不push
    if (subRes.length == 4 && start < s.length) {  // 满4段，字符未耗尽，不用往下选了
      return;
    }
    for (let len = 1; len <= 3; len++) {           // 枚举出选择，三种切割长度
      if (start + len - 1 >= s.length) return;     // 加上要切的长度就越界，不能切这个长度
      if (len != 1 && s[start] == '0') return;     // 不能切出'0x'、'0xx'

      const str = s.substring(start, start + len); // 当前选择切出的片段
      if (len == 3 && +str > 255) return;          // 不能超过255

      subRes.push(str);                            // 作出选择，将片段加入subRes
      dfs(subRes, start + len);                    // 基于当前选择，继续选择，注意更新指针
      // 为什么是撤销
      subRes.pop(); // 上面一句的递归分支结束，撤销最后的选择，进入下一轮迭代，考察下一个切割长度
    }
  };

  dfs([], 0);       // dfs入口
  return res;
};

31. 下一个排列

思路：

function nextPermutation(nums) {
    let i = nums.length - 2;                   // 向左遍历，i从倒数第二开始是为了nums[i+1]要存在
    while (i >= 0 && nums[i] >= nums[i + 1]) { // 寻找第一个小于右邻居的数
        i--;
    }
    if (i >= 0) {                             // 这个数在数组中存在，从它身后挑一个数，和它换
        let j = nums.length - 1;                // 从最后一项，向左遍历
        while (j >= 0 && nums[j] <= nums[i]) {  // 寻找第一个大于 nums[i] 的数
            j--;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]]; // 两数交换，实现变大
    }
    // 如果 i = -1，说明是递减排列，如 3 2 1，没有下一排列，直接翻转为最小排列：1 2 3
    let l = i + 1;           
    let r = nums.length - 1;
    while (l < r) {                            // i 右边的数进行翻转，使得变大的幅度小一些
        [nums[l], nums[r]] = [nums[r], nums[l]];
        l++;
        r--;
    }
}