力扣题库练习

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

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)

Jetbrains全家桶1年46，售后保障稳定

哈希表：

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);
  }
}

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));

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));

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);
});

其他正确写法

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));

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,
        },
    },
};

// 解法一：递归
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);

// 解法二：迭代
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;
};

// 解法三：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);