Golang每日一练(leetDay0073) 实现前缀树、最短子数组

简介: Golang每日一练(leetDay0073) 实现前缀树、最短子数组

208. 实现 Trie (前缀树) Implement-trie-prefix-tree


Trie(发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。


请你实现 Trie 类:


   Trie() 初始化前缀树对象。


   void insert(String word) 向前缀树中插入字符串 word 。


   boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。


   boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false 。


示例:


输入

["Trie", "insert", "search", "search", "startsWith", "insert", "search"]

[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]


输出

[null, null, true, false, true, null, true]


解释

Trie trie = new Trie();

trie.insert("apple");

trie.search("apple");   // 返回 True

trie.search("app");     // 返回 False

trie.startsWith("app"); // 返回 True

trie.insert("app");

trie.search("app");     // 返回 True


提示:

   1 <= word.length, prefix.length <= 2000

   word 和 prefix 仅由小写英文字母组成

   insert、search 和 startsWith 调用次数 总计 不超过 3 * 10^4 次


代码:

package main
import "fmt"
type Trie struct {
  isEnd bool
  next  [26]*Trie
}
/** Initialize your data structure here. */
func Constructor() Trie {
  return Trie{}
}
/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
  node := this
  for _, ch := range word {
    if node.next[ch-'a'] == nil {
      node.next[ch-'a'] = &Trie{}
    }
    node = node.next[ch-'a']
  }
  node.isEnd = true
}
/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
  node := this
  for _, ch := range word {
    if node = node.next[ch-'a']; node == nil {
      return false
    }
  }
  return node.isEnd
}
/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
  node := this
  for _, ch := range prefix {
    if node = node.next[ch-'a']; node == nil {
      return false
    }
  }
  return true
}
func main() {
  trie := Constructor()
  trie.Insert("apple")
  fmt.Println(trie.Search("apple"))   // 返回 true
  fmt.Println(trie.Search("app"))     // 返回 false
  fmt.Println(trie.StartsWith("app")) // 返回 true
  trie.Insert("app")
  fmt.Println(trie.Search("app")) // 返回 true
}

输出:

true

false

true

true


209. 长度最小的子数组 Minimum-size-subarray-sum


给定一个含有 n 个正整数的数组和一个正整数 target 。


找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。


示例 1:

输入:target = 7, nums = [2,3,1,2,4,3]

输出:2

解释:子数组 [4,3] 是该条件下的长度最小的子数组。


示例 2:

输入:target = 4, nums = [1,4,4]

输出:1


示例 3:

输入:target = 11, nums = [1,1,1,1,1,1,1,1]

输出:0


提示:

   1 <= target <= 10^9

   1 <= nums.length <= 10^5

   1 <= nums[i] <= 10^5


进阶:

   如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。


代码:

package main
import "fmt"
func minSubArrayLen(target int, nums []int) int {
  minLen := 1 << 31
  left, right := 0, 0
  sum := 0
  for right < len(nums) {
    sum += nums[right]
    for sum >= target {
      minLen = min(minLen, right-left+1)
      sum -= nums[left]
      left++
    }
    right++
  }
  if minLen == 1<<31 {
    return 0
  }
  return minLen
}
func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}
func main() {
  nums := []int{2, 3, 1, 2, 4, 3}
  fmt.Println(minSubArrayLen(7, nums))
  nums = []int{1, 4, 4}
  fmt.Println(minSubArrayLen(4, nums))
  nums = []int{1, 1, 1, 1, 1, 1, 1, 1}
  fmt.Println(minSubArrayLen(11, nums))
}



输出:

2

1

0

目录
相关文章
|
3月前
|
Go
Golang语言之数组(array)快速入门篇
这篇文章是关于Go语言中数组的详细教程,包括数组的定义、遍历、注意事项、多维数组的使用以及相关练习题。
37 5
|
4月前
|
监控 Serverless Go
Golang 开发函数计算问题之Go 语言中切片扩容时需要拷贝原数组中的数据如何解决
Golang 开发函数计算问题之Go 语言中切片扩容时需要拷贝原数组中的数据如何解决
|
7月前
|
程序员 Go
第七章 Golang数组和切片
第七章 Golang数组和切片
51 2
|
7月前
|
Shell Linux 算法
Shell编程——弱数据类型的脚本语言快速入门指南
Shell编程——弱数据类型的脚本语言快速入门指南
94 0
Shell编程——弱数据类型的脚本语言快速入门指南
|
7月前
|
Go Linux Shell
Linux 终端命令之文件浏览(2) more
Linux 终端命令之文件浏览(2) more
65 0
Linux 终端命令之文件浏览(2) more
|
7月前
|
Shell 机器学习/深度学习 Linux
Linux 终端操作命令(2)内部命令
Linux 终端操作命令(2)内部命令
67 0
Linux 终端操作命令(2)内部命令
|
7月前
|
C++ 算法 存储
力扣 C++|一题多解之动态规划专题(2)
力扣 C++|一题多解之动态规划专题(2)
64 0
力扣 C++|一题多解之动态规划专题(2)
|
7月前
|
Python 索引
Python Numpy入门基础(一)创建数组
Python Numpy入门基础(一)创建数组
73 0
Python Numpy入门基础(一)创建数组
|
7月前
|
Java 容器 程序员
Java语言程序设计试卷6套
Java语言程序设计试卷6套
785 0
Java语言程序设计试卷6套
|
7月前
|
Java Go C++
Golang每日一练(leetDay0120) 反转字符串中的元音字母、前K个高频元素
Golang每日一练(leetDay0120) 反转字符串中的元音字母、前K个高频元素
71 0
Golang每日一练(leetDay0120) 反转字符串中的元音字母、前K个高频元素