ORID50

今天完成了每日挑战，这道题如果不用hashset来解决，方法还是很奇妙的。因为跟题目给的限制很有关系。题目说这个数组的数字只能是0<= num < n 也就是说可以用指针的方法来判断有没有重复。参考了discussion里面的答案，发现你只要把但前数字所代表的指针位置的数字换成负数就可以了，这样你下次再通过一个数来找到这个指针的数字的时候，你判断当前是否为负数，就可以找重了。（你把当前数字当作指针的时候用Math.abs()）这个方法来取绝对值。

最近还有一个数字结构我觉得很重要，就是Trie（字母树），这个数字结构好像经常会考，所以最近有学习了相关的题目，最主要的还是能够自己实现一个字母树吧。不过我现在还不能顺利或者说流利的实现一个字母树，所以我需要不断练习。
其实最重要的就那么几步。

1. java里面有个TrieNode的结构，你只要建立一个TrieNode[] root = new TrieNode[26]; 这样一个结构就可以了。
   然后在children = new TrieNode[26];
2. 在每次添加一个新的单词的时候，你只要把一个isWord boolean的值设置成true就可以了。下次查找的时候直接返回wd.isWord。这样如果之前没有插入过这个单词，那么isWord这个参数的初始值就是false，所以返回的答案就是对的。我觉得这里的设计很巧妙。因为在网上看到了python一般使用一个‘#’来代替但前这个词是出现在字典里面的。
3. 找prefix的时候就只要返回true or false就可以了。isWord只是用来查找单词用的。

下面是代码：

class TrieNode {
    public char val;
    public boolean isWord;
    public TrieNode[] children = new TrieNode[26];
    public TrieNode() {}
    TrieNode(char c) {
        TrieNode node = new TrieNode();
        node.val = c;
    }
}
public class Trie {

    /** Initialize your data structure here. */
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
        root.val = ' ';
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode w = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (w.children[c - 'a'] == null) {
                w.children[c - 'a'] = new TrieNode(c);
            }
            w = w.children[c - 'a'];
        }
        w.isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode wd = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (wd.children[c - 'a'] == null) return false;
            wd = wd.children[c - 'a'];
        }
        return wd.isWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode wd = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (wd.children[c - 'a'] == null) return false;
            wd = wd.children[c - 'a'];
        }
        return true;
    }
}