【当前排名67359】挑战leetcode进入前1w名

李恒道

https://leetcode.cn/problems/reverse-linked-list/
反转链表

var reverseList = function(head) {
    let pre=null;
    while(head!=null){
      const next=head.next;
      head.next=pre;
      pre=head;
      head=next;
    }
    return pre
};

李恒道

https://leetcode.cn/problems/reorder-list/submissions/591128737/
没太理解
但是过了...

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @Return {ListNode}
 */
var reverseList = function (head) {
  let pre = null;
  while (head != null) {
    const next = head.next;
    head.next = pre;
    pre = head;
    head = next;
  }
  return pre;
};
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function (head) {
  let slow = head;
  let fast = head;
  while (fast?.next != null) {
    fast = fast.next?.next;
    slow = slow.next;
  }
  return slow;
};
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function (head) {
  let mid = middleNode(head);
  let head2 = reverseList(mid);
  let ans=head
  while(head2.next!==null){
    const next=head.next;
    const next2=head2.next;
    head.next=head2;
    head2.next=next;
    head=next;
    head2=next2
  }
  return ans
};

李恒道

https://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/591129441/
秒了

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @Return {number[]}
 */
var preorderTraversal = function(root) {
    const result = []; function traverse(node) { if (!node) return; result.push(node.val); traverse(node.left); traverse(node.right); } traverse(root); return result;
};

李恒道

https://leetcode.cn/problems/binary-tree-postorder-traversal/submissions/591129599/
后续

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @Return {number[]}
 */
var postorderTraversal = function(root) {
      const result = [];
  function traverse(node) {
    if (!node) return;
    traverse(node.left);
    traverse(node.right);
    result.push(node.val);
  }
  traverse(root);
  return result;
};

李恒道

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/submissions/591135898/
都不知道怎么扣过去的

var findMin = function (nums) {
  let l = 0,
    r = nums.length - 1;
  let min = nums[0];
  while (l <= r) {
    const center = l + Math.floor((r - l) / 2);
    min = Math.min(min, nums[center]);
    if (nums[l] == nums[center] && nums[center] == nums[r]) {
      l++;
      r--;
      continue;
    }
    if (nums[l] <= nums[center]) {
      min = Math.min(min, nums[l]);
      l = center + 1;
    } else {
      min = Math.min(min, nums[center]);
      r = center - 1;
    }
  }
  return min;
};

李恒道

https://leetcode.cn/problems/design-an-atm-machine/submissions/591153212/
模拟题，秒了

var ATM = function () {
  this.money = new Array(5).fill(0);
};

/**
 * @param {number[]} banknotesCount
 * @Return {void}
 */
ATM.prototype.deposit = function (banknotesCount) {
  for (let index = 0; index < banknotesCount.length; index++) {
    const money = banknotesCount[index];
    this.money[index] += money;
  }
};

/**
 * @param {number} amount
 * @return {number[]}
 */
ATM.prototype.withdraw = function (amount) {
  const ans = new Array(5).fill(0);
  const list = [20, 50, 100, 200, 500];
  for (let index = 4; index >= 0; index--) {
    ans[index] = Math.floor(amount / list[index]);
    ans[index]=Math.min(ans[index],this.money[index])
    amount -= ans[index] * list[index];
  }
  if (amount !== 0) {
    return [-1];
  }
  for (let index = 0; index < ans.length; index++) {
    const pices = ans[index];
    this.money[index] -= pices;
  }
  return ans;
};

李恒道

https://leetcode.cn/problems/insertion-sort-list/submissions/591160212/
插入排序
秒了

var insertionSortList = function (head) {
  let ans = null;
  let node = head;
  const insert = (node) => {
    let list = ans;
    if (list == null) {
      node.next = null;
      ans = node;
      return;
    }
    if (node.val <= list.val) {
      node.next = list;
      ans = node;
      return;
    }
    pre = list;
    while (list.next !== null) {
      if (node.val <= list.val) {
        pre.next = node;
        node.next = list;
        return;
      }
      pre = list;
      list = list.next;
    }
    if (node.val <= list.val) {
      pre.next = node;
      node.next = list;
    } else {
      node.next = null;
      list.next = node;
    }
  };
  while (node !== null) {
    let next = node.next;
    insert(node);
    node = next;
  }
  return ans;
};

李恒道

https://leetcode.cn/problems/count-primes/submissions/591166551/
靠缓存硬打过去了

function isPrime(num) {
  if (num <= 3) {
    return num > 1;
  } else {
    let sq = Math.sqrt(num);
    for (let i = 2; i <= sq; i++) {
      if (num % i === 0) {
        return 0;
      }
    }
    return 1;
  }
}
/**
 * @param {number} n
 * @Return {number}
 */
const cache = new Map();
var countPrimes = function (n) {
  let ans =0 ;
  for (let index = n - 1; index >= 1; index--) {
    if (cache.has(index)) {
      ans += cache.get(index);
      break;
    }
    ans += isPrime(index);
  }
  cache.set(n-1,ans)
  return ans;
};

李恒道

https://leetcode.cn/problems/maximum-consecutive-floors-without-special-floors/submissions/591336871/

这个题是真的简单

var maxConsecutive = function (bottom, top, special) {
  special.sort((a, b) => a - b);
  let max = 0;
  for (let index = 1; index < special.length; index++) {
    max = Math.max(max, special[index] - special[index - 1] - 1);
  }
  max=Math.max(max,special[0]-bottom,top-special[special.length-1])
  return max
};

李恒道

https://leetcode.cn/problems/house-robber-ii/submissions/591340469/
打家劫舍

var rob1 = function (nums, l, r) {
  const map = new Map();
  const robHouse = (l) => {
    if (l > r) {
      return 0;
    }
    if (map.has(l)) {
      return map.get(l);
    }
    const result1 = nums[l] + robHouse(l + 2);
    const result2 = robHouse(l + 1);
    const result = Math.max(result1, result2);
    map.set(l, result);
    return result;
  };
  return robHouse(l);
};
/**
 * @param {number[]} nums
 * @Return {number}
 */
var rob = function (nums) {
  return Math.max(nums[0] + rob1(nums, 2, nums.length - 2),rob1(nums, 1, nums.length - 1));
};