google面经求人品

写了下最大乘积的代码，但不知道为什么O(n)的方法怎么证明？

1. public class MaxProduct {
   
2.         public static void main(String[] args) {
   
3.                 System.out.println("1 " + maxProduct(100));
   
4.                 System.out.println("2 " + maxProductN(100));
   
5.         }
   
6.        
   
7.         // O(n^2);
   
8.         public static long maxProduct(int n) {
   
9.                 if (n == 0) {
   
10.                         return 0;
    
11.                 }
    
12.                 long[] dp = new long[n + 1];
    
13.                 dp[1] = 1;
    
14.                 for (int i = 2; i <= n; i++) {
    
15.                         long res = i;
    
16.                         for (int j = 1; j < i; j++) {
    
17.                                 res = Math.max(res, (i - j) * dp[j]);
    
18.                         }
    
19.                         dp[i] = res;
    
20.                 }
    
21.                 return dp[n];
    
22.         }
    
23.         public static long maxProductN(int n) {
    
24.                 if (n == 0) {
    
25.                         return 0;
    
26.                 }
    
27.                 long[] dp = new long[n + 4];
    
28.                 dp[1] = 1;
    
29.                 dp[2] = 2;
    
30.                 dp[3] = 3;
    
31.                 for (int i = 4; i <= n; i++) {
    
32.                         dp[i] = Math.max(2 * dp[i - 2], 3 * dp[i - 3]);
    
33.                 }
    
34.                 return dp[n];
    
35.         }
    
36. 
    
37. }
    

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

楼主请问字典那道题，googl或者goeogle算不算1个typo？如果这样的话字典树就不能用了吧

kakaChen 发表于 2015-10-30 21:23
我是用的字典树，然后逐个往下找，如果有一个不match，就拿别的替换继续向下找。

写了下第二轮的函数，欢迎指教，感觉这里用trie和map在时间复杂度上没有区别啊，只是空间上有优势而已。

1. public class TypeOne {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 String[] strs = {"google", "facebook", "amazon"};
   
5.                 TypeOne to = new TypeOne(strs);
   
6.                 System.out.println(to.containsOneType("google"));
   
7.                 System.out.println(to.containsOneType("geogle"));
   
8.                 System.out.println(to.containsOneType("geogla"));
   
9.         }
   
10.         private Trie trie;
    
11.         public TypeOne(String[] strs) {
    
12.                 trie = new Trie();
    
13.                 for (String str : strs) {
    
14.                         trie.insert(str);
    
15.                 }
    
16.         }
    
17.        
    
18.         public boolean containsOneType(String str) {
    
19.                 for (int i = 0; i < str.length(); i++) {
    
20.                         for (char c = 'a'; c <= 'z'; c++) {
    
21.                                 if (c == str.charAt(i)) {
    
22.                                         continue;
    
23.                                 }
    
24.                                 String newStr = str.substring(0, i) + c + str.substring(i + 1);
    
25.                                 if (trie.search(newStr)) {
    
26.                                         return true;
    
27.                                 }
    
28.                         }
    
29.                 }
    
30.                
    
31.                 return false;
    
32.         }
    
33.        
    
34.         class Trie {
    
35.                 class TrieNode {
    
36.                         char c;
    
37.                         boolean isLeaf = false;
    
38.                         HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
    
39. 
    
40.                         public TrieNode() {
    
41.                         }
    
42. 
    
43.                         public TrieNode(char c) {
    
44.                                 this.c = c;
    
45.                         }
    
46.                 }
    
47. 
    
48.                 private TrieNode root;
    
49. 
    
50.                 public Trie() {
    
51.                         root = new TrieNode();
    
52.                 }
    
53. 
    
54.                 public void insert(String word) {
    
55.                         TrieNode cur = null;
    
56.                         HashMap<Character, TrieNode> curChildren = root.children;
    
57.                         for (int i = 0; i < word.length(); i++) {
    
58.                                 char c = word.charAt(i);
    
59.                                 if (curChildren.containsKey(c)) {
    
60.                                         cur = curChildren.get(c);
    
61.                                 } else {
    
62.                                         TrieNode tmp = new TrieNode(c);
    
63.                                         curChildren.put(c, tmp);
    
64.                                         cur = tmp;
    
65.                                 }
    
66.                                 curChildren = cur.children;
    
67.                                 if (i == word.length() - 1) {
    
68.                                         cur.isLeaf = true;
    
69.                                 }
    
70.                         }
    
71.                 }
    
72. 
    
73.                 public boolean search(String word) {
    
74.                         TrieNode node = searchNode(word);
    
75.                         return node != null && node.isLeaf;
    
76.                 }
    
77. 
    
78.                 public TrieNode searchNode(String word) {
    
79.                         TrieNode cur = null;
    
80.                         HashMap<Character, TrieNode> curChildren = root.children;
    
81.                         for (int i = 0; i < word.length(); i++) {
    
82.                                 char c = word.charAt(i);
    
83.                                 if (curChildren.containsKey(c)) {
    
84.                                         cur = curChildren.get(c);
    
85.                                 } else {
    
86.                                         return null;
    
87.                                 }
    
88.                                 curChildren = cur.children;
    
89.                         }
    
90. 
    
91.                         return cur;
    
92.                 }
    
93.                
    
94.         }
    
95. }
    

复制代码