作业

xiaoxucong · xiaoxucong · commit ff7c465be07a · 2020-07-26T15:25:55.000+08:00
diff --git a/Week07/GoStairs.java b/Week07/GoStairs.java
@@ -0,0 +1,26 @@
+package com.algorithm.ok.week_7;
+
+/***
+ * 70. 爬楼梯
+ */
+public class GoStairs {
+
+    public int climbStairs(int n) {
+        int[] dp = new int[n + 1];
+        dp[0] = 1;
+        dp[1] = 1;
+        for(int i = 2; i <= n; i++) {
+            dp[i] = dp[i - 1] + dp[i - 2];
+        }
+        return dp[n];
+    }
+
+    /***
+     * 可知本题是斐波那契数列，那么用斐波那契数列的公式即可解决问题
+     */
+    public int ss(int n) {
+        double sqrt_5 = Math.sqrt(5);
+        double fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
+        return (int)(fib_n / sqrt_5);
+    }
+}
diff --git a/Week07/Trie.java b/Week07/Trie.java
@@ -0,0 +1,60 @@
+package com.algorithm.ok.week_7;
+
+/***
+ * 208. 实现 Trie (前缀树)
+ * Trie trie = new Trie();
+ *
+ * trie.insert("apple");
+ * trie.search("apple");   // 返回 true
+ * trie.search("app");     // 返回 false
+ * trie.startsWith("app"); // 返回 true
+ * trie.insert("app");
+ * trie.search("app");     // 返回 true
+ */
+public class Trie {
+    TrieNode   root;
+    public Trie() {
+        root = new TrieNode();
+    }
+
+    /** Inserts a word into the trie. */
+    public void insert(String word) {
+        if(word == null || word.equals(""))  return ;
+        TrieNode node = root;
+        for(int i = 0; i<word.length(); i++){
+            char ch = word.charAt(i);
+            if(!node.next.containsKey(ch)) {
+                node.next.put(ch,new TrieNode());
+            }
+            node = node.next.get(ch);
+            node.path++;
+        }
+        node.end++;
+
+    }
+
+    /** Returns if the word is in the trie. */
+    public boolean search(String word) {
+        if(word == null || word.equals("")) return false;
+        TrieNode node = root;
+        for(int i = 0; i<word.length(); i++){
+            char ch = word.charAt(i);
+            if(!node.next.containsKey(ch)) return false;
+            node = node.next.get(ch);
+        }
+        if(node.end == 0) return false;
+        return true;
+    }
+
+    /** Returns if there is any word in the trie that starts with the given prefix. */
+    public boolean startsWith(String word) {
+        if(word == null || word.equals("")) return false;
+        TrieNode node = root;
+        for(int i = 0; i<word.length(); i++){
+            char ch = word.charAt(i);
+            if(!node.next.containsKey(ch)) return false;
+            node = node.next.get(ch);
+        }
+        return true;
+    }
+}
diff --git a/Week07/TrieNode.java b/Week07/TrieNode.java
@@ -0,0 +1,15 @@
+package com.algorithm.ok.week_7;
+
+import java.util.HashMap;
+
+public class TrieNode{
+    public int path;
+    public int end;
+    public HashMap<Character, TrieNode> next;
+
+    public TrieNode(){
+        path = 0;
+        end = 0;
+        next = new HashMap<>();
+    }
+}
