LeetCode刷题总结1
1.数字题
1.1 第一类
1.1.1 整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 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 回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
代码：
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的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
代码：
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表列名称
给定一个正整数，返回它在 Excel 表中相对应的列名称。
例如，
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表列序号
给定一个Excel表格中的列名称，返回其相应的列序号。
例如，
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 各位相加
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
示例:
输入: 38
输出: 2
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 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 丑数
编写一个程序判断给定的数是否为丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例 1:
输入: 6
输出: true
解释: 6 = 2 × 3
示例 2:
输入: 8
输出: true
解释: 8 = 2 × 2 × 2
示例 3:
输入: 14
输出: false
解释: 14 不是丑数，因为它包含了另外一个质因数 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 有效的完全平方数
给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如 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第二类
1.2.1 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 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 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [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 加一
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 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的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
代码：
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 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
- 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 杨辉三角
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
img
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 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
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
img
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 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 买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 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 买卖股票的最佳时机2
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 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 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 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 两数之和2--给定有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 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 存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 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 存在重复元素2
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 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 表记录出现过的元素
for i,x := range nums {
if j,ok := hash[x]; ok && i-j<=k { // 如果之前出现过，判断下标之差是否不超过 k
return true
}
hash[x] = i
}
return false
}
1.2.14 缺失数字
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 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游戏
你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。
你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。
示例:
输入: 4
输出: false
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。
代码：
func canWinNim(n int)bool{
if n%4!=0{
return true
}
return false
}
1.2.16 3的幂
给定一个整数，写一个函数来判断它是否是 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的幂
给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 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 两整数之和
不使用运算符 + 和 - ，计算两整数 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
}
网友评论