leetcode刷题记录(12)-中等

1.加油站

题目：

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明: 

如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。

思路：作差，每个下表的差就是离开这个点还剩的油（也可以理解为到了下个点的时候还剩的油）。对于某个点，从这个点开始，每个点的累计的油大于等于0，那么结果就是这个点

/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function(gas, cost) {
  const l = gas.length;
  const list = new Array(l);
  let sum = 0;
  for (let i = 0; i < l; i++) {
    list[i] = gas[i] - cost[i];
    sum += list[i];
  }
  if (sum < 0) return -1;
  for (let i = 0; i < l; ) {
    sum = 0;
    for (let count = 0; count < l; count++) {
      sum += list[(i + count) % l];
      if (sum < 0) {
        i += count;
        break;
      }
    }
    if (sum >= 0) return i;
    i++;
  }
  return -1;
};

2.只出现一次的数字

题目：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

思路：先用map记录

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
  const map = new Map();
  for (const i of nums) {
    map.set(i, (map.get(i) || 0) + 1);
  }
  for (const v of map.keys()) {
    if (map.get(v) == 1) return v;
  }
};

接下来是优化，不使用额外空间。其实这是一个数学方法。3(a+b+c)=3(b+c)+a+2a，也就是2a=3(a+b+c)- (3(b+c) + a )

首先，用set去重，我们就能得到3(a+b+c)，然后，对原数组求和，两个的差值就是2a。

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let arr=[...new Set(nums)]; 
    return (3*arr.reduce((a,b)=>a+b)-nums.reduce((a,b)=>a+b))/2
}

或者，可以排序，如果某个值和后面一个值不相等，那么就是这个数

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
     nums.sort((a,b)=>a-b);
    for(let i=0;i<nums.length;i+=3){
        if(nums[i] != nums[i+1]) return nums[i];
    }
}

3.复制带随机指针的链表

题目：

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的 深拷贝。 

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。

思路：先不管随机指针，我们先按顺序复制整个链表，然后再遍历链表，把随机指针指向复制出来的节点即可。所以我们用map来记录新节点和旧节点的关系

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
  if (!head) return head;
  const map = new Map();
  let res = new Node();
  let a = res;
  let res1 = res;
  while (head) {
    res.next = getNode(head);
    head = head.next;
    res = res.next;
  }
  res1 = res1.next;
  while (res1) {
    res1.random = getNode(res1.random);
    res1 = res1.next;
  }
  function getNode(node) {
    if (!node) return node;
    if (map.get(node)) {
      return map.get(node);
    } else {
      const newNode = new Node(node.val, node.next, node.random);
      map.set(node, newNode);
      return newNode;
    }
  }
  return a.next;
};

4.单词拆分

题目：

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
  const wordSet = new Set(wordDict);
  const memo = new Array(s.length);

  const check = (s, wordSet, start, memo) => {
    if (start == s.length) return true;
    if (memo[start] !== undefined) return memo[start]; 

    for (let i = start + 1; i <= s.length; i++) {
      const word = s.slice(start, i);                
      if (wordSet.has(word) && check(s, wordSet, i, memo)) {
        return memo[start] = true;
      }
    }
    return memo[start] = false;
  };

  return check(s, wordSet, 0, memo);
};

5.环形链表II

题目：

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

思路：先用set记录遍历过的节点，遇到遍历过的，就返回该节点，直到null

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
  let fast = head;
  let slow = head;
  while (fast && fast.next) {
    fast = fast.next.next;
      slow = slow.next;
    if (slow == fast) {
      while (slow !== head) {
        slow = slow.next;
        head = head.next;
      }
      return head;
    } 
  }
  return null;
};

进阶：不使用额外空间的话，就用快慢指针。之前用快慢指针判断过链表是否为环形链表，现在是要找到入环的第一个节点，这里用官方的图示意一下：

我们利用已知的条件：慢指针移动 1 步，快指针移动 2 步，来说明它们相遇在环的入口处。（下面证明中的 tortoise 表示慢指针，hare 表示快指针）

2(F+a)=F + a + b +a

F= b

所以我们用快慢指针找到相遇的节点，然后同时移动开始节点和这个相遇的节点，它们相遇的节点就是入环的节点

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
  let fast = head;
  let slow = head;
  while (fast && fast.next) {
    fast = fast.next.next;
      slow = slow.next;
    if (slow == fast) {
      while (slow !== head) {
        slow = slow.next;
        head = head.next;
      }
      return head;
    } 
  }
  return null;
};

​    
  


​