LeetCode杂题

1.两数之和

题目描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

var twoSum = function(nums, target) {
    const prevNums = {};                         // 存放出现过的数字，和对应的索引
    for (let i = 0; i < nums.length; i++) {      // 遍历每一项
        const curNum = nums[i];                    // 当前项
        const targetNum = target - curNum;         // 希望从过去的数字中找到的呼应项
        const targetNumIndex = prevNums[targetNum];// 在prevNums中找targetNum的索引
        if (targetNumIndex !== undefined) {        // 如果能找到
            return [targetNumIndex, i];              // 直接返回targetNumIndex和当前的i
        }                                          // 如果找不到，说明之前没出现过targetNum
        prevNums[curNum] = i;                      // 往prevNums存当前curNum和对应的i
    }
};

537.复数乘法

题目描述：输入两个表示复数的字符串，输出它们相乘的结果的字符串。复数字符串用a+bi表示(a, b 为整数, i为虚数单位，i2=1)

注意:
1.输入字符串不包含额外的空格。
2.输入字符串将以 a+bi 的形式给出，其中整数 a 和 b 的范围均在 [-100, 100] 之间。输出也应当符合这种形式。

var complexNumberMultiply = function(a, b) {
    let alist = a.includes("+")?a.split("+"):a.split("-")
    let blist = b.includes("+")?b.split("+"):b.split("-")
    let r = alist[0] * blist[0] - parseInt(alist[1].slice(0,alist[1].length-1))*parseInt(blist[1].slice(0,blist[1].length-1))
    let c = alist[0] * parseInt(blist[1].slice(0,blist[1].length-1)) + parseInt(alist[1].slice(0,alist[1].length-1) )* blist[0]
    return r+"+"+c+"i"
};

1154.一年中的第几天

题目描述：给你一个按 YYYY-MM-DD 格式表示日期的字符串 date，请你计算并返回该日期是当年的第几天。
通常情况下，我们认为 1 月 1 日是每年的第 1 天，1 月 2 日是每年的第 2 天，依此类推。每个月的天数与现行公元纪年法（格里高利历）一致。

var dayOfYear = function(date) {
    let time = new Date(date);
    let year = time.getFullYear();
    let mouth = time.getMonth();
    let day = time.getDate();
    let sum = 0;
    let days = new Array(31,28,31,30,31,30,31,31,30,31,30,31);
    if(year%400==0||(year%4==0&&year%100!=0)){
        days[1]=29;
    }
    for(var i=0;i<mouth;i++){
        sum = sum+days[i];
    }
    sum = sum+day*1;
    return sum;
};

146.LRU缓存

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。

写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

详解：https://leetcode-cn.com/problems/lru-cache/solution/bu-yong-yu-yan-nei-jian-de-map-gua-dang-feng-zhuan/

class ListNode {
  constructor(key, value) {
    this.key = key
    this.value = value
    this.next = null
    this.prev = null
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.hashTable = {}
    this.count = 0
    this.dummyHead = new ListNode()
    this.dummyTail = new ListNode()
    this.dummyHead.next = this.dummyTail
    this.dummyTail.prev = this.dummyHead
  }

  get(key) {
    let node = this.hashTable[key]
    if (node == null) return -1
    this.moveToHead(node)
    return node.value
  }

  put(key, value) {
    let node = this.hashTable[key]
    if (node == null) {
      let newNode = new ListNode(key, value)
      this.hashTable[key] = newNode
      this.addToHead(newNode)
      this.count++
      if (this.count > this.capacity) {
        this.removeLRUItem()
      }
    } else {
      node.value = value
      this.moveToHead(node)
    }
  }

  moveToHead(node) {
    this.removeFromList(node)
    this.addToHead(node)
  }
  
  removeFromList(node) {
    let tempForPrev = node.prev
    let tempForNext = node.next
    tempForPrev.next = tempForNext
    tempForNext.prev = tempForPrev
  }

  addToHead(node) {
    node.prev = this.dummyHead
    node.next = this.dummyHead.next
    this.dummyHead.next.prev = node
    this.dummyHead.next = node
  }

  removeLRUItem() {
    let tail = this.popTail()
    delete this.hashTable[tail.key]
    this.count--
  }

  popTail() {
    let tailItem = this.dummyTail.prev
    this.removeFromList(tailItem)
    return tailItem
  }
}

29.顺时针打印矩阵

题目描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

image.png

思路分析：

循环的条件是 top <= bottom && left <= right
每遍历完一条边，下一条边遍历的起点被“挤占”，所以要更新相应的边界
因为要在循环过程中更新边界，可能出现：循环的条件在中途不再满足，即 top > bottom || left > right ，其中一对边界彼此交错了
说明此时所有项都遍历完了，如果没有及时地 break，就会重复遍历，造成元素重复地被推入结果数组
解决办法：
每遍历完一条边，更新完相应的边界后，都加一句：if (top > bottom || left > right) break
但其实发现，遍历结束要么发生在遍历完“上边”，要么发生在遍历完“右边”
所以只需在这两步操作之后加 if (top > bottom || left > right) break 即可，不用每一条后面都加

const spiralOrder = (matrix) => {
  if (matrix.length == 0) return [];
  const res = [];

  let top = 0;
  let bottom = matrix.length - 1;
  let left = 0;
  let right = matrix[0].length - 1;

  while (top <= bottom && left <= right) {
    for (let i = left; i <= right; i++) {
      res.push(matrix[top][i]);
    }
    top++;
    for (let i = top; i <= bottom; i++) {
      res.push(matrix[i][right]);
    }
    right--;

    if (top > bottom || left > right) break;

    for (let i = right; i >= left; i--) {
      res.push(matrix[bottom][i]);
    }
    bottom--;
    for (let i = bottom; i >= top; i--) {
      res.push(matrix[i][left]);
    }
    left++;
  }
  return res;
};