生命不息,刷题不止,hhhhhhhhhh … 可爱的我又来了
1. Leetcode 1013. 将数组分成和相等的三个部分
**思路一:**最开始看到题目的时候cc是这么想的,既然能分成三个部分,不妨先计算每个部分的和,然后只要能成功地截取两边的部分,中间部分肯定也满足条件了,就可以判定能划分。所以我把题目转化为寻找 [0,i), [i,j), [j,num.length)
中的i和j,使得sum(A[0]-A[i-1]) = totalSum/3
且 sum(A[j]-A[length-1] = totalSum/3)
代码就这么出炉了:
var canThreePartsEqualSum = function(A) {
if(A.length < 3){
return false
}
let totalSum = A.reduce((pre,cur) => pre+cur) // 计算数组之和
if(totalSum % 3 !== 0){ // 和不能被3整除,不可能存在划分
return false
}
let partSum = totalSum / 3
let i = 1, j = A.length-1
let partA = A[0],partC = A[j]
while(partA !== partSum || partB !== partSum){
if(partA !== partSum){
partA += A[i]
i++
}
if(partB !== partSum){
j--
partB += A[j]
}
if(i >= j){
return false
}
}
return true
}
运行结果:
上面我这种方法是比较直接的两侧遍历法,我就叫做两头分割法了,(emmm 怎么感觉有点血腥)
看了其他人的题解,还有如下方法,都比较简单:
思路二、遍历计数法:也是像我上面一样,计算整个数组的和,进而得到每部分的和,从左到右遍历,记录遍历过的数值之和temp和与部分数目count
- 当
temp= totalSum/3
的时候sum = 0, cnt ++
遍历过程中,count只要等于3都可以划分,当然大于也可以[0,0,0,0,0],所以count = 3 的时候就可以返回true
var canThreePartsEqualSum = function(A){
let totalSum = A.reduce((pre,cur) => pre+cur)
if(totalSum % 3 !== 0) return false
let temp = 0
let cnt = 0
for(let item in A){
temp += A[item]
if(temp === totalSum/3){
temp = 0
cnt ++
}
if(cnt === 3) return true
}
return false
}
第二种看似代码简单,但实际的性能并不强,所以cc还是安利自己的血腥**“双头分割法”**(2333333),类似双头指针的原理。
2. Leetcode 300. 最长上升子序列
思路一:动态规划法:遍历一遍数组,记录当前位置的上升子序列长,和当前最长的上升子序列长,遍历结束,输出最长上升子序列长度即可,在i>j的情况下,
- 如果nums[i] > nums[j],
maxLen[i] = max(maxLen[j]+1, maxLen[i])
- 如果nums[i] <= nums[j],maxLen[i]不变
- 记录当前全局的max 也就是所有maxLen[i]中的最大值
var lengthOfLIS = function(nums){
if(nums.length < 2){
return nums.length
}
let max = 1
let maxLens = new Array(nums.length).fill(1)
for(let i = 1; i < nums.length; i++){
for(let j = 0; j < i; j++){
if(nums[i] > nums[j]){
maxLens[i] = Math.max(maxLens[j]+1, maxLens[i])
}
}
max = Math.max(maxLens[i], max)
}
return max
}
在上述遍历情况下的,时间复杂度:O(n*n)
,空间复杂度:O(n)
, 是否有可能简化遍历呢?可能需要我们重新设计状态定义
思路二: 动态规划+二分查找法:结合二分查找,改变思路一中的双重for循环,可以将时间复杂度降至O(nlogN)
,具体的思路就类似于插入排序,依旧是i>j的情况下:
- 当我们当前遍历的元素大于递增序列的尾元素时(
num[i] > num[j]
),把当前元素直接放到序列后面 - 否则(
num[i] <= num[j]
),把之前递增序列中第一个比当前元素大的元素替换为当前元素,插入后依然有序
(比方,之前递增序列为[1,2,5,9],当前元素是4,那么就把序列替换为[1,2,4,9],插入的过程就是使用二分查找) - 这种方法得到的序列未必是方法一中最终的递增序列,但是长度和最长递增序列肯定是相同的
var lengthOfLIS = function(nums){
let n = nums.length
if(n < 2){
return n
}
let tail = new Array(n);
tail[0] = nums[0]
let end = 0
for(let i = 1; i < n; i++){
if(nums[i] > tail[end]){
tail[++end] = nums[i]
}else{
let left = 0
let right = end
while(left < right){
let mid = left + ((right-left) >>1)
if(tail[mid] < nums[i]){
left = mid + 1
}else{
right = mid
}
}
tail[left] = nums[i]
}
}
return end + 1
}
或者也可以这样写,通过更新新增的索引来求长度
var lengthOfLIS = function(nums){
let n = nums.length
if(n < 2){
return n
}
let tail = [nums[0]]
for(let i = 0; i < n; i++){
if(nums[i] > tail[tail.length-1]){
tail.push(nums[i])
}else{
let left = 0
let right = tail.length - 1
while(left < right){
let mid = (left + right) >> 1
if(tail[mid] < nums[i]){
left = mid + 1
}else{
right = mid
}
}
tail[left] = nums[i]
}
}
return tail.length
}
3. Leetcode 695. 岛屿的最大面积
思路一: 万能的递归法+DFS,计算某个位置(i,j)处的岛屿面积,(i,j)处的岛屿面积情况如下:如果此处是岛屿,则他周围的岛屿面积等于1+四周的岛屿面积;否则返回0。遍历整个二维数组,记录每个(i,j)处的岛屿面积,记录最大值,输出
var maxAreaOfIsland = function (grid) {
let maxArea = 0
// 查找相邻的岛屿面积
const getArea = function(i, j){
if(grid[i] === void 0 || grid[i][j] === void 0 || grid[i][j] === 0){
return 0
}
// 如果该块已经被统计过了,置为0,防止重复统计
grid[i][j] = 0
return 1 + getArea(i-1,j) + getArea(i+1,j) + getArea(i,j-1) + getArea(i,j+1)
}
// 循环遍历找最大岛屿面积
for(let i = 0; i < grid.length; i++){
for(let j = 0; j < grid[i].length; j++){
maxArea = Math.max(getArea(i,j), maxArea)
}
}
return maxArea
};
时间和空间复杂度都是O(m*n)
思路二: 广度优先遍历(BFS),遍历二维数组,借助队列记录非水区域块grid[i][j]=1
的坐标[i,j]
,和相关的区域面积area
。每次都弹出队头,如果队头满足在区域内且是非水区域,则岛屿面积加一(area++
),同时弹入其四周的位置入队列;否则继续弹出队头,直到队列为空,更新最大面积(maxArea = max(area, maxArea)
)。继续遍历二维数组,将非水区域的坐标放入空队列,初始化岛屿面积0,弹出队头元素,弹入… … 直到遍历结束,输出最大面积maxArea
var maxAreaOfIsland = function(grid){
let maxArea = 0
let row = grid.length, column = grid[0].length
let dx = [1, -1, 0, 0], dy = [0, 0, 1, -1]
for(let i = 0; i < row; i ++){
for(let j = 0; j < column; j++){
if(grid[i][j] === 0) continue
// 初始化小岛块区域的坐标和岛屿面积
let queue = [[i,j]]
let area = 0
while(queue.length > 0){ // 队列不为空的时候
let [x,y] = queue.shift() // 弹出队头位置的坐标
if(x < 0 || x >= row ||y < 0 || y >= column || grid[x][y] === 0) continue
++ area // 弹出的是范围内的非水块,面积加一
grid[x][y] = 0 // 将该块标记为0,防止重复计算
for(let k = 0; k < 4; k ++){
queue.push([x+dx[k], y+dy[k]]) // 将四周的位置坐标弹入队列
}
}
maxArea = Math.max(area, maxArea)
}
}
return maxArea
};
或者也可以在弹入队列的时候就判断周围元素坐标范围,只让范围内的区域坐标进队列,避免弹入又弹出的麻烦
var maxAreaOfIsland = function(grid){
let maxArea = 0
let row = grid.length, column = grid[0].length
let dx = [1,-1,0,0], dy = [0,0,1,-1]
for(let i = 0; i < row; i++){
for(let j = 0; j < column; j++){
if(grid[i][j] === 0) continue
// 初始化非水块队列及岛屿面积
let queue = [[i,j]]
let area = 0
while(queue.length > 0){
// 弹出队头坐标,区域面积+1,置0防止重复计算
let [x,y] = queue.shift()
if(grid[x][y] === 0) continue
++ area
grid[x][y] = 0
// 弹入四周位置时,添加判断,满足条件再入队列
for(let k = 0; k < 4; k ++){
// 判断是否在范围内
if(x+dx[k] >= 0 && x+dx[k] < row && y+dy[k] >=0 && y+dy[k] < column){
queue.push([x+dx[k],y+dy[k]])
}
}
}
maxArea = Math.max(area, maxArea)
}
}
return maxArea
}
方法二的时间复杂度和空间复杂度依旧是O(m*n)
,但实际在leetcode上运行的结果显示,DFS的运行效果要更优
4. 剑指offer 01.06. 字符串压缩
思路: 统计字符串中连续出现的字符的数目,压缩后的新字符串cstr = {char in str + count}*
,比较cstr 和 str 选择较短者
var compressString = function(S){
if(S.length < 2) return S
let res = ''
let c = S[0]
let cnt = 1
for(let i = 1; i < S.length; i++){
if(c === S[i]){
cnt ++
}else{
res += c + cnt.toString()
c = S[i]
cnt = 1
}
}
res += c + cnt.toString()
return res.length < S.length ? res : S
}
5. Leetcode 1160. 拼写单词
思路: 计算每个单词中字符的个数,遍历单词集中的每个单词中字符出现的次数,和字母集中的字符次数做对比,如果字母集中的字符的个数小于单词中的字符个数,则不能拼写,若单词中每个字符的个数都小于等于字母集中的字符个数,则可以拼写,计入长度
var countCharacters = function(words, chars){
let ans = 0
let countChars = function(word, char){
// 计算字符串word中出现字符char的次数
let res = 0
for(let item of word){
res += item===char? 1: 0
}
return res
}
for(let word of words){
let isSuccess = 1 // 标记是否可以拼词成功
for(let letter of word){
if(countChars(word, letter) > countChars(chars, letter)){
isSuccess = 0
break
}
}
if(isSuccess === 1){
ans += word.length
}
}
return ans
};
思路二:哈希计数法,遍历字母集chars用map记录每个字母出现的次数_set get has;遍历单词集words,检查每个字符并计数,复制一份map,check函数:检查字符w是否出现在map中,(map.has(i) && map.get(i) > 0),出现则map中的次数减一
var countCharacters = function(words, chars){
let map = new Map()
let count = 0
for(let c of chars){
map.set(c, map.has(c)? map.get(c)+1: 1)
}
for(let w of words){
if(check(w, new Map(map))){
count += w.length
}
}
return count
};
function check(w, map){
for(let i of w){
if(map.has(i) && map.get(i) > 0){
map.set(i, map.get(i)-1)
}else{
return false
}
}
return true
}
6. Leetcode 836. 矩形重叠
**思路:**初次根据两个矩形的左下角坐标判断两矩形的相对位置,接下来我的说法也是将矩形当做点来看待,一共有四种情况,在每种情况下,判断圈中的点与矩形1中点的位置关系,比如当矩形2在第二象限时,判断矩形2的右下角点A与矩形1的左上角点B的位置关系,如果A在B的右下方,两矩形重叠输出true,否则返回false,请看cc的抽象派手绘图
思路确定之后,就是各种暴力的判断了:
var isRetangleOverlap = function(rec1, rec2){
//判断相对位置,比较每个位置上对应的两点
if(rec1[0] < rec2[0] && rec1[1] < rec2[1]){
// 第一象限
return rec1[2] > rec2[0] && rec1[3] > rec2[1]
}
else if(rec1[0] > rec2[0] && rec1[1] < rec2[1]){
// 第二象限
return rec1[0] < rec2[2] && rec1[3] > rec2[1]
}
else if(rec1[0] > rec2[0] && rec1[1] > rec2[1]){
// 第三象限
return rec1[0] < rec2[2] && rec1[1] < rec2[3]
}
else{
// 第四象限
return rec1[2] > rec2[0] && rec1[1] < rec2[3]
}
return false
}
这个思路不算复杂,但代码看起来非常的难缠,有没有更简便的方法呢,围观了大佬的做法
思路二:在一维的情况下,如果判断两个线段是否相互重叠,例如[l1,r1]
和 [l2,r2]
,如果两线段重叠的话,必有max(l1,l2) < min(r1,r2)
同样,扩展到二维的情况下,我们不直接比较两个矩形,而是分别比较两个矩形在x轴和y轴上的投影线段,如果两轴上的投影线段都重合,那说明两个矩形必定垂直。两矩形在x轴上的投影线段分别为[rec1[0], rec1[2]]
和[rec2[0], rec2[2]]
,在y轴上的投影线段分别为[rec1[1], rec1[3]]
和[rec2[1], rec2[3]]
var isRectangleOverlap = function(rec1, rec2){
return (Math.max(rec1[0],rec2[0]) < Math.min(rec1[2],rec2[2]))&& (Math.max(rec1[1],rec2[1]) < Math.min(rec1[3],rec2[3]))
}
大佬就是大佬! 某人判断半天的语句,大佬一行代码return!流下了没技术的泪水
7.Leetcode 409.最长回文串
思路: 利用Hash表统计字符串中每个字符出现的次数cnt,使用数组存放提高效率,若出现的次数为偶数,res +=cnt
; 若出现的次数为奇数, len += cnt-1
, 最后如果回文串长度小于总字符串长度res < s.length
,说明可以加上一个字母放在回文串正中央,return res + 1
var longestPalindrome = function(s){
if(s.length === 0) return 0
s = s.split('') // 将字符串划分为Array
let counts = new Array(58).fill(0) // A是65,a是97
let res = 0
s.filter(item => {
counts[(item.charCodeAt()-65)] ++
})
for(let i = 0 ; i < counts.length && counts[i] > 0; i++){
res += counts[i]%2 ? counts[i]-1 : counts[i]
}
return res < s.length ? res+1: res
}
8.Leetcode 118.杨辉三角
思路: 两层循环即可,每一行数据的首尾部放1,其余位置元素为arr[i][j] = arr[i-1][j-1]+arr[i-1][j]
var generate = function(numRows) {
let resArr = []
if(numRows <= 0) return resArr
for(let i = 0; i < numRows; i++){
let row = []
for(let j = 0; j < i; j ++){
if(j === 0 || j === i-1){
row.push(1)
continue
}
row.push(resArr[i-1][j-1] + resArr[i-1][j])
}
resArr.push(row)
}
return resArr
}
9.Leetcode 119.杨辉三角 II
思路: 和上面的差距就在于直接输出第k行的结果,可以直接用上面的办法,令numRows = k,输出第k行的row即可
var getRow = function(rowIndex){
let res = []
for(let i = 0; i < rowIndex; i++){
res.push(1)
for(let j = i; j > 0; j--){
res[j] += res[j-1]
}
}
res.push(1)
return res
}
但是相比动态更新上面每一层的方法O(n*n)
,有没有办法可以优化算法的复杂度到O(k) 有的有的
利用递推公式,学过组合数学的同学一定非常清楚了,杨辉三角中的每层中的每一项都可以看做是一个组合数列,如图:
因此就可以使用递推公式,逐项通过递推关系求解第k行的数值,递推公式为C(n,k) = C(n, n-k) * (n-k+1) / k!
和C(n,k) / C(n,k-1) = (n - k +1) / k
var getRow = function(rowIndex){
let res = [1]
if(rowIndex === 0) return res
let value = 1
for(let i = 1; i <= rowIndex; i++){
res[i] = value * (rowIndex - i + 1) / i
value = res[i]
}
return res
}
10. 牛客美团面试题——数组的前置和与后置和相等的子数组的个数
题目: 一个数组x[],数组每一个元素都大于0,称x[0] + …+ x[i]为前置和,而x[j] + … + x[n-1]为后置和,写一个程序,求x有多少相同的前置和后置和。
示例 :[1, 2, 5,1, 8, 9, 7, 1] 前置[1,2,5] = 后置[1,7] ,即找到类似这样的子数组的个数。
思路: 在牛客面经里看到的,应该是双指针吧,然后计算前置和后置数组的值,由于数组都是正数,left < right
, 左边指针右滑,left > right
时,右边指针左滑,left = right时,个数+1
var findEqualArray = function(nums){
if(nums.length <= 1) return 0
let cnt = 0
let i = 0, j = nums.length-1
let left = num[i], right = nums[j]
while(i < j){
if(left === right){
cnt ++
}else if(left < right){
i++
left += nums[i]
}else{
j--
right += nums[j]
}
}
return cnt
}
最近要开始各种笔试面试了,加油啊!冲冲冲