首頁目錄 點(diǎn)擊查看
第一題：
- 難度：簡單
- 題目： 1.兩數(shù)之和
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)敢会，并返回他們的數(shù)組下標(biāo)底扳。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案魄梯。但是颖杏，數(shù)組中同一個(gè)元素不能使用兩遍。
解題思路
我首先想到遍歷數(shù)組兩次的方法左腔，找到num[j] = traget - num[i]铃剔，保存后輸出兩個(gè)index.
我的答案
- 兩個(gè)for循環(huán)
var twoSum = function (nums, target) {
for (let i = 0; i <= nums.length - 1; i++) {
for (let j = i + 1; j <= nums.length - 1; j++) {
if (nums[i] === target - nums[j]) {
return [ i, j]
break
}
}
}
};
- 時(shí)間復(fù)雜度：O(N2)
-
空間復(fù)雜度： O(N)
這明顯不是最好的解決方案，就憑這兩個(gè)for循環(huán)就很拉胯
image.png
當(dāng)然我也想出了另外一種方案析恢，只需要一個(gè)for循環(huán)墨坚，用一個(gè)對(duì)象角標(biāo)來保存目標(biāo)數(shù)值： 這種方法從時(shí)間復(fù)雜度上只需要O(N)
var twoSum = function (nums, target) {
let useNum = {}
for (let i = 0; i <= nums.length - 1; i++) {
const currentNum = nums[i];
const targetNum = target - currentNum;
const targetIndex = useNum[targetNum]
if (targetIndex !== undefined) {
return [targetIndex, i]
break
}
useNum[currentNum] = i
}
};
- 時(shí)間復(fù)雜度：O(N)
-
空間復(fù)雜度： O(N)
結(jié)果
第二題
- 難度：中等
- 題目：763. 劃分字母區(qū)間
字符串 S 由小寫字母組成。我們要把這個(gè)字符串劃分為盡可能多的片段映挂，同一個(gè)字母只會(huì)出現(xiàn)在其中的一個(gè)片段泽篮。返回一個(gè)表示每個(gè)字符串片段的長度的列表盗尸。
示例
輸入：S = "ababcbacadefegdehijhklij"
輸出：[9,7,8]
解釋：
劃分結(jié)果為 "ababcbaca", "defegde", "hijhklij"。
每個(gè)字母最多出現(xiàn)在一個(gè)片段中帽撑。
像 "ababcbacadefegde", "hijhklij" 的劃分是錯(cuò)誤的泼各，因?yàn)閯澐值钠螖?shù)較少。
解題思路
- 這道題雖然標(biāo)簽是貪心算法和雙指針亏拉，想了一下還是只能想出用hash處理扣蜻。所以這里把他放到hash相關(guān)來
我的答案
var partitionLabels = function (S) {
let map = {}
let arr = []
let start = 0
for (let i = 0; i <= S.length - 1; i++) {
map[S[i]] = i;
}
let splitIndex = 0;
for (let i = 0; i <= S.length; i++) {
let lastIndex = map[S[i]];
splitIndex = Math.max(splitIndex, lastIndex);
if (i === splitIndex) {
arr.push(i - start + 1);
start = i + 1
}
}
return arr
};
image.png
第三題
- 難度：中等
- 題目：49. 字母異位詞分組
給定一個(gè)字符串?dāng)?shù)組，將字母異位詞組合在一起专筷。字母異位詞指字母相同弱贼，但排列不同的字符串。
示例
輸入: ["eat", "tea", "tan", "ate", "nat", "bat"]
輸出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
解題思路
- 這道題需要把每個(gè)單獨(dú)的字符串進(jìn)行排序然后用map對(duì)象hash存儲(chǔ)磷蛹，如果相同的則都放在數(shù)組里面吮旅，最后輸出數(shù)組
我的答案
var groupAnagrams = function (strs) {
let map = {};
let array = []
for (let i = 0; i <= strs.length - 1; i++) {
let sortStr = strs[i].split("").sort((a, b) => {
return a > b ? 1 : -1
}).join("")
!map[sortStr] && (map[sortStr] = []);
map[sortStr].push(strs[i])
}
for (let i in map) {
array.push(map[i])
}
return array
};
image.png
第四題
- 難度：簡單
- 題目：242. 有效的字母異位詞
給定兩個(gè)字符串 s 和 t ，編寫一個(gè)函數(shù)來判斷 t 是否是 s 的字母異位詞味咳。
示例
輸入: s = "anagram", t = "nagaram"
輸出: true
輸入: s = "rat", t = "car"
輸出: false
解題思路
- 這道題最簡單的解法是把兩個(gè)字符排序然后作比較庇勃，但是性能不太好，看了題解槽驶，而且這道題本來是用hash來做责嚷，前面那樣就不算hash解法，所以有了第二個(gè)解法掂铐。
我的答案
- 排序
var isAnagram = function (s, t) {
let sStr = s.split("").sort((a, b) => {
return a > b ? 1 : -1
}).join("");
let tStr = t.split("").sort((a, b) => {
return a > b ? 1 : -1
}).join("");
return sStr === tStr
};
image.png
- hash
var isAnagram = function (s, t) {
if (s.length !== t.length) {
return false
}
let hash = new Array(26).fill(0);
let codeA = "a".charCodeAt()
for (let i = 0; i <= s.length - 1; i++) {
hash[s.charCodeAt(i) - codeA]++;
hash[t.charCodeAt(i) - codeA]--;
}
for (let i in hash) {
if (hash[i]) {
return false
}
}
return true
};
image.png
第五題
- 難度：簡單
- 題目：204. 計(jì)數(shù)質(zhì)數(shù)
統(tǒng)計(jì)所有小于非負(fù)整數(shù) n 的質(zhì)數(shù)的數(shù)量罕拂。
示例
輸入：n = 10
輸出：4
解釋：小于 10 的質(zhì)數(shù)一共有 4 個(gè), 它們是 2, 3, 5, 7 。
輸入：n = 0
輸出：0
解題思路
-
這道題我能想到的是暴力算法全陨，但是暴力算法直接超時(shí)了爆班，所以得對(duì)暴力遍歷進(jìn)行優(yōu)化，比如對(duì)于偶數(shù)直接跳過即可辱姨。但這明顯不是最優(yōu)解柿菩，時(shí)間都達(dá)到500多MS了，只是內(nèi)存占用較少雨涛，看了題解發(fā)現(xiàn)了厄拉多塞篩法枢舶，這個(gè)方法非常高效。
image.png
對(duì)此替久，我們可以聲明一個(gè)長度為最大限制數(shù)的布爾數(shù)組凉泄。用布爾值來區(qū)別篩選出的數(shù)和質(zhì)數(shù)。
我的答案
var countPrimes = function (n) {
if (n < 3) {
return 0
}
let num = 1;
for (let i = 3; i <= n - 1; i++) {
if (i % 2 == 0) //過濾掉偶數(shù)蚯根，2 因?yàn)槟J(rèn)num就是1了所以也算在其中了旧困。
continue;;
let flag = true
for (let j = 3; j * j <= i; j += 2) {
if (i % j === 0) {
flag = false
break;
}
}
if (flag) {
num += 1
}
}
return num
};
image.png
- 厄拉多塞篩法
var countPrimes = function (n) {
let num = 0;
let map = new Array(n).fill(false);
for (let i = 2; i <= n - 1; i++) {
if (!map[i]) {
num += 1;
for (let j = i + i; j <= n - 1; j += i) {
map[j] = true
}
}
}
return num
}
image.png
第六題
- 難度：中等
- 題目：299. 猜數(shù)字游戲
你在和朋友一起玩 猜數(shù)字（Bulls and Cows）游戲，該游戲規(guī)則如下：
你寫出一個(gè)秘密數(shù)字稼锅，并請(qǐng)朋友猜這個(gè)數(shù)字是多少吼具。
朋友每猜測(cè)一次，你就會(huì)給他一個(gè)提示矩距，告訴他的猜測(cè)數(shù)字中有多少位屬于數(shù)字和確切位置都猜對(duì)了（稱為“Bulls”, 公牛）拗盒，有多少位屬于數(shù)字猜對(duì)了但是位置不對(duì)（稱為“Cows”, 奶牛）。
朋友根據(jù)提示繼續(xù)猜锥债，直到猜出秘密數(shù)字陡蝇。
請(qǐng)寫出一個(gè)根據(jù)秘密數(shù)字和朋友的猜測(cè)數(shù)返回提示的函數(shù)，返回字符串的格式為 xAyB 哮肚，x 和 y 都是數(shù)字登夫，A 表示公牛乾蛤，用 B 表示奶牛狈茉。
xA 表示有 x 位數(shù)字出現(xiàn)在秘密數(shù)字中，且位置都與秘密數(shù)字一致企孩。
yB 表示有 y 位數(shù)字出現(xiàn)在秘密數(shù)字中潮剪，但位置與秘密數(shù)字不一致涣楷。
請(qǐng)注意秘密數(shù)字和朋友的猜測(cè)數(shù)都可能含有重復(fù)數(shù)字，每位數(shù)字只能統(tǒng)計(jì)一次抗碰。
示例
輸入: secret = "1807", guess = "7810"
輸出: "1A3B"
解釋: 1 公牛和 3 奶牛狮斗。公牛是 8，奶牛是 0, 1 和 7弧蝇。
輸入: secret = "1123", guess = "0111"
輸出: "1A1B"
解釋: 朋友猜測(cè)數(shù)中的第一個(gè) 1 是公牛碳褒，第二個(gè)或第三個(gè) 1 可被視為奶牛。
解題思路
- 這道題公牛很好判斷看疗，一個(gè)for循環(huán)相同位置相等的即為公牛沙峻，奶牛比較麻煩，就需要兩個(gè)map對(duì)象來存儲(chǔ)當(dāng)前出現(xiàn)的數(shù)字次數(shù)鹃觉，最后比較兩者之間相同的數(shù)字最少出現(xiàn)的次數(shù)就為奶牛专酗。
我的答案
var getHint = function (secret, guess) {
let ANum = 0;
let BNum = 0;
let mapS = {};
let mapG = {}
for (let i = 0; i <= secret.length - 1; i++) {
if (secret[i] === guess[i]) {
ANum += 1
} else {
!mapS[secret[i]] && (mapS[secret[i]] = 0);
!mapG[guess[i]] && (mapG[guess[i]] = 0);
mapS[secret[i]] += 1;
mapG[guess[i]] += 1;
}
}
for (let i in mapG) {
if (mapS[i]) {
BNum += Math.min(mapS[i], mapG[i])
}
}
return ANum + "A" + BNum + "B"
};
image.png
第七題
- 難度：中等
- 題目： 554. 磚墻
你的面前有一堵矩形的、由多行磚塊組成的磚墻盗扇。 這些磚塊高度相同但是寬度不同祷肯。你現(xiàn)在要畫一條自頂向下的、穿過最少磚塊的垂線疗隶。
磚墻由行的列表表示佑笋。 每一行都是一個(gè)代表從左至右每塊磚的寬度的整數(shù)列表。
如果你畫的線只是從磚塊的邊緣經(jīng)過斑鼻，就不算穿過這塊磚蒋纬。你需要找出怎樣畫才能使這條線穿過的磚塊數(shù)量最少，并且返回穿過的磚塊數(shù)量。
你不能沿著墻的兩個(gè)垂直邊緣之一畫線蜀备，這樣顯然是沒有穿過一塊磚的关摇。
示例
輸入: [[1,2,2,1],
[3,1,2],
[1,3,2],
[2,4],
[3,1,2],
[1,3,1,1]]
輸出: 2
解釋:
解題思路
- 這道題很簡單，只需要依次把每一行的數(shù)加起來碾阁，然后統(tǒng)計(jì)每一行某個(gè)和出現(xiàn)的次數(shù)输虱，最多的那個(gè)數(shù)字就是沒穿過的，穿過的就是數(shù)組長度減去出現(xiàn)最多的數(shù)字脂凶。
我的答案
var leastBricks = function (wall) {
let map = {}
let max = 0
for (let i = 0; i <= wall.length - 1; i++) {
let sum = 0
for (let j = 0; j < wall[i].length - 1; j++) {
sum += wall[i][j]
!map[sum] && (map[sum] = 0);
map[sum] += 1
max = Math.max(map[sum], max)
}
}
return wall.length - max
};
image.png
第八題
- 難度：中等
- 題目：974. 和可被 K 整除的子數(shù)組
給定一個(gè)整數(shù)數(shù)組 A宪睹，返回其中元素之和可被 K 整除的（連續(xù)、非空）子數(shù)組的數(shù)目蚕钦。
示例
輸入：A = [4,5,0,-2,-3,1], K = 5
輸出：7
解釋：
有 7 個(gè)子數(shù)組滿足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
解題思路
- 這里只需要每個(gè)數(shù)組元素的和是5的倍數(shù)就可以亭病，但是可能會(huì)出現(xiàn)0的情況，所以就在加一個(gè)5就可以把0的情況包含進(jìn)去嘶居，于是...
我的答案
var subarraysDivByK = function (A, K) {
let sum = 0;
let result = 0;
let map = new Array(K).fill(0)
for (let i = 0; i <= A.length - 1; i++) {
sum += A[i];
let num = (sum % K + K) % K
if (num === 0) result++
result += map[num]
map[num] += 1;
}
return result
};
