返回总目录 [链接] 1.两数之后 题目描述 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 示例 给定 nums = [2, 7, 11, 15], targe ..

日刷 leetcode-- 简单版(一)

返回总目录

日刷leetcode--简单版

1.两数之后

题目描述

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路 1

示例代码
func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] + nums[j] ==target {
                return []int{i,j}
            }
        }
    }
    return nil
}
运行结果

执行用时 :56 ms, 在所有 Go 提交中击败了 32.33% 的用户
内存消耗 :3 MB, 在所有 Go 提交中击败了 78.76% 的用户

解题思路 2

示例代码
func twoSum(nums []int, target int) []int {
	maps := make(map[int]int)

	for k, v := range nums {
		difference := target - v
		if _, ok := maps[difference]; ok { // 判断是否存在指定k的值
			return []int{maps[difference], k}
		}
		maps[v] = k // 将值作为key存储到map中
	}
	return nil
}
运行结果

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


7.整数反转

题目描述

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。
示例 1

输入: 123
输出: 321

示例 2

输入: -123
输出: -321

示例 3

输入: 120
输出: 21

注意

假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [− 231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

解题思路

示例代码
func reverse(x int) int {
	num := 0
	for x != 0 {
		num = num*10 + x%10
		x = x / 10
	}
	if num > math.MaxInt32 || num < math.MinInt32 {
		return 0
	}
	return num
}
运行结果

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


9.回文数

题目描述

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
示例 1:

输入: 121
输出: true

示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

解题思路 1

示例代码
func isPalindrome(x int) bool {
	if x < 0 || (x != 0 && x%10 == 0) {
		return false
	}
	s := strconv.Itoa(x)
	fmt.Println(s)
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		if s[i] != s[j] {
			return false
		}
	}
	return true
}
运行结果

执行用时 :20 ms, 在所有 Go 提交中击败了 81.69% 的用户
内存消耗 :5.5 MB, 在所有 Go 提交中击败了 15.78% 的用户

解题思路 2

示例代码
func isPalindrome(x int) bool {
	if x < 0 || (x != 0 && x%10 == 0) {
		return false
	}
	var i int
	for i < x {
		i = i*10 + x%10
		x /= 10
	}
	return x == i || x == i/10
}
运行结果

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


PS: 执行速度感觉是和网速有关的,如果你觉得你的程序够快,就多提交几次。上面思路二的代码一开始 40 多秒。


13. 罗马数字转整数

题目描述

罗马数字包含以下七种字符: 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.

解题思路

示例代码
func romanToInt(s string) int {
	roman := map[byte]int{
		'I': 1,
		'V': 5,
		'X': 10,
		'L': 50,
		'C': 100,
		'D': 500,
		'M': 1000,
	}
	var sum int
	index := 999
	for i := 0; i < len(s); i++ {
		this := roman[s[i]]
		if index < this {
			sum = sum - index*2
		}
		sum += this
		index = this
	}
	return sum
}
运行结果

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

14. 最长公共前缀

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
解题思路
示例代码
func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}
	for i := 0; i < len(strs[0]); i++ {
		for j := 1; j < len(strs); j++ {
			if i == len(strs[j]) || strs[j][i] != strs[0][i] {
				return strs[0][:i]
			}
		}
	}
	return strs[0]
}
运行结果

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

20. 有效的括号

题目描述

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
    注意空字符串可被认为是有效字符串。
    示例 1:
输入: "()"
输出: true
> 示例 2:
>``` 
> 输入: "()[]{}"
> 输出: true
>```
> 示例 3:
>``` 
> 输入: "(]"
> 输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true
解题思路
示例代码
func isValid(s string) bool {
	brackets := map[int32]int32{
		')': '(',
		'}': '{',
		']': '[',
	}
	list := []int32{}
	for _, v := range s {
		if v == '(' || v == '{' || v == '[' {
			list = append(list, v)
		} else {
			l := len(list) - 1
			if len(list) != 0 && list[l] == brackets[v] {
				list = list[:l]
			} else {
				return false
			}
		}
	}
	return len(list) == 0
}
运行结果

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

21.合并两个有序链表

题目描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
解题思路
示例代码
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	if l1.Val < l2.Val {
		l1.Next = mergeTwoLists(l1.Next, l2)
		return l1
	} else {
		l2.Next = mergeTwoLists(l1, l2.Next)
		return l2
	}
}
运行结果

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

返回总目录

日刷leetcode--简单版

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    162 引用 • 61 回帖
  • golang

    Go 语言是 Google 推出的一种全新的编程语言,可以在不损失应用程序性能的情况下降低代码的复杂性。谷歌首席软件工程师罗布派克(Rob Pike)说:我们之所以开发 Go,是因为过去 10 多年间软件开发的难度令人沮丧。Go 是谷歌 2009 发布的第二款编程语言。

    357 引用 • 1198 回帖 • 714 关注
  • 算法
    284 引用 • 205 回帖 • 12 关注
1 回帖
请输入回帖内容...