算法题

兔` 、

1.两数之和

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var visitedMap = {} // 已经访问过的数组元素及下标 
    for (var i = 0; i < nums.length; i++){
        const curNum = nums[i]
        const wantedNum = target - curNum // 要找的目标值
        if (visitedMap[wantedNum]!==undefined){ // 目标值在map中存在
            if(visitedMap[wantedNum] !== i) { // 下标不重复
                return [visitedMap[wantedNum], i] // 返回结果
            }
        } else {
            visitedMap[curNum] = i // 没有找到，将当前数值加入到map中
        }
    }
    return []
};

79单词搜索

const exist = (board, word) => {
  const m = board.length;
  const n = board[0].length;
  const used = new Array(m);    // 二维矩阵used
  // 空矩阵，用来记录是否访问过
  for (let i = 0; i < m; i++) {
    used[i] = new Array(n);
  }
  // 判断当前点是否是目标路径上的点
  const canMove = (row, col, i) => { // row col是当前点的坐标，i是当前考察的字符索引
    if (i > word.length - 1) {       // 递归的出口
      return true;
    }
    if (row < 0 || row >= m || col < 0 || col >= n) { // 当前点不存在
      return false;
    }
    if (used[row][col] || board[row][col] != word[i]) { // 当前的点已经走过，或当前点就不是目标点
      return false;
    }
    // 排除掉这些false情况，当前点是没问题的，可以继续递归考察
    used[row][col] = true;  // used记录一下当前点被访问了
    const canMoveRest =
      canMove(row + 1, col, i + 1) ||
      canMove(row - 1, col, i + 1) ||
      canMove(row, col + 1, i + 1) ||
      canMove(row, col - 1, i + 1); 
    if (canMoveRest) { // 基于当前点，可以为剩下的字符找到路径
      return true;    
    }
    used[row][col] = false; // 找不出，返回false，继续考察别的分支，并撤销当前点的访问状态。
    return false;
  };
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] == word[0] && canMove(i, j, 0)) { // 找到dfs的起点
        return true; // 找到起点，且dfs的结果也true，则找到了目标路径
      }
    }
  }
  return false; // 怎么样都没有返回true，则返回false
}

104: 树的最大深度

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(root == null) {
        return 0;
    } else {
        let left = maxDepth(root.left);
        let right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
};

141 环型链表

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let map = new Map()
    // 1. 如果链表没有结束
    while (head) {
    // 2. 如果之前访问过， 证明有环
    if (map.has(head)) {
      return true;
    } else {
     // 3. 登记一下
     map.set(head, true)
    }
    // 4. 一直往链表尾部走
    head = head.next;
  }
  // 5. 如果没有重复，那么返回 false
  return false;
};