力扣题库练习_let getnext = function (n) { return n.tostring().s

1 两数之和

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

本人简单暴力解答：

var twoSum = function(nums, target) {
  let a=0,b=0;
  outer:
  for(let i=0;i<nums.length;i++){
    inner:
      for(let j=0;j<nums.length;j++){
          if(i!=j){
              if(nums[i]+nums[j] === target){
                  a=i;b=j;
                  break outer;
              }
          }
      }
  };
  return [a,b];
};
twoSum([11,15,7,8,2],9)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

哈希表：

var twoSum = function(nums, target) {
  let len = nums.length;
  const MAP = new Map();
  MAP.set(nums[0], 0);
  for(let i=1;i<len;i++){
    let other = target - nums[i];
    if(MAP.get(other) !== undefined){
      return [MAP.get(other), i];
    }
    MAP.set(nums[i], i);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12

2 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123
输出：321
示例 2：
输入：x = -123
输出：-321
示例 3：
输入：x = 120
输出：21
示例 4：
输入：x = 0
输出：0

var reverse = function(x) {
  let strToArr=x.toString().split('');
  strToArr = strToArr.reverse();
  return strToArr.join('');
};
console.log(reverse(123));
1
2
3
4
5
6

3

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x
示例 1：
输入：n = 27
输出：true
示例 2：
输入：n = 0
输出：false
示例 3：
输入：n = 9
输出：true
示例 4：
输入：n = 45
输出：false

let isPowerOfThree = n => {
  if(n === 1) return true;
  if(Number.isInteger(n / 3) && n !== 0){
    return isPowerOfThree(n / 3);
  }
  return false;
}

console.log(isPowerOfThree(81));
1
2
3
4
5
6
7
8
9

4 快乐数

编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。
示例 1：
输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入：n = 2
输出：false
我的写法，递归法，行不通，会报错超出最大调用栈

let isHappy = (n,cb) => {
  n = n.toString();
  let arr=n.split('');
  let newNum=0;
  for(let i=0;i<arr.length;i++){
    newNum += Math.pow(Number(arr[i]),2);
  }
  if(newNum>1 && newNum < Math.pow(2,31)-1){
    isHappy(newNum,cb);
  }else{
    if(newNum == 1){
      cb(true);
    }else{
      cb(false);
    };
    return ;
  }
}
isHappy(19,(rel) => {
  console.log(rel);
});
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

其他正确写法

let getNext = n => {
  return n.toString().split('').map(i => i ** 2).reduce((a, b) => a + b);
}

let isHappy = n => {
  let slow = n; // 2
  let fast = getNext(n); // 4
  while(fast !== 1 && fast !== slow){
    slow = getNext(slow);         // 4  16 37 58 89 145 42 20 4
    fast = getNext(getNext(fast)) // 37 89 42 4  37 89  42 4  37
  }
  return fast === 1;
}

console.log(isHappy(7));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5 二叉树的中序遍历

关于二叉树的遍历，主要有三种：
1、先【根】序遍历【根左右】
2、中【根】序遍历【左根右】
3、后【根】序遍历【左右根】

先【根】序遍历【根左右】：A B D H E I C F J K G
中【根】序遍历【左根右】 : D H B E I A J F K C G
后【根】序遍历【左右根】 : H D I E B J K F G C A

☆ 中序遍历

const treeData = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
            left: null,
            right: null,
        },
        right: {
            val: 5,
            left: null,
            right: null,
        },
    },
    right: {
        val: 3,
        left: {
            val: 6,
            left: null,
            right: null,
        },
        right: {
            val: 7,
            left: null,
            right: null,
        },
    },
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

// 解法一：递归
function inorderTraversal(root){
  let treeRes = [];
  const inorder = (root) => {
    if(!root) {
      return;
    }
    inorder(root.left);
    treeRes.push(root.val);
    inorder(root.right);
  }
  inorder(root);
  return treeRes;
}
let finalResult = inorderTraversal(treeData);
console.log(finalResult);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// 解法二：迭代
var inorderTraversal = function(root) {
  const res = [];
  const stk = [];
  while (root || stk.length) {
      while (root) {
          stk.push(root);
          root = root.left;
      }
      root = stk.pop();
      res.push(root.val);
      root = root.right;
  }
  return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 解法三：Morris 中序遍历
var inorderTraversal = (root) => {
  const res = [];
  let transfer = null;
  while(root){
    if(root.left){
      transfer = root.left;
      while(transfer.right && transfer.right !== root){
        transfer = transfer.right;
      }
      if(!transfer.right){
        transfer.right = root;
        root=root.left;
      }else{
        res.push(root.val);
        transfer.right = null;
        root = root.right;
      }
    }else{
      res.push(root.val);
      root = root.right;
    }
  }
  return res;
}

let finalResult = inorderTraversal(treeData);
console.log(finalResult);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

解法三太绕了，实在变态变态。