用Go語言刷LeetCode記錄,只是為了練習Go語言,能力有限不保證都是最優解,只能在此拋轉引玉了,
資料結構和演算法
資料結構和演算法是程式員的命根子,沒了命根子也就沒有了尊嚴,
1. 兩數之和
題目描述
力扣(LeetCode)鏈接
給定一個整數陣列 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 {
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{}
}
2. 兩數相加
題目描述
力扣(LeetCode)鏈接
給出兩個 非空 的鏈表用來表示兩個非負的整數,其中,它們各自的位數是按照 逆序 的方式存盤的,并且它們的每個節點只能存盤 一位 數字,
如果,我們將這兩個數相加起來,則會回傳一個新的鏈表來表示它們的和,
您可以假設除了數字 0 之外,這兩個數都不會以 0 開頭,
示例:
輸入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 輸出:7 -> 0 -> 8 原因:342 + 465 = 807
我的解法
/**
* 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
}
3. 無重復字符的最長子串
題目描述
力扣(LeetCode)鏈接
給定一個字串,請你找出其中不含有重復字符的最長子串的長度,
示例1:
輸入: "abcabcbb" 輸出: 3 解釋: 因為無重復字符的最長子串是 "abc",所以其長度為 3,
示例2:
輸入: "bbbbb" 輸出: 1 解釋: 因為無重復字符的最長子串是 "b",所以其長度為 1,
示例3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke",所以其長度為 3,
請注意,你的答案必須是 子串 的長度,"pwke" 是一個子序列,不是子串,
我的解法
func lengthOfLongestSubstring(s string) int {
i := 0
max := 0
a := []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
}
4. 尋找兩個有序陣列的中位數
題目描述
力扣(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
我的解法
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
}
}
7. 整數反轉
題目描述
力扣(LeetCode)鏈接
給出一個 32 位的有符號整數,你需要將這個整數中每位上的數字進行反轉,
示例 1:
輸入: 123
輸出: 321
示例 2:
輸入: -123
輸出: -321
示例 3:
輸入: 120
輸出: 21
注意:
假設我們的環境只能存盤得下 32 位的有符號整數,則其數值范圍為 [−231, 231 − 1],請根據這個假設,如果反轉后整數溢位那么就回傳 0,
我的解法
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
}
9. 回文數
題目描述
力扣(LeetCode)鏈接
判斷一個整數是否是回文數,回文數是指正序(從左向右)和倒序(從右向左)讀都是一樣的整數,
示例 1:
輸入: 121
輸出: true
示例 2:
輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 , 從右向左讀, 為 121- ,因此它不是一個回文數,
示例 3:
輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 ,因此它不是一個回文數,
我的解法
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
}
13. 羅馬數字轉整數
題目描述
力扣(LeetCode)鏈接
羅馬數字包含以下七種字符: 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 {
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
}
14. 最長公共前綴
題目描述
力扣(LeetCode)鏈接
撰寫一個函式來查找字串陣列中的最長公共前綴,
如果不存在公共前綴,回傳空字串 ““,
示例 1:
輸入: ["flower","flow","flight"]
輸出: "fl"
示例 2:
輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴,
說明:
所有輸入只包含小寫字母 a-z ,
我的解法
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
}
15. 三數之和
題目描述
力扣(LeetCode)鏈接
給定一個包含 n 個整數的陣列 nums,判斷 nums 中是否存在三個元素 a,b,c ,使得 a + b + c = 0 ?找出所有滿足條件且不重復的三元組,
注意:答案中不可以包含重復的三元組,
例如, 給定陣列 nums = [-1, 0, 1, 2, -1, -4],
滿足要求的三元組集合為:
[
[-1, 0, 1],
[-1, -1, 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
}
20. 有效的括號
題目描述
力扣(LeetCode)鏈接
給定一個只包括 ‘(‘,’)‘,’{‘,’}‘,’[‘,’]‘ 的字串,判斷字串是否有效,
有效字串需滿足:
- 左括號必須用相同型別的右括號閉合,
- 左括號必須以正確的順序閉合, 注意空字串可被認為是有效字串,
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
我的解法
func isValid(s string) bool {
m := map[byte]byte{
')':'(',
']':'[',
'}':'{',
}
a := make([]byte, 0, len(s)/2)
for _, b := range []byte(s){
if b == '(' || b == '{' || b == '['{
a = append(a, b)
continue
}
if b == ')' || b == '}' || b == ']'{
if len(a) >0 && m[b] == a[len(a)-1]{
a = a[:len(a)-1]
continue
}else {
return false
}
}
}
if len(a) == 0 {
return true
}else {
return false
}
}
21. 合并兩個有序鏈表
題目描述
力扣(LeetCode)鏈接
將兩個有序鏈表合并為一個新的有序鏈表并回傳,新鏈表是通過拼接給定的兩個鏈表的所有節點組成的,
示例:
輸入:1->2->4, 1->3->4
輸出:1->1->2->3->4->4
我的解法
/**
* 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
}
26. 洗掉排序陣列中的重復項
題目描述
力扣(LeetCode)鏈接
給定一個排序陣列,你需要在原地洗掉重復出現的元素,使得每個元素只出現一次,回傳移除后陣列的新長度,
不要使用額外的陣列空間,你必須在原地修改輸入陣列并在使用 O(1) 額外空間的條件下完成,
示例 1:
給定陣列 nums = [1,1,2],
函式應該回傳新的長度 2, 并且原陣列 nums 的前兩個元素被修改為 1, 2,
你不需要考慮陣列中超出新長度后面的元素,
示例 2:
給定 nums = [0,0,1,1,1,2,2,3,3,4],
函式應該回傳新的長度 5, 并且原陣列 nums 的前五個元素被修改為 0, 1, 2, 3, 4,
你不需要考慮陣列中超出新長度后面的元素,
說明:
為什么回傳數值是整數,但輸出的答案是陣列呢?
請注意,輸入陣列是以“參考”方式傳遞的,這意味著在函式里修改輸入陣列對于呼叫者是可見的,
你可以想象內部操作如下:
// nums 是以“參考”方式傳遞的,也就是說,不對實參做任何拷貝
int len = removeDuplicates(nums);
// 在函式里修改輸入陣列對于呼叫者是可見的,
// 根據你的函式回傳的長度, 它會列印出陣列中該長度范圍內的所有元素,
for (int i = 0; i < len; i++) {
print(nums[i]);
}
我的解法
注意與27題解題思路的比較,
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
ret := 1
for i:=0;i<len(nums)-1;{
if nums[i+1] == nums[i]{
nums = append(nums[:i], nums[i+1:]...)
continue
}
i++
ret++
}
return ret
}
27. 移除元素
題目描述
力扣(LeetCode)鏈接
給定一個陣列 nums 和一個值 val,你需要原地移除所有數值等于 val 的元素,回傳移除后陣列的新長度,
不要使用額外的陣列空間,你必須在原地修改輸入陣列并在使用 O(1) 額外空間的條件下完成,
元素的順序可以改變,你不需要考慮陣列中超出新長度后面的元素,
示例 1:
給定 nums = [3,2,2,3], val = 3,
函式應該回傳新的長度 2, 并且 nums 中的前兩個元素均為 2,
你不需要考慮陣列中超出新長度后面的元素,
示例 2:
給定 nums = [0,1,2,2,3,0,4,2], val = 2,
函式應該回傳新的長度 5, 并且 nums 中的前五個元素為 0, 1, 3, 0, 4,
注意這五個元素可為任意順序,
你不需要考慮陣列中超出新長度后面的元素,
說明:
為什么回傳數值是整數,但輸出的答案是陣列呢?
請注意,輸入陣列是以“參考”方式傳遞的,這意味著在函式里修改輸入陣列對于呼叫者是可見的,
你可以想象內部操作如下:
// nums 是以“參考”方式傳遞的,也就是說,不對實參作任何拷貝
int len = removeElement(nums, val);
// 在函式里修改輸入陣列對于呼叫者是可見的,
// 根據你的函式回傳的長度, 它會列印出陣列中該長度范圍內的所有元素,
for (int i = 0; i < len; i++) {
print(nums[i]);
}
我的解法
func removeElement(nums []int, val int) int {
ret := 0
for i:=0;i<len(nums);{
if nums[i] != val {
nums[ret] = nums[i]
ret++
}
i++
}
return ret
}
83. 洗掉排序鏈表中的重復元素
題目描述
力扣(LeetCode)鏈接
給定一個排序鏈表,洗掉所有重復的元素,使得每個元素只出現一次,
示例 1:
輸入: 1->1->2
輸出: 1->2
示例 2:
輸入: 1->1->2->3->3
輸出: 1->2->3
我的解法
/**
* 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
}
82. 洗掉排序鏈表中的重復元素 II
題目描述
力扣(LeetCode)鏈接
給定一個排序鏈表,洗掉所有含有重復數字的節點,只保留原始鏈表中 沒有重復出現 的數字,
示例 1:
輸入: 1->2->3->3->4->4->5
輸出: 1->2->5
示例 2:
輸入: 1->1->1->2->3
輸出: 2->3
我的解法
遞回法:
/**
* 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
}
206. 反轉鏈表
題目描述
力扣(LeetCode)鏈接
反轉一個單鏈表,
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
我的解法
迭代方式:
/**
* 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
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/houduan/47201.html
標籤:Go
上一篇:選項模式
下一篇:常見排序演算法
