leetcode刷题之easy系列

原创

f1sh

发布于 2024-07-23 16:51:28

850

发布于 2024-07-23 16:51:28

leetcode刷题之easy系列

go前两天看了看框架，但是发现对于语言的使用还是不够熟练，所以接下来准备用go写一写leetcode的题

这篇文章主要是前100道中的easy部分。

1_twoSum

这个有两种方式可以解决

第一种方式可以通过正常的循环嵌套来解决

 package twosum
 
 // TwoSum
 func TwoSum(nums []int, target int) []int {
     for i,a := range(nums){
         for j,b := range(nums){
             if i == j {
                 continue
             }
             if (a + b ) == target{
                 return []int{i,j}
             }
         }
     }
     return nil
 }

进阶：还可以想出一个时间复杂度小于O(n^2)的算法吗？

这种方式用到了哈希表

 package twosum
 
 func TwoSum(nums []int, target int) []int  {
     hmap := make(map[int]int)
     for i, a := range nums {
         if j, ok := hmap[target-a]; ok{
             return []int{i, j}
         }
         hmap[a] = i
     }
     return nil
 }

9_Palindrome

第一种方法用到了双指针法，用两个指针来遍历数组或字符串，通常一个从起点开始，另一个从终点开始，两者相向移动。

 func isPalindrome(x int) bool {
     if x < 0 {
         return false
     }
     if x == 0 {
         return true
     }
     if x % 10 == 0 {
         return false
     }
 
     arr := make([]int, 0, 32)
     for x > 0 {
         arr = append(arr, x % 10)
         x = x / 10
     }
 
     sz := len(arr)
     for i, j := 0, sz-1; i <= j; i, j = i+1, j-1 {
         if arr[i] != arr[j] {
             return false
         }
     }
 
     return true
 }

在这种解法中我发现了一个有意思的东西，

明明是把容量降低了，速度应该更快了，但是结果确实变慢了

在这个特定的函数中，初始容量设置为 8 或 32 都可以正确地判断是否为回文数。扩容是一个相对昂贵的操作，因为它涉及到内存重新分配和数据复制。选择较大的初始容量（如 32）可以减少扩容次数，从而在处理大数时提供更好的性能，而较小的初始容量（如 8）则更节省内存，但可能会增加扩容次数。

另一种方法是直接反转整数

 func isPalindrome(x int) bool {
     if x < 0 || (x % 10 == 0 && x != 0) {
         return false
     }
     
     reversedNumber := 0
     originalNumber := x
     
     for x > 0 {
         reversedNumber = reversedNumber * 10 + x % 10
         x /= 10
     }
     
     return originalNumber == reversedNumber
 }

进阶：你能不将整数转为字符串来解决这个问题吗？

 func isPalindrome(x int) bool {
     if x < 0 {
         return false
     }
     if x < 10 {
         return true
     }
     s := strconv.Itoa(x)
     length := len(s)
     for i := 0; i <= length/2; i++ {
         if s[i] != s[length-1-i] {
             return false
         }
     }
     return true
 }

13_romanToInt

这一道题没有想象中那么难，定义一个切片，然后从后面一个一个取出字符，然后判定即可

 var roman = map[byte]int{
     'I': 1,
     'V': 5,
     'X': 10,
     'L': 50,
     'C': 100,
     'D': 500,
     'M': 1000,
 }
 
 func romanToInt(s string) int {
     total := 0
     lastint := 0
 
     for i := len(s)-1; i >= 0; i-- {
         num := roman[s[i]]
         if num >= lastint {
             total += num
         } else {
             total -= num
         }
         //if-else 语句。可以减少代码的冗余并提高可读性
         lastint = num
     }
     return total
 }

大致演示一下为什么num<lastint时要total -= num V (5) -> total = 5， lastint = 5 I (1) -> 1 < 5，表示需要执行减法：total = 5 - 1 = 4，lastint = 1 C (100) -> 100 > 1，表示需要执行加法：total = 4 + 100 = 104，lastint = 100 X (10) -> 10 < 100，表示需要执行减法：total = 104 - 10 = 94，lastint = 10 M (1000) -> 1000 > 10，表示需要执行加法：total = 94 + 1000 = 1094，lastint = 1000 C (100) -> 100 < 1000，表示需要执行减法：total = 1094 - 100 = 994，lastint = 100 M (1000) -> 1000 > 100，表示需要执行加法：total = 994 + 1000 = 1994，lastint = 1000

14_longestCommonPrefix

这种方法是利用切片的定义，读取特定长度的切片，然后与前缀进行对比，不匹配则进一步缩短前缀长度，最终结果即为公共前缀

 func longestCommonPrefix(strs []string) string {
 if len(strs) == 0{
     return ""
 }
 if len(strs) == 1{
     return strs[0]
 }
     // 初始化前缀为第一个字符串
     prefix := strs[0]
 
     // 遍历数组中的每个字符串
     for i := 1; i < len(strs); i++ {
         // 更新前缀直到当前字符串包含前缀
         for len(strs[i]) < len(prefix) || strs[i][:len(prefix)] != prefix {
             prefix = prefix[:len(prefix)-1]
             if prefix == "" {
                 return ""
             }
         }
     }
     return prefix
 
 }

20_isValid

这个代码首先for循环遍历字符串的每一个字符，然后将每一个字符进行if判断，判断是否在bracketMap中有这个键，如果有，就把这个键对应的值赋给left,若没有说明遍历到的这个字符是一个左括号，将这个左括号压入rune栈中,然后看回if len(stack) == 0 || stack[len(stack)-1] != left {，这个判断是为了防止出现，第一个就读取到右括号和检查栈顶元素是否是对应的左括号。如果栈顶元素不是 left（对应的左括号），说明匹配失败。

 func isValid(s string) bool {
     // 创建一个栈，用于存储左括号
     stack := []rune{}
 
     // 创建一个映射，用于匹配括号
     bracketMap := map[rune]rune{
         ')': '(',
         '}': '{',
         ']': '[',
     }
 
     for _, char := range s {
         // 如果当前字符是右括号
         if left, ok := bracketMap[char]; ok {
             // 如果栈为空或者栈顶元素不是对应的左括号，返回false
             if len(stack) == 0 || stack[len(stack)-1] != left {
                 return false
             }
             // 弹出栈顶元素
             stack = stack[:len(stack)-1]
             //弹出栈顶元素。即从栈中移除最后一个元素，因为这个元素已经成功匹配了当前的右括号。
         } else {
             // 如果当前字符是左括号，压入栈中
             stack = append(stack, char)
         }
     }
 
     // 如果栈为空，则所有括号都匹配，返回true；否则返回false
     return len(stack) == 0
 }

21_mergeTwoLists

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
   var list ListNode  // 定义一个虚拟头节点，方便操作
   tmp := &list       // tmp 指针指向虚拟头节点
   tmp1 := list1      // tmp1 指向 list1 的头节点
   tmp2 := list2      // tmp2 指向 list2 的头节点

   for { // 无限循环，直到合并完成
      if tmp1 == nil && tmp2 == nil {
         break // 如果两个链表都为空，退出循环
      }

      var node *ListNode
      if tmp1 != nil && tmp2 != nil { // 如果两个链表都不为空
         if tmp1.Val < tmp2.Val { // 比较当前节点值，选择较小的节点
            node = tmp1
            tmp1 = tmp1.Next  // 移动 tmp1 指针
         } else {
            node = tmp2
            tmp2 = tmp2.Next  // 移动 tmp2 指针
         }
      } else if tmp1 != nil { // 如果只有链表1不为空
         node = tmp1
         tmp1 = tmp1.Next  // 移动 tmp1 指针
      } else if tmp2 != nil { // 如果只有链表2不为空
         node = tmp2
         tmp2 = tmp2.Next  // 移动 tmp2 指针
      }

      tmp.Next = node // 将选中的节点接到结果链表上
      tmp = node      // 移动 tmp 指针到新节点
      //将当前节点 tmp 的 Next 指针指向选择的节点 node。
	 //将 tmp 移动到 node 节点，以便继续构建结果链表。
   }

   return list.Next // 返回结果链表的头节点
   //最后返回结果链表的头节点 list.Next（跳过初始的虚拟头节点 list）
   /*
如果直接返回 list 而不是 list.Next，结果会包含一个不需要的初始虚拟头节点，导致链表的第一个节点的值是未初始化的零值。这是因为 list 只是一个临时的虚拟节点，起到占位作用，不包含实际有效的数据。
*/
}

26_removeDuplicates

基础的for循环嵌套

func removeDuplicates(nums []int) int {
	for i := 0; i < len(nums); i++ {
		j := i + 1
		for j < len(nums) {
			if nums[j] == nums[i] {
				nums = append(nums[:j], nums[j+1:]...)
			} else {
				j++
			}
            //内层循环中删除元素后，`j`的值保持不变（通过`else`语句），确保不会跳过任何元素。
		}
	}
	return len(nums)
}

这个算法的时间复杂度为O(n)，因为它仅需一次遍历数组。空间复杂度为O(1)，因为它不需要额外的空间。

func removeDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	last, finder := 0, 0
	for last < len(nums)-1 {
		for nums[finder] == nums[last] {
			finder++
			if finder == len(nums) {
				return last + 1
			}
		}
		nums[last+1] = nums[finder]
		last++
	}
	return last + 1
}

27_removeElement

双指针和填充零值

func removeElement(nums []int, val int) int {
    index := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] != val {
            nums[index] = nums[i]
            index++
        }
    }

    // 将剩余部分填充为零值
    for i := index; i < len(nums); i++ {
        nums[i] = 0 // 对于int类型，零值是0；对于其他类型，根据类型的不同，零值不同
    }
    
    return index
}

双指针方法:

index 用来记录新数组的末尾。
遍历数组 nums，将不等于 val 的元素移动到 index 位置，并递增 index。
遍历完成后，index 的值即为新数组的有效长度。

填充零值:

从 index 到数组末尾的位置用零值填充。
对于 int 类型，零值是 0。对于其他类型，可以根据类型的零值进行填充。

28_strStr

for循环嵌套函数

func strStr(haystack string, needle string) int {
    // 外层循环：遍历 haystack 中每一个可能的起始位置
    for i := 0; ; i++ {
        // 内层循环：从当前起始位置开始检查子串是否等于 needle
        for j := 0; ; j++ {
            // 如果内层循环的索引 j 达到 needle 的长度，说明完全匹配，返回起始位置 i
            if j == len(needle) {
                return i
            }
            // 如果外层循环的索引 i 加上内层循环的索引 j 达到 haystack 的长度，说明遍历完成，没有找到匹配，返回 -1
            if i+j == len(haystack) {
                return -1
            }
            // 如果当前字符不匹配，退出内层循环，外层循环的 i 增加 1，检查下一个起始位置
            if needle[j] != haystack[i+j] {
                break
            }
        }
    }
}

外层循环遍历 haystack 中每一个可能的起始位置 i。内层循环检查从 haystack[i] 开始的子串是否等于 needle。如果完全匹配，返回 i。如果到达 haystack 末尾仍未找到匹配，返回 -1。

这个和第一种算法差别不大

func strStr(haystack string, needle string) int {
    // 获取 haystack 和 needle 的长度
    m, n := len(haystack), len(needle)
    
    // 如果 needle 是空字符串，返回 0
    if n == 0 {
        return 0
    }

    // 遍历 haystack 中的每一个可能的起始位置，范围为 0 到 m-n
    for i := 0; i <= m-n; i++ {
        // 初始化 j 为 0
        j := 0
        
        // 内层循环：检查从当前起始位置 i 开始的子串是否等于 needle
        for j < n && haystack[i+j] == needle[j] {
            j++
        }
        
        // 如果 j 达到了 needle 的长度，说明完全匹配，返回当前起始位置 i
        if j == n {
            return i
        }
    }
    
    // 如果遍历完成仍未找到匹配项，返回 -1
    return -1
}

可以使用go中的内置函数来解决这个问题

该函数用于查找子字符串在字符串中第一次出现的位置。如果子字符串不存在，则返回 -1。

func strStr(haystack string, needle string) int {
    return strings.Index(haystack, needle)
}

35_searchInsert

这道题的主要难点在于要按顺序插入

func searchInsert(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)>>1
		if nums[mid] >= target {
			high = mid - 1
		} else {
			if (mid == len(nums)-1) || (nums[mid+1] >= target) {
				return mid + 1
			}
			low = mid + 1
		}
	}
	return 0
}

这道题有两个需要注意的点，一个是二分查找所需的时间复杂度为 O(logn)。另一个是使用右移操作符 >> 进行除以2操作，可以防止溢出。

58_lengthOfLastWord

func lengthOfLastWord(s string) int {
	words := strings.Fields(s)
	a := len(words)
	return len(words[a-1])
}

strings.Fields 是 Go 标准库中 strings 包提供的一个函数，用于将字符串分割成切片，并自动忽略空白字符。它的作用是根据空白字符（如空格、制表符等）将输入字符串拆分成多个子字符串，并将这些子字符串存储在一个切片中。

66_plusOne

func plusOne(digits []int) []int {
	for i := len(digits) - 1; i >= 0; i-- {
		digits[i]++
		if digits[i] != 10 {
			// no carry
			return digits
		}
		// carry
		digits[i] = 0
	}
	// all carry
	digits[0] = 1
	digits = append(digits, 0)
	return digits
}

很妙的思路

67_addBinary

这个代码有点难度，主要是对应的进制转换函数在这里不能用了。

func addBinary(a string, b string) string {
    ans := ""
    carry := 0
    lenA, lenB := len(a), len(b)
    n := max(lenA, lenB)
    //通过定义的max函数找出最长的字符串

    for i := 0; i < n; i++ {
        // 如果a还有未处理的字符，加入到carry中
        if i < lenA {
            carry += int(a[lenA-i-1] - '0')
            //字符减去字符 '0'： 在 Go 中，字符是以 ASCII 码表示的。字符 '0' 的 ASCII 值是 48，字符 '1' 的 ASCII 值是 49。因此，将字符 '0' 或 '1' 减去字符 '0' 的结果是整数 0 或 1：
        }
        // 如果b还有未处理的字符，加入到carry中
        if i < lenB {
            carry += int(b[lenB-i-1] - '0')
            //字符减去字符 '0'： 在 Go 中，字符是以 ASCII 码表示的。字符 '0' 的 ASCII 值是 48，字符 '1' 的 ASCII 值是 49。因此，将字符 '0' 或 '1' 减去字符 '0' 的结果是整数 0 或 1：
        }
        // 计算当前位的结果，并加入到ans字符串的最前面
        ans = strconv.Itoa(carry%2) + ans
        //strconv.Itoa用于将整数转换为字符串
        // 计算新的进位
        carry /= 2
    }
    // 如果最后有进位，加入到结果的最前面
    if carry > 0 {
        ans = "1" + ans
    }
    return ans
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

69_mySqrt

func mySqrt(x int) int {
	if x <= 1 {
		return x
	}

	end, start := x, 1

	for start <= end {
		mid := start + (end-start)/2
		if mid*mid == x {
			return mid
		}
		if mid*mid < x {
			start = mid + 1
		}
		if mid*mid > x {
			end = mid - 1
		}
	}
	return end
}

二分查找更新逻辑：

如果 mid*mid < x，需要更新 start = mid + 1 而不是 start = mid。
如果 mid*mid > x，需要更新 end = mid - 1 而不是 end = mid。

返回值逻辑：

在找不到准确的平方根时，应该返回 end 而不是 start。end 会是小于等于 x 平方根的最大整数。

70_climbStairs

这道题可以使用动态规划，最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子

f(x)=f(x−1)+f(x−2)

func climbStairs(n int) int {
	p, q, r := 0, 0, 1
	for i := 0; i < n; i++ {
		p = q
		q = r
		r = p + q
	}
	return r
}

83_deleteDuplicates

比较简单的一道删除链表特定元素的题

直接使用原链表

func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	cur := head
	for cur.Next != nil {
		if cur.Next.Val == cur.Val {
		cur.Next = cur.Next.Next
		}else {
			cur = cur.Next
		}
	}
	return head
}

88_merge

func merge(nums1 []int, m int, nums2 []int, n int) {
	// Initialize pointers for nums1 and nums2
	i, j, k := m-1, n-1, m+n-1

	// Iterate from the end of nums1 and nums2 and fill nums1 from the end
	for j >= 0 {
		if i >= 0 && nums1[i] > nums2[j] {
			nums1[k] = nums1[i]
			i--
		} else {
			nums1[k] = nums2[j]
			j--
		}
		k--
	}
}

94_inorderTraversal

这个二叉树有点难，原理很简单，应用到代码上有点看不懂了，不过最后还是解决了

递归

func inorderTraversal(root *TreeNode) (ans []int) {
	var dfs func(*TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Left)
		ans = append(ans, root.Val)
		dfs(root.Right)
	}
	dfs(root)
	return
}

先从最下面的节点开始拼接，最左子树拼接完之后，拼接右子树。

迭代

func inorderTraversal(root *TreeNode) (res []int) {
	stack := []*TreeNode{}
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, root.Val)
		root = root.Right
	}
	return
}

100_isSameTree

深度优先搜索

代码不难理解。

func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}

	if p == nil || q == nil {
		return false
	}

	if p.Val != q.Val {
		return false
	}
	return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)

}

广度优先搜索

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        }
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        queue1.offer(p);
        queue2.offer(q);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            if (node1.val != node2.val) {
                return false;
            }
            TreeNode left1 = node1.left, right1 = node1.right, left2 = node2.left, right2 = node2.right;
            if (left1 == null ^ left2 == null) {
                return false;
            }
            if (right1 == null ^ right2 == null) {
                return false;
            }
            if (left1 != null) {
                queue1.offer(left1);
            }
            if (right1 != null) {
                queue1.offer(right1);
            }
            if (left2 != null) {
                queue2.offer(left2);
            }
            if (right2 != null) {
                queue2.offer(right2);
            }
        }
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

算法

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

算法

登录后参与评论

0 条评论

热度

leetcode刷题之easy系列

leetcode刷题之easy系列

leetcode刷题之easy系列

1_twoSum

9_Palindrome

13_romanToInt

14_longestCommonPrefix

20_isValid

21_mergeTwoLists

26_removeDuplicates

27_removeElement

28_strStr

35_searchInsert

58_lengthOfLastWord

66_plusOne

67_addBinary

69_mySqrt

70_climbStairs

83_deleteDuplicates

88_merge

94_inorderTraversal

100_isSameTree

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐