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)
哈希表：
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);
解法三太绕了，实在变态变态。