Merge pull request #1246 from vgyhn159115/id_406_key

melody-li · web-flow · commit 9b10b37ab03a · 2019-12-12T18:48:23.000+08:00
406-Week 08
diff --git a/Week 08/id_406/Create Leetcode_205_406.py b/Week 08/id_406/Create Leetcode_205_406.py
@@ -0,0 +1,21 @@
+class Solution:
+    def isIsomorphic(self, s: str, t: str) -> bool:
+        s2t = {}
+        mapped_t = set()
+        for i in range(len(s)):
+            if s[i] in s2t:
+                if s2t[s[i]] != t[i]:
+                    return False
+            else:
+                if t[i] in mapped_t:
+                    return False
+                mapped_t.add(t[i])
+                s2t[s[i]] = t[i]
+        return True
+
+
+def reverse(s,k):
+	a = list(s)
+	for i in xrange(0, len(a), 2*k):
+		a[i:i+k] = reversed(a[i:i+k])
+	return "".join(a)
diff --git a/Week 08/id_406/Create Leetcode_541_406.py b/Week 08/id_406/Create Leetcode_541_406.py
@@ -0,0 +1,6 @@
+class Solution:
+    def reverseStr(self, s: str, k: int) -> str:
+        a = list(s)
+        for i in range(0, len(a), 2*k):
+            a[i:i+k] = reversed(a[i:i+k])
+        return "".join(a)
diff --git a/Week 08/id_406/Create Leetcode_818_406.py b/Week 08/id_406/Create Leetcode_818_406.py
@@ -0,0 +1,21 @@
+class Solution:
+    def racecar(self, target: int) -> int:
+        K = target.bit_length() + 1
+        barrier = 1 << K
+        pq = [(0, target)]
+        dist = [float('inf')] * (2 * barrier + 1)
+        dist[target] = 0
+        
+        while pq:
+            steps, targ = heapq.heappop(pq)
+            if dist[targ] > steps: continue
+            
+            for k in range(K+1):
+                walk = (1 << k) - 1
+                steps2, targ2 = steps + k + 1, walk - targ
+                if walk == targ: steps2 -= 1
+                
+                if abs(targ2) <= barrier and steps2 < dist[targ2]:
+                    heapq.heappush(pq, (steps2, targ2))
+                    dist[targ2] = steps2
+        return dist[0]
