算法习题练习
1. 需求：给定输入字符串”aa b c” 以空格分隔的话输出[“aa”, “b”, “c”]；输入字符串 aa “b c d” ee 输出为[“aa”, “b c d”, ee]; 输入字符串为 aa “b c d 输出为[“aa”, “\”b”, “c”, “d”]。请用golang实现该需求
你可以使用 Golang 中的字符串分割函数来实现这个需求。在 Golang 中，可以使用 `strings.Split()` 函数来按照指定的分隔符将字符串分割为多个子串。为了满足给定的需求，我们需要处理引号内的空格和不在引号内的空格。下面是实现该需求的 Golang 代码：
“`go
package main
import (
“fmt”
“strings”
)
func splitWithQuotes(input string) []string {
var result []string
var inQuotes bool
var current string
for _, c := range input {
if c == ‘”‘ {
inQuotes = !inQuotes
}
if !inQuotes && c == ‘ ‘ {
// 如果不在引号内且遇到空格，将当前字符串添加到结果中
if current != “” {
result = append(result, current)
}
current = “”
} else {
// 在引号内或者非空格字符，将字符添加到当前字符串
current += string(c)
}
}
// 处理最后一个字符串
if current != “” {
result = append(result, current)
}
return result
}
func main() {
input1 := `aa b c`
input2 := `aa “b c d” ee`
input3 := `aa “b c d`
fmt.Println(splitWithQuotes(input1)) // Output: [aa b c]
fmt.Println(splitWithQuotes(input2)) // Output: [aa “b c d” ee]
fmt.Println(splitWithQuotes(input3)) // Output: [aa “b c d]
}
“`
在这个实现中，我们使用 `inQuotes` 变量来记录是否在引号内。然后，我们遍历输入字符串的每个字符，根据引号内外的情况来处理字符串拼接和分割。最后，将分割得到的子串添加到结果中并返回。
2 需求：给你一个int数组[1,3,4,5,6,2]，请使用golang语言计算出数组中两个元素和的最大值，不能用map、set等
对不起，我之前的实现依然使用了哈希表。如果不使用排序和哈希表，我们可以采用一种更简单的方法，通过一次遍历找到最大的两个元素。
以下是不使用排序和哈希表的 Golang 代码：
“`go
package main
import “fmt”
func findMaxSum(nums []int) int {
// 初始化两个变量，用于存储最大的两个元素
max1, max2 := 0, 0
// 遍历数组
for _, num := range nums {
// 如果当前元素大于 max1，则更新 max2 和 max1
if num > max1 {
max2 = max1
max1 = num
} else if num > max2 { // 如果当前元素大于 max2，则只更新 max2
max2 = num
}
}
// 返回最大的两个元素的和
return max1 + max2
}
func main() {
nums := []int{1, 3, 4, 5, 6, 2}
fmt.Println(findMaxSum(nums)) // Output: 11 (6 + 5 = 11)
}
“`
在这个实现中，我们通过一次遍历找到了最大的两个元素 `max1` 和 `max2`。不需要排序和哈希表，直接找到最大的两个元素的和并返回即可。这个实现的时间复杂度是 O(n)，其中 n 是数组的长度。
3 需求：请用golang 语言实现：不适用内置数学公式，编码实现(1+2*3+1)/2=4的公式。输入为字符串，可任意组合计算表达式
你可以使用栈数据结构来实现一个简单的计算器来处理这个需求。栈可以帮助你处理运算符的优先级和操作数的计算。以下是使用 Golang 实现的代码：
“`go
package main
import (
“fmt”
“strconv”
“unicode”
)
func calculate(s string) int {
// 定义两个栈，一个用于存储数字，一个用于存储运算符
numStack := make([]int, 0)
opStack := make([]byte, 0)
// 定义优先级映射表
precedence := map[byte]int{
‘+’: 1,
‘-‘: 1,
‘*’: 2,
‘/’: 2,
}
// 辅助函数：根据运算符计算结果
calculateResult := func(op byte, num1, num2 int) int {
switch op {
case ‘+’:
return num1 + num2
case ‘-‘:
return num1 – num2
case ‘*’:
return num1 * num2
case ‘/’:
return num1 / num2
default:
return 0
}
}
// 遍历输入字符串
i := 0
for i < len(s) {
ch := s[i]
i++
if unicode.IsDigit(rune(ch)) {
// 如果是数字，继续读取直到遇到非数字字符
start := i – 1
for i < len(s) && unicode.IsDigit(rune(s[i])) {
i++
}
num, _ := strconv.Atoi(s[start:i])
numStack = append(numStack, num)
} else if ch == ‘(‘ {
// 如果是左括号，入运算符栈
opStack = append(opStack, ch)
} else if ch == ‘)’ {
// 如果是右括号，进行计算直到遇到左括号
for len(opStack) > 0 && opStack[len(opStack)-1] != ‘(‘ {
num2 := numStack[len(numStack)-1]
numStack = numStack[:len(numStack)-1]
num1 := numStack[len(numStack)-1]
numStack = numStack[:len(numStack)-1]
op := opStack[len(opStack)-1]
opStack = opStack[:len(opStack)-1]
result := calculateResult(op, num1, num2)
numStack = append(numStack, result)
}
// 弹出左括号
opStack = opStack[:len(opStack)-1]
} else if ch == ‘+’ || ch == ‘-‘ || ch == ‘*’ || ch == ‘/’ {
// 如果是运算符，进行计算直到运算符栈为空或者栈顶运算符优先级小于当前运算符
for len(opStack) > 0 && opStack[len(opStack)-1] != ‘(‘ && precedence[opStack[len(opStack)-1]] >= precedence[ch] {
num2 := numStack[len(numStack)-1]
numStack = numStack[:len(numStack)-1]
num1 := numStack[len(numStack)-1]
numStack = numStack[:len(numStack)-1]
op := opStack[len(opStack)-1]
opStack = opStack[:len(opStack)-1]
result := calculateResult(op, num1, num2)
numStack = append(numStack, result)
}
opStack = append(opStack, ch)
}
}
// 计算剩余的运算
for len(opStack) > 0 {
num2 := numStack[len(numStack)-1]
numStack = numStack[:len(numStack)-1]
num1 := numStack[len(numStack)-1]
numStack = numStack[:len(numStack)-1]
op := opStack[len(opStack)-1]
opStack = opStack[:len(opStack)-1]
result := calculateResult(op, num1, num2)
numStack = append(numStack, result)
}
return numStack[0]
}
func main() {
s := “(1+2*3+1)/2”
fmt.Println(calculate(s)) // Output: 4
}
“`
在这个实现中，我们使用了两个栈 `numStack` 和 `opStack`，一个用于存储数字，一个用于存储运算符。我们遍历输入字符串，并根据优先级进行计算和处理。最终得到的 `numStack`
4 需求：请用golang实现两个链表数字相加
要实现两个链表数字相加，首先需要定义链表的数据结构，并编写函数来进行链表数字的相加操作。以下是使用 Golang 实现的代码：
“`go
package main
import “fmt”
// Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
// 创建一个哑节点(dummy)作为结果链表的头部
dummy := &ListNode{}
// 定义当前节点和进位
current, carry := dummy, 0
// 遍历两个链表进行相加操作
for l1 != nil || l2 != nil {
// 取两个链表当前节点的值
val1, val2 := 0, 0
if l1 != nil {
val1 = l1.Val
l1 = l1.Next
}
if l2 != nil {
val2 = l2.Val
l2 = l2.Next
}
// 计算当前节点的值和进位
sum := val1 + val2 + carry
carry = sum / 10
current.Next = &ListNode{Val: sum % 10}
current = current.Next
}
// 如果最后还有进位，添加一个新节点
if carry > 0 {
current.Next = &ListNode{Val: carry}
}
return dummy.Next
}
func main() {
// 创建两个测试链表
l1 := &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 3}}}
l2 := &ListNode{Val: 5, Next: &ListNode{Val: 6, Next: &ListNode{Val: 4}}}
// 计算两个链表数字相加的结果
result := addTwoNumbers(l1, l2)
// 输出结果链表的值
for result != nil {
fmt.Printf(“%d “, result.Val)
result = result.Next
}
// Output: 7 0 8 (表示结果为 342 + 465 = 807)
}
“`
在这个实现中，我们首先定义了链表的数据结构 `ListNode`，包含一个整数值 `Val` 和指向下一个节点的指针 `Next`。然后，我们编写了 `addTwoNumbers` 函数来实现链表数字的相加操作。该函数会遍历两个输入链表，将对应位置的数字相加，并处理进位。然后将相加结果构建成新的链表并返回。测试用例中演示了两个链表的数字相加的结果。
5. 需求：请用golang实现两个有序链表合并
要合并两个有序链表，你可以遍历这两个链表并将节点按照顺序合并成一个新的链表。以下是使用 Golang 实现的代码：
“`go
package main
import “fmt”
// Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
// 创建一个哑节点(dummy)作为结果链表的头部
dummy := &ListNode{}
// 定义当前节点
current := dummy
// 遍历两个链表进行合并操作
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
current.Next = l1
l1 = l1.Next
} else {
current.Next = l2
l2 = l2.Next
}
current = current.Next
}
// 将剩余的节点直接连接到结果链表的尾部
if l1 != nil {
current.Next = l1
}
if l2 != nil {
current.Next = l2
}
return dummy.Next
}
func main() {
// 创建两个测试有序链表
l1 := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 4}}}
l2 := &ListNode{Val: 1, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4}}}
// 合并两个有序链表
mergedList := mergeTwoLists(l1, l2)
// 输出合并后的链表结果
for mergedList != nil {
fmt.Printf(“%d “, mergedList.Val)
mergedList = mergedList.Next
}
// Output: 1 1 2 3 4 4
}
“`
在这个实现中，我们首先定义了链表的数据结构 `ListNode`，包含一个整数值 `Val` 和指向下一个节点的指针 `Next`。然后，我们编写了 `mergeTwoLists` 函数来合并两个有序链表。该函数会遍历两个输入链表，并将节点按照顺序合并成一个新的链表。最后，我们输出合并后的链表结果。测试用例中演示了两个有序链表的合并结果。
6 需求：请用golang实现 2的2000次方，不能用内置数学函数
我明白了，对不起我之前的实现中仍然使用了 `math/big` 包。如果不使用任何标准库和数学包，我们可以通过手动实现大整数的乘法来计算 2 的 2000 次方。以下是用 Golang 实现的代码：
“`go
package main
import “fmt”
func multiplyByTwo(num []int) []int {
// 计算一个大整数数组乘以2的结果
carry := 0
for i := len(num) – 1; i >= 0; i– {
val := num[i]*2 + carry
num[i] = val % 10
carry = val / 10
}
if carry > 0 {
num = append([]int{carry}, num…)
}
return num
}
func powerOfTwo(exp int) []int {
// 初始化一个大整数数组为1
result := []int{1}
// 逐步计算2的exp次方
for i := 0; i < exp; i++ {
result = multiplyByTwo(result)
}
return result
}
func main() {
exp := 2000
power := powerOfTwo(exp)
for _, digit := range power {
fmt.Printf(“%d”, digit)
}
fmt.Println()
}
“`
在这个实现中，我们使用一个整数数组 `num` 来表示大整数，并实现了一个手动的乘法函数 `multiplyByTwo`，用于将大整数数组乘以 2。然后，我们使用 `powerOfTwo` 函数来逐步计算 2 的 `exp` 次方。最后，我们将结果输出，得到 2 的 2000 次方的结果。
请注意，由于 Golang 中整数长度有限，如果计算的结果超出了整数能表示的范围，可能会导致溢出。在这个实现中，我们只是输出结果的每一位，而不是将整个结果当做一个整数输出，以避免溢出问题。
本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/194845ace2.html
相关推荐
-
IDEA2023创建Maven Archetype和创建旧版本Maven的区别，主要是针对Maven Archtype。
IDEA2023创建Maven Archetype和创建旧版本Maven的区别，主要是针对Maven Archtype。 使用配置： 编译器：idea JDK：jdk 17 注意：…
-
【java】使用 BeanUtils.copyProperties 11个坑(注意事项)
文章目录 背景 第1个坑： 类型不匹配 第2个坑: `BeanUtils.copyProperties`是浅拷贝 第3个坑：属性名称不一致 第4个坑：Null 值覆盖 第5个坑：注…
-
java使用jdbcTemplate查询并插入百万级数据解决方案
背景：使用JdbcTemplate查询500万数据，然后插入到数据库。 这么多的数据按照普通的方式直接查询然后插入，服务器肯定会挂掉，我尝试过使用分页查询的方式去进行分批查询插入，…
-
SpringBoot动态导出word文档（完美实整教程 复制即可使用，不能实现你找我）
背景 最近有一个需求是需要动态导出合同、订单等信息，导出一个word文档供客户进行下载查看。 需要导出的word文件，主要可以分为两种类型。 导出固定内容和图片的word文档 导出…
-
解决Correct the classpath of your application so that it contains compatible versions
springboot启动失败 报错Correct the classpath of your application so that it contains compatible …
-
java大文件上传，大文件下载解决方案
一.大文件上传解决方案： 普通的Servlet文件上传： 使用Java Servlet技术，通过表单提交文件，然后在服务器端使用流将文件写入磁盘。这适用于小文件，但不太适合大文件，…
-
java如何将对象转换为map？如何将map转换为对象？
目录 1、使用 BeanUtils 2、ObjectMapper 3、Gson 4、Jackson 5、手动进行转换 1、使用 BeanUtils BeanUtil…
-
【js】JavaScript清除所有（多个）定时器的方法：
文章目录 一、停止单个定时器 二、暂停与恢复定时器 三、使用Promise来管理定时器 四、使用ES6特性管理定时器 五、案例（定时获取页面列表数据） 一、停止单个定时器 #在某些…
-
如何mock当前类的私有方法
背景 基础知识 mockito单元测试：它的做法是mock掉当前类的所有外部依赖，保障自己的代码没有问题。举个例子，如果数据库查询的语句出了问题，单元测试不会测试出来。因为它直接m…
-
解决IDEA报错：无效的目标发行版: 17
解决IDEA报错：无效的目标发行版: 17 目录 解决IDEA报错：无效的目标发行版: 17 报错由来 解决报错 【1】检查setting设置，查看编译器编译模块的编译版本是否是你…
