1 两数之和

1.1 题目介绍

  • 给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。
  • 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
  • 你可以按任意顺序返回答案。
  • 示例：
1
2
3

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

1.2 解题思路

1.2.1 枚举（$$ O(n^2) $$）

1
2
3
4
5
6
7
8
9

function twoNum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
}

1.2.2 Map（$$O(n)$$）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

function twoNum(nums, target) {
  // 值作为key，下标作为value
  const map = new Map()
  for (let i = 0; i < nums.length; i++) {
    // 作差，准备找与之匹配的另外一个数x
    const x = target - nums[i]
    // 如果在map中找到了，直接返回即可
    if (map.has(x)) return [map.get(x), i]
    // 否则将数组中的值和对应下标暂时存入map中
    map.set(nums[i], i)
  }
}

2 两数相加

2.1 题目介绍

  • 给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
  • 请你将两个数相加，并以相同形式返回一个表示和的链表。
  • 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

image.png

1
2
3

输入： l1 = [2,4,3], l2 = [5,6,4]
输出： [7,0,8]
解释： 342 + 465 = 807.

2.2 解题思路

2.2.1 声明单向链表构造函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

/**
* 声明构造函数 listNode
* 节点特征：
*    val 保存节点的值
*    next 保存下一个节点的引用地址
*/

function ListNode(val, next) {
  this.val = (val===undefined ? 0 : val)
  this.next = (next===undefined ? null : next)
}

3 无重复字符的最长子串

3.1 题目介绍

  • 给定一个字符串s，请找出其中不含有重复字符的最长子串的长度
  • 示例
1
2
3

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

3.2 解题思路

  • 输入字符串：abcdbe，在遍历字符串时，我们使用数组subStr存储不重复的子串。
  • 假定我们有两个指针：左指针和右指针，在初始时都指向了字符串的第一个字符； 开始遍历时，右指针开始挪动，将不重复的字符依次放入到数组中。
  • 如果遇到某个字符已经在数组subStr中，则说明当前不重复子串已经是最长了，需要开启新的不重复子串了。
  • 新的不重复子串从哪里开始记录呢？！
  • 重点： 从该重复字符在不重复子串中的下一个位置开始记录。
  • 在该case中，第一次记录的不重复子串为 abcd。下一个字符b开始重复，新的一个不重复子串开始位置为c，即字符b第一次出现的位置的下一个字符。
  • 此刻的处理方式是移动左指针位置，即将数组subStr中的元素从开头开始进行删除，直到移除重复字符b。
  • 将当前的字符b存储到subStr中。
  • 比对当前不重复子串的长度与历史记录的最大长度，取最大值。
  • 重复上述的过程，直到字符串遍历结束。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function lengthOfLongestSubstring(s) {
      const subStr = [];
      let maxLen = 0;
      for (let i = 0; i < s.length; i++) {
        // 从队首一个一个删，直到删到没有重复字符（while的条件返回false）为止，即左指针移动至重复字符的下一个
        while (subStr.includes(s[i])) {
          subStr.shift();
        }
        subStr.push(s[i]);
        maxLen = Math.max(subStr.length, maxLen);
      }
      return maxLen;
    }
    const result = lengthOfLongestSubstring("abcdbe");

4 回文数

4.1 题目介绍

  • 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

  • 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

  • 例如，121 是回文，而 123 不是。

  • 示例：

1
2
3
4
5

输入：x = 121
输出：true
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

4.2 解题思路

  • 判断回文字符串的逻辑
    1. 基于首位的索引进行判断
    2. 该字符串是否只有一个字符（肯定是true）
    3. 该字符串是否是首位一致（否则肯定是false）
    4. 最后判断s[i]和s[j]中间是否只有一个字符（如果是返回true，否则进入下一次递归）
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function (x) {
  	// 小于零因为有负号，所以肯定不是
    if (x < 0) return false
  	// 转换为字符串
    const str = x.toString()
    // 判断是否回文字符串的逻辑
    const isPalindromeStr = (i, j) => {
        if (i === j) return true
        if (str[i] !== str[j]) return false
        if (i + 1 === j) return true;
        return isPalindromeStr(i + 1, j - 1)
    }
    return isPalindromeStr(0, str.length ? str.length - 1 : 0)
};

5 扁平数据（互相）转tree

5.1 扁平数据转tree

5.2 tree转扁平数据