0~n-1中缺失的数字
0~n-1中缺失的数字描述一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
示例
示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
代码及思路思路题目中的关键信息:长度为n-1, 但有n个数字(0~n-1), 数字递增, 有且只有一个数字不在该数组中。
通过这几个关键信息我们可以得出的结论是:只能按照间隔为1进行递增,如果后一个数字减去前一个数字大于1,那说明这两个数字之间的数即为缺失的数字。
但这个是一般情况,考虑特殊情况: [1,2,3]和[0,1,2],缺少的数字分别是是0和3,但是后一个数字减去前一个数字都为1。这种情况要单独处理一下。
还有一种情况(最开始未考虑导致未通过): 如果数组的长度为1.[0] 或者 [1],也要单独考虑。
代码12345678910111213141516/** * @param {number[]} nums * @re ...
顺次数
1291.顺次数描述我们定义「顺次数」为:每一位上的数字都比前一位上的数字大 1 的整数。
请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表(从小到大排序)。
示例
示例 1:
输出:low = 100, high = 300
输出:[123,234]
示例 2:
输出:low = 1000, high = 13000
输出:[1234,2345,3456,4567,5678,6789,12345]
提示:
10 <= low <= high <= 10^9
代码及思路思路我的这个思路比较暴力,不是很好。首先想的是把这两个数字转为字符串,然后可以知道是几位数。小数的最高位加上其「长度减一」,如果大于或等于10,说明在这个长度下不会存在连续数。所以长度应该加一,最高为置为1。如果小于10,那么就循环从最高位加到最低位,即为一个结果。
举个栗子:low=100, high=1000那么low_len = 3, high_len = 4; 100的最高位是1, 1 + low_len = 4 < 10, 所以存在连续数 ...
连续赋值
关于连续赋值的问题题目12345let a = { n: 1 };let b = a;a.x = a = { n: 2 };console.log(a.x);console.log(b.x);
具体的文字描述引用知乎大佬的解释,说的比较到位:
12let a = { n: 1 };let b = a;
这两行比较好理解。在栈内存中,a与b是不同的,是两个变量,但是他们的指针是相同的,指向同一个堆。
关键点来啦:
1a.x = a = { n: 2 };
JS成员访问的优先级要比赋值运算高。先获取等号左侧的a.x,但a.x并不存在,于是JS为(堆内存中的)对象创建一个新成员x,这个成员的初始值为undefined.
(这也是为什么直接引用一个未定义的变量会报错,但是直接引用一个对象的不存在的成员时,会返回undefined.)
创建完成后,目标指针已经指向了这个新成员x,并会先挂起,单等等号右侧的内容有结果了,便完成赋值。
接着执行赋值语句的右侧,发现a={n:2}是个简单的赋值操作,于是a的新值等于了{n ...
宝石与石头
771. 宝石与石头描述给定字符串J代表石头中宝石的类型,和字符串S代表你拥有的石头。 S中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。
J中的字母不重复,J和S中的所有字符都是字母。字母区分大小写,因此”a”和”A”是不同类型的石头。
示例
示例 1:
输入: J = “aA”, S = “aAAbbbb”
输出: 3
示例 2:
输入: J = “z”, S = “ZZ”
输出: 0
注意:
S 和 J 最多含有50个字母。
J 中的字符不重复。
代码及思路思路想着是把宝石J和石头S字符串转为数组。然后利用filter方法过滤出石头数组中包含的宝石,取其长度。
代码1234567891011121314/** * @param {string} J * @param {string} S * @return {number} */var numJewelsInStones = function(J, S) { let jArr = J.split(& ...
设计哈希集合
705.设计哈希集合描述不使用任何内建的哈希表库设计一个哈希集合
具体地说,你的设计应该包含以下的功能
add(value):向哈希集合中插入一个值。
contains(value) :返回哈希集合中是否存在这个值。
remove(value):将给定值从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。
注意:
所有的值都在 [0, 1000000]的范围内。
操作的总数目在[1, 10000]范围内。
不要使用内建的哈希集合库。
示例123456789MyHashSet hashSet = new MyHashSet();hashSet.add(1);hashSet.add(2);hashSet.contains(1);// 返回 truehashSet.contains(3);// 返回 false (未找到)hashSet.add(2);hashSet.contains(2);// 返回 truehashSet.remove(2);hashSet.contains(2);// 返回 false (已经被删除)
代码及思路思路利用数组的push,includes,s ...
检测大写字母
520. 检测大写字母描述给定一个单词,你需要判断单词的大写使用是否正确。
我们定义,在以下情况时,单词的大写用法是正确的:
全部字母都是大写,比如”USA”。
单词中所有字母都不是大写,比如”leetcode”。
如果单词不只含有一个字母,只有首字母大写, 比如 “Google”。
否则,我们定义这个单词没有正确使用大写字母。
输入是由大写和小写拉丁字母组成的非空单词
示例
示例1
输入: “USA”
输出: True
示例2
输入: “FlaG”
输出: False
代码及思路思路如果是全部大写那么 str.toUpperCase() === str;
如果是全部小写那么 str.toLowerCase() === str;
如果str[0].toUpperCase() + str.slice(1).toLowerCase() === str,说明首字母大写,其他小写。
否则 返回false。
代码12345678910/** * @param {string} word * @return {boolean} */let dete ...
两个数组的交集
349.两个数组的交集描述给定两个数组,编写一个函数来计算它们的交集。
示例
示例1
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
示例2
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
代码及思路思路对这两个数组中的任意一个数组进行遍历,然后判断另一个数组中是有这个值,如果有就把这个值添加到到结果集合中(主要考虑到集合的元素不重复)。遍历结束后,将集合转为数组返回即可。
代码1234567891011121314/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */let intersection = function(nums1, nums2) { let res = new Set(); for(let item of nums1) { if(nums2.includes(item)) ...
多数元素
169.多数元素描述给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例
示例1
输入: [3,2,3]
输出: 3
示例2
输入: [2,2,1,1,1,2,2]
输出: 2
代码及思路思路遍历数组,利用map,记录相同数字出现的次数。如果某一个元素出现的次数大于n/2,则直接返回这个元素。
代码1234567891011121314151617/** * @param {number[]} nums * @return {number} */let majorityElement = function(nums) { let map = new Map(); for(let item of nums) { if(map.has(item)) { map.set(item, map.get(item) + 1); } else { ma ...
杨辉三角
118.杨辉三角描述给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
在杨辉三角中,每个数是它左上方和右上方的数的和。
示例
示例1
代码及思路思路仔细观察一下,可以看出来每个数组的第一位和最后一位都为1,并且大数组的第n个元素数组长度为n。所以假设大数组为arr, i 为第i个元素数组,会有arr[i][0] = 1 和 arr[i][i] = 1;这样第i个元素数组的首元素和最后一个元素就都值啦。中间元素的值可以写一个循环arr[i][j] = arr[i-1][j-1] + arr[i-1][j].
代码12345678910111213141516/** * @param {number} numRows * @return {number[][]} */let generate = function(numRows) { let res = []; for(let i = 0; i < numRows; i++) { res[i] = []; res[i][0] ...
矩阵置零
73.矩阵置零描述给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例
示例1
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例2
输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
思路及代码思路暂且不管题目中要求原地算法。不管白猫还是黑猫。能抓住老鼠就是好猫。于是我就大胆的开始想方法啦。
既然要把0所在的行和列都要置为0,首先要把出现0的位置记录下来。然后就有下面的代码:
12345678910111213141516/** * @param {number[][]} matrix * @return {void} Do not return anything, modify matrix in-place instead. */ ...