LeetCode go
16lz
2021-04-15
目录
- 一、数据结构和算法
- 1.13.1 题目描述
- 1.13.2 我的解法
- 1.12.1 题目描述
- 1.12.2 我的解法
- 1.11.1 题目描述
- 1.11.2 我的解法
- 1.10.1 题目描述
- 1.10.2 我的解法
- 1.9.1 题目描述
- 1.9.2 我的解法
- 1.8.1 题目描述
- 1.8.2 我的解法
- 1.7.1 题目描述
- 1.7.2 我的解法
- 1.6.1 题目描述
- 1.6.2 我的解法
- 1.5.1 题目描述
- 1.5.2 我的解法
- 1.4.1 题目描述
- 1.4.2 我的解法
- 1.3.1 题目描述
- 1.3.2 我的解法
- 1.2.1 题目描述
- 1.2.2 我的解法
- 1.1.1 题目描述
- 1.1.2 我的解法
- 1.1 1. 两数之和
- 1.2 2. 两数相加
- 1.3 3. 无重复字符的最长子串
- 1.4 4. 寻找两个有序数组的中位数
- 1.5 7. 整数反转
- 1.6 9. 回文数
- 1.7 13. 罗马数字转整数
- 1.8 14. 最长公共前缀
- 1.9 15. 三数之和
- 1.10 21. 合并两个有序链表
- 1.11 83. 删除排序链表中的重复元素
- 1.12 82. 删除排序链表中的重复元素 II
- 1.13 206. 反转链表
更新、更全的《Go从入门到放弃》的更新网站，更有python、go、人工智能教学等着你：https://www.cnblogs.com/nickchen121/p/11517502.html
用Go语言刷LeetCode记录，只是为了练习Go语言，能力有限不保证都是最优解，只能在此抛转引玉了。
一、数据结构和算法
数据结构和算法是程序员的命根子，没了命根子也就没有了尊严。
1.1 1. 两数之和
1.1.1 题目描述
力扣（LeetCode）链接
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]
1.1.2 我的解法
func twoSum(nums []int, target int) []int { l := len(nums) for i:=0;i<l;i++{ for j:=i+1;j<l;j++{ if nums[i]+nums[j] == target{ return []int{i,j} } } } return []int{}}1.2 2. 两数相加
1.2.1 题目描述
力扣（LeetCode）链接
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807
1.2.2 我的解法
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { var ret = new(ListNode) current := ret carry := 0 for l1 != nil || l2 != nil { x, y := 0, 0 if l1 != nil { x = l1.Val l1 = l1.Next } if l2 != nil { y = l2.Val l2 = l2.Next } sum := x + y + carry current.Next = &ListNode{Val:sum%10} current = current.Next carry = sum/10 } if carry > 0{ current.Next=&ListNode{Val:carry} } return ret.Next}1.3 3. 无重复字符的最长子串
1.3.1 题目描述
力扣（LeetCode）链接
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例1：
输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例2：
输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例3：
输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1.3.2 我的解法
func lengthOfLongestSubstring(s string) int {i := 0max := 0a := []rune(s)for m, c := range a {for n := i; n < m; n++ {if a[n] == c {i = n + 1}}if m-i+1 > max {max = m - i + 1}}return max}1.4 4. 寻找两个有序数组的中位数
1.4.1 题目描述
力扣（LeetCode）链接
给定两个大小为m和n的有序数组nums1和nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为O(log(m + n))。
你可以假设nums1和nums2不会同时为空。示例1：
nums1 = [1, 3]nums2 = [2]则中位数是 2.0
示例2：
nums1 = [1, 2]nums2 = [3, 4]则中位数是 (2 + 3)/2 = 2.5
1.4.2 我的解法
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { len1 := len(nums1) len2 := len(nums2) lenSum := len1+len2 if lenSum == 0 { return float64(0) } l, r := 0, 0 a := make([]int,0,lenSum) for l <len1 && r < len2{ if nums1[l] < nums2[r]{ a = append(a,nums1[l]) l++ }else { a = append(a, nums2[r]) r++ } } a = append(a, nums1[l:]...) a = append(a, nums2[r:]...) if lenSum%2 != 0 { return float64(a[lenSum/2]) }else { return (float64(a[lenSum/2-1]) + float64(a[lenSum/2]))/2 }}1.5 7. 整数反转
1.5.1 题目描述
力扣（LeetCode）链接
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123输出: 321
示例 2:
输入: -123输出: -321
示例 3:
输入: 120输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
1.5.2 我的解法
func reverse(x int) int { var recv int for x != 0 { pop := x % 10 x /= 10 if recv*10 > 1<<31-1 || (recv*10 == 1<<31-1 && pop > 7){ return 0 } if recv*10 < -1<<31 || (recv*10 == -1<<31 && pop < 8) { return 0 } recv = recv*10+pop } return recv}1.6 9. 回文数
1.6.1 题目描述
力扣（LeetCode）链接
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121输出: true
示例 2:
输入: -121输出: false解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10输出: false解释: 从右向左读, 为 01 。因此它不是一个回文数。
1.6.2 我的解法
func isPalindrome(x int) bool { // 如果是负数或类似10、100、1000这种就直接返回false if x < 0 || (x != 0 && x %10 == 0) { return false } // 反转后半部分的数字，和前半部分做比较 var right int for x > right{ right = right*10 + x%10 x /= 10 } // 注意前半部分和后半部分刚好相等（1221）或正好差一位（121） return x == right || x == right/10 }1.7 13. 罗马数字转整数
1.7.1 题目描述
力扣（LeetCode）链接
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值I 1V 5X 10L 50C 100D 500M 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.
1.7.2 我的解法
func romanToInt(s string) int { m := map[string]int{ "I": 1, "IV": 4, "V": 5, "IX": 9, "X": 10, "XL": 40, "L": 50, "XC": 90, "C": 100, "CD": 400, "D": 500, "CM": 900, "M": 1000, } var ret int for i:=0;i<len(s);{ // 先尝试读两个字符，注意索引不要越界 if i+2<=len(s)&&m[s[i:i+2]]!=0{ ret +=m[s[i:i+2]] i+=2 continue }else{ ret +=m[s[i:i+1]] i++ continue } } return ret}1.8 14. 最长公共前缀
1.8.1 题目描述
力扣（LeetCode）链接
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ““。
示例 1:
输入: ["flower","flow","flight"]输出: "fl"
示例 2:
输入: ["dog","racecar","car"]输出: ""解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
1.8.2 我的解法
func longestCommonPrefix(strs []string) string { if len(strs) == 0{ return "" }prefix := strs[0]for i := 1; i < len(strs); i++ {for !strings.HasPrefix(strs[i], prefix) {prefix = strs[0][0 : len(prefix)-1]if prefix == "" {return ""}}}return prefix}1.9 15. 三数之和
1.9.1 题目描述
力扣（LeetCode）链接
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[ [-1, 0, 1], [-1, -1, 2]]
1.9.2 我的解法
func threeSum(nums []int) [][]int { lenNums := len(nums) ret := make([][]int, 0, 0) if lenNums < 3{ return ret } // 排序 sort.Ints(nums) for i:=0;i<lenNums;i++{ if nums[i] > 0{break} if i > 0 && nums[i] == nums[i-1]{continue} // 去重 l, r := i+1, lenNums-1 for l < r { sum := nums[i] + nums[l] + nums[r] if sum == 0 { ret = append(ret, []int{nums[i],nums[l], nums[r]}) for l< r && nums[l] == nums[l+1]{l++} // 左边去重 for r < r && nums[r] == nums[r-1]{r--} // 后边去重 l++ r-- } if sum > 0 {r--} if sum < 0 {l++} } } return ret}1.10 21. 合并两个有序链表
1.10.1 题目描述
力扣（LeetCode）链接
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4输出：1->1->2->3->4->4
1.10.2 我的解法
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { var ret = new(ListNode) // 前置虚拟节点法 cur := ret // 定义一个保存当前节点的变量 for l1 != nil && l2 != nil { if l1.Val < l2.Val{ cur.Next = l1 l1 = l1.Next }else { cur.Next = l2 l2 = l2.Next } cur = cur.Next // 当前节点向后移 } // 追加没遍历到的链表 if l1 != nil { cur.Next = l1 } if l2 != nil { cur.Next = l2 } return ret.Next}1.11 83. 删除排序链表中的重复元素
1.11.1 题目描述
力扣（LeetCode）链接
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2输出: 1->2
示例 2：
输入: 1->1->2->3->3输出: 1->2->3
1.11.2 我的解法
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func deleteDuplicates(head *ListNode) *ListNode { cur := head for cur != nil && cur.Next != nil { if cur.Val == cur.Next.Val { cur.Next = cur.Next.Next }else { cur = cur.Next } } return head}1.12 82. 删除排序链表中的重复元素 II
1.12.1 题目描述
力扣（LeetCode）链接
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5输出: 1->2->5
示例 2:
输入: 1->1->1->2->3输出: 2->3
1.12.2 我的解法
递归法：
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func deleteDuplicates(head *ListNode) *ListNode { if head == nil { return head } if head.Next != nil && head.Val == head.Next.Val{ for head!=nil&&head.Next !=nil && head.Val == head.Next.Val{ head = head.Next } return deleteDuplicates(head.Next) }else { head.Next = deleteDuplicates(head.Next) } return head}前置虚假节点方法：
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func deleteDuplicates(head *ListNode) *ListNode { if head == nil || head.Next==nil { return head } dummy := new(ListNode) dummy.Next = head pre := dummy cur := head for cur != nil&& cur.Next!=nil{ if cur.Val == cur.Next.Val{ for cur.Next!=nil && cur.Val == cur.Next.Val{ cur = cur.Next } pre.Next = cur.Next cur = cur.Next }else { pre = cur cur = cur.Next } } return dummy.Next}1.13 206. 反转链表
1.13.1 题目描述
力扣（LeetCode）链接
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL
1.13.2 我的解法
迭代方式：
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func reverseList(head *ListNode) *ListNode { var pre *ListNode cur := head for cur!= nil{ tmp := cur.Next cur.Next = pre pre = cur cur = tmp } return pre}递归方式：
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func reverseList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } p := reverseList(head.Next) head.Next.Next = head head.Next = nil return p}持续更新中…
©著作权归作者所有：来自51CTO博客作者wx5b1fd43180419的原创作品，如需转载，请注明出处，否则将追究法律责任更多相关文章
- Java基础编程练习10：求1!+2!+3!+…+n!, n<=15。
- Token Bucket在QoS中入门级介绍python示例
- Java基础编程练习5：求1~100之间的偶数和？
- Hibernate快速入门+简单示例
- NoSQL Manager for MongoDB 操作教程（基础篇）
- 第102天： Python异步之aiohttp
- 华裔教授发现二次方程「极简」解法：丢掉公式，全球教科书可能都要改
- 哪些 Python 库让你相见恨晚？
- 概率分布生成和蒙特卡洛模拟的实战示例