判断是否为回文整数
- 或者只判断后半部分反转是否等于前半部分
var isPalindrome = function(x) {
if(x<0||(x%10==0&&x!=0)){
return false;
}
var changeNum=x;
var num=0;
while(changeNum!=0){
num=num*10+changeNum%10;
changeNum=parseInt(changeNum/10);
}
return num==x;
};
console.log(isPalindrome("120"))
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
var isValid = function(s) {
var stack=[];
s=s.toString().split("");
for(var item of s){
if(item=="("||item=="["||item=="{"){
stack.unshift(item);
}else{
if(stack.length!==0){
var now=stack.shift();
if((now=="("&&item!==")")||(now=="["&&item!=="]")||(now=="{"&&item!=="}")){
return false;
}
}else{
return false;
}
}
}
if(stack.length==0){
return true;
}else{
return false;
}
};
//执行用时 : 92 ms, 在Valid Parentheses的JavaScript提交中击败了84.95% 的用户
//内存消耗 : 34.4 MB, 在Valid Parentheses的JavaScript提交中击败了52.21% 的用户
var isValid = function (s) {
let stack = []
let paren_map = { ')': '(', ']': '[', '}': '{' }
for (const c of s) {
if (!(c in paren_map)) stack.push(c)
else if (!stack.length || paren_map[c] != stack.pop()) return false
}
return !stack.length
};
//执行用时 : 88 ms, 在Valid Parentheses的JavaScript提交中击败了96.12% 的用户
//内存消耗 : 34.2 MB, 在Valid Parentheses的JavaScript提交中击败了54.18% 的用户
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
var longestCommonPrefix = function(strs) {
let minLen=Math.min(...strs.map(x=>x.length));
let res="";
for(let i=0;i<minLen;i++){
let newset=new Set(strs.map(x=>x[i]));
if(newset.size==1){
res+=[...newset][0];//把他变成数组
}else{
break;
}
}
return res;
};
//执行用时 : 132 ms, 在Longest Common Prefix的JavaScript提交中击败了27.53% 的用户
//内存消耗 : 33.9 MB, 在Longest Common Prefix的JavaScript提交中击败了82.51% 的用户
var longestCommonPrefix = function(strs) {
let minLen=Math.min(...strs.map(x=>x.length));
if(!strs||strs.length==0)return "";
let res="";
for(let i=0;i<minLen;i++){
var now=strs[0][i];
console.log(now);
if(strs.every(val=>val[i]==now)){
res+=now;
}else{
break;
}
}
return res;
};
//执行用时 : 104 ms, 在Longest Common Prefix的JavaScript提交中击败了63.87% 的用户
//内存消耗 : 35.2 MB, 在Longest Common Prefix的JavaScript提交中击败了30.03% 的用户
荷兰国旗
let arr = [0,1,2,1,1,2,0,2,1,0];
function paixu(arr){
let current = 0;
let begin = 0;
let end = arr.length-1;
while(current <= end ){
if(arr[current] == '0'){
[arr[current],arr[begin]]= [arr[begin],arr[current]];
current++;
begin++;
}else if(arr[current] == '1'){
current++;
}else if(arr[current] == '2'){
[arr[current],arr[end]] = [arr[end],arr[current]]
end -- ;
}
}
console.log(arr);
}
paixu(arr);
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
该问题是非常典型的、入门的动态规划问题。很多算法书上的都采用类似的例子来开始介绍动态规划。
设计动态规划的三个步骤
将问题分解成最优子问题；
用递归的方式将问题表述成最优子问题的解；
自底向上的将递归转化成迭代；（递归是自顶向下）;
最优子问题
对于连续的 nn 栋房子：H1,H2,H3......HnH 1 ,H 2 ,H 3 ......H n ，小偷挑选要偷的房子，且不能偷相邻的两栋房子，方案无非两种：
方案一：挑选的房子中包含最后一栋；
方案二：挑选的房子中不包含最后一栋；
获得的最大收益的最终方案，一定在这两种方案中产生，用代码表述就是：
最优结果 = Math.max(方案一最优结果，方案二最优结果)
子问题的递归表述
JavaScript
var robTo = function (nums, lastIndex) {
if (lastIndex === 0) {
return nums[0];
}
// 方案一，包含最后一栋房子，则应该丢弃倒数第二栋房子
let sum1 = robTo(nums, lastIndex - 2) + nums[lastIndex];
// 方案二，不包含最后一栋房子，那么方案二的结果就是到偷到 lastIndex-1 为止的最优结果
let sum2 = robTo(nums, lastIndex - 1);
return Math.max(sum1, sum2);
};
将问题表述成最优子问题的解后，这个问题就解决了：
JavaScript
var rob = function(nums) {
return robTo(nums, nums.length - 1);
};
递归转迭代
到上一步为止，该问题就已经解决了。但是递归的方式性能太差，中间有太多重复的计算，所以还需要最后一步：将 自顶向下 的递归，转化成 自底向上 的迭代。
JavaScript
var rob = function(nums) {
if (nums.length === 0) {
return 0;
}
if (nums.length === 1) {
return nums[0];
}
// 仍然用两个变量来存储方案一和方案二的最优结果
// 不同的是，这次从0开始，lastIndex 取最小值 1
let sum1 = nums[0];
let sum2 = nums[1];
// 然后通过迭代不断增大 lastIndex，过程中维护新的sum1，sum2，直到数组末尾
for (let lastIndex=2; lastIndex<nums.length; lastIndex++) {
let tmp = sum1;
// 此时的方案一就是上一步中的方案二，
// 但要求的是最优解，所以要判断前一步的 sum1 和 sum2 哪个更大
if (sum2 > sum1) {
sum1 = sum2;
}
// sum2 是包含最后一栋房子的方案，
// 每向后增加一栋房子，就是前一步的 sum1（不包含 lastIndex - 1 ）
// 加上当前 lastIndex 栋房子的金钱
sum2 = tmp + nums[lastIndex];
}
return sum1 > sum2 ? sum1 : sum2;
};
报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
111211211111221
1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
注意：整数顺序将表示为一个字符串。
var countAndSay = function(n) {
return createStr(1, ['1'], n)
function createStr(index, str, n) {
if(index == n)
return str.join('')
index++
let newChar = []
let k = 1
for(let j = 0; j < str.length; j++) {
let char = str[j]
if(char == str[j+1] && j != str.length - 1) {
k++
}else {
newChar.push(k)
newChar.push(str[j])
k=1
}
}
return createStr(index, newChar, n)
}
};
寻找和为定值的两个数
- 输入一个整数数组和一个整数，在数组中查找一对数，满足它们的和正好是输入那个整数。如果有多对数的和等于输入的整数，输出任意一对即可。
//在数组有序的前提下采用排序夹逼的方法
function findNums(numArr,sum){
// sort(numArr);
let begin = 0;
let end = numArr.length-1;
//需要一个满足循环条件，勿忘
while(begin<end){
curSum = numArr[begin] + numArr[end];
if(curSum === sum){
console.log(numArr[begin], numArr[end]);
//不要忘记break
//break;
//如果想输出所有对，加上这两句
begin++;
end--;
}else if(curSum < sum){
begin++;
}else{
end--;
}
}
}
findNums([1,2,3,4,5,6],9)
最大连续子数组和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let maxsums = nums[0];
let cursums = 0;
for(let i=0;i<nums.length;i++){
if(cursums>=0){
cursums += nums[i];
}else if(cursums<0){
cursums = nums[i];
}
if(cursums>maxsums){
maxsums = cursums;
}
}
return maxsums;
};
按奇偶排序数组
给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素
/**
* @param {number[]} A
* @return {number[]}
*/
function isodd(num){
if(num%2 === 0){
return false;
}else{
return true;
}
}
var sortArrayByParity = function(nums) {
let head = 0;
let end = nums.length-1;
while(head<end){
if(!isodd(nums[head])){
head++;
} else if(isodd(nums[end])){
end--;
}else{
temp = nums[head];
nums[head] = nums[end];
nums[end] = temp;
}
}
return nums;
};
