aquawj

9. Palindrome Number  (easy)

实质：回文数字

Determine whether an integer is a palindrome.

121-> true ; -121 -> false; 10 -> false 

解法：

aquawj

//1. HashSet (先sort)
class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> built = new HashSet<String>();
        String res = "";
        for (String w : words) {
            if (w.length() == 1 || built.contains(w.substring(0, w.length() - 1))) {
                res = w.length() > res.length() ? w : res;
                built.add(w);

aquawj

734. I:
Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.

For example, "great acting skills" and "fine drama talent" are similar, if the similar word pairs are pairs = [["great", "fine"], ["acting","drama"], ["skills","talent"]].

Note that the similarity relation is not transitive. For example, if "great" and "fine" are similar, and "fine" and "good" are similar, "great" and "good" are not necessarily similar.

However, similarity is symmetric. For example, "great" and "fine" being similar is the same as "fine" and "great" being similar.

Also, a word is always similar with itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, even though there are no specified similar word pairs.

aquawj

import java.util.ArrayList;
import java.util.List;


public class Solution {
    //普通两个数组的点乘
    public int dotProduct(int[] a, int[] b) {
        int len = a.length;
        int res = 0;
        for (int i = 0; i < len; i++) {

aquawj

处理random有两种方法：
1. Math.random() 生成[0,1)之间随机数
2. Random类，可以调用不同方法

Random 类中的方法比较简单，每个方法的功能也很容易理解。需要说明的是，Random类中各方法生成的随机数字都是均匀分布的，也就是说区间内部的数字生成的几率是均等的
a 、public boolean nextBoolean()
该方法的作用是生成一个随机的boolean值，生成true和false的值几率相等，也就是都是50%的几率。
b 、public double nextDouble()
该方法的作用是生成一个随机的double值，数值介于[0,1.0)之间，这里中括号代表包含区间端点，小括号代表不包含区间端点，也就是0到1之间的随机小数，包含0而不包含1.0。 
c 、public int nextInt()

aquawj

Design a data structure that supports the following two operations:
 void addWord(word)
 boolean search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or'.'means it can represent any one letter.
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true

aquawj

题目要求：b3[a2[c]d]e => b accd accd accd e (不带空格，只是为了看着方便）

class Solution {
    public String decodeString(String s) {
        //看过最优解(56答案中的135)，自己写
        //1. stack
        StringBuilder cur = new StringBuilder();
        Stack<Integer> intStack = new Stack<>();
        Stack<StringBuilder> strStack = new Stack<>();
        int k = 0;

aquawj

与hashtable和binary tree比较，Trie的好处：
1. hashtable的size很大之后，会有很多collision，时间可能至O(n)-n为要插入的key的number
2. binary tree中查找，时间为O(mlongn)
3. Trie将很多相同prefix的key存在一起，空间上小鱼hashtable，时间只有O(m）-m为key的长度

此题先定义TrieNode，再定义Trie Tree
TrieNode两个变量：TrieNode[26] children存所有的节点link（如：节点下面有3个分支，分别连字母l，k，t，那么children[l]!=null,children[k]!=null……）
                boolean isEnd 表示是否为单词的结尾。如果值为false表示这只是prefix，并无法形成word
Trie：定义好root即可
insert(word):遍历word每个字符，如果存在这个link，就继续向下找；如果不存在就创建一个新的；结尾isEnd设为true

aquawj

Given an array of strings, group anagrams together.
For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], 
Return:
[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]
思路:
1.map<String, List<String>>，key是排过序的String, List是相同的anagram

aquawj

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
12345 -> 12354 -> 12435 -> 12453 -> 12534
class Solution {
    public void nextPermutation(int[] nums){
        if(nums == null || nums.length < 2){
            return;
        }
        for(int i = nums.length - 2; i >= 0; i--){