Leet Code 00 - 基础题合集
0. 整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
func reverse(x int) int {
var sign int64 = 1
if x < 0 {
sign = -1
x = -x
}
nums := make([]int, 0, 10)
for i:=0; x > 0; i++ {
mod := x % 10
// x -= mod; 这里不需要做这个减法
x /= 10
if len(nums) == 0 && mod == 0 {
continue
}
nums = append(nums, mod)
}
var n int64 = 0
for _, v := range nums {
n *= 10
n += int64(v)
}
n *= sign
if n > int64(+(1<<31)-1) {
return 0
}
if n < int64(-(1<<31)-0) {
return 0
}
return 0
}
1. 两数相加
题目链接 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
head := &ListNode{0, nil}
tail := head
C := 0 // 进位
for i:=0; l1 != nil || l2 != nil || C != 0; i++ {
a := 0
b := 0
if l1 != nil {
a = l1.Val
l1 = l1.Next
}
if l2 != nil {
b = l2.Val
l2 = l2.Next
}
sum := a + b + C
n := sum % 10
if n != sum {
C = 1
} else {
C = 0
}
newNode := &ListNode{n, nil}
if i != 0 {
tail.Next = newNode
tail = newNode
} else {
head = newNode
tail = head
}
}
return head
}
2. 回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。 进阶:
你能不将整数转为字符串来解决这个问题吗？
不将整数转为字符串来解决这个问题的版本
主要有两个坑
- 注意只有一位的数的情况
- 注意结尾是0的数的情况
func isPalindrome(x int) bool {
if x < 0 {
return false
}
if x < 10 {
return true
}
// 除0以外的所有以0结尾的数都不会是回文数
if x % 10 == 0 {
return false
}
a := x
b := 0
for {
if a < b {
return false
}
a = x/10
b *= 10
b += x % 10
if a == b || a/10 == b {
return true
}
x = a
}
}
3. 罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。 给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:
输入: "III"
输出: 3
示例 2:
输入: "IV"
输出: 4
示例 3:
输入: "IX"
输出: 9
示例 4:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
提示： 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。 IC 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。 关于罗马数字的详尽书写规则，可以参考罗马数字 - Mathematics 。
纯体力活
func romanToInt(s string) int {
Len := len(s)
n := 0
for i:=0; i稍微优雅的实现版本
type op struct {
Value int
PreChar byte
NextValue int
}
func romanToInt(s string) int {
m := map[byte]op{
'I': {1, ' ', 0},
'V': {5, 'I', 4},
'X': {10, 'I', 9},
'L': {50, 'X', 40},
'C': {100, 'X', 90},
'D': {500, 'C', 400},
'M': {1000, 'C', 900},
}
Len := len(s)
n := 0
for i := 0; i < Len; i++ {
c := s[i]
cNext := byte(' ')
if (i + 1) < Len {
cNext = s[i+1]
}
v := 0
oNext := m[cNext]
if c == oNext.PreChar {
v = oNext.NextValue
i += 1
} else {
v = m[c].Value
}
n += v
}
return n
}
4. 有效的括号
给定一个只包括 ‘(‘，’)‘，’{‘，’}‘，’[‘，’]‘ 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
func match(l, r rune) bool {
if (l == '{' && r == '}') || (l == '[' && r == ']') || (l == '(' && r == ')') {
return true
}
return false
}
func isValid(s string) bool {
// 如果奇数长度必然不能配对
if len(s) % 2 == 1 {
return false
}
stack := make([]rune, 0, 256)
for _, c := range s {
if len(stack) == 0 {
stack = append(stack, c)
} else {
data := stack[len(stack)-1]
if !match(data, c) {
stack = append(stack, c)
} else {
stack = stack[:len(stack)-1]
}
}
}
if len(stack) != 0 {
return false
}
return true
}
5. Z字形变换
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”LCIRETOESIIGEDHN”。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:
L D R
E O E I I
E C I H N
T S G
解题思路： 上述排列等价于下面的排列
L C I R
E T O E S I I G
E D H N
可以看出两个相邻的字母不可能处于同一行，所以只需要对每个字母生成好行数，按行取出来就可以了。
需要注意的是对单行
func convert(s string, numRows int) string {
lenS := len(s)
if numRows == 1 || lenS <= numRows {
return s
}
buf := make([]int, lenS)
inx := 0
delta := 0
for i := 0; i < lenS; i++ {
inx += delta
if inx == 0 {
delta = 1
}
if inx == (numRows - 1) {
delta = -1
}
buf[i] = inx
}
ns := make([]byte, lenS)
inx = 0
for row := 0; row < numRows; row++ {
for i := row; i < lenS; i++ {
if buf[i] != row {
continue
}
ns[inx] = s[i]
inx++
}
}
return string(ns)
}
进阶解法
假设5行的情况 ABCDEDCBABCDEDCBABCDEDCBA...
可以总结出:
A步长: 8 8 8 8 8 ...
B步长: 6 2 6 2 6 ...
C步长: 4 4 4 4 4 ...
D步长: 2 6 2 6 2 ...
E步长: 8 8 8 8 8 ...
可以总结出
最大步长为maxStep = 2*(numRows-1)
B-D的步长公式为: maxStep - 2*行, 2*行, ... 交替
A、E按上述公式算出为0，直接换成maxStep就可以了
解答如下
func convert(s string, numRows int) string {
lenS := len(s)
fmt.Println(lenS)
ns := make([]byte, lenS)
if numRows == 1 {
return s
}
maxStep := 2 * (numRows - 1)
inx := 0
for i := 0; i < numRows; i++ {
step := 0
col := 0
for j := i; j < lenS; j += step {
if col%2 == 0 {
step = maxStep - 2*i
} else {
step = 2 * i
}
col++
if step == 0 {
step = maxStep
}
fmt.Println(inx, i, j)
ns[inx] = s[j]
inx++
}
}
return string(ns)
}
6. 加一
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
唯一需要注意的是最高为还有可能额外进一位的情况
func plusOne(digits []int) []int {
c := 1
lenD := len(digits)
data := make([]int, lenD+1)
for i := lenD - 1; i >= 0; i-- {
n := digits[i] + c
if n >= 10 {
data[i+1] = n - 10
c = 1
} else {
data[i+1] = n
c = 0
}
}
if c == 1 {
data[0] = 1
return data
}
return data[1:]
}
7. 二进制求和
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
提示：
每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。
func addBinary(a string, b string) string {
lenA := len(a)
lenB := len(b)
maxLen := lenA
if maxLen < lenB {
maxLen = lenB
}
maxLen += 1
o := make([]byte, maxLen)
c := 0
va := 0
vb := 0
i := 0
j := 0
for i = maxLen - 1; i >= 0; i-- {
inxA := lenA - 1 - j
inxB := lenB - 1 - j
j++
if inxA < 0 && inxB < 0 {
break
}
if inxA >= 0 {
va = int(a[inxA]) - int('0')
} else {
va = 0
}
if inxB >= 0 {
vb = int(b[inxB]) - int('0')
} else {
vb = 0
}
n := va + vb + c
o[i] = '0' + byte(n%2)
c = 0
if n >= 2 {
c = 1
}
}
if c == 1 {
o[i] = '1'
return string(o[i:])
}
return string(o[i+1:])
}
8. 两数之和
给定一个整数数组nums和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解答如下
func twoSum(nums []int, target int) []int {
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
}
9. 删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的n保证是有效的。
以下是进阶解法，只遍历一遍完成删除。
func removeNthFromEnd(head *ListNode, n int) *ListNode {
var poineer *ListNode
var deleter *ListNode
poineer = head
deleter = &ListNode{0, head}
// 向前移动n个，就和deleter相隔n+1个节点
// 这样deleter就指向了要删除节点的父节点
for i := 0; i < n && poineer != nil; i++ {
poineer = poineer.Next
}
// 一次遍历到尾部节点
for poineer != nil {
poineer = poineer.Next
deleter = deleter.Next
}
// 删除倒数第n个节点
if deleter.Next != head {
deleter.Next = deleter.Next.Next
} else {
head = head.Next
}
return head
}