LeetCode(5) -- 290, 292, 299, 303, 326

P290. Word Pattern (Easy)

给一个字符串作为pattern，再给一个字符串作为句子，检验这个句子的每个单词是否符合这个pattern.

Input: pattern = "abba", str = "dog cat cat dog"
Output: true

我的思路

先把字符串切分成单词，然后用HashMap使之与前面的pattern相对应。

我的代码

public class E_290_WordPattern {
    public boolean wordPattern(String pattern, String str) {
        String[] words = str.split(" ");
        if (pattern.length() != words.length) {
            return false;
        }
        char[] chars = pattern.toCharArray();
        HashMap<Character, String> hashMap = new HashMap<>();
        for (int i = 0; i < chars.length; i++) {
            if (!hashMap.containsKey(chars[i]) && !hashMap.containsValue(words[i])) {
                hashMap.put(chars[i], words[i]);
            } else if (hashMap.containsKey(chars[i])) {
                if (!hashMap.get(chars[i]).equals(words[i])) {
                    return false;
                }
            } else if (hashMap.containsValue(words[i])){
                return false;
            }
        }
        return true;
    }
}

超过99.6%

最优解

class Solution {
    public boolean wordPattern(String pattern, String str) {
        HashMap<Character, String> hm = new HashMap();
        int strIndex = 0;
        for (int i = 0; i < pattern.length(); i++) {
            if (strIndex > str.length()) {
                return false;
            }
            int strEndIndex = strIndex + 1;
            while (strEndIndex < str.length() && str.charAt(strEndIndex) != ' ') {
                strEndIndex++;
            }
            String word = str.substring(strIndex, strEndIndex);
            strIndex = strEndIndex + 1;
            Character c = new Character(pattern.charAt(i));
            String s = hm.get(c);
            if (s == null) {
                if (hm.containsValue(word)) {
                    return false;
                }
                hm.put(c, word);
            } else if (!s.equals(word)) {
                return false;
            }
        }
        return (strIndex == str.length() + 1);
    }
}

P292. Nim Game (Easy)

桌上有一堆小石头，n个。两个人，每人每次可以拿走1-3个石头。拿走最后一个石头的是胜利者。

我的思路

似乎是动态规划。 每个人的策略都取决于桌上还有多少石头。如果桌上还有4个石头，我是必输的。如果桌上还有5，6，7个石头，对手必输，因为我只要给他剩下4个就行了。如果桌上有8个石头，那对手必赢，因为无论我怎么拿，对手都会剩下5，6，7个石头。如果桌上有9，10，11个石头，那我就赢了，因为我只需要给对手剩下8个石头，我一定能赢。

由此找到规律，当桌上有4个，8个，12个。。。石头的时候，我是必输的。所以只要不是4的倍数，我必赢。

我的代码

class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

超过100%

最优解

class Solution {
    public boolean canWinNim(int n) {
        return (n % 4) != 0;
    }
}

比较简单，答案很明显。

P299. Bulls and Cows (Easy)

你和你的朋友玩一个游戏：你在纸上写下一个数，比如1807，你告诉他长度是4，然后让你的朋友猜这个数。如果某个数字大小和位置都猜对了，就叫“bulls”, 记作A；如果只猜对了大小，而猜错了位置，就叫“cows”，记作B; 长度是相等的。

Example:

Input: secret = "1807", guess = "7810"

Output: "1A3B"

Explanation: 1 bull and 3 cows. The bull is 8, the cows are 0, 1 and 7.

我的思路

因为只有0到9这十个数字，就用ASCII码做一个长度为10的int数组，记录下每个数字出现的次数即可。

我的代码

public class E_299_BullsAndCows {
    public String getHint(String secret, String guess) {
        int[] digits = new int[10];
        char[] secretDigits = secret.toCharArray();
        char[] guessDigits = guess.toCharArray();
        int bulls = 0, cows = 0;
        for (int i = 0; i < secretDigits.length; i++) {
            if (secretDigits[i] == guessDigits[i]) {
                bulls++;
            } else {
                digits[secretDigits[i] - '0']++;
            }
        }
        for (int i = 0; i < guessDigits.length; i++) {
            if (secretDigits[i] != guessDigits[i] && digits[guessDigits[i] - '0'] > 0) {
                cows++;
                digits[guessDigits[i] - '0']--;
            }
        }
        return bulls + "A" + cows + "B";
    }
}

超过100%

最优解

class Solution {
    public String getHint(String secret, String guess) {
        int cow =0;
        int bull =0;
        int[] arr1 = new int[10];
        int[] arr2 = new int[10];
        for(int i=0;i< secret.length(); i++){
            char c1 = secret.charAt(i);
            char c2 = guess.charAt(i);
            if(c1==c2){
                bull++;
            }
            else{
                arr1[c1-'0']++;
                arr2[c2-'0']++;
            }
        }

        for(int i=0;i<10;i++){
            cow+= Math.min(arr1[i], arr2[i]);
        }

        return bull+"A"+cow+"B";
    }
}

跟我思路差不多，不过他用了两个数组分别记录了两个字符串每个字符出现的次数。然后两个数组的每个数，较小的那个就是cow，因为较小的数其实就是这两个字符串中，这个字符匹配上的个数，也就是猜中的次数。

这个方法比我的好，我那样先加再减，减的时候就需要重复验证这两个字符不一样，即，不是“Bulls”，比较麻烦，容易出bug。

P303. Range Sum Query - Immutable (Easy)

给一个整数数组， 求从索引i到j的所有数的和

我的思路

直接加就完了。。。

我的代码

public class E_303_RangeSumQuery {

    private int[] nums;

    public E_303_RangeSumQuery(int[] nums) {
        this.nums = nums;
    }

    public int sumRange(int i, int j) {
        int sum = 0;
        for (int k = i; k <= j; k++) {
            sum += nums[k];
        }
        return sum;
    }

}

超过7%，相比别人非常慢。

最优解

class NumArray {
    int[] sums;
    int[] nums;
    public NumArray(int[] nums) {
        this.nums = nums;
        this.sums = new int[nums.length];
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            this.sums[i] = sum;
        }
    }

    public int sumRange(int i, int j) {
        return this.sums[j] - this.sums[i] + this.nums[i];
    }
}

这个有点无语。。。在构造方法里先把每个数以前的和都算出来，调用的时候直接用j-i。

答案

private int[] sum;

public NumArray(int[] nums) {
    sum = new int[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
        sum[i + 1] = sum[i] + nums[i];
    }
}

public int sumRange(int i, int j) {
    return sum[j + 1] - sum[i];
}

P326. Power of Three (Easy)

给一个整数，判断它是否是3的幂。

我的思路

根据算2的幂的经验，肯定不能直接除以3。用位运算的话，3是11，9是1001，27是11011，81是1010001。。。 乘3可以看成是往左移一位，再加上自己。写到2187还是找不出来规律。。。

网上搜了一下：

我们首先分析3的幂的特点，假设一个数Num是3的幂，那么所有Num的约数都是3的幂，如果一个数n小于Num且是3的幂，那么这个数n一定是Num的约数。

了解上述性质，我们只需要找到一个最大的3的幂，看看参数n是不是此最大的幂的约数就行了，假设参数是整型，那么3的最大的幂的求法为：

int maxPower = (int) Math.pow(3,(int)(Math.log(0x7fffffff)/Math.log(3)));

0x7fffffff是整型最大值，也就是Integer.maxValue()。表达式后面两个对数相处结果为double，要转化为整型。 下一步只要判断n是不是maxPower的约数即可：

maxPower % n == 0
``` 

————————————————
版权声明：本文为CSDN博主「小白的学习笔记」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：[https://blog.csdn.net/x_i_y_u_e/article/details/50507281](https://blog.csdn.net/x_i_y_u_e/article/details/50507281)

### 最优解

```java
public class E_326_RowerOfThree {
    public boolean isPowerOfThree(int n) {
        if(n == 0) return false;
        while(n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
}

最快的答案反而是常规解法。。。估计测试时间出了问题。

答案：

方法一：

public class Solution {
    public boolean isPowerOfThree(int n) {
        if (n < 1) {
            return false;
        }

        while (n % 3 == 0) {
            n /= 3;
        }

        return n == 1;
    }
}

O(log(n))

方法二：

public class Solution {
    public boolean isPowerOfThree(int n) {
        return Integer.toString(n, 3).matches("^10*$");
    }
}

转化为3进制，然后看是否是“10000…”这种形式

O(log(n))

方法三：

public class Solution {
    public boolean isPowerOfThree(int n) {
        return (Math.log(n) / Math.log(3) + epsilon) % 1 <= 2 * epsilon;
    }
}

方法四：

Java中最大的整数是2147483647（MaxInt）

log_3(MaxInt) = 19.56

floor(19.56) = 19

3^19 = 1162261467

所以最大的3的幂就是1162261467，它如果能整除n，则说明n也是3的幂。

public class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

O(1) 如果执行很多次，方法四肯定是最好的。