LeetCode刷題總結(jié)1
1.數(shù)字題
1.1 第一類(lèi)
1.1.1 整數(shù)反轉(zhuǎn)
給出一個(gè) 32 位的有符號(hào)整數(shù)昭伸，你需要將這個(gè)整數(shù)中每位上的數(shù)字進(jìn)行反轉(zhuǎn)。
示例 1:
輸入: 123
輸出: 321
示例 2:
輸入: -123
輸出: -321
示例 3:
輸入: 120
輸出: 21
代碼：
func reverse(x int)int{
var result int64
for x!=0{
result=result*10+int64(x%10)
x=x/10
}
if result>math.MaxInt32||result<math.MinInt32{
return 0
}
return int(result)
}
1.1.2 回文數(shù)
判斷一個(gè)整數(shù)是否是回文數(shù)寞蚌≈樵觯回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)杂拨。
示例 1:
輸入: 121
輸出: true
示例 2:
輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 。 從右向左讀, 為 121- 补胚。因此它不是一個(gè)回文數(shù)码耐。
示例 3:
輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 。因此它不是一個(gè)回文數(shù)溶其。
代碼：
func isPalindrome(x int)bool{
if x<0||(x%10==0&&x!=0){
return false
}
var result int
for x>result{
result=result*10+x%10
x=x/10
}
result (x==result)||(x==result/10)
}
1.1.3 x的平方根
實(shí)現(xiàn) int sqrt(int x) 函數(shù)骚腥。
計(jì)算并返回 x 的平方根，其中 x 是非負(fù)整數(shù)瓶逃。
由于返回類(lèi)型是整數(shù)束铭，結(jié)果只保留整數(shù)的部分，小數(shù)部分將被舍去厢绝。
示例 1:
輸入: 4
輸出: 2
示例 2:
輸入: 8
輸出: 2
說(shuō)明: 8 的平方根是 2.82842...,
由于返回類(lèi)型是整數(shù)契沫，小數(shù)部分將被舍去。
代碼：
func sqrt(x int)int{
if x==0{
return 0
}
n:=x
for n*n>x{
n=(n+x/n)/2
}
return n
}
1.1.4 Execl表列名稱(chēng)
給定一個(gè)正整數(shù)昔汉，返回它在 Excel 表中相對(duì)應(yīng)的列名稱(chēng)懈万。
例如，
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
...
示例 1:
輸入: 1
輸出: "A"
示例 2:
輸入: 28
輸出: "AB"
示例 3:
輸入: 701
輸出: "ZY"
代碼：
func convertToTitle(n int)string{
hash:=[26]string{}
for i:=0;i<26;i++{
hash[i]=string('A'+i)
}
ans:=""
for n!=0{
t:=(n-1)%26
ans=hash[t]+ans
n=(n-1)/26
}
return ans
}
1.1.5 Excel表列序號(hào)
給定一個(gè)Excel表格中的列名稱(chēng)靶病，返回其相應(yīng)的列序號(hào)会通。
例如，
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
示例 1:
輸入: "A"
輸出: 1
示例 2:
輸入: "AB"
輸出: 28
示例 3:
輸入: "ZY"
輸出: 701
代碼：
func titleToNumber(s string)int{
ans:=0
for _,x:=range s{
t:=int(x-'A')+1
ans=ans*26+t
}
return ans
}
1.1.6 各位相加
給定一個(gè)非負(fù)整數(shù) num娄周，反復(fù)將各個(gè)位上的數(shù)字相加涕侈，直到結(jié)果為一位數(shù)。
示例:
輸入: 38
輸出: 2
解釋: 各位相加的過(guò)程為：3 + 8 = 11, 1 + 1 = 2煤辨。 由于 2 是一位數(shù)驾凶，所以返回 2。
代碼：
func addDigits(num int)int{
for num>9{
sum:=0
for num!=0{
sum+=num%10
num/=10
}
num=sum
}
return num
}
1.1.7 丑數(shù)
編寫(xiě)一個(gè)程序判斷給定的數(shù)是否為丑數(shù)掷酗。
丑數(shù)就是只包含質(zhì)因數(shù) 2, 3, 5 的正整數(shù)。
示例 1:
輸入: 6
輸出: true
解釋: 6 = 2 × 3
示例 2:
輸入: 8
輸出: true
解釋: 8 = 2 × 2 × 2
示例 3:
輸入: 14
輸出: false
解釋: 14 不是丑數(shù)窟哺，因?yàn)樗肆硗庖粋€(gè)質(zhì)因數(shù) 7泻轰。
代碼：
func isUgly(num int)bool{
if num==0{
return false
}
for num!=1{
if num%2==0{
num/=2
}else if num%3==0{
num/=3
}else if num%5==0{
num/=5
}else{
return false
}
}
return true
}
1.1.8 有效的完全平方數(shù)
給定一個(gè)正整數(shù) num，編寫(xiě)一個(gè)函數(shù)且轨，如果 num 是一個(gè)完全平方數(shù)浮声，則返回 True虚婿，否則返回 False。
說(shuō)明：不要使用任何內(nèi)置的庫(kù)函數(shù)泳挥，如 sqrt然痊。
示例 1：
輸入：16
輸出：True
示例 2：
輸入：14
輸出：False
代碼：
func isPerfectSquare(num int)bool{
r:=num
for r*r>num{
r=(r+num/r)/2
}
if r*r==num{
return true
}
return false
}
1.2第二類(lèi)
1.2.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è)答案。但是矗钟，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素唆香。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
代碼：
func towSum(nums []int,target int)[]int{
if len(nums)<2{
return nil
}
for i:=0;i<len(nums)-1;i++{
for j:=i+1;j<len(nums);j++{
if nums[i]+nums[j]==target{
return []int{i,j}
}
}
}
return nil
}
1.2.2 最大子序和
給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）吨艇，返回其最大和躬它。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6东涡。
代碼：
func maxSubArray(nums []int)int{
sum:=nums[0]
ans:=sum
for i:=1;i<len(nums);i++{
if sum<0{
sum=nums[i]
}else{
sum+=nums[i]
}
ans=max(ans,sum)
}
return ans
}
func max(a,b int)int{
if a>b{
return a
}
return b
}
1.2.3 加一
給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)冯吓，在該數(shù)的基礎(chǔ)上加一。
最高位數(shù)字存放在數(shù)組的首位疮跑， 數(shù)組中每個(gè)元素只存儲(chǔ)一個(gè)數(shù)字组贺。
你可以假設(shè)除了整數(shù) 0 之外，這個(gè)整數(shù)不會(huì)以零開(kāi)頭祸挪。
示例 1:
輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入數(shù)組表示數(shù)字 123锣披。
示例 2:
輸入: [4,3,2,1]
輸出: [4,3,2,2]
解釋: 輸入數(shù)組表示數(shù)字 4321。
代碼：
func PlusOne(nums []int)[]int{
for i:=len(nums)-1;i>=0;i--{
if nums[i]!=9{
nums[i]++
break
}else{
nums[i]=0
}
}
if nums[0]==0{
newans:=make([]int,len(nums)+1)
newans[0]=1
return newans
}
return nums
}
1.2.4 x的平方根
實(shí)現(xiàn) int sqrt(int x) 函數(shù)贿条。
計(jì)算并返回 x 的平方根雹仿，其中 x 是非負(fù)整數(shù)。
由于返回類(lèi)型是整數(shù)整以，結(jié)果只保留整數(shù)的部分胧辽，小數(shù)部分將被舍去。
示例 1:
輸入: 4
輸出: 2
示例 2:
輸入: 8
輸出: 2
說(shuō)明: 8 的平方根是 2.82842...,
由于返回類(lèi)型是整數(shù)公黑，小數(shù)部分將被舍去邑商。
代碼：
func sqrt(x int)int{
if x==0{
return 0
}
n:=x
for n*n>x{
n=(n+x/n)/2
}
return n
}
1.2.5 爬樓梯
假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂凡蚜。
每次你可以爬 1 或 2 個(gè)臺(tái)階人断。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個(gè)正整數(shù)朝蜘。
示例 1：
輸入： 2
輸出： 2
解釋?zhuān)?有兩種方法可以爬到樓頂恶迈。
- 1 階 + 1 階
- 2 階
示例 2：
輸入： 3
輸出： 3
解釋?zhuān)?有三種方法可以爬到樓頂。
- 1 階 + 1 階 + 1 階
- 1 階 + 2 階
- 2 階 + 1 階
代碼：
func climbStairs(n int)int{
switch n{
case 1:
return 1
case 2:
return 2
default:
dp1,dp2:=1,2
for i:=2;i<n;i++{
dp1,dp2=dp2,dp1+dp2
}
}
return dp2
}
1.2.6 楊輝三角
給定一個(gè)非負(fù)整數(shù) numRows谱醇，生成楊輝三角的前 numRows 行暇仲。
在楊輝三角中步做，每個(gè)數(shù)是它左上方和右上方的數(shù)的和。
示例:
輸入: 5
輸出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
代碼：
func generget(numRows int)[][]int{
if numRows==0{
return nil
}
a:=make([][]int,0)
a=append(a,[]int{1})
for i:=1;i<numRows;i++{
temp:=[]int{1}
for j:=1;j<i-1;j++{
temp=append(temp,a[i-1][j-1]+a[i-1][j])
}
temp=append(temp,1)
a=append(a,temp)
}
return a
}
1.2.7 楊輝三角2
給定一個(gè)非負(fù)索引 k奈附，其中 k ≤ 33全度，返回楊輝三角的第 k 行。
在楊輝三角中斥滤，每個(gè)數(shù)是它左上方和右上方的數(shù)的和将鸵。
示例:
輸入: 3
輸出: [1,3,3,1]
代碼：
func getRow(rowIndex int)[]int{
a:=[]int{1}
for i:=1;i<=rowIndex;i++{
for j:=0;j<i-1;j++{
a[j]=a[j]+a[j+1]
}
temp:=[]int{1}
a=append(temp,a...)
}
return a
}
1.2.8 買(mǎi)賣(mài)股票的最佳時(shí)機(jī)
給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格中跌。
如果你最多只允許完成一筆交易（即買(mǎi)入和賣(mài)出一支股票）咨堤，設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。
注意你不能在買(mǎi)入股票前賣(mài)出股票漩符。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入一喘，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣(mài)出，最大利潤(rùn) = 6-1 = 5 嗜暴。
注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u(mài)出價(jià)格需要大于買(mǎi)入價(jià)格凸克。
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0。
代碼：
func maxProfit(prices []int)int{
Max:=0
for i:=0;i<len(prices)-1;i++{
for j:=i+1;j<len(prices);j++{
delta:=prices[j]-prices[i]
if delta>Max{
Max=delta
}
}
}
return Max
}
1.2.9 買(mǎi)賣(mài)股票的最佳時(shí)機(jī)2
給定一個(gè)數(shù)組闷沥，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格萎战。
設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你可以盡可能地完成更多的交易（多次買(mǎi)賣(mài)一支股票）舆逃。
注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買(mǎi)前出售掉之前的股票）蚂维。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 路狮。
隨后虫啥，在第 4 天（股票價(jià)格 = 3）的時(shí)候買(mǎi)入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 6-3 = 3 奄妨。
示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入涂籽，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購(gòu)買(mǎi)股票砸抛，之后再將它們賣(mài)出评雌。
因?yàn)檫@樣屬于同時(shí)參與了多筆交易，你必須在再次購(gòu)買(mǎi)前出售掉之前的股票直焙。
示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0景东。
代碼：
func maxProfit(prices []int)int{
var num=0
for i:=0;i<len(prices);i++{
if prices[i]<prices[i+1]{
num+=prices[i+1]-prices[i]
}
}
return num
}
1.2.10 只出現(xiàn)一次的數(shù)字
給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外奔誓，其余每個(gè)元素均出現(xiàn)兩次斤吐。找出那個(gè)只出現(xiàn)了一次的元素。
說(shuō)明：
你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來(lái)實(shí)現(xiàn)嗎曲初？
示例 1:
輸入: [2,2,1]
輸出: 1
示例 2:
輸入: [4,1,2,1,2]
輸出: 4
func singleNumber(nums []int)int{
ret:=0
for _,num:=range nums{
ret=ret^num
}
return ret
}
1.2.11 兩數(shù)之和2--給定有序數(shù)組
給定一個(gè)已按照升序排列 的有序數(shù)組，找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)杯聚。
函數(shù)應(yīng)該返回這兩個(gè)下標(biāo)值 index1 和 index2臼婆，其中 index1 必須小于 index2。
說(shuō)明:
返回的下標(biāo)值（index1 和 index2）不是從零開(kāi)始的幌绍。
你可以假設(shè)每個(gè)輸入只對(duì)應(yīng)唯一的答案颁褂，而且你不可以重復(fù)使用相同的元素。
示例:
輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 2 與 7 之和等于目標(biāo)數(shù) 9 傀广。因此 index1 = 1, index2 = 2 颁独。
代碼：
func twoSum(numbers []int,target int)[]int{
if len(numbers)<2{
return nil
}
for i:=0;i<len(numbers);i++{
for j:=i+1;j<len(numbers);j++{
if numbers[i]+numbers[j]==target&&i<j{
return []int{i+1,j+1}
}
}
}
return nil
}
1.2.12 存在重復(fù)元素
給定一個(gè)整數(shù)數(shù)組，判斷是否存在重復(fù)元素伪冰。
如果任何值在數(shù)組中出現(xiàn)至少兩次誓酒，函數(shù)返回 true。如果數(shù)組中每個(gè)元素都不相同贮聂，則返回 false靠柑。
示例 1:
輸入: [1,2,3,1]
輸出: true
示例 2:
輸入: [1,2,3,4]
輸出: false
示例 3:
輸入: [1,1,1,3,3,4,3,2,4,2]
輸出: true
代碼：
func containsDuplicate(nums []int)bool{
if len(nums)==0{
return false
}
for i:=0;i<len(nums)-1;i++{
for j:=i+1;j<len(nums);j++{
if nums[i]==nums[j]{
return true
}
}
}
return false
}
1.2.13 存在重復(fù)元素2
給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù) k，判斷數(shù)組中是否存在兩個(gè)不同的索引 i 和 j吓懈，使得 nums [i] = nums [j]歼冰，并且 i 和 j 的差的絕對(duì)值最大為 k。
示例 1:
輸入: nums = [1,2,3,1], k = 3
輸出: true
示例 2:
輸入: nums = [1,0,1,1], k = 1
輸出: true
示例 3:
輸入: nums = [1,2,3,1,2,3], k = 2
輸出: false
代碼：
func containsNearbyDuplicate(nums []int, k int) bool {
hash := make(map[int]int) // hash 表記錄出現(xiàn)過(guò)的元素
for i,x := range nums {
if j,ok := hash[x]; ok && i-j<=k { // 如果之前出現(xiàn)過(guò)耻警，判斷下標(biāo)之差是否不超過(guò) k
return true
}
hash[x] = i
}
return false
}
1.2.14 缺失數(shù)字
給定一個(gè)包含 0, 1, 2, ..., n 中 n 個(gè)數(shù)的序列隔嫡，找出 0 .. n 中沒(méi)有出現(xiàn)在序列中的那個(gè)數(shù)。
示例 1:
輸入: [3,0,1]
輸出: 2
示例 2:
輸入: [9,6,4,2,3,5,7,0,1]
輸出: 8
代碼：
func missingNumber(nums []int)int{
length:=len(nums)
sum1,sum2:=length,0
for i:=0;i<lenght;i++{
sum1+=i
sum2+=nums[i]
}
return sum1-sum2
}
1.2.15 Nim游戲
你和你的朋友甘穿，兩個(gè)人一起玩 Nim 游戲：桌子上有一堆石頭腮恩，每次你們輪流拿掉 1 - 3 塊石頭。 拿掉最后一塊石頭的人就是獲勝者扒磁。你作為先手庆揪。
你們是聰明人直砂，每一步都是最優(yōu)解艾疟。 編寫(xiě)一個(gè)函數(shù)，來(lái)判斷你是否可以在給定石頭數(shù)量的情況下贏得游戲凉翻。
示例:
輸入: 4
輸出: false
解釋: 如果堆中有 4 塊石頭兰伤，那么你永遠(yuǎn)不會(huì)贏得比賽内颗；
因?yàn)闊o(wú)論你拿走 1 塊、2 塊 還是 3 塊石頭敦腔，最后一塊石頭總是會(huì)被你的朋友拿走均澳。
代碼：
func canWinNim(n int)bool{
if n%4!=0{
return true
}
return false
}
1.2.16 3的冪
給定一個(gè)整數(shù)，寫(xiě)一個(gè)函數(shù)來(lái)判斷它是否是 3 的冪次方。
示例 1:
輸入: 27
輸出: true
示例 2:
輸入: 0
輸出: false
示例 3:
輸入: 9
輸出: true
示例 4:
輸入: 45
輸出: false
代碼：
func isPowerOfThree(n int)bool{
i:=1
for ;i<n;i*=3{
}
if i==n{
return true
}
return false
}
1.2.17 4的冪
給定一個(gè)整數(shù) (32 位有符號(hào)整數(shù))找前，請(qǐng)編寫(xiě)一個(gè)函數(shù)來(lái)判斷它是否是 4 的冪次方糟袁。
示例 1:
輸入: 16
輸出: true
示例 2:
輸入: 5
輸出: false
代碼：
func isPowerOfFour(num int)bool{
i:=1
for ;i<num;i*=4{
}
if i==num{
return true
}
return false
}
1.2.18 兩整數(shù)之和
不使用運(yùn)算符 + 和 - ，計(jì)算兩整數(shù) a 躺盛、b 之和项戴。
示例 1:
輸入: a = 1, b = 2
輸出: 3
示例 2:
輸入: a = -2, b = 3
輸出: 1
代碼：
func getSum(a int, b int) int {
for a & b != 0{
a, b = a^b, (a&b) << 1
}
return a | b
}
