当前位置： 首页 > article >正文

Golang每日一练(leetDay0007)

article 2025/1/15 9:26:17

目录

19. 删除链表的倒数第 N 个结点 Remove-nth-node-from-end-of-list  ★★

20. 有效的括号 Valid Parentheses  ★

21. 合并两个有序链表 Mmerge-two-sorted-lists  ★

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

19. 删除链表的倒数第 N 个结点 Remove-nth-node-from-end-of-list

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

代码：

package main

import (
	"fmt"
)

type ListNode struct {
	data int
	next *ListNode
}

func (head *ListNode) build(list []int) {
	for i := len(list) - 1; i >= 0; i-- {
		p := &ListNode{data: list[i]}
		p.next = head.next
		head.next = p
	}
}

func (head *ListNode) travel() {
	for p := head.next; p != nil; p = p.next {
		fmt.Print(p.data)
		if p.next != nil {
			fmt.Print("->")
		}
	}
	fmt.Println("<nil>")
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	var fast, slow *ListNode
	fast = head
	slow = head
	for i := 0; i < n; i++ {
		fast = fast.next
	}
	if fast == nil {
		head = head.next
		return head
	}
	for fast.next != nil {
		fast = fast.next
		slow = slow.next
	}
	slow.next = slow.next.next
	return head
}

func main() {

	nums := []int{1, 2, 3, 4, 5}
	head := &ListNode{}
	head.build(nums)
	head.travel()
	head = removeNthFromEnd(head, 2)
	head.travel()

	head = &ListNode{}
	head.build([]int{1})
	head.travel()
	head = removeNthFromEnd(head, 1)
	head.travel()

	head = &ListNode{}
	head.build([]int{1, 2})
	head.travel()
	head = removeNthFromEnd(head, 1)
	head.travel()

}

输出：

1->2->3->4->5<nil>
1->2->3->5<nil>

1<nil>
<nil>

1->2<nil>
1<nil>

其他解法：

package main

import (
	"fmt"
)

type ListNode struct {
	data int
	next *ListNode
}

func (head *ListNode) build(list []int) {
	for i := len(list) - 1; i >= 0; i-- {
		p := &ListNode{data: list[i]}
		p.next = head.next
		head.next = p
	}
}

func (head *ListNode) travel() {
	for p := head.next; p != nil; p = p.next {
		fmt.Print(p.data)
		if p.next != nil {
			fmt.Print("->")
		}
	}
	fmt.Println("<nil>")
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	if head == nil {
		return nil
	}
	len := countBackwards(head, n)
	if n >= len {
		return head.next
	}
	return head
}

func countBackwards(p *ListNode, n int) int {
	if p.next == nil {
		return 1
	}
	res := countBackwards(p.next, n) + 1
	if res == n+1 {
		if n == 1 {
			p.next = nil
		} else {
			p.next = p.next.next
		}
	}
	return res
}

func main() {

	nums := []int{1, 2, 3, 4, 5}
	head := &ListNode{}
	head.build(nums)
	head.travel()
	head = removeNthFromEnd(head, 2)
	head.travel()

	head = &ListNode{}
	head.build([]int{1})
	head.travel()
	head = removeNthFromEnd(head, 1)
	head.travel()

	head = &ListNode{}
	head.build([]int{1, 2})
	head.travel()
	head = removeNthFromEnd(head, 1)
	head.travel()

}

20. 有效的括号 Valid Parentheses

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

提示：

  • 1 <= s.length <= 10^4
  • s 仅由括号 '()[]{}' 组成

代码：

package main

import (
	"fmt"
)

func isValid(s string) bool {
	stack := make([]byte, 0)
	for _, ch := range s {
		switch ch {
		case '(':
			fallthrough
		case '[':
			fallthrough
		case '{':
			stack = append(stack, byte(ch))
		case ')':
			if len(stack) > 0 && stack[len(stack)-1] == '(' {
				stack = stack[:len(stack)-1]
			} else {
				return false
			}
		case ']':
			if len(stack) > 0 && stack[len(stack)-1] == '[' {
				stack = stack[:len(stack)-1]
			} else {
				return false
			}
		case '}':
			if len(stack) > 0 && stack[len(stack)-1] == '{' {
				stack = stack[:len(stack)-1]
			} else {
				return false
			}
		}
	}
	return len(stack) == 0
}

func main() {

	fmt.Println(isValid("()"))
	fmt.Println(isValid("()[]{}"))
	fmt.Println(isValid("(]"))
	fmt.Println(isValid("([)]"))
	fmt.Println(isValid("{()}"))

}

输出：

true
true
false
false
true

21. 合并两个有序链表 Mmerge-two-sorted-lists

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

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

代码：

package main

import (
	"fmt"
)

type ListNode struct {
	data int
	next *ListNode
}

func (head *ListNode) build(list []int) {
	for i := len(list) - 1; i >= 0; i-- {
		p := &ListNode{data: list[i]}
		p.next = head.next
		head.next = p
	}
}

func (head *ListNode) travel() {
	for p := head.next; p != nil; p = p.next {
		fmt.Print(p.data)
		if p.next != nil {
			fmt.Print("->")
		}
	}
	fmt.Println("<nil>")
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	res := &ListNode{}
	p := res
	for l1 != nil && l2 != nil {
		if l1.data < l2.data {
			p.next = l1
			l1 = l1.next
		} else {
			p.next = l2
			l2 = l2.next
		}
		p = p.next
	}
	if l1 != nil {
		p.next = l1
	} else {
		p.next = l2
	}
	return res.next
}

func main() {

	nums1 := []int{1, 2, 4}
	nums2 := []int{1, 3, 4}

	l1 := &ListNode{}
	l2 := &ListNode{}
	l1.build(nums1)
	l2.build(nums2)
	l1.travel()
	l2.travel()

	result := mergeTwoLists(l1, l2).next
	result.travel()

}

输出：

1->2->4<nil>
1->3->4<nil>
1->1->2->3->4->4<nil>

递归法：

package main

import (
	"fmt"
)

type ListNode struct {
	data int
	next *ListNode
}

func (head *ListNode) build(list []int) {
	for i := len(list) - 1; i >= 0; i-- {
		p := &ListNode{data: list[i]}
		p.next = head.next
		head.next = p
	}
}

func (head *ListNode) travel() {
	for p := head.next; p != nil; p = p.next {
		fmt.Print(p.data)
		if p.next != nil {
			fmt.Print("->")
		}
	}
	fmt.Println("<nil>")
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	if l1.data < l2.data {
		l1.next = mergeTwoLists(l1.next, l2)
		return l1
	}
	l2.next = mergeTwoLists(l1, l2.next)
	return l2
}

func main() {

	n1 := []int{1, 2, 4}
	n2 := []int{1, 3, 4}

	l1 := &ListNode{}
	l2 := &ListNode{}
	l1.build(n1)
	l2.build(n2)
	l1.travel()
	l2.travel()

	result := mergeTwoLists(l1, l2).next
	result.travel()

}

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

​

Golang每日一练 专栏

​

Python每日一练 专栏

​

C/C++每日一练 专栏

​

Java每日一练 专栏


http://www.kler.cn/a/909.html

相关文章：

  • unity——Preject3——面板基类
  • vue3+vite+ts集成第三方js
  • 2 XDMA IP中断
  • 数据分析-使用Excel透视图/表分析禅道数据
  • 语音技术与人工智能：智能语音交互的多场景应用探索
  • 【2024年华为OD机试】(C卷,100分)- 攀登者1 （Java JS PythonC/C++）
  • 【基础算法】单链表的OJ练习(6) # 复制带随机指针的链表 #
  • 【前端】深入浅出缓存原理
  • 彻底理解Session、Cookie、Token，入门及实战
  • ASEMI代理瑞萨TW9992AT-NA1-GE汽车芯片
  • 5.springcloud微服务架构搭建 之 《springboot集成Hystrix》
  • OSPF*MGRE实验：
  • Microsoft Word 远程代码执行漏洞（CVE-2023-21716）
  • 掌握CentOS7环境下的Docker使用（六）Link实现单向通信、brige网桥实现双向通信、特权模式、Volume数据共享
  • Spring Cloud -- GateWay
  • 全连接神经网络
  • 算法---完成任务的最少工作时间段
  • 集成方法！
  • Android开发的这一年里，Jetpack的Room源码是怎么狠狠奖励我的？
  • mysql面试经典问题
  • Qt5.12实战之QByteArray与字符指针及字符串转换
  • 奇异值分解(SVD)原理与在降维中的应用
  • 关于.Net和Java的看法——我见过最牛的一个小实习生经历
  • 女子举重问题
  • 力扣-排名靠前的旅行者
  • 【Java版oj】day10 井字棋、密码强度等级