[失业前端恶补算法]JavaScript leetcode刷题top100（一）

• 题面
  给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
• 知识点：
  哈希表
• 思路
  遍历整个数组，对于每个值，如果 target - x 已经出现过，那么返回这组解，否则就把这个当前值存到哈希表中，使用 [ 值：下标 ] 的形式进行存储
• 代码

var twoSum = function (nums, target) {let hash = {};for (var i = 0; i < nums.length; i++) {if(typeof hash[target - nums[i]] !== 'undefined'){return [hash[target - nums[i]],i];}hash[nums[i]] = i;}};

• 题面
  给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
  有效字符串需满足：
  左括号必须用相同类型的右括号闭合。
  左括号必须以正确的顺序闭合。
  每个右括号都有一个对应的相同类型的左括号。
• 知识点
  栈
• 思路
  遇到左一半的括号就压入栈中，遇到右一半的括号就判定栈顶元素是不是匹配，匹配就抛出栈顶元素，根据根据栈中有没有剩余没有匹配的元素判定是不是匹配
• 代码

var isValid = function (s) {let stack = [];for (var i = 0; i < s.length; i++) {if(s[i] == ')' && stack[stack.length-1] == '('){stack.pop();}else if(s[i] == '}' && stack[stack.length-1] == '{'){stack.pop();}else if(s[i] == ']' && stack[stack.length-1] == '['){stack.pop();}else{stack.push(s[i]);}}return stack.length == 0;
};

• 题面
  将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
• 知识点
  链表操作
• 思路
  新建一个链表作为返回需要，两个链表从头开始遍历，如果每次将两个链表当前值较大的一个放到新链表中，之后放入新链表的那一链表指向下一个值，直到一个链表全部遍历完成，之后将还没有操作完毕的链表链接在新链表的尾部。
• 代码

var mergeTwoLists = function (list1, list2) {var a = new ListNode(0, null);b = a;while (list1 != null && list2 != null) {if (list1.val < list2.val) {a.next = list1;a = a.next;list1 = list1.next;} else {a.next = list2;a = a.next;list2 = list2.next;}}if( list1 ){a.next = list1}else if( list2 ){a.next = list2}return b.next;
};

• 题面
  假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
• 知识点
  动态规划
• 思路
  对于每一步，他可能从 n-1 到来，或者从 n-2 到来，所以第 n 步的可能方案是第 n-1 和第 n-2 的方案数的和，从 2 开始遍历到 n 步即可
• 代码

var climbStairs = function (n) {let dp = [1, 1];for (var i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];
};

• 题面
  给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
• 知识点
  二叉树，中序遍历
• 思路
  dfs 实现中序遍历，对于每一个节点，如果有左孩子就一直搜索左孩子，没有左孩子就输出节点内容，最后再搜索二叉树的右孩子
• 代码

var inorderTraversal = function (root) {let re = [];let dfs = (node) => {if (!node) {return;}if (node.left) {dfs(node.left);}re.push(node.val);if (node.right) {dfs(node.right);}}dfs(root);return re;
};