[图片] 返回总目录 日刷 leetcode–简单版 119. 杨辉三角 II 题目描述 [图片] 解题思路 此题与 118 类似,直接冲 118 中返回最后一个数组即可,但是要优化到 O(k)就显得不是那么容易了 公式:[图片] 简单的来说就是前面的数乘以一个分数,这个分数从左到右分别为 n/1, (n-1)/2, ..

日刷 leetcode-- 简单版(五)

返回总目录

日刷 leetcode–简单版


119. 杨辉三角 II

题目描述

image.png

解题思路

示例代码
func getRow(rowIndex int) []int {
	arr := make([]int, rowIndex+1)
	if rowIndex == 0 {
		return arr
	}
	arr[0] = 1
	for i := 1; i <= rowIndex; i++ {
		arr[i] = arr[i-1] * (rowIndex - i + 1) / i
	}
	return arr
}
运行结果

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

121. 买卖股票的最佳时机

题目描述

image.png

解题思路 1

示例代码(无)

解题思路二

示例代码
func maxProfit(prices []int) int {
	maxPrices, min := 0, math.MaxUint32
	for i := 0; i < len(prices); i++ {
		if prices[i] < min {
			min = prices[i] // 最小买入
		}
		if prices[i]-min > maxPrices {
			maxPrices = prices[i] - min // 最大利润
		}
	}
	return maxPrices
}
运行结果

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

122. 买卖股票的最佳时机 II

题目描述

image.png

解题思路

示例代码
func maxProfit1(prices []int) int {
	max := 0
	for i := 0; i < len(prices)-1; i++ {
		if prices[i] < prices[i+1] {
			max += prices[i+1] - prices[i]
		}
	}
	return max
}
运行结果

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

125. 验证回文串

题目描述

image.png

解题思路

示例代码
func isPalindrome(s string) bool {
	for i, j := 0, len(s)-1; i < j; {
		for (s[i] < 48 || (s[i] > 57 && s[i] < 65) || (s[i] < 97 && s[i] > 90) || s[i] > 122) && i < j {
			i++
		}
		for (s[j] < 48 || (s[j] > 57 && s[j] < 65) || (s[j] < 97 && s[j] > 90) || s[j] > 122) && i < j {
			j--
		}
		if ToUpper(s[i]) != ToUpper(s[j]) {
			return false
		}
		i++
		j--
	}
	return true
}

func ToUpper(ascii uint8) uint8 {
	if ascii > 96 && ascii <= 122 {
		ascii -= 32
	}
	return ascii
}
运行结果

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

136. 只出现一次的数字

题目描述

image.png

解题思路 1

示例代码
func singleNumber(nums []int) int {
	list := make(map[int]int, len(nums))
	for i := 0; i < len(nums); i++ {
		list[nums[i]]++
	}
	for k, v := range list {
		if v == 1 {
			return k
		}
	}
	return 0
}
运行结果

执行用时 :12 ms, 在所有 Go 提交中击败了 93.55% 的用户
内存消耗 :5.9 MB, 在所有 Go 提交中击败了 14.34% 的用户

解题思路 2

示例代码
func singleNumbers(nums []int) int {
	a := 0
	for _, v := range nums {
		a ^= v
	}
	return a
}
运行结果

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

141. 环形链表

题目描述

image.png

生成环链表

根据 GO 实现一个单链表,添加如下代码即可实现环列表

func (head *ListNode) CreateCycle(pos int) {
	p := head
	i := 0
	for head.Next != nil {
		if i == pos {
			p = head
		}
		head = head.Next
		i++
	}
	head.Next = p
}

解题思路--哈希

示例代码
func hasCycle(head *ListNode) bool {
	nodes := make(map[*ListNode]int)
	for head != nil {
		if _, ok := nodes[head]; ok {
			return true
		} else {
			nodes[head] = head.Val
		}
		head = head.Next
	}
	return false
}
运行结果

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

解题思路--双指针

示例代码
func hasCycle(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return false
	}
	slow := head
	fast := head.Next
	for slow != fast {
		if fast == nil || fast.Next == nil {
			return false
		}
		slow = slow.Next
		fast = fast.Next.Next
	}
	return true
}
运行结果

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

160. 相交联表

题目描述

image.png
image.png
image.png

解题思路

示例代码
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	if headA == nil || headB == nil {
		return nil
	}
	Pa, Pb := headA,headB
	for Pa != Pb {
		if Pa == nil {
			Pa = headB
			continue
		}
		if Pb == nil {
			Pb = headA
		}
		Pa = Pa.Next
		Pb = Pb.Next
	}
	return Pa
}
运行结果

执行用时 :44 ms, 在所有 golang 提交中击败了 99.33% 的用户
内存消耗 :7.9 MB, 在所有 golang 提交中击败了 5.53% 的用户

  • LeetCode

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

    164 引用 • 61 回帖 • 1 关注
  • 算法
    305 引用 • 229 回帖 • 14 关注
  • golang

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

    375 引用 • 1249 回帖 • 693 关注
回帖
请输入回帖内容...