无重复字符的最长子串
var lengthOfLongestSubstring = function(s) {
let dic = '';
let left = 0;
let right = 0;
let res = 0
while(s.length-left >= res) {
if(!dic.includes(s.charAt(right))) {
dic += s.charAt(right);
res = Math.max(res, dic.length);
} else {
let step = dic.indexOf(s.charAt(right)) + 1;
left +=step
dic = dic.substr(step)
dic += s.charAt(right);
}
right++;
}
return res
};
比较版本号
var compareVersion = function(version1, version2) {
const versions1 = version1.split('.');
const versions2 = version2.split('.');
for(let i =0; i<Math.max(versions1.length,version2.length); i++) {
const v1 = versions1[i];
const v2 = versions2[i];
if(Number(v1) > Number(v2)) return 1;
if(Number(v1) < Number(v2)) return -1;
if(Number(v1) && !Number(v2)) return 1;
if(!Number(v1) && Number(v2)) return -1;
if(i === Math.max(versions1.length,version2.length) - 1) return 0
}
};
合并两个有序数组
const merge = function(nums1, m, nums2, n) {
nums1.splice(m, n, ...nums2);
nums1.sort((a,b) => a-b);
return nums1
};
或者双指针
var merge = function(nums1, m, nums2, n) {
let p1 = m - 1, p2 = n - 1;
let tail = m + n - 1;
var cur;
while (p1 >= 0 || p2 >= 0) {
if (p1 === -1) {
cur = nums2[p2--];
} else if (p2 === -1) {
cur = nums1[p1--];
} else if (nums1[p1] > nums2[p2]) {
cur = nums1[p1--];
} else {
cur = nums2[p2--];
}
nums1[tail--] = cur;
}
};
求根节点到叶节点数字之和
深度优先
var sumNumbers = function(root) {
const defSum = function(node, sum) {
sum = 10 * sum + node.val;
if(node.right && !node.left) {
return defSum(node.right, sum)
}
if(node.left && !node.right) {
return defSum(node.left, sum)
}
if(node.left && node.right) {
return defSum(node.left, sum) + defSum(node.right, sum)
}
return sum
}
return defSum(root, 0)
};
广度优先
var sumNumbers = function(root) {
let sum = 0
const nodeArr = [];
const numArr = []
nodeArr.push(root)
numArr.push(root.val)
while(nodeArr.length) {
const node = nodeArr.shift();
const num = numArr.shift()
if(!node.left && !node.right) {
sum += num
}
if(node.left) {
nodeArr.push(node.left);
numArr.push(num * 10 + node.left.val)
}
if(node.right) {
nodeArr.push(node.right);
numArr.push(num * 10 + node.right.val)
}
}
return sum
};
路径总和
var hasPathSum = function(root, targetSum) {
let flag = false
function def(node, sum) {
if(flag || !node) return
if(!node.left && !node.right && (sum + node.val) === targetSum) flag = true
if(node.left) def(node.left, sum+node.val)
if(node.right) def(node.right, sum+node.val)
}
def(root, 0)
return flag
};
最大子数组和
var maxSubArray = function(nums) {
let pre = 0, maxAns = nums[0];
nums.forEach((x) => {
pre = Math.max(pre + x, x);
maxAns = Math.max(maxAns, pre);
console.log(x, pre, maxAns)
});
return maxAns;
};
爬楼梯
一次爬1个或者两个台阶，问爬n个台阶有多少种组合
var climbStairs = function(n) {
let p = 0, q = 0, r = 1;
for (let i = 1; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
};
反转链表
var reverseList = function(head) {
if(!head) return head
const result = new ListNode()
let temp = result
function def(node, depth) {
if(node.next) {
def(node.next, depth+1)
}
temp.val = node.val;
if(depth === 0) return
temp.next = new ListNode()
temp = temp.next
}
def(head, 0)
return result
};
字符串相加
var addStrings = function (num1, num2) {
if (!num1 && !num2) return '';
if (!num1) return num2;
if (!num2) return num1;
const len = Math.max(num1.length, num2.length)
let sum = []
let addition = 0
for (let i = len - 1; i > -1; i--) {
let num = 0
if (num1.length > num2.length) {
num = (addition + 1 * (num1[i] || 0) + 1 * (num2[i - num1.length + num2.length] || 0))
} else {
num = (addition + 1 * (num1[i + num1.length - num2.length] || 0) + 1 * (num2[i] || 0))
}
if (num >= 10) {
addition = 1;
num = num - 10;
} else {
addition = 0
}
sum.unshift(num)
}
if (addition) {
sum.unshift(1)
}
return sum.join('')
};
全排列
var permute = function(nums) {
if(nums.length === 0 || nums.length === 1) return [nums];
const res = []
const used = []
let path = []
function back() {
if(path.length === nums.length) {
res.push([...path]);
return
}
for(let i =0; i< nums.length ; i++) {
if(used[i]) continue;
path.push(nums[i]);
used[i] = true
back();
path.pop()
used[i] = false;
}
}
back();
return res
};
打家劫舍
var rob = function(nums) {
let result = 0;
if(nums.length === 0 )return 0
if(nums.length === 1) return nums[0]
if(nums.length === 2) return Math.max(nums[0], nums[1])
const dp = new Array(nums.length).fill(0);
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1])
for(let i = 2; i<nums.length; i++) {
dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2])
}
return dp[nums.length - 1]
};
二分查找
var search = function(nums, target) {
if(!nums) return -1
if(nums.length === 1) {
if(nums[0] === target) return 0
return -1
}
function _search(n, k) {
const center = Math.floor((k+n)/2)
if(n>k) return -1
if(nums[center] === target) return center;
if(nums[center] > target) return _search(n, center-1)
return _search(center+1, k)
}
return _search(0, nums.length - 1)
};
快速排序
function partion(arr, start, end) {
let pivotIndex = start;
const pivotValue = arr[end];
for(let i = start; i<end; i++) {
if(arr[i] < pivotValue) {
[arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]]
pivotIndex++
}
}
[arr[pivotIndex], arr[end]] = [arr[end], arr[pivotIndex]]
return pivotIndex
}
function quickSort(arr, start, end) {
if(start >= end) return;
const partionIndex = partion(arr, start ,end);
quickSort(arr, start, partionIndex - 1)
quickSort(arr, partionIndex + 1, end)
}
function sortArray(nums) {
quickSort(nums, 0, nums.length - 1);
return nums
}
平衡二叉树
function depth(node) {
if(!node) return 0
return Math.max(depth(node.left), depth(node.right)) + 1
}
var isBalanced = function(node) {
if(!node) return true
const result = Math.abs(depth(node.left) - depth(node.right)) <= 1
if(result) {
return isBalanced(node.left) && isBalanced(node.right)
}
else return false
};
