chunhuigao / leetcode Goto Github PK
View Code? Open in Web Editor NEW学习算法，提升自己
leetcode's People
Contributors
Watchers
leetcode's Issues
16. 最接近的三数之和
暴力破解
var threeSumClosest = function(nums, target) {
const len = nums.length;
let total = nums[0]+nums[1]+nums[2];
for(let i = 0 ; i < len-2;i++){
for(let j = i+1;j<len-1;j++){
for(let k = j+1;k<len ;k++){
const sum = nums[i] + nums[j] + nums[k];
if(Math.abs(target-total) > Math.abs(target-sum)){
total = sum;
}
}
}
}
return total
};时间复杂度o(n^3)
优化后
var threeSumClosest = function (nums, target) {
//排序
nums.sort((a, b) => a - b);
//找最小值
let min = nums[0] + nums[1] + nums[2];
//遍历nums
for (let i = 0, len = nums.length; i < len - 2; i++) {
//设置左区间
let j = i + 1;
//设置右区间
let k = len - 1
//遍历区间
while (j < k) {
//找到任意数值
let n = nums[i] + nums[j] + nums[k]
//比较
if (Math.abs(n - target) < Math.abs(min - target)) {
min = n
}
if (n > target) {
k--
} else if (n < target) {
j++
} else {
return target
}
}
}
//输出结果
return min;
};最大子序和
来自每日一题
代码：
var maxSubArray = function (nums) {
const len = nums.length
let max = nums[0]
let result = nums[0]
for (let i = 1; i < len; i++) {
max = Math.max(nums[i], max + nums[i])
result = Math.max(result, max)
}
return result
}实现 pow(x, n) ，即计算 x 的 n 次幂函数
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function(x, n) {
if(n === 0) return 1
if(n < 0){
x = 1/x;
n = -n
}
let result = 1;
while(n>=1){
if(n %2 === 1){
result *=x;
}
x*=x;
n = Math.floor(n / 2);
}
return result
};来自每日一题
解题思路
从三角形底层向上层寻找最小路径；
第一步：现将底层与倒数第二层逐一对比，找出底层到倒数第二层的最小值，并更新
代码
/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
let len = triangle.length;
if (len < 2) return triangle[0][0];
for (let i = len - 2; i >= 0; i--) {
let currArr = triangle[i];
let nextArr = triangle[i + 1];
for (let j = 0; j < currArr.length; j++) {
let min = Math.min(currArr[j] + nextArr[j], currArr[j] + nextArr[j + 1]);
currArr[j] = min;
}
}
return triangle[0][0];
};19. 删除链表的倒数第N个节点
解题思路
快慢指针找到第N个节点，然后删除
代码
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function (head, n) {
if(!head || !head.next) return null;
let header = new ListNode(-1)
header.next = head
let frist = header
let second = header
for (let i = 0; i < n ; i++) {
frist = frist.next
}
while (frist.next != null) {
frist = frist.next
second = second.next
}
second.next = second.next.next
return header.next
};13. 罗马数字转整数
迭代法
找到罗马数子与十进制正数对应关系，将罗马数字依字符串的形式遍历
已知：
- 罗马数字由 I,V,X,L,C,D,M 构成；
- 当小值在大值的左边，则减小值，如 IV=5-1=4；
- 当小值在大值的右边，则加小值，如 VI=5+1=6；
按照已知条件书写一下代码：
var romanToInt = function(s) {
const len = s.length;
const map = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
let result = 0;
for(let i = 0 ; i < len ; i++){
if(i < len-1 && map[s[i]]<map[s[i+1]]){
result-=map[s[i]]
}else{
result+=map[s[i]]
}
}
return result
};215. 数组中的第K个最大元素
来自每日一题
方法1
首先想到排序，让数组降序排列，查找索引第k-i位置的值即为所求：
代码如下
var findKthLargest = function (nums, k) {
nums.sort((a,b)=>b-a)
return nums[k - 1];
};方法2
方法1中调用API将数组所有的值降序排列，但是实际上我们只需要将0~k最大的数排列就行了。通过这个思路，可以使用冒泡法将前K大的数值【冒泡】出来；
具体代码如下
var findKthLargest = function (nums, k) {
const len = nums.length;
for (let i = 0; i < k; i++) {
for (let j = len - 1; j > i; j--) {
if (nums[j] > nums[j - 1]) {
const t = nums[j];
nums[j] = nums[j - 1];
nums[j - 1] = t;
}
}
}
return nums[k - 1];
};1.两数之和
##暴力解题
循环所有两个元素相加出现的可能，找到目标值
var twoSum = function (nums, target) {
const len = nums.length;
for (let i = 0; i < len; i++) {
for (let j = i + 1; j < len; j++) {
if (target === nums[i] + nums[j]) {
return [i, j];
}
}
}
return [];
};时间复杂度：O(n^2)
##哈希表记录需要的元素
var twoSum = function (nums, target) {
const len = nums.length;
let map = new Map();
for (let i = 0; i < len; i++) {
const diff = target - nums[i];
if (map.has(diff)) {
return [map.get(diff), i];
} else {
map.set(nums[i], i);
}
}
return [];
};315. 计算右侧小于当前元素的个数
解题思路
利用搜索二叉树特性，记录每一个值右侧小于当前值的数量，并统计
代码
var countSmaller = function (nums) {
//声明一个二叉树构建函数
function TreeNode(val) {
this.val = val; //二叉树当前值
this.left = null;
this.right = null;
this.num = 0; //右侧比当前值小的个数
}
const len = nums.length;
let root = null;
let result = Array(len).fill(0);
//遍历数组
for (let i = len - 1; i >= 0; i--) {
//将数组值放入搜索二叉树
root = helper(root, nums[i], i);
}
return result;
//搜索二叉树
function helper(node, val, idx) {
//如果树为叶子节点，将值放入树的val
if (node === null) {
node = new TreeNode(val);
} else if (val <= node.val) {
//如果数组值小于当前二叉树值，将二叉树num+1；
node.num += 1;
//递归
node.left = helper(node.left, val, idx);
} else {
result[idx] += node.num + 1;
node.right = helper(node.right, val, idx);
}
return node;
}
};350. 两个数组的交集 II
来自每日一题
解题思路
使用对象将nums1数组元素保存起来；在遍历nums2；如果当前元素在map中，将当前元素放入result数组；并将map当前元素数量-1
代码
var intersect = function(nums1, nums2) {
let map = {};
nums1.forEach(e=>{
if(map[e] === undefined){
map[e] = 1
}else{
map[e]+=1
}
})
let result = []
nums2.forEach(e=>{
if(map[e]){
result.push(e)
map[e]-=1
}
})
return result
};面试题 17.13. 恢复空格
解题思路
动态规划
代码
var respace = function(dictionary, sentence) {
const len = dictionary.length;
let map = new Map();
for(let i = 0 ; i < len ; i++){
map.set(dictionary[i],dictionary[i])
}
const m = sentence.length;
let array = Array(m+1).fill(0)
for(let i = 1 ; i <= m ; i++){
array[i] = array[i-1]+1;
for(let j = 0 ; j < i ; j++){
const s = sentence.substring(j,i)
if(map.has(s)){
array[i] = Math.min(array[i],array[j])
}
}
}
return array[m]
};12. 整数转罗马数字
思路
暴力破解
枚举十进制与罗马数字进制的所有关系；while遍历即可
/**
* @param {number} num
* @return {string}
*/
var intToRoman = function (num) {
let resulte = '';
while (num >= 1) {
if (num >= 1000) {
resulte += 'M';
num = num - 1000;
} else if (num < 1000 && num >= 900) {
resulte += 'CM';
num = num - 900;
} else if (num < 900 && num >= 500) {
resulte += 'D';
num = num - 500;
} else if (num < 500 && num >= 400) {
resulte += 'CD';
num = num - 400;
} else if (num < 400 && num >= 100) {
resulte += 'C';
num = num - 100;
} else if (num < 100 && num >= 90) {
resulte += 'XC';
num = num - 90;
} else if (num < 90 && num >= 50) {
resulte += 'L';
num = num - 50;
} else if (num < 50 && num >= 40) {
resulte += 'XL';
num = num - 40;
} else if (num < 40 && num >= 10) {
resulte += 'X';
num = num - 10;
} else if (num < 10 && num >= 9) {
resulte += 'IX';
num = num - 9;
} else if (num < 9 && num >= 5) {
resulte += 'V';
num = num - 5;
} else if (num < 5 && num >= 4) {
resulte += 'IV';
num = num - 4;
} else if (num < 4 && num >= 1) {
resulte += 'I';
num = num - 1;
}
}
return resulte;
//console.log(resulte)
};虽然可以实现需求，但是代码可能有点不够优雅；优化一下
var intToRoman = function (num) {
const keys = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
const values = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I'];
let result = '';
let index = 0;
while (index < keys.length) {
while (num >= keys[index]) {
num -= keys[index];
result += values[index];
}
index++;
}
return result;
};面试题 16.11. 跳水板
来自每日一题
解题思路
跳水板只有两种可能长度，使用k块木板；遍历计算所有可能的结果
计算公式为：
1*shorter + （k-1）*longer
因为计算过程中可能会有重复值；所以使用map保存已有值；每次计算出新的长度值在map中询问是否存在，不存在的值放入数组中
对输出数组排序
代码
/**
* @param {number} shorter
* @param {number} longer
* @param {number} k
* @return {number[]}
*/
var divingBoard = function(shorter, longer, k) {
let array = [];
let map = new Map();
if (k === 0) return [];
for (let i = 0; i <= k; i++) {
const n1 = i * shorter;
const n2 = (k - i) * longer;
const n = n1 + n2;
if (map.get(n)) continue;
map.set(n, n);
array.push(n);
}
return array.sort((a, b) => a - b);
};18. 四数之和
解题思路
暴力破解
代码
var fourSum = function (nums, target) {
let length = nums.length;
if (length < 4) return []
//排序
nums.sort((a, b) => a - b);
//找最小值
let result = [];
//遍历nums
for (let i = 0; i < length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue
let nMaxi = nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3]
let nMini = nums[i] + nums[length - 1] + nums[length - 2] + nums[length - 3]
if (nMaxi > target) break
if (nMini < target) continue
for (let j = i + 1; j < length - 2; j++) {
if (j - i > 1 && nums[j] == nums[j - 1]) continue
let nMaxj = nums[i] + nums[j] + nums[j + 1] + nums[j + 2]
let nMinj = nums[i] + nums[j] + nums[length - 1] + nums[length - 2]
if (nMaxj > target) break
if (nMinj < target) continue
let left = j + 1;
let right = length - 1
while (left < right) {
let number = nums[i] + nums[j] + nums[left] + nums[right]
if (number == target) {
result.push([nums[i], nums[j], nums[left], nums[right]])
while (left < right && nums[left] == nums[left + 1]) left += 1;
while (left < right && nums[right] == nums[right - 1]) right -= 1;
left += 1;
right -= 1;
} else if (number > target) {
right -= 1
} else {
left += 1
}
}
}
}
//console.log(result)
//输出结果
return result;
};187. 重复的DNA序列
所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来查找目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
思路：
字符串长度固定，可以用map保存已经出现的字串，如果字串已经存在，表示有重复的序列
代码：
var findRepeatedDnaSequences = function (s) {
const len = s.length
if (len <= 10) return []
let map = new Map()
let result = []
for (let i = 0; i < len - 9; i++) {
const string = s.substring(i, i + 10)
if (map.has(string)) {
if (map.get(string) > 1) {
continue
} else {
result.push(string)
}
map.set(string, map.get(string) + 1)
} else {
map.set(string, 1)
}
}
return result
}14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
方法1
先找到数组中字符长度最小的字符串
遍历最小字符串；将字符串当前位置字符与数组中其他字符串相同位置对比，即可得到结果
代码如下；
var longestCommonPrefix = function (strs) {
const len = strs.length;
if (len === 0) return '';
let minStr = strs[0];
strs.forEach((v) => {
if (v.length < minStr.length) {
minStr = v;
}
});
const l = minStr.length;
let result = '';
for (let i = 0; i < l; i++) {
const s = minStr[i];
for (let j = 0; j < len; j++) {
if (s !== strs[j][i]) return result;
}
result += s;
}
return result;
};
63. 不同路径 II
来自每日一题
var uniquePathsWithObstacles = function(obstacleGrid) {
let m = obstacleGrid.length;
let n = obstacleGrid[0].length;
let result = Array(n).fill(0);
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i == 0 && j == 0) {
result[j] = 1;
}
if (obstacleGrid[i][j] == 1) {
result[j] = 0;
} else if (j > 0) {
result[j] += result[j - 1];
}
}
}
//console.log(result, result[n - 1]);
return result[n - 1];
};15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
方法1
var threeSum = function (nums) {
//对数据排序
nums.sort((a, b) => a - b);
let result = [];
const len = nums.length;
/**
* 思路：
* 如果三个整数a,b,c之和为0；那么在经过排序的数据中必有a<=0;所以num[i]>0中停止循环
* 如果答案中的元素不重复，相同元素应该跳过
* 声明左右指针left,right
* 左右指针进入循环
* 循环可以获取数组中当前值nums[i];数组左侧值nums[left] 数组右侧值nums[right]
* 如果左右指针值之和小于0-n;需要left向右移动一位；
* 如果左右指针之和大于0-n；需要right向左移动一位；
* 如果左右指针之和正好等于0-n;将结果存放在result数组中,此时找到一组解
* 避免答案中有重复数据，如果left<right;并且nums[left] === nums[left-1];left应到再向右移动，直到nums[left] !== nums[left-1]或者left>=right
* right同理
*
*/
for (let i = 0; i < len - 2; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = len - 1;
while (left < right) {
const l = nums[left];
const r = nums[right];
const n = nums[i];
const t = l + r;
if (t < 0 - n) {
left++;
} else if (t > 0 - n) {
right--;
} else {
result.push([l, r, n]);
left++;
right--;
while (left < right && nums[left] === nums[left - 1]) left++;
while (left < right && right !== len - 1 && nums[right] === nums[right + 1]) right--;
}
}
}
return result;
};7. 整数反转
方法1
现将数字转换为字符串，对字符串反转然后将反转后的字符串转换为数字；实现整数反转
var reverse = function(x) {
let num = x + ''
let sign = num.indexOf('-')
if(sign>=0){
num = num.substring(1)
}
num = num.split('').reverse().join('');
num = sign >= 0 ? -Number(num) : Number(num)
if(Math.pow(-2,31) > num || num > Math.pow(2,31)-1 ){
return 0
}
return num
};方法2
操作数字将整数反转
var reverse = function (x) {
const max = 2147483647
const min = -2147483648
let result = 0
while (x !== 0) {
const temp = x % 10
result = result * 10 + temp
x = ~~(x / 10)
}
return result > max || result < min ? 0 : result
}3. 无重复字符的最长子串
##代码附上
var lengthOfLongestSubstring = function (s) {
let len = s.length;
if (len < 2) return len;
let result = 0;
let start = 0;
for (let i = 0; i < len; i++) {
const index = s.substring(start, i).indexOf(s[i]);
if (index !== -1) {
start = start + index + 1;
}
result = Math.max(result, i - start + 1);
}
return result;
};6. Z 字形变换
总结规律，字符串需要从左到右逐行读取，那是不是表示我可以用变量保存给定行数；让变量从0->给定行数->0之间变换；
具体代码如下：
var convert = function(s, numRows){
if(numRows === 1) return s;
//定义一个数组，用来保存数据
let array = Array(numRows).fill('')
const len = s.length;
let index = 0;
let sign = -1;
for(let i = 0 ; i < len ; i++){
//将当前字符串保存在对应未知
array[index] +=s[i];
if(index === 0 || index === numRows-1){
sign = -sign
}
index +=sign
}
return array.join('')
}剑指 Offer 09. 用两个栈实现队列
来自每日一题
无脑写代码
var CQueue = function() {
this.list = []
};
/**
* @param {number} value
* @return {void}
*/
CQueue.prototype.appendTail = function(value) {
this.list.push(value)
};
/**
* @return {number}
*/
CQueue.prototype.deleteHead = function() {
const n = this.list.shift();
return n?n:-1
};5453. 所有蚂蚁掉下来前的最后一刻
来自第 196 场周赛
有一块木板，长度为 n 个 单位 。一些蚂蚁在木板上移动，每只蚂蚁都以 每秒一个单位 的速度移动。其中，一部分蚂蚁向 左 移动，其他蚂蚁向 右 移动。
当两只向 不同 方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。
而当蚂蚁在某一时刻 t 到达木板的一端时，它立即从木板上掉下来。
给你一个整数 n 和两个整数数组 left 以及 right 。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。无脑解题
题干度了半天，理解能力太差了，手动滑稽脸^_^
/**
* 对左侧蚂蚁排序
* 有右侧蚂蚁排序
* 获取左右两侧蚂蚁数量
* 如果向左侧运动的蚂蚁数量为0，向右测的蚂蚁的最左侧蚂蚁需要的时间就是结果
* 如有向右侧运动的蚂蚁数量为0；同理，可得结果
* 如果左右都有蚂蚁，判断向右与向左的蚂蚁是否有交集；
* 如果无交集，返回向左侧和向右侧蚂蚁掉下去花费的最长时间
* 如果有交集；显找到交集的中点
* 中点计算：向左运动的蚂蚁的最右侧蚂蚁所在位置与向右运动的蚂蚁的最左侧所在位置之和
* 向左运动的蚂蚁全部掉下去所用的时间是：到达中点的时间+中点到向右掉下去的时间t1
* 同理可得向右的蚂蚁掉下去所用的时间t2
* 返回t1,t2的较大值
*
*/
var getLastMoment = function (n, left, right) {
left.sort((a, b) => a - b)
right.sort((a, b) => a - b)
const l = left.length
const r = right.length
if (l === 0) {
return n - right[0]
} else if (r === 0) {
return left[l - 1]
} else {
if (left[l - 1] < right[0]) {
return Math.max(left[l - 1], n - right[0])
} else {
const len = left[l - 1] + right[0]
const mid = len / 2
const ltr = Math.ceil(left[l - 1] - mid)
const ltre = n - Math.ceil(mid)
const lrt = ltre + ltr
const rtl = Math.ceil(mid - right[0])
const rtle = Math.floor(mid)
const rlt = rtle + rtl
return Math.max(lrt, rlt)
}
}
}112. 路径总和
来自每日一题
递归法
var hasPathSum = function(root, sum) {
if(root === null) return false;
if(root.left === null && root.right === null){
return sum - root.val === 0
}
return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val)
};209. 长度最小的子数组
来自每日一题
常规解法
遍历数组，将遍历到的数据累加到total变量中；当total变量大于s时；从total中减去数组中下标start开始的数据；找到和大于s且子串长度最小
var minSubArrayLen = function (s, nums) {
let len = nums.length;
let total = 0;
let result = Infinity;
let start = 0;
for (let i = 0; i < len; i++) {
total += nums[i];
while (s <= total) {
const l = i - start + 1;
result = Math.min(result, l);
total -= nums[start++];
}
}
return result === Infinity ? 0 : result;
};35. 搜索插入位置
解题思路
此处撰写解题思路
代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
const len = nums.length;
for(let i = 0 ; i < len ; i++){
const n = nums[i]
if(n === target){
return i
}else if( n > target){
if(i === 0) return 0;
return i
}
}
return len
};32. 最长有效括号
来自每日一题
var longestValidParentheses = function(s) {
let l = s.length;
if (l < 2) return 0;
let result = [];
let len = 0;
let aIndex = [];
for (let i = 0; i < l; i++) {
if (s[i] == "(") {
result.push("(");
aIndex.push(i);
} else {
let index = result.length;
if (result[index - 1] == "(") {
result.pop();
aIndex.pop();
len += 2;
} else {
result.push(")");
aIndex.push(i);
}
}
}
aIndex.push(l);
aIndex.unshift(0);
let max = 0;
for (let i = 1, len = aIndex.length; i < len; i++) {
let n = aIndex[i] - aIndex[i - 1];
if (n != 0 && n % 2 == 0) {
max = Math.max(max, n);
} else if (n % 2 == 1) {
max = Math.max(max, n - 1);
}
}
return max;
};5452. 判断能否形成等差数列
来自第 196 场周赛
给你一个数字数组 arr 。
如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。
如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。排序，求差
现将数组排序，排序后数组前后元素值之差与数组最后一位和第一位之差长度的平均值相等；即可认定为等差数列
var canMakeArithmeticProgression = function (arr) {
arr.sort((a, b) => a - b)
const len = arr.length
const start = arr[0]
const end = arr[len - 1]
const diff = (end - start) / (len-1)
for (let i = 1; i < len; i++) {
if (arr[i] - arr[i - 1] !== diff) return false
}
return true
}108. 将有序数组转换为二叉搜索树
来自每日一题
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
方法：
思路：二分法+递归
每次取中间值，将中间值放在二叉树定点位置，数组左侧交给root.left;数组右侧交给root.right
var sortedArrayToBST = function(nums) {
if (!nums.length) return null;
const root = new TreeNode(null);
if(nums.length > 1) root.left = sortedArrayToBST(nums.splice(0, nums.length / 2));
root.val = nums[0];
root.right = sortedArrayToBST(nums.splice(1));
return root;
};113. 路径总和 II
根据112的路径总和很容易得到答案，思路在注释中
/**
* 声明result保存结果
* 声明helper函数帮助递归获取目标
* 递归入参root二叉树，sum总和，path目标数组
* 当root === null为递归出口
* 将root.val放入path中
* 判断当前节点是否为叶子节点
* 如果当前节点是叶子节点，判断根节点到叶子节点所有和是否为sum
* 如果根节点到叶子节点所有和为sum，将path放到result
* 如果当前节点不是叶子节点，递归root.left和root.right;
* 直到递归到叶子节点，如果不是目标path删除最后一个元素，回溯
*
*/
var pathSum = function (root, sum) {
let result = [];
helper(root, sum, []);
return result;
function helper(root, sum, path) {
if (!root) return 0;
path.push(root.val);
if (!root.left && !root.right) {
if (sum - root.val === 0) {
const a = [].concat(path);
result.push(a);
}
}
helper(root.left, sum - root.val, path);
helper(root.right, sum - root.val, path);
path.pop();
}
};54. 螺旋矩阵
var spiralOrder = function (matrix) {
let map = (arr, r = []) => {
let begin = []
for (let i = 0, l = arr.length; i < l; i++) {
if (i == 0) {
r = r.concat(arr[i])
} else if (i == l - 1) {
r = r.concat(arr[i].reverse())
} else {
r.push(arr[i].pop())
let ele = arr[i][0]
if (ele != undefined) {
begin.push(arr[i].shift())
}
}
}
arr.shift();
arr.pop()
r = r.concat(begin.reverse())
if (arr[0] && arr[0][0]) {
return map(arr, r)
} else {
return r
}
}
let result = map(matrix);
//console.log('arr', result)
return result
};392. 判断子序列
解题思路
此处撰写解题思路
代码
var isSubsequence = function (s, t) {
let sl = s.length;
let tl = t.length;
if (sl > tl) return false
if (sl == tl && s == t) return true
let k = 0
for (let i = 0; i < tl; i++) {
if (s[k] == t[i]) {
k++
}
}
//console.log(k, sl)
return k == sl
};718. 最长重复子数组
来自每日一题
方法1暴力求解：
var findLength = function (A, B) {
A = A.map((v) => `(${v})`);
B = B.map((v) => `(${v})`);
const s = A.join(',');
let result = 0;
const len = B.length;
for (let i = 0; i < len; i++) {
for (let j = i; j < len; j++) {
const a = B.slice(i, j + 1);
const str = a.join(',');
if (s.includes(str)) {
const t = str.split(',');
result = Math.max(result, t.length);
}
}
}
return result;
};然后超时了
方法2:动态规划；
动态规划最重要的是找到状态转移方程
将数组A与数组B元素一一对比并将对比结果放在一个二维数组中；
如果 A[i] == B[j]，那么计算当前 dp[i][j] (公共长度) = dp[i + 1][j + 1] + 1；
var findLength = function (A, B) {
const alen = A.length;
const blen = B.length;
let dp = [];
for (let i = 0; i <= alen; i++) {
dp[i] = Array(blen + 1).fill(0);
}
let result = 0;
for (let i = 1; i <= alen; i++) {
for (let j = 1; j <= blen; j++) {
if (A[i - 1] === B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
result = Math.max(result, dp[i][j]);
}
}
return result;
};67. 二进制求和
#每日一题
今天的算法是简单类型，无脑写下去就完事了；
var addBinary = function (a, b) {
//获取字符串长度
let al = a.length;
let bl = b.length;
//声明进位变量
let sign = 0;
let result = '';
while (al > 0 || bl > 0) {
let an = a[al - 1];
let bn = b[bl - 1];
if (al <= 0) {
an = 0;
}
if (bl <= 0) {
bn = 0;
}
let n = Number(an) + Number(bn) + sign;
// 二进制进位
if (n > 1) {
sign = 1;
n = n - 2;
} else {
sign = 0;
}
result = n + result;
al--;
bl--;
}
//循环结束后判断一下进位值是否为1
if (sign) {
result = '1' + result;
}
// 输出结果
return result;
};96. 不同的二叉搜索树
解题思路
此处撰写解题思路
代码
/**
* @param {number} n
* @return {number}
*/
var numTrees = function(n) {
let result = 1
for (let i = 0; i < n; ++i) {
result = result * 2 * (2 * i + 1) / (i + 2);
}
return result
};11. 盛最多水的容器
中等难度的题
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
思路
- 左右开工，使用双指针，分别指向数组的左右两端；
- 找到指针所指数据中的较小值；
- 找到两个指针的相对距离
- 根据2、3可以计算出当前可以盛多少水
- 比较两指针值，值较小的指针移动到下一位
var maxArea = function (height) {
const len = height.length;
let left = 0;
let right = len - 1;
let result = 0;
while (left < right) {
const w = right - left;
const h = Math.min(height[left], height[right]);
result = Math.max(result, w * h);
if (height[left] > height[right]) {
right--;
} else {
left++;
}
}
return result;
};5. 最长回文子串
中心扩散法
大概思路是这样的，因为需要找出最长回文子串；回文字符串的特性是字符串反转==原字符串
根据这个特性，遍历字符串，选定当前i字符串为中心，向i的左侧和右侧寻找字符，如果左侧和右侧字符相同，在向左侧右侧寻找字符串；直到找到左右字符串不相同，记录当前回文字符串长度；
时间复杂度(n^2)
var longestPalindrome = function(s) {
const len = s.length;
if(len < 2) return s
let result = ''
for(let i = 0 ; i < len ; i++){
helper(i,i)
helper(i,i+1)
}
return result
function helper(left,right){
while(left >=0 && right <len && s[left] === s[right]){
const l = right-left+1;
if(l > result.length){
result = s.substring(left,right+1)
}
left--;
right++
}
}
};378. 有序矩阵中第K小的元素
来自每日一题
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
方法一
思路：将数组拍平，排序，找到第K小的数值;代码如下：
var kthSmallest = function(matrix, k) {
const len = matrix.length;
let array = []
for(let i = 0 ; i < len ; i++){
for(let j = 0. ;j < len ; j++){
array.push(matrix[i][j])
}
}
array.sort((a,b)=>a-b)
return array[k-1]
};方法2
var kthSmallest = function (matrix, k) {
const len = matrix.length;
let array = [];
for (let i = 0; i < len; i++) {
array = array.concat(matrix[i]);
const l = array.length;
if (l >= k) {
array.sort((a, b) => a - b);
array = array.slice(0, k);
}
}
return array.pop();
};16. 最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
方法：暴力破解
思路：没思路，直接暴力循环啊～手动尴尬脸
var threeSumClosest = function(nums, target) {
const len = nums.length;
let total = nums[0]+nums[1]+nums[2];
for(let i = 0 ; i < len-2;i++){
for(let j = i+1;j<len-1;j++){
for(let k = j+1;k<len ;k++){
const sum = nums[i] + nums[j] + nums[k];
if(Math.abs(target-total) > Math.abs(target-sum)){
total = sum;
}
}
}
}
return total
};方法2:
思路：排序+双指针
/**
* 数组排序
* 获取整个数组最小值 min
* 获取数组长度，遍历数据
* 固定i出的起始值,使用双指针left,right滑动找到最接近target的值
* 计算数组i,left，right位置数值之和n
* 三数之和与target比较，将更接近target的n保存到min中，用来与下次三数之和对比
* 如果三数之和n小于target；将左指针left向右移动一位
* 如果三数之和n大于target；将右指针right向左移动一位
* 如果三数之和n等于target；返回target
* 最后输出min最小值
*
*/
var threeSumClosest = function (nums, target) {
nums.sort((a, b) => a - b);
let min = nums[0] + nums[1] + nums[2];
const len = nums.length;
for (let i = 0; i < len - 2; i++) {
let left = i + 1;
let right = len - 1;
while (left < right) {
const n = nums[left] + nums[right] + nums[i];
if (Math.abs(n - target) < Math.abs(min - target)) {
min = n;
}
if (n < target) {
left++;
} else if (n > target) {
right--;
} else {
return target;
}
}
}
return min;
};
139. 单词拆分
每日一题
无脑版，将字符串拆分成所有可以拆分的字符串，判断拆分后字符串是否在wordDict存在
var wordBreak = function(s, wordDict) {
const len = s.length;
let array =Array(len+1).fill(false) ;
array[0] = true;
for(let i = 0 ; i <= len ; i++){
for(let j = 0 ; j < i ; j++){
if(array[j] && wordDict.includes(s.substring(j,i))){
array[i] = true;
break;
}
}
}
return array[len]
};9. 回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
方法1
将整数转化为字符串，遍历字符串判断字符串两侧字符是否相同
var isPalindrome = function(x) {
if(x<0) return false
const s = String(x);
const len = s.length;
if(len === 1) return true;
for(let i = 0 ; i < len ; i++){
if(s[i] !== s[len-1-i]){
return false
}
}
return true
};##方法 2
将整数反转，如果反转后整数与原整数相同则证明整数是回文整数
var isPalindrome = function(x) {
if(x < 0) return false;
let reverse = 0;
const t = x;
while(x){
reverse=reverse*10 + x%10;
x = Math.floor(x/10)
}
return t === reverse
};8. 字符串转换整数 (atoi)
方法1
直接调用API有点欺负人啊
var myAtoi = function(str) {
let n = Number.parseInt(str)
if((n+'') == 'NaN') return 0
if(-2147483648 >= n) return -2147483648
if(2147483648 <= n) return 2147483647
return n
};方法2
正则匹配
var myAtoi = function (str) {
const s = str.trim().match(/^(\-|\+)?\d+/g)
const min = -2147483648
const max = 2147483647
if (s) {
const n = Number(s[0])
return Math.max(Math.min(n, max), min)
} else {
return 0
}
}174. 地下城游戏
来自每日一题
解题思路
此处撰写解题思路
代码
/**
* @param {number[][]} dungeon
* @return {number}
*/
var calculateMinimumHP = function (dungeon) {
const m = dungeon.length
const n = dungeon[0].length
let max = Infinity
let dp = new Array(n + 1).fill(max)
dp[n - 1] = 1
for (let i = m - 1; i >= 0; --i) {
for (let j = n - 1; j >= 0; --j) {
dp[j] = Math.max(1, Math.min(dp[j], dp[j + 1]) - dungeon[i][j])
}
}
return dp[0]
}2. 两数相加
#2. 两数相加
这个简单
例如：
2 -> 4 -> 3
5 -> 6 -> 4
| 数据 | 个位 | 十位 | 百位 |
|---|---|---|---|
| 链表 1 数据 | 2 | 4 | 3 |
| 链表 2 数据 | 5 | 6 | 4 |
| 数据 1、2 之和 | 7 | 0 | 8 |
| 进位 | 0 | 1 | 0 |
这里引入一个变量保存进位，当当前链表数据之和大于等于 10，进位变量为 1 用于下一位数据之和相加相加，数据之和-10;
根据上面的思路编写出下面的代码
var addTwoNumbers = function (l1, l2) {
let root = new ListNode(-1);
let list = root;
let sign = 0; //进位变量
while (l1 || l2 || sign) {
//保证l1.val有值
if (!l1) {
l1 = new ListNode(0);
}
//保证l2.val有值
if (!l2) {
l2 = new ListNode(0);
}
const n = l1.val + l2.val + sign; //不要忘记加上进位
//如果结果值大于10，sign进位1
if (n >= 10) {
sign = 1;
n = n - 10;
} else {
sign = 0;
}
list.next = new ListNode(n);
l1 = l1.next;
l2 = l2.next;
list = list.next;
}
return root.next;
};17. 电话号码的字母组合
var letterCombinations = function(digits) {
let obj = {
2:'abc',
3:'def',
4:'ghi',
5:'jkl',
6:'mno',
7:"pqrs",
8:'tuv',
9:"wxyz"
}
let resArr = []
while (digits) {
lsatDig = digits[0]
if(lsatDig){
digits = digits.substr(1);
resArr = blend(resArr,obj[lsatDig])
}else{
break
}
}
function blend(a,b){
let arr = []
let aL = a.length;
let bL = b.length;
if(bL){
for(let i = 0 ; i < bL ; i++){
if(aL == 0){
arr.push(b[i])
}else{
for(let j = 0 ; j < aL ; j++){
arr.push(a[j]+b[i])
}
}
}
}
return arr
}
return resArr
//console.log(resArr)
};02.01. 移除重复节点
来自每日一题
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
思路：常规操作，遍历链表，将链表用map缓存起来，每次去map中查看当前链表节点是否已存在，如果存在删除当前节点，如果不存在，当前节点不动
var removeDuplicateNodes = function (head) {
let root = new ListNode(-1)
root.next = head
let map = new Map()
while (root.next) {
const n = root.next.val
if (!map.has(n)) {
map.set(n, 1)
root = root.next
} else {
if (root.next.next) {
root.next = root.next.next
} else {
root.next = null
}
}
}
return head
}279. 完全平方数
来自每日一题
解题思路
此处撰写解题思路
代码
/**
* @param {number} n
* @return {number}
*/
var numSquares = function (n) {
let temp = n
while (temp % 4 === 0) {
temp = Math.floor(temp / 4)
}
if (temp % 8 === 7) return 4
const s = Math.sqrt(n, 2)
if (s % 1 === 0) return 1
let index = 0
while (index * index < n) {
const a = index * index
const bb = n - a
b = Math.sqrt(bb, 2)
if (b % 1 === 0) return 2
index++
}
return 3
}Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.