首頁目錄 點(diǎn)擊查看
第一題
- 難度：中等
- 題目：3. 無重復(fù)字符的最長子串
給定一個(gè)字符串磨取，請(qǐng)你找出其中不含有重復(fù)字符的 最長子串 的長度赂摆。
示例
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"，所以其長度為 3。
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"甥雕，所以其長度為 1贬堵。
解題思路
-
這道理我想了好久啊招驴，都覺得沒有很好地方式可以處理腹鹉，看了一個(gè)大神的解題思路，我豁然開朗怔蚌，貼出來
使用一個(gè)數(shù)組來維護(hù)滑動(dòng)窗口
遍歷字符串巩步，判斷字符是否在滑動(dòng)窗口數(shù)組里不在則 push 進(jìn)數(shù)組
在則刪除滑動(dòng)窗口數(shù)組里相同字符及相同字符前的字符，然后將當(dāng)前字符 push 進(jìn)數(shù)組
然后將 max 更新為當(dāng)前最長子串的長度
遍歷完桦踊，返回 max 即可
image.png
我的答案
根據(jù)以上思路渗钉，答案就很容易寫出來了
var lengthOfLongestSubstring = function (s) {
let max = 0,
array = [];
for (let i = 0; i <= s.length - 1; i++) {
let index = array.indexOf(s[i])
if (index !== -1) {
array.splice(0, index + 1)
}
array.push(s[i])
max = Math.max(array.length, max)
}
return max
};
image.png
- 時(shí)間復(fù)雜度：O(N)
- 空間復(fù)雜度： O(N)
高分答案
除了以上的維護(hù)數(shù)組的方法，還有另外兩種解題思路钞钙，維護(hù)下標(biāo)以及優(yōu)化map
//維護(hù)下標(biāo)
var lengthOfLongestSubstring = function(s) {
let index = 0, max = 0
for(let i = 0, j = 0; j < s.length; j++) {
index = s.substring(i, j).indexOf(s[j])
if(index !== -1) {
i = i + index + 1
}
max = Math.max(max, j - i + 1)
}
return max
};
//優(yōu)化Map
var lengthOfLongestSubstring = function(s) {
let map = new Map(), max = 0
for(let i = 0, j = 0; j < s.length; j++) {
if(map.has(s[j])) {
i = Math.max(map.get(s[j]) + 1, i)
}
max = Math.max(max, j - i + 1)
map.set(s[j], j)
}
return max
};
這兩個(gè)的性能都差不多鳄橘，稍微比我的第一種要好一點(diǎn)，在內(nèi)存消耗上優(yōu)勢(shì)更加明顯芒炼。
image.png
第二題
- 難度：中等
- 題目：11. 盛最多水的容器
給你 n 個(gè)非負(fù)整數(shù) a1运提，a2觅丰，...膝藕，an亭饵，每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn) (i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線子寓，垂直線 i 的兩個(gè)端點(diǎn)分別為 (i, ai) 和 (i, 0)暗挑。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水斜友。
說明：你不能傾斜容器炸裆，且 n 的值至少為 2。
image
圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]鲜屏。在此情況下烹看，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。
示例：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解題思路
- 簡(jiǎn)單粗暴雙循環(huán)洛史，遍歷數(shù)組惯殊，挨個(gè)去比較
- 雙指針 效率更高,定義兩個(gè)角標(biāo)i,j 根據(jù)數(shù)值的大小動(dòng)態(tài)改變i,j的值，直到把數(shù)組數(shù)值都比較一遍也殖。
我的答案
- 簡(jiǎn)單粗暴雙循環(huán)
let area = 0,
carea = 0;
for (let i = 0; i <= height.length - 1; i++) {
for (let j = i + 1; j <= height.length - 1; j++) {
carea = Math.min(height[i], height[j]) * (j - i)
if (area <= carea) {
area = carea
}
}
}
return area
時(shí)間復(fù)雜度：O(N2)
-
空間復(fù)雜度： O(N)
image.png 雙指針
let area = 0,
carea = 0,
i = 0,
j = height.length - 1;
while (i < j) {
carea = Math.min(height[i], height[j]) * (j - i)
if (area <= carea) {
area = carea
}
if (height[i] < height[j]) {
i++
} else {
j--
}
}
return area
- 時(shí)間復(fù)雜度：O(N)
-
空間復(fù)雜度： O(N)
image.png
這兩者的性能差距實(shí)在是太大了土思，所以還是推薦雙指針吧。
第三題
- 難度：中等
- 題目： 15. 三數(shù)之和
給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a己儒，b崎岂，c ，使得 a + b + c = 0 址愿？請(qǐng)你找出所有滿足條件且不重復(fù)的三元組该镣。
注意：答案中不可以包含重復(fù)的三元組冻璃。
示例
給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]响谓，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]
解題思路
雙指針的做法，首先對(duì)數(shù)組進(jìn)行排序省艳，如果第一個(gè)數(shù)大于零則直接返回空娘纷，遍歷整個(gè)數(shù)組，如果當(dāng)前的nums[i] ===nums[i + 1] 則直接continue跋炕，沒必要浪費(fèi)時(shí)間赖晶，設(shè)置left=i+1、right = nums.length-1 當(dāng)left <right辐烂，判斷nums[i] + nums[left] + nums[right]遏插，如果和大于零，則減小right 反之增大left纠修，如果相等胳嘲，保存數(shù)值，也要判斷left和right的上一位和下一位是否相等扣草，如果相等則直接進(jìn)行下一個(gè)了牛。
我的答案
var threeSum = function (nums) {
let array = []
nums.sort((a, b) => {
return a - b
})
if (nums[0] > 0) {
return array
}
for (let i = 0; i <= nums.length - 1&& nums[i] <=0; i++) {
let left = i + 1;
let right = nums.length - 1
if (nums[i] == nums[i - 1]) continue; // 去重
while (left < right) {
let sum = nums[i] + nums[left] + nums[right]
if (sum < 0) {
left++
}
if (sum > 0) {
right--
}
if (sum === 0) {
array.push([nums[left], nums[right], nums[i]])
while (left < right && nums[left] == nums[left + 1]) left++; // 去重
while (left < right && nums[right] == nums[right - 1]) right--; // 去重
left++;
right--
}
}
}
return array
};
image.png
第四題
- 難度：中等
- 題目： 16. 最接近的三數(shù)之和
給定一個(gè)包括 n 個(gè)整數(shù)的數(shù)組 nums 和 一個(gè)目標(biāo)值 target。找出 nums 中的三個(gè)整數(shù)辰妙，使得它們的和與 target 最接近鹰祸。返回這三個(gè)數(shù)的和。假定每組輸入只存在唯一答案密浑。
示例
輸入：nums = [-1,2,1,-4], target = 1
輸出：2
解釋：與 target 最接近的和是 2 (-1 + 2 + 1 = 2) 蛙婴。
解題思路
- 這道題的解題思路和之前的的三數(shù)之和很類似，相當(dāng)于之前的相加等于0尔破，現(xiàn)在改為任意數(shù)字敬锐，然后加一個(gè)判斷是否和是和目標(biāo)最接近的。
我的答案
var threeSumClosest = function (nums, target) {
let dis = null,
result = 0;
nums.sort((a, b) => {
return a - b
})
for (let i = 0; i <= nums.length - 1; i++) {
let left = i + 1;
let right = nums.length - 1
if (nums[i] == nums[i - 1]) continue; // 去重
while (left < right) {
let sum = nums[i] + nums[left] + nums[right]
let current = Math.abs(target - sum)
if (dis > current) {
dis = current
result = sum
}
if (dis === null) {
dis = current
result = sum
}
if (sum > target) {
right--
}
if (sum < target) {
left++
}
if (sum - target === 0) {
return sum
}
}
}
return result
};
image.png
第五題
- 難度：簡(jiǎn)單
- 題目：26. 刪除排序數(shù)組中的重復(fù)項(xiàng)
給定一個(gè)排序數(shù)組呆瞻，你需要在 原地 刪除重復(fù)出現(xiàn)的元素台夺，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長度痴脾。
不要使用額外的數(shù)組空間颤介，你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成。
示例：
給定數(shù)組 nums = [1,1,2],
函數(shù)應(yīng)該返回新的長度 2, 并且原數(shù)組 nums 的前兩個(gè)元素被修改為 1, 2。
你不需要考慮數(shù)組中超出新長度后面的元素滚朵。
給定 nums = [0,0,1,1,1,2,2,3,3,4],
函數(shù)應(yīng)該返回新的長度 5, 并且原數(shù)組 nums 的前五個(gè)元素被修改為 0, 1, 2, 3, 4冤灾。
你不需要考慮數(shù)組中超出新長度后面的元素。
說明：
為什么返回?cái)?shù)值是整數(shù)辕近，但輸出的答案是數(shù)組呢?
請(qǐng)注意韵吨，輸入數(shù)組是以「引用」方式傳遞的，這意味著在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的移宅。
你可以想象內(nèi)部操作如下:
// nums 是以“引用”方式傳遞的归粉。也就是說，不對(duì)實(shí)參做任何拷貝
int len = removeDuplicates(nums);
// 在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的漏峰。
// 根據(jù)你的函數(shù)返回的長度, 它會(huì)打印出數(shù)組中該長度范圍內(nèi)的所有元素糠悼。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
解題思路
- 裁剪數(shù)組
這道題可以倒著遍歷數(shù)組，創(chuàng)建一個(gè)last用于存放數(shù)組最后一個(gè)數(shù)浅乔，用當(dāng)前遍歷到的數(shù)和last對(duì)比倔喂，如果不等于last則把當(dāng)前數(shù)賦值給last，否則說明兩數(shù)相等靖苇，刪除當(dāng)前數(shù)值席噩。 - 雙指針
這里雙指針的方法，和之前不太一樣贤壁，right不是從最后一個(gè)數(shù)開始悼枢，而是從left下一位開始，比較兩數(shù)大小芯砸，如果兩者不相等萧芙，則將right的值賦值給left的下一位。
我的答案
- 裁剪數(shù)組
var removeDuplicates = function (nums) {
let last = nums[nums.length] - 1;
for (let i = nums.length - 1; i >= 0; i--) {
if (nums[i] !== last) {
last = nums[i]
} else {
nums.splice(i, 1)
}
}
return nums.length
};
console.log(removeDuplicates([1, 1, 2, 2, 3, 3, 4, 5, 6]))
image.png
- 雙指針
var removeDuplicates = function (nums) {
let i = 0;
let j = 1;
while (j < nums.length) {
if (nums[i] !== nums[j]) {
nums[++i] = nums[j]
}
j++
}
return i + 1
};
console.log(removeDuplicates([1, 1, 2, 2, 3, 3, 4, 5, 6]))
image.png
這兩種方法比較極端啊假丧，一個(gè)內(nèi)存消耗低双揪，一個(gè)執(zhí)行時(shí)間短，各有所長包帚，不過我更覺得雙指針更好
第六題
- 難度：中等
- 題目：75. 顏色分類
給定一個(gè)包含紅色渔期、白色和藍(lán)色，一共 n 個(gè)元素的數(shù)組渴邦，原地對(duì)它們進(jìn)行排序疯趟，使得相同顏色的元素相鄰，并按照紅色谋梭、白色信峻、藍(lán)色順序排列。
此題中瓮床，我們使用整數(shù) 0盹舞、 1 和 2 分別表示紅色产镐、白色和藍(lán)色。
注意:
不能使用代碼庫中的排序函數(shù)來解決這道題踢步。
示例
輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]
進(jìn)階
一個(gè)直觀的解決方案是使用計(jì)數(shù)排序的兩趟掃描算法癣亚。
首先，迭代計(jì)算出0获印、1 和 2 元素的個(gè)數(shù)述雾，然后按照0、1兼丰、2的排序玻孟，重寫當(dāng)前數(shù)組。
你能想出一個(gè)僅使用常數(shù)空間的一趟掃描算法嗎地粪？
解題思路
- 這道題因?yàn)楸緛砭蛯儆陔p指針的題目取募，所以理所當(dāng)然就使用雙指針琐谤，只是這里蟆技，單純的雙指針明顯是不夠用的，所以這里需要添加一個(gè)current斗忌，表示當(dāng)前的數(shù)值index质礼。
- 另外一個(gè)方法是看了題解，遇到0就刪除該元素织阳，放到最前面眶蕉，遇到2就刪除該元素，放到最后面唧躲，遇到1不處理
我的答案
- 操作刪除元素
var sortColors = function (nums) {
let index = 0;
let count = 0;
while (count < nums.length) {
if (nums[index] === 0) {
nums.splice(index, 1)
nums.unshift(0)
index++
} else if (nums[index] === 2) {
nums.splice(index, 1)
nums.push(2)
} else {
index++
}
count++
}
return nums
};
image.png
- 雙指針
var sortColors = function (nums) {
let left = 0;
let right = nums.length - 1;
let current = 0
while (current <= right) {
if (nums[current] === 0) {
[nums[current], nums[left]] = [nums[left], nums[current]];
left++
current++
continue;
} else if (nums[current] === 2) {
[nums[current], nums[right]] = [nums[right], nums[current]];
right--
continue;
} else {
current++
continue;
}
}
return nums
};
image.png
雙指針的性能和直接操作元素的差距還是比較明顯的造挽。
第七題
- 難度：中等
- 題目：209. 長度最小的子數(shù)組
給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的長度最小的 連續(xù) 子數(shù)組弄痹，并返回其長度饭入。如果不存在符合條件的子數(shù)組，返回 0肛真。
示例
輸入：s = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組谐丢。
解題思路
- 這道題的解題思路就是滑動(dòng)窗口，先擴(kuò)大搜索范圍蚓让，找到合適的區(qū)域乾忱，然后再縮小區(qū)域，找出最合適的解历极。
我的答案
var minSubArrayLen = function (s, nums) {
let minLen = Infinity;
let left = 0;
let right = 0;
let sum = 0;
while (right < nums.length ) {
sum += nums[right]
while (sum >= s) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left]
left++
}
right++
}
return minLen === Infinity ? 0 : minLen
};
image.png
第八題
- 難度：中等
- 題目：80. 刪除排序數(shù)組中的重復(fù)項(xiàng) II
給定一個(gè)排序數(shù)組窄瘟，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素最多出現(xiàn)兩次趟卸，返回移除后數(shù)組的新長度蹄葱。
不要使用額外的數(shù)組空間纲酗，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。
示例
給定 nums = [1,1,1,2,2,3],
函數(shù)應(yīng)返回新長度 length = 5, 并且原數(shù)組的前五個(gè)元素被修改為 1, 1, 2, 2, 3 新蟆。
你不需要考慮數(shù)組中超出新長度后面的元素觅赊。
給定 nums = [0,0,1,1,1,1,2,3,3],
函數(shù)應(yīng)返回新長度 length = 7, 并且原數(shù)組的前五個(gè)元素被修改為 0, 0, 1, 1, 2, 3, 3 。
你不需要考慮數(shù)組中超出新長度后面的元素琼稻。
為什么返回?cái)?shù)值是整數(shù)吮螺，但輸出的答案是數(shù)組呢?
請(qǐng)注意，輸入數(shù)組是以“引用”方式傳遞的帕翻，這意味著在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的鸠补。
你可以想象內(nèi)部操作如下:
// nums 是以“引用”方式傳遞的。也就是說嘀掸，不對(duì)實(shí)參做任何拷貝
int len = removeDuplicates(nums);
// 在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的紫岩。
// 根據(jù)你的函數(shù)返回的長度, 它會(huì)打印出數(shù)組中該長度范圍內(nèi)的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
解題思路
- 這道題和 26. 刪除排序數(shù)組中的重復(fù)項(xiàng)非常類似睬塌，只需要把+1改為+2就是答案泉蝌，但是這個(gè)答案的效率看了一下并不是很高，所以看了一下題解揩晴，看到一個(gè)大哥的答案勋陪，覺得解題思路很厲害，貼出來
我的答案
- 26題改
var removeDuplicates = function (nums) {
let index = 0;
let pass = 0;
while (index + pass <= nums.length - 1) {
let current = nums[index + pass + 2];
if (current === nums[index]) {
pass++
} else {
index++;
[nums[index], nums[index + pass]] = [nums[index + pass], nums[index]]
}
}
return index
};
image.png
- 空間O(1)
var removeDuplicates = function (nums) {
let index = 0;
for (let i = 0; i <= nums.length - 1; i++) {
if (index < 2 || nums[i] > nums[index - 2]) {
nums[index++] = nums[i];
}
}
return index
};
image.png
