sailei1 / algorithm Goto Github PK
View Code? Open in Web Editor NEWLeetCode 笔记
LeetCode 笔记
请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9],它可以表示为:
示例 1:
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.
说明:
链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。
解法:
链表关系 跳过目标节点
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} node
* @return {void} Do not return anything, modify node in-place instead.
*/
var deleteNode = function(node) {
node.val=node.next.val;
node.next=node.next.next;
};
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
解法:
循环配合值, 如果发现目标值 跳过当前节点 直接指向next
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function(head, val) {
let cur=head;
let pre=null;
while(cur){
if (cur.val === val) {
if (pre) {
pre.next = cur.next; //跳过当前节点
} else {
head = cur.next;// 如果是第一个节点 直接跳过
}
} else {
pre = cur; //标记
}
cur = cur.next;
}
return head;
};
编写一个程序,找到两个单链表相交的起始节点。
如下面的两个链表:
在节点 c1 开始相交。
示例 1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
示例 2:
输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。
示例 3:
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
解释:这两个链表不相交,因此返回 null。
注意:
如果两个链表没有交点,返回 null.
在返回结果后,两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
思路:
根据长度不一样,找到公共长度的尾部
A尾部 跟B 尾部 对比 根据结果返回
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
var getIntersectionNode = function(headA, headB) {
let lena = getLen(headA);
let lenb = getLen(headB);
let a = headA;
let b = headB;
if (lena > lenb) {
let tem = lena - lenb
for (let i=0; i<tem; i++) {
a = a.next;
}
} else {
let tem = lenb - lena
for (let i=0; i<tem; i++) {
b = b.next;
}
}
//找到一样长度的尾部
while (a) {
if (a === b) {
return a;
}
a = a.next;
b = b.next;
}
return null;
};
function getLen(list) { //获取长度
let len = 0;
while (list) {
len += 1;
list = list.next;
}
return len;
}
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
解法:
1 当前节点的值跟 下一个节点的值相同
2 当前节点的下一个节点 指向下一个下一个的节点 (注意是循环)
3 递归查找 重复 1 2 步
4 找到最后一个节点 跳出
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function(head) {
if(!head){return head;} //尾部返回
while(head.next&&head.val === head.next.val){
head.next=head.next.next; // 当前值跟下一个值 一样时, 跳过当前值
}
// console.log(head.val);
deleteDuplicates(head.next); //依次递归
return head
};
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:
0
/ \
-3 9
/ /
-10 5
解法:
有序数组取数组的中间元素作为结点, 将数组分成左右两部分,对数组的两部分用递归的方法分别构建左右子树。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function(nums) {
let sort=(left, right)=>{
if(left > right){
return null;
}
// console.log(` ${left} ${right}`);
var m = left + Math.floor((right-left)/2); //取中间值 递归排序
var node = new TreeNode(nums[m]);
node.left = sort(left, m-1);
node.right = sort(m+1, right);
return node;
}
return sort(0, nums.length-1);
};
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
解法
1 有子节点时 深度+1,没子节点时深度+0;
2 一层一层往下递归,比较当前节点左右值
var maxDepth = function(root) {
if(root===null){ //当前节点为空时
return 0
}
var left = 1
var right = 1 //有子节点时 深度+1;
left += maxDepth(root.left)
right += maxDepth(root.right)
return left > right?left : right //比较左右值 一层一层往下递归, 都没有子节点时停止递归
};
给定一个整数 n,返回 n! 结果尾数中零的数量。
示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
解法:
最直观的想法 直接把数字的阶乘算出来,但是这样稳稳的上溢。
比如5 的阶乘是120 后面有一个0. 为了统计处这样的0 有多少个。
我们只需要知道所有可能的数字 里面相乘 可以得到10 的个数。
比如5! = 5 X4 X3 X2 X1 其中 5X2得到10;这就是最后一个0 的来源
在思考一下,要得到整数10 只能由 2X5 得到,我们可以把问题转换成为 寻找<n 的所有数字中 的分解 因子中的2 和5 的个数。一个2和一个5 就能构成10 。
比如10! =(2X5)X9X(2X4)X7X(2X3)X(5X1)X(2X2)X3X(2X1)X1 其中有 6个2 2个5 只能构成两个10 所以 10 的结果应该是2 。
并且我们发现统计2的个数没有意义的,2 的个数必然比5 多,因此我们只需要统计5 的个数就行了。
如何统计5的个数。
例如 30 它的5 的来源只能是5,10,15,20,25 (5X5),30中得到。总共应该是7个。(25 =5X5)
公式为 n+=n/5;
30 =30/5+6/5 =6+1 =7
//**
* @param {number} n
* @return {number}
*/
var trailingZeroes = function(n) {
// return n>=5?n/5+trailingZeroes(n/5):0;
let count = 0;
while(n >= 5) {
count += Math.floor(n/5);
n = n/5;
}
return count;
};
给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。
解法
//1先判断 正负数
2然后字符串反转
3 再转数值 判断是否越界
var reverse = function(x) {
let rs='';
if(x<0){
rs='-'
}
let str= (Math.abs(x)+'').replace(/\0/g, '');
rs+= str.split('').reverse().join('');
if( Number(rs)<Math.pow(-2, 31)||Number(rs)>Math.pow(2, 31)-1){
rs=0;
}
return rs;
};
罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:
I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:
输入: "III"
输出: 3
示例 2:
输入: "IV"
输出: 4
示例 3:
输入: "IX"
输出: 9
示例 4:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
解法:
1 建立 map 对应关系
2 建立换算关系
IV= 1+5-1-1
VI=5+1
/**
* @param {string} s
* @return {number}
*/
var romanToInt = function(s) {
let arr=s.split('');
let m={
I:1,
V:5,
X:10,
L:50,
C:100,
D:500,
M:1000
};
let rs=0,pre=0;
for(let i=0;i<arr.length;i++){
if(rs ===0){
rs=m[arr[i]];
pre=m[arr[i]]; // 别忘了标记初始值 为前一位 使用
}else{
let b=rs,n=0;
if(m[arr[i-1]]<m[arr[i]]){ //IV型 运算
n=m[arr[i]]-m[arr[i-1]];
rs=b+n-pre;
}else{
pre=m[arr[i]];
rs=b+pre;
}
}
}
return rs;
};
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
解法:
多个连续峰值的和 等于最大峰值
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let max=0;
for(let i=0;i<prices.length-1;i++){
if(prices[i] < prices[i+1]){
max+=prices[i+1]-prices[i]; //多个连续峰值的和
}
}
return max;
};
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
解法
1 节点值 谁小 谁靠前
2 小的节点值的next 跟 大的节点当前值 做比较 决定当前节点next
3 大的节点 next 跟小的节点当前值做比较 决定当前节点next
4 递归
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function(l1, l2) {
if(l1&&l2){
let node;
if(l1.val<l2.val){ //节点值 谁小 谁靠前
node=new ListNode(l1.val);
node.next=mergeTwoLists(l1.next,l2); //小的节点值的next 跟 大的节点当前值 做比较 决定 next
}else{ //相反的情况
node=new ListNode(l2.val);
node.next=mergeTwoLists(l1,l2.next);
}
return node;
}
return l1||l2;// 其中一个为空的情况
};
给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
在杨辉三角中,每个数是它左上方和右上方的数的和。
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
解法:
上一行遍历获取左上方和右上方的数的和
/**
* @param {number} numRows
* @return {number[][]}
*/
var generate = function (numRows) {
let res = []
for (let i = 0; i < numRows; i++) {
if (i === 0) {
res.push([1])// 第一行 基础行
} else {
const arrs = [1];// 初始化当前行的第一个元素为1
const preRows = res[i - 1];// 上一行数据
for (let j = 0; j < preRows.length; j++) {// 上一行遍历获取左上方和右上方的数的和
arrs.push(preRows[j] + (preRows[j + 1] || 0));
}
res.push(arrs);
}
}
return res;
};
给定两个二进制字符串,返回他们的和(用二进制表示)。
输入为非空字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
解法:
二进制 1010
1011
-----
竖向相加 2021 逢2 进1
10101
/**
* @param {string} a
* @param {string} b
* @return {string}
*/
// var addBinary = function(a, b) {
// let rs=convert(a)+convert(b);
// return rs.toString(2); //转换2进制
// };
// function convert(str){ return parseInt(str, 2); } //转换十进制
// 有溢出问题
var addBinary = function (a, b) {
let carry = 0;// 进位标记
let res = [];
aindex = a.length - 1;//
bindex = b.length - 1;
while (aindex >= 0 || bindex >= 0) {// a或b还有位可以相加
sum = (+a[aindex] || 0) + (+b[bindex] || 0) + carry;// aindex bindex 长度不一致时 0替补
carry = sum >= 2 ? 1 : 0;//进位数值
res.push(sum % 2);
aindex--;
bindex--;
}
if (carry) {
res.push(1);
}
return res.reverse().join(''); // 数组反推 返回结果
};
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数,小数部分将被舍去。
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
return Math.floor(Math.pow(x,0.5));
};
示例 1:
输入:
1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出: true
示例 2:
输入:
1 1
/ \
2 2
[1,2], [1,null,2]
输出: false
示例 3:
输入:
1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
输出: false
解法:
1 先对比 当前值 相同 再对比左右
2 有一个存在 的情况 返回false
3 递归
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function(p, q) {
// console.log(p);
// console.log(q);
if(p&&q && p.val == q.val){
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}else{
if(p||q){
return false;
}else{
return true;
}
}
// 解法2
// return JSON.stringify(p) === JSON.stringify(q) 树 本身就是object 直接转 json 对比 最快
};
给定一个正整数,返回它在 Excel 表中相对应的列名称。
例如,
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
...
示例 1:
输入: 1
输出: "A"
示例 2:
输入: 28
输出: "AB"
示例 3:
输入: 701
输出: "ZY"
解法:
余数相加
/**
* @param {number} n
* @return {string}
*/
/**
* @param {number} n
* @return {string}
*/
var convertToTitle = function(n) {
let m=['A','B','C','D','E','F','G','H','I','J',
'K','L','M','N','O','P','Q','R','S','T',
'U','V','W','X','Y','Z'];
let res='',ls=m.length;
while(n>=1)
{ n--; //字母数组下标对应
res=m[n%ls]+res; //余数相加
n=Math.floor(n/ls);
// console.log(n);
}
return res;
};
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
解法:
获取 左右两边 最大深度,相减绝对值大于1 非平衡二叉树。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function(root) {
let rs=true; //默认平衡
let findDepth=(node)=>{
if(!node){return 0;}
let left=findDepth(node.left); //获取左边最大深度
let right=findDepth(node.right);// 获取后边最大深度
if(Math.abs(left-right)>1){ //不平衡
rs=false;
}
return Math.max(left, right)+1;
}
findDepth(root);
return rs;
};
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
解法
途径节点 相减 跟节点值 做匹配
注意 叶子节点是指没有子节点的节点。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {boolean}
*/
var hasPathSum = function(root, sum) {
let left = false, right = false;
if(root) {
sum -= root.val;//途径节点 相减 缩小范围
if(root.left) {left = hasPathSum(root.left, sum);}
if(root.right){ right = hasPathSum(root.right, sum);}
if(!root.left && !root.right && sum == 0) { //确定节点没有子节点
return true;
}
}
return left || right;
};
// let hasPathSum = function(root, sum) {
// if(!root) return false;
// if(root.left === null && root.right === null) return sum === root.val;
// return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
// };
//思路跟上边一样,少减一次
设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
解法:
利用数组的特性
/**
* initialize your data structure here.
*/
var MinStack = function() {
this.stack=[];
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.stack.push(x);
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
return this.stack.pop();
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1]
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
return Math.min.apply(this, this.stack);
};
/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(x)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:
你能不将整数转为字符串来解决这个问题吗?
解法
1 number 转 string
2 字符串反转
3 string转number 对比 返回结果
/**
* @param {number} x
* @return {boolean}
*/
var isPalindrome = function(x) {
let rs='';
let str= x+'';
rs+= str.split('').reverse().join('');
let t= x===Number(rs);
return t
};
给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
解法:
快慢指针同时从头节点出发,慢指针一次走一步,快指针一次走两步,如果快指针追上了慢指针,证明链表中有环;否则直到快指针走到链表尾都没有追上,则链表不包含环。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
let slow = head;
let fast = slow;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
break;
}
}
if (fast == null || fast.next == null) {
return false;
}
return true
};
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
解法:
1建立两个索引
2 循环原数组 j++;
3 元素对比 如果发现不同的元素i++;
4 把原数组j位元素 移动i位
5 返回 i+1位 为去重数组长度
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
// let o={};
// for(let i=0;i<nums.length;i++){
// if(!o[nums[i]]){
// o[nums[i]]=0;
// }
// }
// let rs=[];
// for(let k in o){
// rs.push(k);
// }
// rs.sort((a,b)=>{return a-b;})
// for(let i=0;i<rs.length;i++){
// nums[i]=rs[i];
// }
// return rs.length;
if(nums.length==0){
return 0;
}
let i = 0;
for (let j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) { //判断是否重复
i++;
nums[i] = nums[j]; //数组元素移动
}
}
return i+1;
};
给定一个Excel表格中的列名称,返回其相应的列序号。
例如,
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
示例 1:
输入: "A"
输出: 1
示例 2:
输入: "AB"
输出: 28
示例 3:
输入: "ZY"
输出: 701
解法:
Z=26 处在第2位 2626的2-1次方 2626
Y=25 出在第一位 26 的1-1次方 251
2626+25*1=701
/**
* @param {string} s
* @return {number}
*/
var titleToNumber = function(s) {
let key={
'A':1,
'B':2,
'C':3,
'D':4,
'E':5,
'F':6,
'G':7,
'H':8,
'I':9,
'J':10,
'K':11,
'L':12,
'M':13,
'N':14,
'O':15,
'P':16,
'Q':17,
'R':18,
'S':19,
'T':20,
'U':21,
'V':22,
'W':23,
'X':24,
'Y':25,
'Z':26
};
let str=s.split('').reverse(),rs=0;
for(let i=0;i<str.length;i++){
rs=key[str[i]]*Math.pow(26,i)+rs; //转换公式
}
return rs;
};
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。
对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
解法 太简单了
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
return haystack.indexOf(needle);
};
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false
解法
“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。
先过滤 再 反转后 跟原字符对比
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
let str=s.toLowerCase().replace(/[^a-z0-9]/g,''); //过滤
let re=str.split('').reverse().join(''); // 反转
return str===re
};
给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
解法:
字符串转number 有溢出的问题,所以放弃。
从数组最后一位判断是否需要进位 比如49+1=50 9+1=0 再4+1;
依次类推 999 +1 =1000
/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function(digits) {
let f=true;
let ls=digits.length;
for(let i=ls-1;i>=0;i--){
if(digits[i]+1>9){ //大于9 数位循环+1;
digits[i]=0;
}else{
digits[i]+=1; //+1后 小于10 停止
f=false; // 进位标记
break;
}
}
if(f){
digits.unshift(1); // 999 情况 进1
}
console.log(digits);
return digits;
};
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
说明:
如果你可以运用递归和迭代两种方法解决这个问题,会很加分。
解法:
1 左左 右右比较 左右 右左比较 (关键点)
2 递归
3 注意兼容 空值 或 只有一个节点存在时
var isSymmetric = function(root) {
if(!root)return true;
let result = true; //默认对称
let fun = (l, r) => {
if(!l && !r){ return;} //最底层节点 不比较
if(!l || !r){ // 一个存在时 不对称
result = false;
return;
}
if(l.val === r.val){ //相等 递归比较
fun(l.left, r.right) // 左左 右右比较
fun(l.right, r.left) // 左右 右左比较
}else{
result = false; //不对称
return;
}
}
fun(root.left, root.right);
return result;
};
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
解法:
1 建立开始结束关系。
2利用栈的先进后出特点。
3 遍历每一个字符,如果与栈顶元素匹配,则出栈,不匹配则进栈;
最后为空栈说明是合法的。
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
let rs=false;
let key={
'(':')',
'{':'}',
'[':']'
};
if(s.length==0){
rs=true;
}
let stack=[];
for(let i=0;i<s.length;i++){
let char=s[i];
if(char===key[stack[stack.length-1]]){ // 确立关系
stack.pop();
}else{
stack.push(char);
}
}
if(stack.length==0){
rs=true;
}
return rs;
};
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
解法:
比较值, 根据值大小 锁定位置
1小于 第一个 0
2 相等 i
3 紧挨着的 大于前面 小于后面 i+1
4 大于最后一个 length
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
if(target-nums[0]<=0){ //小于 第一个
return 0;
}
for(let i = 0 ;i<nums.length;i++){
if(target == nums[i]){ //相等
return i;
}
if(target > nums[i] && target < nums[i+1]){ //大于前面 小于后面
return i+1;
}
}
if(target-nums[nums.length-1]>0){ //大于最后一个
return nums.length;
}
};
给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
解法:
有序数组 越后面越大
反推对比值大小
大的 直接后面追加
小的 下标往前移动 对比 目标数组前一位
注意 最前面 数组下标 比如 -1
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {
for(let i=n-1;i>=0;i--){
// console.log(nums1);
let k=nums2[i];
if(k>nums1[m-1]|| m == 0){ //最大值比较 大于 尾部追加最大值
nums1[m+i]=k; //
}else{
// console.log(`${m+i} ${m-1}`);
nums1[m + i] = nums1[m - 1] //nums2不大于 num1最大值往后移动
m--;
i++; // nums2 当前值 跟 nums1 前一位 比较 m==0 防止越界
}
}
};
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
解法:
1 找到长度最低的那个元素
2 转换字符串数组
3 从后面依次按照字母找
4 如果都存在 确定是不是相邻关系。
5 返回相邻结果集
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
let rs=''; //不匹配时 返回'';
if(strs.length==1){ // 只有一个的时候返回 当前值
rs=strs[0];
}else if(strs.length>1){
let t_arr=strs.sort((el,next)=>{
return el.length-next.length;
})
let els=t_arr[0].split(''),temp=-1; //找到长度最低的那个元素
for(let l=0;l<els.length;l++){
let t=true;
for(let i=1;i<t_arr.length;i++){ //从后面依次按照字母找
if(t_arr[i][l].indexOf(els[l])==-1){
t=false; //找到没有的时候跳出循环
break;
}
}
if(t){ //如果都存在 确定是不是相邻的
if(l-temp===1){ rs+=els[l];}
temp=l;
}
}
}
return rs;
};
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
// 循环
let pre=null;
while(head){
let next=head.next; //先保存原始next
head.next=pre; //改变next 关系
pre=head; //标记前一位
head=next;//后移
}
return pre;
//function reverse(pre,cur){ //递归
// if (cur == null){
// return pre
// }
// let head= reverse(cur, cur.next)
// cur.next = pre;
// return head
// }
// return reverse(null,head);
};
给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
说明:
返回的下标值(index1 和 index2)不是从零开始的。
你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
解法:
target 减一个小值, 寻找另一个值 返回下标
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
for(let i=0;i<numbers.length;i++){
let f=target-numbers[i];
for(let l=i+1;l<numbers.length;l++){
if(f===numbers[l]){
return [i+1,l+1];
}
}
}
};
颠倒给定的 32 位无符号整数的二进制位。
示例 1:
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596,
因此返回 964176192,其二进制表示形式为 00111001011110000010100101000000。
示例 2:
输入:11111111111111111111111111111101
输出:10111111111111111111111111111111
解释:输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293,
因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001。
提示:
请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在上面的 示例 2 中,输入表示有符号整数 -3,输出表示有符号整数 -1073741825。
进阶:
如果多次调用这个函数,你将如何优化你的算法?
解法:
1 转换string 补齐格式
2 字符串反转
3 转换二进制
/**
* @param {number} n - a positive integer
* @return {number} - a positive integer
*/
var reverseBits = function(n) {
var res = (n).toString(2);//转换string
while(res.length<32){
res = '0'+res; //没有的前面补齐 给反转做准备
}
res = res.split('').reverse().join(''); //反转
return parseInt(res, 2); //转换字符串 二进制
};
//位移
// var reverseBits = function(n) {
// let res = 0;
// for (let i = 0; i < 32; i++) {
// res = (res << 1) + (n & 1); //(进位运算) 将 res 的二进制形式向左移1位,右边用0填充。 n&1 比较 0&1=0 1&1=1 二进制运算
// // console.log(res.toString(2));
// // console.log((n & 1).toString(2))
// n = n >>> 1; //(反转) 将 n 的二进制表示向右移1位,丢弃被移出的位,并使用 0 在左侧填充。
// }
// // console.log(res);
// return res >>> 0; //左侧填充0 二进制转换;
// };
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解法:
1 num2= target - num1
2 然后从数组里面找到 num2 的下标 并返回结果
var twoSum = function(nums, target) {
let length = nums.length
for(let i = 0; i < nums.length; i++) {
let item = nums[i]
let other = target - item
let index
if((nums.indexOf(other) != -1 && nums.indexOf(other) != i)){
index = nums.indexOf(other)
return [i, index]
}
}
};
给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
解法:
1 发现元素与目标值 不相同 找到下标I
2 原数组 i位 移动j位 j从0位开始 j++;
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
let j=0;
for(let i=0;i<nums.length;i++){
if(nums[i]!==val){
nums[j]=nums[i];
j++;
}
}
return j;
};
给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。
在杨辉三角中,每个数是它左上方和右上方的数的和。
示例:
输入: 3
输出: [1,3,3,1]
/**
* @param {number} rowIndex
* @return {number[]}
*/
var getRow = function(rowIndex) {
let res = []
for (let i = 0; i <=rowIndex; i++) {
if (i === 0) {
res.push([1])// 第一行 基础行
} else {
let arrs = [1];// 初始化当前行的第一个元素为1
let preRows = res[i - 1];// 上一行数据
for (let j = 0; j < preRows.length; j++) {// 上一行遍历获取左上方和右上方的数的和
arrs.push(preRows[j] + (preRows[j + 1] || 0));
}
res.push(arrs);
}
}
return res[rowIndex];
};
给定一个仅包含大小写字母和空格 ' ' 的字符串,返回其最后一个单词的长度。
如果不存在最后一个单词,请返回 0 。
说明:一个单词是指由字母组成,但不包含任何空格的字符串。
示例:
输入: "Hello World"
输出: 5
/**
* @param {string} s
* @return {number}
*/
var lengthOfLastWord = function(s) {
let arr=s.trim().split(' '); // 去掉两边空格 按空格分割
return arr[arr.length-1].length;
};
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
说明:
尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的原地算法。
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
// var rotate = function(nums, k) {
// let ls=nums.length,s=k+1;
// let arr=nums.splice(s,ls-1).concat(nums.splice(0,s));
// console.log(arr);
// return arr;
// };
/**
* 利用队列的出队和入队**
* 时间复杂度;O(),空间复杂度O(1)
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function(nums, k) {
let len = nums.length
if (len < 2) {
return
}
while (k--) {
// 先出队再入队
nums.unshift(nums.pop())
}
};
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
解法
1 2 3 4 5 6 7
1 2 3 5 8 13 21
3的值 (3=1+2) 1 的值+2的值
4的值( 5=2+3) 2的值加3的值
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
// console.log(n);
if(n==1||n==2){
return n;
}
// if(n>2){
// n--;
// return climbStairs(n)+climbStairs(n-1);
// }
// 递归超时了,可能效率不行,测试通过不了 只能循环了。
let b1=1,b2=2,sum=0;
for(let i=2;i<n;i++){
sum=b1+b2;
b1=b2;
b2=sum;
}
return sum;
};
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
解法
利用map 存在+1 不存在创建key 查看key
/**
* @param {number[]} nums
* @return {number}
*/
// var singleNumber = function(nums) {
// let ls=nums.length;
// for(let i=0;i<ls;i++){
// let str=nums[i];
// if(nums.lastIndexOf(str)==nums.indexOf(str)){ //效率不高
// return str;
// }
// }
// };
var singleNumber = function (nums) {
let count = {};
nums.forEach(num => {
if (count[num]) {
count[num]++;
}
else{
count[num] = 1;
}
});
for (let key in count) {
if (count[key] === 1) {
return key;
}
}
};
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其自底向上的层次遍历为:
[
[15,7],
[9,20],
[3]
]
解法:
1 从上到下 压入数组
2 根据深度 合并数值
2 数组反转 返回
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrderBottom = function(root) {
// if(root === null ){
// return [];
// }
// let arr=[];
// arr.push([root.val]);
// let findNode=(root)=>{
// if(root){
// if(root.left&&root.right){
// arr.push([root.left.val,root.right.val]);
// findNode(root.left);
// findNode(root.right);
// }else{
// if(root.left){
// arr.push([root.left.val]);
// findNode(root.left);
// }
// if(root.right){
// arr.push([root.right.val]);
// findNode(root.right);
// }
// }
// }
// //console.log(arr);
// }
// findNode(root);
// 上面没考虑深度合并
if(root === null ){
return [];
}
let arr=[];
let findNode= (root,deep)=>{ //
if(root){
arr[deep]=arr[deep]||[];//兼容
arr[deep].push(root.val) // 靠deep 来合并数值
if(root.left){
findNode(root.left,deep+1);
}
if(root.right){
findNode(root.right,deep+1); //先左后右
}
}
}
findNode(root,0);
return arr.reverse();//反转 输出
};
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
/**
* @param {number} n
* @return {number}
*/
// var countPrimes = function(n) {
// //质数:只能被1和本身整除,1不是质数
// let res=1;//从3开始计算,所以初始为1
// if(n<3){ res=0;}
// else{
// for(let i=3;i<n;i++){
// if(i%2 == 0){
// continue;
// }
// let flag=true;//false表示不是素数
// for(let j=3;j<=Math.sqrt(i);j+=2){
// if(i%j==0){
// flag=false;
// break;
// }
// }
// if(flag){res++; }
// }
// }
// return res;
// };
var countPrimes = function(n) {
if(n <= 2) {
return 0
}
if(n === 3) {
return 1
}
let count = 1;
let arr = {};
for(let i = 3; i < n; i += 2) {//叠加
if(arr[i]) {
continue;
}
count++;
for(let j = i; j < n; j += i) { //叠加
arr[j] = true;
}
}
return count;
};
给定两个字符串 s 和 t,判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。
示例 1:
输入: s = "egg", t = "add"
输出: true
示例 2:
输入: s = "foo", t = "bar"
输出: false
示例 3:
输入: s = "paper", t = "title"
输出: true
说明:
你可以假设 s 和 t 具有相同的长度。
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isIsomorphic = function(s, t) {
for (let i = 0; i < s.length; i++) {
if (s.indexOf(s[i], i + 1) !== t.indexOf(t[i], i + 1)) {
//遍历两个字符串,查找当前字符出现在后续字符串中的位置,如果是同构字符串,每个字符出现的位置是相同的
return false;
}
}
return true;
};
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.
解法:
获取左 右两边值 对比 获取小值;
注意[1,2] 这种特殊树,被坑了
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var minDepth = function(root) {
let findDepth=(node)=>{
if(!node){return 0;}
let left=findDepth(node.left); //获取左边最小深度
let right=findDepth(node.right);// 获取后边最小深度
if(left&&right){
return Math.min(left, right)+1;
}
return 1+left+right; //如果数据结构为[1,2],则为特殊情况,单独一个根节点,不为最小深度
}
return findDepth(root);
};
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
解法
找到 各个低峰值, 然后对比上升值
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let val=prices[0],max=0;
for(let i=0;i<prices.length;i++){
if(prices[i] < val){
val = prices[i]; //找低峰值
}else if(prices[i] - val > max){ // 低峰值时的最大值比较
max = prices[i] - val;
}
}
return max;
};
给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
解法
利用map
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
let ls=nums.length;m=Math.ceil(ls/2),o={};
if(ls===1){
return nums[0];
}
for(let i=0;i<ls;i++){
if(o[nums[i]]){
o[nums[i]]=o[nums[i]]+1;
if(o[nums[i]]>=m){ //大于一半时的
return nums[i];
}
}else{
o[nums[i]]=1;
}
}
};
编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。
示例 1:
输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。
示例 2:
输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。
示例 3:
输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。
提示:
请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在上面的 示例 3 中,输入表示有符号整数 -3。
进阶:
如果多次调用这个函数,你将如何优化你的算法?
/**
* @param {number} n - a positive integer
* @return {number}
*/
var hammingWeight = function(n) {
var res = (n).toString(2);//转换string
let arr=res.match(new RegExp('1', 'g'))||[] //正则查找
return arr.length;
};
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。
解法:
1 累加 跟前一个值 做比较
2 sum大于0 累加 更大
3 sum 小于 直接等于下一位
4 循环对比最大值 返回最大值
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let res = nums[0];
let sum = 0;
for(let i=0;i<nums.length;i++){
if(sum>0) { //sum 大于0 累加
sum += nums[i];
}else {
sum = nums[i]; //sum 直接等于下一位
}
res = Math.max(res,sum);// 循环对比最大值 返回最大值
}
return res;
};
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
解法:
rs[i-1] , rs[i-2]+nums[i] 对比大小
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
if(nums.length==0){
return 0;
}
if(nums.length<3){
return Math.max(...nums);
}
let rs=[];
rs[0] = nums[0];
rs[1] = Math.max(nums[0],nums[1]);
for(let i = 2;i< nums.length ;i++) {
rs[i] = Math.max(rs[i-1] , rs[i-2]+nums[i]); // 状态转移方程
};
// console.log(rs)
return rs[nums.length - 1];
};
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.