golang力扣leetcode 第 286 场周赛

简介: golang力扣leetcode 第 286 场周赛

前言

难度只能算都是中等题

第一题

2215.找出两数组的不同

2215.找出两数组的不同

题解

easy题,太简单,不解释了

代码

func findDifference(nums1, nums2 []int) [][]int {
  mp1, mp2 := map[int]bool{}, map[int]bool{}
  for _, v := range nums1 {
    mp1[v] = true
  }
  for _, v := range nums2 {
    mp2[v] = true
  }
  var a, b []int
  for v := range mp1 {
    if !mp2[v] {
      a = append(a, v)
    }
  }
  for v := range mp2 {
    if !mp1[v] {
      b = append(b, v)
    }
  }
  return [][]int{a, b}
}

第二题

2216.美化数组的最少删除数

2216.美化数组的最少删除数

题解

贪心:通过题目给的数组,我们来构造美化数组stack

  • 如果当前位置是偶数,那么直接添加进stack
  • 如果当前位置是奇数,并且当前数组的值与数组stack的最新值不相等,则直接添加进stack,否则跳过


遍历完数组后,如果数组stack的奇数个,则直接删去最后一个即可

代码

func minDeletion(nums []int) int {
  stack := make([]int, 0)
  cnt := 0
  for i := 0; i < len(nums); i++ {
    if cnt%2 != 0 {
      if nums[i] != stack[cnt-1] {
        cnt++
        stack = append(stack, nums[i])
      }
    } else {
      cnt++
      stack = append(stack, nums[i])
    }
  }
  if len(stack)%2 != 0 {//如果是奇数个,去掉最后一个
    cnt--
    stack = stack[:len(stack)-1]
  }
  ans := len(nums) - cnt
  return ans
}

第三题

2217.找到指定长度的回文数

2217.找到指定长度的回文数

题解

思路:


  • 首先构造回文数的左半边,那么最终的回文数通过左半边翻转就能得到了
  • 题目给定了要找第几个回文数,那么就是half := base + q - 1
  • 例如三位数,第16个,10+16-1=25,翻转,252就是第16个回文数,这里-1是因为101是第一个回文数,而如果q是1的话,10+1=11,111是第二个回文数,所有要减1
  • 例如四位数,第8个,10+8-1=17,翻转,1771就是第8个回文数
  • 如果是奇数的话,翻转时把左半边的最后一位去掉即可
  • 对于一位数的回文数来说,最多1 * 9个,对于二位数,最多1 * 9个,对于三位数,最多10 * 9个,对于四位数,最多10 * 9个。可以发现最多的数量是左半边的base * 9,所以如果q大于base * 9的话,一定找不到

代码

func kthPalindrome(queries []int, intLength int) []int64 {
  ans := make([]int64, len(queries))
  n := (intLength - 1) / 2
  base := int(math.Pow10(n))
  for i, q := range queries {
    if q > base*9 {
      ans[i] = -1
      continue
    }
    half := base + q - 1
    cnt := half
    if intLength%2 != 0 {
      cnt /= 10
    }
    for cnt != 0 {
      half = half*10 + cnt%10
      cnt /= 10
    }
    ans[i] = int64(half)
  }
  return ans
}

第四题

2218.从栈中取出K个硬币的最大面值和

2218.从栈中取出K个硬币的最大面值和

题解

分组背包,用dp来做,又因为取硬币是栈操作,用前缀和来化简取硬币的操作


  • 因为每组只能取一次物品(题目中栈的关系),所以可以先看作是01背包
  • 那么取一次物品,取多少呢?用前缀和来选择,pile[ i ],即取前 i+1 个,因为下标从0开始,所以是i+1
  • 用滚动数组来优化,二维降一维
  • 到了该取这一组物品的一次物品的时候了,到底取几个呢?
  • 遍历一遍前缀和数组即可,会自动滚动到每个容量的最优价值

代码

func maxValueOfCoins(piles [][]int, k int) int {
  dp := make([]int, k+1)
  for _, pile := range piles {
    //计算前缀和
    //这里的外层循环每一层可以看作是一件物品
    //下面的for range是将这一件物品变成一组物品
    //每一组,最多只能取一次前缀和物品
    n := len(pile)
    for i := 1; i < n; i++ {
      pile[i] += pile[i-1]
    }
    //滚动数组
    for j := k; j > 0; j-- {
      //这里的w+1可以看作01背包中的重量,v是价值。w是从零开始的,所以真正的是w+1
      //pile[:min(n, j)]的原因是,如果index(重量)> j(容量),那就没有意义了
      for w, v := range pile[:min(n, j)] {
        dp[j] = max(dp[j], dp[j-w-1]+v)
      }
    }
  }
  return dp[k]
}
func max(i, j int) int {
  if i > j {
    return i
  }
  return j
}
func min(i, j int) int {
  if i < j {
    return i
  }
  return j
}
目录
相关文章
|
3月前
|
Go
【LeetCode 热题100】DP 实战进阶:最长递增子序列、乘积最大子数组、分割等和子集(力扣300 / 152/ 416 )(Go语言版)
本文深入解析三道经典的动态规划问题:**最长递增子序列(LIS)**、**乘积最大子数组** 和 **分割等和子集**。 - **300. LIS** 通过 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列长度,支持 O(n²) 动态规划与 O(n log n) 的二分优化。 - **152. 乘积最大子数组** 利用正负数特性,同时维护最大值与最小值的状态转移方程。 - **416. 分割等和子集** 转化为 0-1 背包问题,通过布尔型 DP 实现子集和判断。 总结对比了三题的状态定义与解法技巧,并延伸至相关变种问题,助你掌握动态规划的核心思想与灵活应用!
131 1
|
3月前
|
分布式计算 算法 Go
【LeetCode 热题100】BFS/DFS 实战:岛屿数量 & 腐烂的橘子(力扣200 / 994 )(Go语言版)
本文讲解了两道经典的图论问题:**岛屿数量(LeetCode 200)** 和 **腐烂的橘子(LeetCode 994)**,分别通过 DFS/BFS 实现。在“岛屿数量”中,利用深度或广度优先搜索遍历二维网格,标记连通陆地并计数;“腐烂的橘子”则采用多源 BFS,模拟腐烂传播过程,计算最短时间。两者均需掌握访问标记技巧,是学习网格搜索算法的绝佳实践。
139 1
|
4月前
|
Go 开发者 索引
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣33 / 81/ 153/154)(Go语言版)
本文深入探讨了LeetCode中四道关于「搜索旋转排序数组」的经典题目,涵盖了无重复和有重复元素的情况。通过二分查找的变形应用,文章详细解析了每道题的解题思路和Go语言实现代码。关键点包括判断有序区间、处理重复元素以及如何缩小搜索范围。文章还总结了各题的异同,并推荐了类似题目,帮助读者全面掌握二分查找在旋转数组中的应用。无论是初学者还是有经验的开发者,都能从中获得实用的解题技巧和代码实现方法。
254 14
|
3月前
|
Go
【LeetCode 热题100】BFS/DFS 实战:岛屿数量 & 腐烂的橘子(力扣200 / 994 )(Go语言版)
本篇博客详细解析了三道经典的动态规划问题:198. 打家劫舍(线性状态转移)、279. 完全平方数与322. 零钱兑换(完全背包问题)。通过 Go 语言实现,帮助读者掌握动态规划的核心思想及其实战技巧。从状态定义到转移方程,逐步剖析每道题的解法,并总结其异同点,助力解决更复杂的 DP 问题。适合初学者深入理解动态规划的应用场景和优化方法。
83 0
|
3月前
|
算法 Go 索引
【LeetCode 热题100】回溯:括号生成 & 组合总和(力扣22 / 39 )(Go语言版)
本文深入解析了LeetCode上的两道经典回溯算法题:**22. 括号生成**与**39. 组合总和**。括号生成通过维护左右括号数量,确保路径合法并构造有效组合;组合总和则允许元素重复选择,利用剪枝优化搜索空间以找到所有满足目标和的组合。两者均需明确路径、选择列表及结束条件,同时合理运用剪枝策略提升效率。文章附有Go语言实现代码,助你掌握回溯算法的核心思想。
103 0
|
12月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
184 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
137 6
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
302 2
|
12月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
198 3
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
10月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
245 1

推荐镜像

更多