数据结构算法

dunwu · dunwu · commit c3bf9fba91b4 · 2018-11-05T10:28:55.000+08:00
diff --git a/codes/data-structure/src/main/java/io/github/dunwu/ds/str/AddBinary.java b/codes/data-structure/src/main/java/io/github/dunwu/ds/str/AddBinary.java
@@ -0,0 +1,43 @@
+package io.github.dunwu.ds.str;
+
+//    【二进制求和】
+//
+//    给定两个二进制字符串，返回他们的和（用二进制表示）。
+//
+//    输入为非空字符串且只包含数字 1 和 0。
+//
+//    示例 1:
+//
+//    输入: a = "11", b = "1"
+//    输出: "100"
+//    示例 2:
+//
+//    输入: a = "1010", b = "1011"
+//    输出: "10101"
+
+
+/**
+ * @author Zhang Peng
+ * @date 2018-11-04
+ */
+public class AddBinary {
+    public static String addBinary(String a, String b) {
+        StringBuilder sb = new StringBuilder();
+        int i = a.length() - 1, j = b.length() - 1, carry = 0;
+        while (i >= 0 || j >= 0) {
+            int sum = carry;
+            if (j >= 0) {
+                sum += b.charAt(j--) - '0';
+            }
+            if (i >= 0) {
+                sum += a.charAt(i--) - '0';
+            }
+            sb.append(sum % 2);
+            carry = sum / 2;
+        }
+        if (carry != 0) {
+            sb.append(carry);
+        }
+        return sb.reverse().toString();
+    }
+}
diff --git a/codes/data-structure/src/main/java/io/github/dunwu/ds/str/ImplementStrstr.java b/codes/data-structure/src/main/java/io/github/dunwu/ds/str/ImplementStrstr.java
@@ -0,0 +1,66 @@
+package io.github.dunwu.ds.str;
+
+
+//    【实现 strStr() 函数】
+//
+//    给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
+//
+//    示例 1:
+//
+//    输入: haystack = "hello", needle = "ll"
+//    输出: 2
+//    示例 2:
+//
+//    输入: haystack = "aaaaa", needle = "bba"
+//    输出: -1
+//    说明:
+//
+//    当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
+//
+//    对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
+
+
+/**
+ * @author Zhang Peng
+ * @date 2018-11-05
+ */
+public class ImplementStrstr {
+    public static int strStr(String haystack, String needle) {
+        if (haystack.equals(needle)) {
+            return 0;
+        }
+
+        if (haystack == null || haystack.length() == 0) {
+            return -1;
+        }
+
+        if (needle == null || needle.length() == 0) {
+            return 0;
+        }
+
+        if (haystack.length() < needle.length()) {
+            return -1;
+        }
+
+        int begin = 0;
+        int i = 0;
+        int j = 0;
+        while (i < haystack.length() && begin < haystack.length()) {
+            if (j == needle.length()) {
+                return begin;
+            } else if (haystack.charAt(i) == needle.charAt(j)) {
+                i++;
+                j++;
+            } else {
+                j = 0;
+                begin++;
+                i = begin;
+            }
+        }
+
+        if (i == haystack.length() && j == needle.length()) {
+            return begin;
+        }
+        return -1;
+    }
+}
diff --git a/codes/data-structure/src/main/java/io/github/dunwu/ds/str/LongestCommonPrefix.java b/codes/data-structure/src/main/java/io/github/dunwu/ds/str/LongestCommonPrefix.java
@@ -0,0 +1,59 @@
+package io.github.dunwu.ds.str;
+
+//    【最长公共前缀】
+//
+//    编写一个函数来查找字符串数组中的最长公共前缀。
+//
+//    如果不存在公共前缀，返回空字符串 ""。
+//
+//    示例 1:
+//
+//    输入: ["flower","flow","flight"]
+//    输出: "fl"
+//    示例 2:
+//
+//    输入: ["dog","racecar","car"]
+//    输出: ""
+//    解释: 输入不存在公共前缀。
+//    说明:
+//
+//    所有输入只包含小写字母 a-z 。
+
+
+/**
+ * @author Zhang Peng
+ * @date 2018-11-05
+ */
+public class LongestCommonPrefix {
+    public static String longestCommonPrefix(String[] strs) {
+        if (strs == null || strs.length == 0) {
+            return "";
+        }
+
+        int index = 0;
+        StringBuilder sb = new StringBuilder();
+
+        while (index < strs[0].length()) {
+            char c = strs[0].charAt(index);
+            boolean flag = true;
+            for (String str : strs) {
+                if (index >= str.length()) {
+                    flag = false;
+                    break;
+                }
+                if (str.charAt(index) != c) {
+                    flag = false;
+                    break;
+                }
+            }
+
+            if (flag) {
+                sb.append(c);
+                index++;
+            } else {
+                break;
+            }
+        }
+        return sb.toString();
+    }
+}
diff --git a/codes/data-structure/src/test/java/io/github/dunwu/ds/str/AddBinaryTest.java b/codes/data-structure/src/test/java/io/github/dunwu/ds/str/AddBinaryTest.java
@@ -0,0 +1,16 @@
+package io.github.dunwu.ds.str;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * @author Zhang Peng
+ * @date 2018-11-05
+ */
+public class AddBinaryTest {
+    @Test
+    public void test() {
+        Assert.assertEquals("100", AddBinary.addBinary("11", "1"));
+        Assert.assertEquals("10101", AddBinary.addBinary("1010", "1011"));
+    }
+}
diff --git a/codes/data-structure/src/test/java/io/github/dunwu/ds/str/ImplementStrstrTest.java b/codes/data-structure/src/test/java/io/github/dunwu/ds/str/ImplementStrstrTest.java
@@ -0,0 +1,21 @@
+package io.github.dunwu.ds.str;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * @author Zhang Peng
+ * @date 2018-11-05
+ */
+public class ImplementStrstrTest {
+    @Test
+    public void test() {
+        Assert.assertEquals(0, ImplementStrstr.strStr("", ""));
+        Assert.assertEquals(-1, ImplementStrstr.strStr("aaa", "aaaa"));
+        Assert.assertEquals(0, ImplementStrstr.strStr("aaa", ""));
+        Assert.assertEquals(2, ImplementStrstr.strStr("hello", "ll"));
+        Assert.assertEquals(-1, ImplementStrstr.strStr("aaaaa", "bba"));
+        Assert.assertEquals(1, ImplementStrstr.strStr("mississippi", "issi"));
+        Assert.assertEquals(9, ImplementStrstr.strStr("mississippi", "pi"));
+    }
+}
diff --git a/codes/data-structure/src/test/java/io/github/dunwu/ds/str/LongestCommonPrefixTest.java b/codes/data-structure/src/test/java/io/github/dunwu/ds/str/LongestCommonPrefixTest.java
@@ -0,0 +1,19 @@
+package io.github.dunwu.ds.str;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * @author Zhang Peng
+ * @date 2018-11-05
+ */
+public class LongestCommonPrefixTest {
+    @Test
+    public void test() {
+        String[] strs1 = {"flower", "flow", "flight"};
+        String[] strs2 = {"dog", "racecar", "car"};
+
+        Assert.assertEquals("fl", LongestCommonPrefix.longestCommonPrefix(strs1));
+        Assert.assertEquals("", LongestCommonPrefix.longestCommonPrefix(strs2));
+    }
+}
