分治算法思想:
递推算法思想:
枚举算法思想:
递归算法思想:
求阶乘:
贪婪算法思想:
试探算法思想:
1. 两数之和
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
const twoSum = (nums, target) => {
const prevNums = {}; // 存储出现过的数字,和对应的索引
for (let i = 0; i < nums.length; i++) { // 遍历元素
const curNum = nums[i]; // 当前元素
const targetNum = target - curNum; // 满足要求的目标元素
const targetNumIndex = prevNums[targetNum]; // 在prevNums中获取目标元素的索引
if (targetNumIndex !== undefined) { // 如果存在,直接返回 [目标元素的索引,当前索引]
return [targetNumIndex, i];
} else { // 如果不存在,说明之前没出现过目标元素
prevNums[curNum] = i; // 存入当前的元素和对应的索引
}
}
}
2.数字反转
给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。
var reverse = function(x) {
// x ->num
var str = x.toString() //str->String
let arr = str.split(''); //arr->Array
// 判断是否有负号
if(arr[0]!=="-"){
let num =Number(arr.reverse().join(''));
if(num <= 2147483647 && num >= -2147483648){
return num;
}else{
return 0
}
}else {
delete arr[0];
let num =Number(arr.reverse().join(''));
if(num <= 2147483647 && num >= -2147483648){
return ~num+1;
}else{
return 0
}
}
};
3.回文数
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
/**
* @param {number} x
* @return {boolean}
*/
var isPalindrome = function(x) {
var str = x.toString()
var arr = str.split('')
if(x>0 && arr[arr.length-1]!=0){
let num =Number(arr.reverse().join(''));
if (x == num){
return true
}else {
return false
}
} else if(x == 0){
return true
}else {
return false
}
};
简化版:
var isPalindrome = function(x) {
return x === Number(x.toString().split('').reverse().join(''))
};
双指针的方法:
var isPalindrome = function(x) {
if(x < 0) return false;
if(x < 10) return true;
let right = 1;
let left = 0;//初始为 x的总位数
let sum = x;
while(sum >= 1){//算出总位数
sum /= 10;
left++;
}
//获取第n位的数
let getNum = (_x, n) => {
return Math.floor(_x % Math.pow(10, n) / Math.pow(10, n - 1));
}
while(left > right){
if(getNum(