Merge pull request #1280 from serendipity2019/master

melody-li · web-flow · commit ad6f394f7ec7 · 2019-12-12T18:40:39.000+08:00
011-Week 08
diff --git a/Week 08/id_011/decode-ways.go b/Week 08/id_011/decode-ways.go
@@ -0,0 +1,20 @@
+package algorithm00401
+
+func numDecodings(s string) int {
+	if len(s) == 0 || s[:1] == "0" {
+		return 0
+	}
+	a, b := 1, 1
+	for i := 1; i < len(s); i++ {
+		if s[i:i+1] == "0" {
+			a = 0
+		}
+		if s[i-1:i] == "1" || (s[i-1:i] == "2" && s[i:i+1] <= "6") {
+			a = a + b
+			b = a - b
+		} else {
+			b = a
+		}
+	}
+	return a
+}
diff --git a/Week 08/id_011/first-unique-character-in-a-string.go b/Week 08/id_011/first-unique-character-in-a-string.go
@@ -0,0 +1,14 @@
+package algorithm00401
+
+func firstUniqChar(s string) int {
+	var memo [26]int
+	for _, c := range s {
+		memo[c-'a']++
+	}
+	for i, c := range s {
+		if memo[c-'a'] == 1 {
+			return i
+		}
+	}
+	return -1
+}
diff --git a/Week 08/id_011/isomorphic-strings.go b/Week 08/id_011/isomorphic-strings.go
@@ -0,0 +1,17 @@
+package algorithm00401
+
+func isIsomorphic(s string, t string) bool {
+	m1 := make([]int, 256)
+	m2 := make([]int, 256)
+
+	for i := 0; i < len(s); i++ {
+		if m1[s[i]-'a'] != m2[t[i]-'a'] {
+			return false
+		}
+
+		m1[s[i]-'a'] = i + 1
+		m2[t[i]-'a'] = i + 1
+	}
+
+	return true
+}
diff --git a/Week 08/id_011/reverse-only-letters.go b/Week 08/id_011/reverse-only-letters.go
@@ -0,0 +1,23 @@
+package algorithm00401
+
+func reverseOnlyLetters(S string) string {
+	b := []byte(S)
+
+	for l, r := 0, len(b)-1; l < r; {
+		for l < r && !isBetter(b[l]) {
+			l++
+		}
+		for l < r && !isBetter(b[r]) {
+			r--
+		}
+		b[l], b[r] = b[r], b[l]
+		l++
+		r--
+	}
+
+	return string(b)
+}
+
+func isBetter(b byte) bool {
+	return (b >= 'a' && b <= 'z') || (b >= 'A' && b <= 'Z')
+}
diff --git a/Week 08/id_011/reverse-string-ii.go b/Week 08/id_011/reverse-string-ii.go
@@ -0,0 +1,26 @@
+package algorithm00401
+
+func reverseStr(s string, k int) string {
+	b := []byte(s)
+	for i := 0; i < len(s); i++ {
+		j := minInt(i+k, len(s))
+		reverse(b[i:j])
+	}
+	return string(b)
+}
+
+func minInt(i, j int) int {
+	if i < j {
+		return i
+	}
+	return j
+}
+
+func reverse(b []byte) {
+	i, j := 0, len(b)-1
+	for i < j {
+		b[i], b[j] = b[j], b[i]
+		i++
+		j--
+	}
+}
