力扣题目链接：https://leetcode.cn/problems/minimum-sideway-jumps/
给你一个长度为 n 的 3 跑道道路 ，它总共包含 n + 1 个 点 ，编号为 0 到 n 。一只青蛙从 0 号点第二条跑道 出发 ，它想要跳到点 n 处。然而道路上可能有一些障碍。
给你一个长度为 n + 1 的数组 obstacles ，其中 obstacles[i] （取值范围从 0 到 3）表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0 ，那么点 i 处没有障碍。任何一个点的三条跑道中 最多有一个 障碍。
obstacles[2] == 1 ，那么说明在点 2 处跑道 1 有障碍。这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍，这只青蛙也可以在 同一个 点处 侧跳 到 另外一条 跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。
这只青蛙从点 0 处跑道 2 出发，并想到达点 n 处的 任一跑道 ，请你返回 最少侧跳次数 。
注意：点 0 处和点 n 处的任一跑道都不会有障碍。
示例 1：
输入：obstacles = [0,1,2,3,0] 输出：2 解释：最优方案如上图箭头所示。总共有 2 次侧跳（红色箭头）。 注意，这只青蛙只有当侧跳时才可以跳过障碍（如上图点 2 处所示）。
示例 2：
输入：obstacles = [0,1,1,3,3,0] 输出：0 解释：跑道 2 没有任何障碍，所以不需要任何侧跳。
示例 3：
输入：obstacles = [0,2,1,0,3,0] 输出：2 解释：最优方案如上图所示。总共有 2 次侧跳。
提示：
obstacles.length == n + 11 <= n <= 5 * 1050 <= obstacles[i] <= 3obstacles[0] == obstacles[n] == 0也不用先像其他题解那样先考虑普通的DP再考虑如何原地滚动压缩优化到 O ( 1 ) O(1) O(1)空间，直接考虑使用三个整型变量来当DP数组即可
dp[i]表示进行到当前距离时，若青蛙位于第i道上 的最小总横跳次数。
初始时青蛙的前进距离是0，并且位于中间的一道，因此初始值 d p [ 3 ] = 1 , 0 , 1 dp[3] = {1, 0, 1} dp[3]=1,0,1
接着从起点的下一个位置遍历“障碍数组”，每次遍历时，我们分为两边：
for (int i = 1; i < obstacles.size(); i++) {
int minStep = 999999;
// 计算出到达这个前进距离所需的最小横跳次数
// 更新三条跑道到这个前近距离的最小横跳次数
}
最终，返回三条跑道的最小值即可。
class Solution {
public:
int minSideJumps(vector<int>& obstacles) {
int dp[3] = {1, 0, 1};
for (int i = 1; i < obstacles.size(); i++) {
int minStep = 999999;
for (int j = 0; j < 3; j++) { // 计算出到达这个前进距离所需的最小横跳次数
if (obstacles[i] == j + 1) { // 若有障碍则不可达，记为“无穷大”
dp[j] = 999999;
}
else {
minStep = min(minStep, dp[j]);
}
}
for (int j = 0; j < 3; j++) { // 更新三条跑道到这个前近距离的最小横跳次数
if (obstacles[i] != j + 1) { // 若此处非障碍，则可由此前进距离的另外两条跑道横跳而来
dp[j] = min(dp[j], minStep + 1);
}
}
}
return min(dp[0], min(dp[1], dp[2]));
}
};
class Solution:
def minSideJumps(self, obstacles: List[int]) -> int:
dp = [1, 0, 1]
for i in range(1, len(obstacles)):
minStep = 999999
for j in range(3):
if obstacles[i] == j + 1:
dp[j] = 999999
else:
minStep = min(minStep, dp[j])
for j in range(3):
if obstacles[i] != j + 1:
dp[j] = min(dp[j], minStep + 1)
return min(dp)
同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/128745707
ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem
下面有没有更优雅的方法来实现这个:输入:array=[1,1,1,0,0,1,1,1,1,0]输出:4我的算法:streak=0max_streak=0arr.eachdo|n|ifn==1streak+=1elsemax_streak=streakifstreak>max_streakstreak=0endendputsmax_streak 最佳答案 类似于w0lf'sanswer,但通过从chunk返回nil来跳过元素:array.chunk{|x|x==1||nil}.map{|_,x|x.size}.max
前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit
我正在用ruby遍历一个数组。有没有一种简单的方法可以在不返回for循环的情况下获取迭代次数或数组索引？ 最佳答案 啊，知道了。each_with_index哇!编辑:糟糕! 关于ruby-如何使用每个迭代器获取数组索引或迭代次数？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/706115/
在Ruby中如何限制String#gsub的替换次数？在PHP中，这可以通过preg_replace轻松完成，它接受一个参数来限制替换，但我不知道如何在Ruby中做到这一点。 最佳答案 您可以在gsub循环中创建一个计数器并递减它。str='aaaaaaaaaa'count=5pstr.gsub(/a/){ifcount.zero?then$&elsecount-=1;'x'end}#=>"xxxxxaaaaa" 关于ruby-使用gsub时如何限制替换次数？，我们在StackOverf
我正在尝试编写一个Ruby程序来计算两个字母同时出现的次数。这是我正在阅读的文件中写的内容:holachau这就是我想要得到的:ho;ol;la;ch;ha;au;1;1;1;1;1;1;我无法让它正常工作。到目前为止，这是我的代码:file=File.read(gets.chomp)todo=file.scan(/[a-z][a-z]/).each_with_object(Hash.new(0)){|a,b|b[a]+=1}keys=''values=''todo.each_key{|key|keys+=key+';'}todo.each_value{|value|values+=v
给定如下数组:x=['a','b','b','c','a','a','a']我想以显示每个元素按顺序重复多少次的内容结束。所以也许我最终得到以下结果:[['a',1],['b',2],['c',1],['a',3]]结果的结构并不那么重要...可能需要一些其他数据类型。 最佳答案 1.9有Enumerable#chunk仅出于此目的:x.chunk{|y|y}.map{|y,ys|[y,ys.length]} 关于ruby-计算ruby数组中元素的连续出现次数，我们在StackOve
在HowdoIlimitthenumberofreplacementswhenusinggsub?，有人建议用下面的方法来做有限数量的替换:str='aaaaaaaaaa'count=5pstr.gsub(/a/){ifcount.zero?then$&elsecount-=1;'x'end}#=>"xxxxxaaaaa"它有效，但代码混淆了替换(5)的次数和应该替换的内容(如果应该替换，则为“x”，否则为$&)。是否可以将两者分开？(如果在这种情况下很难将这两件事分开，但在其他一些情况下可以做到，请将其作为答案发布) 最佳答案 将
我有a=["a","d","c","b","b","c","c"]并且需要打印类似的东西(按出现次数降序排列):c:3b:2我理解第一部分(发现非唯一)是:b=a.select{|e|a.count(e)>1}=>["c","b","b","c","c"]或putsb.select{|e,c|[e,a.count(e)]}.uniqcb如何按出现次数倒序输出每个非唯一值？ 最佳答案 putsa.uniq.map{|e|[a.count(e),e]}.select{|c,_|c>1}.sort.reverse.map{|c,e|"#{
我有一个哈希{1=>true,7=>false,6=>true,4=>false}或者像这样的数组[1,true],[7,false],[6,true],[4,false]]或[真、假、真、假]。如何找到数组中true的个数？ 最佳答案 为了对元素进行计数，您显然必须遍历集合。由于遍历Hash会产生两个元素的Array，因此前两个实际上完全相同:{1=>true,7=>false,6=>true,4=>false}.count(&:last)[[1,true],[7,false],[6,true],[4,false]].count(