LeetCode刷题总结

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
}

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 194,390评论 5赞 459
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 81,821评论 2赞 371
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 141,632评论 0赞 319
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,170评论 1赞 263
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,033评论 4赞 355
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,098评论 1赞 272
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,511评论 3赞 381
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,204评论 0赞 253
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,479评论 1赞 290
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,572评论 2赞 309
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,341评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,213评论 3赞 312
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,576评论 3赞 298
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 28,893评论 0赞 17
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,171评论 1赞 250
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,486评论 2赞 341
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,676评论 2赞 335

LeetCode刷题总结

LeetCode刷题总结1

1.数字题

1.1 第一类

1.1.1 整数反转

1.1.2 回文数

1.1.3 x的平方根

1.1.4 Execl表列名称

1.1.5 Excel表列序号

1.1.6 各位相加

1.1.7 丑数

1.1.8 有效的完全平方数

1.2第二类

1.2.1 两数之和

1.2.2 最大子序和

1.2.3 加一

1.2.4 x的平方根

1.2.5 爬楼梯

1.2.6 杨辉三角

1.2.7 杨辉三角2

1.2.8 买卖股票的最佳时机

1.2.9 买卖股票的最佳时机2

1.2.10 只出现一次的数字

1.2.11 两数之和2--给定有序数组

1.2.12 存在重复元素

1.2.13 存在重复元素2

1.2.14 缺失数字

1.2.15 Nim游戏

1.2.16 3的幂

1.2.17 4的幂

1.2.18 两整数之和

推荐阅读更多精彩内容