leetcode

commit fa0ba4e434a78e3da70ad6665cdeddc71603b8ee
parent 086da5e2ca2957968b3e7963e8509df66e761457
Author: Jack Sangdahl <jack@pngu.org>
Date:   Mon, 25 May 2026 08:53:37 +0300

1871. jump game 7

Diffstat:
A
jump_game7.c
 | 
44
++++++++++++++++++++++++++++++++++++++++++++
A
jump_game7.py
 | 
32
++++++++++++++++++++++++++++++++

2 files changed, 76 insertions(+), 0 deletions(-)
diff --git a/jump_game7.c b/jump_game7.c
@@ -0,0 +1,44 @@
+// 1871. Jump Game VII
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed binary string 's' and two integers 'minJump' and
+ * 'maxJump'. in the beginning, you are standing at index '0', which is equal to
+ * 0. you can move from index 'i' to index 'j' if the following conditions are
+ * fulfilled: 'i + minJump <= j <= min(i + maxJump, s.length - 1)' and 's[j] ==
+ * 0'. return true if you can reach index 's.length - 1' in 's' or false
+ * otherwise.
+ */
+
+bool canReach(char *s, int minJump, int maxJump) {
+  int n = strlen(s);
+  int *f = (int *)malloc(n * sizeof(int));
+  int *pre = (int *)malloc(n * sizeof(int));
+  f[0] = 1;
+  for (int i = 0; i < minJump; i++)
+    pre[i] = 1;
+  for (int i = minJump; i < n; i++) {
+    int left = i - maxJump, right = i - minJump;
+    if (s[i] == '0') {
+      int total = pre[right];
+      if (left > 0)
+        total -= pre[left - 1];
+      f[i] = total != 0 ? 1 : 0;
+    }
+    pre[i] = pre[i - 1] + f[i];
+  }
+  bool ans = (f[n - 1] == 1);
+  free(f);
+  free(pre);
+  return ans;
+}
+
+int main() {
+  char *s1 = "011010", *s2 = "01101110";
+  bool r1 = canReach(s1, 2, 3);
+  bool r2 = canReach(s2, 2, 3);
+  printf("%d\n", r1);
+  assert(r1 == true);
+  printf("%d\n", r2);
+  assert(r2 == false);
+}
diff --git a/jump_game7.py b/jump_game7.py
@@ -0,0 +1,32 @@
+# 1871. Jump Game VII
+
+"""
+you are given a 0-indexed binary string 's' and two integers 'minJump' and
+'maxJump'. in the beginning, you are standing at index '0', which is equal to
+0. you can move from index 'i' to index 'j' if the following conditions are
+fulfilled: 'i + minJump <= j <= min(i + maxJump, s.length - 1)' and 's[j] ==
+0'. return true if you can reach index 's.length - 1' in 's' or false
+otherwise.
+"""
+
+from collections import deque
+
+
+class Solution:
+    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
+        q, total = deque([0]), 0
+        while q:
+            i = q.popleft()
+            for j in range(max(i + minJump, total + 1), min(i + maxJump + 1, len(s))):
+                if s[j] == "0":
+                    if j == len(s) - 1:
+                        return True
+                    q.append(j)
+            total = max(total, i + maxJump)
+        return False
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.canReach(s="011010", minJump=2, maxJump=3))
+    print(obj.canReach(s="01101110", minJump=2, maxJump=3))