- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
本文已收录到 AndroidFamily ,技术和职场问题,请关注公众号 [彭旭锐] 提问.
T1. 删除子串后的字符串最小长度(Easy) 。
标签:栈 。
T2. 字典序最小回文串(Medium) 。
标签:贪心、双指针 。
T3. 求一个整数的惩罚数(Medium) 。
标签:回溯、状态压缩、前缀和 。
T4. 修改图中的边权(Hard) 。
标签:贪心、最短路 。
https://leetcode.cn/problems/minimum-string-length-after-removing-substrings/
使用栈模拟扫描过程,当扫描到 D 和 B 时检查栈顶元素,最后栈内剩余的元素个数就是无法消除的最小长度:
class Solution {
fun minLength(s: String): Int {
val stack = ArrayDeque<Char>()
for (c in s) {
if (c == 'D' && stack.isNotEmpty() && stack.peek() == 'C') stack.pop()
else if (c == 'B' && stack.isNotEmpty() && stack.peek() == 'A') stack.pop()
else stack.push(c)
}
return stack.size
}
}
复杂度分析:
https://leetcode.cn/problems/lexicographically-smallest-palindrome/
贪心思路:当对称位置不相等时,只需要将其中一个位置修改到与另一个位置相同时,得到的操作次数是最少的:
class Solution {
fun makeSmallestPalindrome(s: String): String {
val arr = s.toCharArray()
val n = s.length
// 判断回文串写法
for (i in 0 until n / 2) {
val j = n - 1 - i
if(arr[i] != arr[j]) {
val temp = if(arr[i] < arr[j]) arr[i] else arr[j]
arr[i] = temp
arr[j] = temp
}
}
return String(arr)
}
}
复杂度分析:
https://leetcode.cn/problems/find-the-punishment-number-of-an-integer/
枚举每个数,使用子集型回溯检查是否存在满足条件的切分方案:
class Solution {
fun punishmentNumber(n: Int): Int {
if (n <= 3) return 1
var ret = 0
for (x in 4 .. n) {
val target = x * x
if (backTrack("$target", 0, x)) ret += target
}
return ret + 1 /* 1 满足条件 */
}
// 子集型回溯
private fun backTrack(str : String, i : Int, target : Int) : Boolean {
if (i == str.length) return target == 0
var cur = 0
for (to in i until str.length) {
cur = cur * 10 + (str[to] - '0')
if (backTrack(str, to + 1, target - cur)) return true
}
return false
}
}
复杂度分析:
由于数字的长度小于 32,我们可以用 int 表示所有切分方案,再检查是否存在满足条件的切分方案:
class Solution {
fun punishmentNumber(n: Int): Int {
if (n <= 3) return 1
var ret = 0
for (x in 4 .. n) {
val target = x * x
if (check("$target", x)) ret += target
}
return ret + 1 /* 1 满足条件 */
}
// 状态压缩
private fun check(str : String, target : Int) : Boolean {
val m = str.length
val upper = (1 shl m) - 1
for (k in 1 .. upper) {
var last = 0
var sum = 0
for (i in 0 until m) {
val cur = str[i] - '0'
if (k and (1 shl i) != 0) {
// 拆
sum += last
last = cur
} else{
// 不拆
last = last * 10 + cur
}
}
if (sum + last == target) return true
}
return false
}
}
复杂度分析:
题解一和题解二在多个测试用例间会重复计算相同数字的切分方案,我们可以预处理 1 - 1000 中所有满足条件的数平方,并维护前缀和数组:
class Solution {
companion object {
private val U = 1000
private val preSum = IntArray(U + 1)
init {
for (x in 4 .. U) {
val target = x * x
if (check("$target", x)) preSum[x] += target
preSum[x] += preSum[x - 1]
}
}
// 状态压缩
private fun check(str : String, target : Int) : Boolean {
}
}
fun punishmentNumber(n: Int): Int {
return preSum[n] + 1
}
}
复杂度分析:
https://leetcode.cn/problems/modify-graph-edge-weights/submissions/434224996/
LeetCode 少有的难题,排进历史 Top 10 没问题吧?
问题无解的情况:
错误的思路:
先把所有负权边设置为 1,再跑 Dijkstra 最短路,如果最短路长度 dis < target,那么将其中一条负权边继续增大 “target - dis”,就能是该路径的长度恰好为 target。然而,由于增加权重后最短路长度有可能变化,所以这个思路不能保证正确性.
正确的思路:
class Solution {
private val INF = 1e9.toInt()
fun modifiedGraphEdges(n: Int, edges: Array<IntArray>, source: Int, destination: Int, target: Int): Array<IntArray> {
if (source !in 0 .. n - 1 || destination !in 0 .. n - 1) return edges
if (source == destination || edges.isNullOrEmpty()) return edges
// 建图(领接表,节点号 + 边号方便修改边权)
val graph = Array(n) { ArrayList<IntArray>() }
for ((i, edge) in edges.withIndex()) {
graph[edge[0]].add(intArrayOf(edge[1], i))
graph[edge[1]].add(intArrayOf(edge[0], i))
}
// 第一轮最短路
val originDis = dijkstra1(graph, edges, source, destination)
if (originDis[destination] > target) return emptyArray() // 无解
// 第二轮最短路
val delta = target - originDis[destination] // 需要补全的最短路
val dis = dijkstra2(graph, edges, source, destination, delta, originDis)
if (dis[destination] < target) return emptyArray() // 无解
// 修改剩余边
for (edge in edges) {
if (edge[2] == -1) edge[2] = INF
}
return edges
}
// return:将 -1 视为 1,并计算从起点到终点的最短路
private fun dijkstra1(graph:Array<ArrayList<IntArray>>, edges: Array<IntArray>, source :Int, destination:Int) : IntArray {
val n = graph.size
val visit = BooleanArray(n)
val dis = IntArray(n) { INF }
dis[source] = 0
while (true) {
// 寻找最短路长度最短的节点
var x = -1
for (i in 0 until n) {
if (visit[i]) continue
if (-1 == x || dis[i] < dis[x]) x = i
}
if (x == destination) break
visit[x] = true // 标记
// 松弛相邻边
for (to in graph[x]) {
var w = edges[to[1]][2]
if (-1 == w) w = 1 // 视为 1
if (dis[x] + w < dis[to[0]]) dis[to[0]] = dis[x] + w
}
}
return dis
}
// 补全
private fun dijkstra2(graph:Array<ArrayList<IntArray>>, edges: Array<IntArray>, source :Int, destination:Int, delta: Int, originDis:IntArray /* 首轮计算的最短路 */) : IntArray {
val n = graph.size
val visit = BooleanArray(n)
val dis = IntArray(n) { INF }
dis[source] = 0
while (true) {
// 寻找最短路长度最短的节点
var x = -1
for (i in 0 until n) {
if (visit[i]) continue
if (-1 == x || dis[i] < dis[x]) x = i
}
if (x == destination) break
visit[x] = true // 标记
// 松弛相邻边
for (to in graph[x]) {
var w = edges[to[1]][2]
if (-1 == w) {
// 补全(两次 Dijkstra 只修改这里)
w = Math.max(delta - dis[x] + originDis[to[0]], 1) // 题目要求至少修改到 1
if (w >= 1) edges[to[1]][2] = w
}
if (dis[x] + w < dis[to[0]]) dis[to[0]] = dis[x] + w
}
}
return dis
}
}
复杂度分析:
最后此篇关于LeetCode周赛346(2023/05/21)仅68人AK的最短路问题的文章就讲到这里了,如果你想了解更多关于LeetCode周赛346(2023/05/21)仅68人AK的最短路问题的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我使用“创建 Kubernetes 集群”功能在 Azure 门户中创建了我的 AKS 集群,并允许它创建新的服务主体。 我开始怀疑这个主体使用的凭据是否过期。为了避免 K8s 在凭证到期时与 Azu
文档描述了如何将 ACR 附加到现有的 AKS 群集,https://learn.microsoft.com/en-us/azure/aks/cluster-container-registry-in
我创建了一个 AKS 集群,并启用了 AKS 管理的 Azure Active Directory 和基于角色的访问控制 (RBAC)。如果我尝试使用 Admin Azure AD 组中包含的其中一个
因此,我可以在 AKS 的见解选项卡中清楚地看到每个容器的统计信息。这些必须来自某个地方,但我只能在查询日志/指标时找到每个节点的统计信息。我如何查询这个(为了构建一个工作簿)。 最佳答案 该数据位于
我遇到的情况是,我的 AKS 集群已经就位,有两个 AKS 集群,并且它们仅在其安全区域内部可用。我不想通过互联网从另一个集群访问集群内的内部资源。 我正在探索专用链接服务和端点,有什么建议吗? 两个
好吧,在过去的两天里,我一直在与这个文档作斗争: https://learn.microsoft.com/en-au/azure/aks/static-ip和 https://learn.micros
我正在尝试找出使用 AKS 和 VSTS 为 Asp.Net Core Web 应用程序设置 CI/CD 的步骤。 https://learn.microsoft.com/en-us/vsts/bui
我遇到的情况是,我的 AKS 集群已经就位,有两个 AKS 集群,并且它们仅在其安全区域内部可用。我不想通过互联网从另一个集群访问集群内的内部资源。 我正在探索专用链接服务和端点,有什么建议吗? 两个
只是一个问题,在微软页面上 https://learn.microsoft.com/en-us/azure/aks/configure-kubenet#bring-your-own-subnet-an
kubectl 任务无法将 list 文件部署到 AKS。管道失败并出现以下错误 ##[错误]未找到与/home/vsts/work/1/s/manifests 匹配的配置文件。 管道在运行两个阶段(
我一直在尝试设置 Kubernetes 1.13 AKS 部署以使用 HPA,但我一直遇到问题: NAME REFERENCE
我们公司封锁了 ssh 端口。如何使用 cloud shell ssh 进入 AKS 集群,以便我们可以从那里 curl 到外部 URL 来测试连接?谢了。 最佳答案 这实际上没有多大意义,但您只需要
我正在通过 azure 安装 istio az aks mesh enable --resource-group 'myrg' --name 'myk8s' 然后启用外部 istio 入口网关 az
查看地形 documentation我无法确定如何将 UAMI 分配为 kubelet_identity对于aks集群。 identity { ... }按照描述设置 controlPlane UAM
我正在通过 azure 安装 istio az aks mesh enable --resource-group 'myrg' --name 'myk8s' 然后启用外部 istio 入口网关 az
查看地形 documentation我无法确定如何将 UAMI 分配为 kubelet_identity对于aks集群。 identity { ... }按照描述设置 controlPlane UAM
我们可以从 Log Analytics Workspace 访问 pod 相关日志,但没有应用程序日志(类似于我们在 kubectl get events 中看到的)。 我指的是 Azure 文档,但
az aks create -n MyServices -g MyKubernetes --generate-ssh-keys 不工作。错误消息:az aks create -n Adestis-Se
我想知道如何通过 ssh 连接到 GKE 和 AKS 中的节点,以及如何在 Kubernetes 集群中安装 ELK 堆栈。 任何一步一步的链接都会对我有帮助。 无法使用此命令连接:gcloud co
使用azure aks get-credentials --admin可以获取kubernetes管理配置文件,azure aks get-credentials只能获取azure上的用户配置文件。
我是一名优秀的程序员,十分优秀!