周末愉快，日常三题。

移动零

题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

思路：这个怎么说呢，简单粗暴的方法确实容易，但是性能堪忧。在原数组操作也不难，我先去撸代码试一下我的想法。
好了，测试完了，一次通过而行速度0ms。完美，直接贴代码:

class Solution {
    public void moveZeroes(int[] nums) {
        int x = 0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0){
                nums[x] = nums[i];
                x++;     
            }
        }
        for(int j = x;j<nums.length;j++){
            nums[j] = 0;
        }
    }
}

其实这个思路还是很简单的。非0的顺序往前排。最后空出的元素都补0就可以了。下一题。

缺失数字

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例 1:
输入: [3,0,1]
输出: 2
示例 2:
输入: [9,6,4,2,3,5,7,0,1]
输出: 8
说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

思路：这个题怎么说呢，我觉得我可以做到。而且第一反应还是异或运算。。。n个数的数组，那么最大值应该就是数组的长度（因为必定是从0开始，顺序来是到length-1结束。不过现在因为缺了一个，所以最后一位应该+1.）我可以用0=n的常数与这个数组异或运算，同样的数异或运算为0.剩下的数就是数组中没有的那个数字。接下来我去写代码了。

class Solution {
    public int missingNumber(int[] nums) {
        int result = 0;
        for(int i = 0; i<nums.length;i++){
            result = result^nums[i];
            result = result^i;
        }
        result = result^nums.length;
        return result;
    }
}

一次搞定，性能百分百。莫名觉得今天的几道题都很顺手啊~~开心！下一题。

单词规律

题目：给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。

示例1:
输入: pattern = "abba", str = "dog cat cat dog"
输出: true
示例 2:
输入:pattern = "abba", str = "dog cat cat fish"
输出: false
示例 3:
输入: pattern = "aaaa", str = "dog cat cat dog"
输出: false
示例 4:
输入: pattern = "abba", str = "dog dog dog dog"
输出: false
说明:
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。

**思路：这种比较题，我第一反应就是哈希。所以这里用了判断。判断有两个点：相同pattern字母对应的str字符串的单词是不是对。但是其实还有一点需要注意：那就是不同pattern对应的str字符串的单词是不是一样。如果是一样的说明也还是不符合要求。如上图的示例四就是一个例子。所以判断的时候两个都要判断一下，直接上代码： **

class Solution {
    public boolean wordPattern(String pattern, String str) {
        Map<Character,String> map = new HashMap<Character,String>();
        String[] arr = str.split(" ");
        if(pattern.length()!=arr.length) return false;
        for(int i=0;i<pattern.length();i++){
            if(map.containsKey(pattern.charAt(i))){
                if(!arr[i].equals(map.get(pattern.charAt(i)))){
                    return false;
                }
            }else{
                if(map.containsValue(arr[i])){
                    return false;
                }else{
                    map.put(pattern.charAt(i),arr[i]);
                }               
            }
        }
        return true;
    }
}

其实这个逻辑很简单，所以我也不多说了，而且速度超过百分百，所以也不看题解了， 继续下一题。

Nim游戏

题目：你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:
输入: 4
输出: false
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

思路：这个游戏我还真玩过。跟那个数30差不多的。我大概记得，其实这个前面可以迅速往下数，主要是争取把四块石头留给对方，这样就稳赢了。我去理理思路。理好了再看怎么实现。
这个题我想装一下B，好好讲讲，首先这道题又是我用眼睛“看出来”的一道题。其实我更觉得他不是代码题，而是一道数学题，找规律的题。
给大家看一下我的草稿：

看的过程

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

其实说实话，这道题依然简单，但是用代码的思维什么递归迭代循环，反而麻烦不少。关于这道题的解不接受批评。下一题。

猜数字游戏

题目：你正在和你的朋友玩 猜数字（Bulls and Cows）游戏：你写下一个数字让你的朋友猜。每次他猜测后，你给他一个提示，告诉他有多少位数字和确切位置都猜对了（称为“Bulls”, 公牛），有多少位数字猜对了但是位置不对（称为“Cows”, 奶牛）。你的朋友将会根据提示继续猜，直到猜出秘密数字。请写出一个根据秘密数字和朋友的猜测数返回提示的函数，用 A 表示公牛，用 B 表示奶牛。请注意秘密数字和朋友的猜测数都可能含有重复数字。

示例 1:
输入: secret = "1807", guess = "7810"
输出: "1A3B"
解释: 1 公牛和 3 奶牛。公牛是 8，奶牛是 0, 1 和 7。
示例 2:
输入: secret = "1123", guess = "0111"
输出: "1A1B"
解释: 朋友猜测数中的第一个 1 是公牛，第二个或第三个 1 可被视为奶牛。
说明: 你可以假设秘密数字和朋友的猜测数都只包含数字，并且它们的长度永远相等。

思路:一开始看题目以为是大了小了那个题目呢。哎，结果没想到比那个复杂多了。这个题怎么说呢，审题吧，我看了第一遍以为是根据提示自己猜这个数呢，第二遍看题才看明白，只不过是比较两串字符串而已，怎么对得起这个名字？好的，我已经透漏了我的思路：就是两串字符串的比对。分两种比对：一种是相同位置相同数字（所谓公牛）。一种是位置不同但是数字相同（所谓奶牛，更外我注意到的一点，虽然公牛肯定满足奶牛了，但是不算做是奶牛，所以判断数字相同还要把公牛去了）。就说到这，我去撸代码
第一版本写完回来了，不出所料，性能差的一批，但是起码逻辑简单粗暴，先贴上来：

class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0;
        int cows = 0;
        for(int i = 0;i<secret.length();i++){
            if(secret.charAt(i)==guess.charAt(i)){
                bulls++;
            }
        }
        for(int i = 0;i<secret.length();i++){
            if(secret.indexOf(guess.charAt(i))!=-1){
                secret = secret.replaceFirst(guess.charAt(i)+"","a");
                cows++;
            }
        }
        return bulls+"A"+(cows-bulls)+"B";
    }
}

我自己都知道这两个循环肯定是有点问题，但是怎么合并成一个还得寻思，我先想想。看了一圈题解也没看出好办法，所以这道题就这样吧。莫名其妙的这道题没啥评论，而且题解也很少。

区域和检索-数组不可变

题目：给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

示例：
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:
你可以假设数组不可变。
会多次调用 sumRange 方法。

思路:这道题怎么说呢，字面上来讲简单的不得了，越是这种题我越心烦，因为不知道题目又是什么暗要求！有什么限制也不明说，日了狗了简直。反正第一版本无脑版直接贴上，我去看看题解这个题到底是什么玩意

class NumArray {

    private int[] nums;

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

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

哦，看了评论了，这道题重点是多次调用，所以每次计算不好，要存储前n位的和。这样取i到j 的之后前j的和减去前i的和加上i就行了。我简直日狗了，这个要求也不难，直接说不能累加不行么？心累，今天刷的最后一道题就这么影响心情。我去按照这个要求去写一版代码:

class NumArray {

    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];
    }

}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

今天的笔记就记录到这里，如果稍微帮到你了记得点个喜欢点个关注呦~！也祝大家工作顺顺利利，周末愉快！