返回总目录

日刷leetcode–简单版


58. 最后一个单词的长度

题目描述

image.png

解题思路

  • 定义一个变量统计,从前往后遍历,遇到空格归零就可以了,注意处理最后几个个字符全为空格的情况
  • 定义一个变量统计,从后往前便利,虽然时间复杂度同为 O(n),但是第二个明显快很多
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func lengthOfLastWord(s string) int {
var count int
for i:= len(s)-1; i >= 0; i-- {
if s[i] == 32{
if count == 0 {
continue
}else{
break
}
}
count ++
}
return count
}
运行结果

执行用时 :0 ms, 在所有 Go 提交中击败了 100.00%的用户
内存消耗 :2.2 MB, 在所有 Go 提交中击败了 39.13%的用户

66.加一

题目描述

image.png

解题思路
  • 从后面往前面循环,最后以一位加 1 即可,处理好末尾9999
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func plusOne(digits []int) []int {
c := 1 // 定义一个变量用来进位,进位归零则程序结束
for i := len(digits) - 1; i >= 0; i-- {
digits[i] += c
c--
if digits[i] == 10 {
digits[i] = 0
c = 1
}
if c == 0 {
return digits
}
}
if c != 0 { // 循环完后依旧存在进位则表示遇到了999
digits = append([]int{1}, digits...)
}
return digits
}
运行结果

执行用时 :0 ms, 在所有 Go 提交中击败了 100.00%的用户
内存消耗 :2.2 MB, 在所有 Go 提交中击败了 30.57%的用户

67.二进制求和

题目描述

image.png

解题思路

  • 判断两个字符串的大小,保证 a 为较长的一个
  • 从后往前循环相加,先循环较短的字符串,再循环长字符串剩余的,定义一个变量记录是否需要进位,两个字符串相加是需要加上进位的值
  • 最后判断进位值是否为 0,不为 0 则在相加后字符串最前面一位加 1
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func addBinary(a string, b string) string {
la, lb := len(a), len(b)
if la < lb {
la, lb = lb, la
a, b = b, a
}
var carry, s byte
str := make([]byte, la+1)
for lb > 0 {
la--
lb--
s = byte(a[la]-'0') + byte(b[lb]-'0') + carry
carry = s / 2
s = s % 2
str[la+1] = byte(s + '0')
}
for la > 0 {
la--
s = byte(a[la]-'0') + carry
carry = s / 2
s = s % 2
str[la+1] = byte(s + '0')
}
if carry == 1 {
str[la] = carry + '0'
} else {
str = str[la+1:]
}
return string(str[la:])
}
运行结果

执行用时 :0 ms, 在所有 Go 提交中击败了 100.00%的用户
内存消耗 :2.3 MB, 在所有 Go 提交中击败了 68.18%的用户

69. x 的平方根

题目描述

image.png

解题思路 1

  • 使用官方包 math.Sqrt,然后提取整数部分即可(不提供代码)

解题思路 2

  • 使用二分法,判断中位数的积是否大于 x,是则右边向左移,否则左边直接等于中位数
  • 注意的是取中位数是要取右中位数,也就是要加1,不然会死循环
示例代码 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func mySqrt(x int) int {
l, r := 0, x/2+1
for l < r {
mid := (l + r + 1) / 2
sqrt := mid * mid
if sqrt > x {
r = mid - 1
} else {
l = mid
}
fmt.Println(l, r, mid)
}

return l
}
运行结果

执行用时 :8 ms, 在所有 Go 提交中击败了 29.75%的用户
内存消耗 :2.8 MB, 在所有 Go 提交中击败了 5.23%的用户

70. 爬楼梯

题目描述

image.png

解题思路

  • 这是一个标准的斐波拉切数列,所以就不多说
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
func climbStairs(n int) int {
if n < 3 {
return n
}

a, b := 1, 2
res := 0
for i := 2; i < n; i++ {
res = a + b
a, b = b, res
}
return res
}
运行结果

执行用时 :0 ms, 在所有 Go 提交中击败了 100.00%的用户
内存消耗 :2 MB, 在所有 Go 提交中击败了 52.61%的用户

83. 删除排序链表中的重复

题目描述

image.png

解题思路

  • 因为是排序了的,所以就相对来说比较简单,判断是否与下一个相等,相等即后移即可,讲Next指向Next.Next
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}

carry := head

for carry != nil && carry.Next != nil {
if carry.Val == carry.Next.Val {
carry.Next = carry.Next.Next
}else{
carry = carry.Next
}
}
return head
}
运行结果

执行用时 :4 ms, 在所有 Go 提交中击败了 96.46%的用户
内存消耗 :3.2 MB, 在所有 Go 提交中击败了 48.18%的用户