周末愉快，日常三题。
移动零
题目：给定一个数组 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，好好讲讲，首先这道题又是我用眼睛“看出来”的一道题。其实我更觉得他不是代码题，而是一道数学题，找规律的题。
给大家看一下我的草稿：
看的过程
如图所示:4在谁手谁肯定会输。
换个想法：5在谁手里谁肯定会赢。原因是5-1.取走一块把4.留给了对方
再换个想法：6在谁手里谁也肯定会赢。6-2 取走两块还是把4留给对方
再来：7在谁手里谁肯定会赢。 7-3 取走三块仍然是4留给对方。
接下来要注意了：8在谁手里谁肯定会输，因为八不管拿走几块结果只能是5，6，7.这个能确定对方肯定会赢。
然后同理：9在谁手里谁肯定会赢， 因为9-1拿走一块，把八块留给对方了
10也是这样， 肯定能赢
11也是这样， 肯定能赢
到了12问题反转：12不管拿走几块， 9 ，10 ，11 肯定在对方手里，对方肯定赢，所以本方肯定输。
其实从上面的几个就能看出规律了。我图中只是把规律表现的更明显。这个规律就是谁拿到了四的倍数肯定输， 不然就肯定能赢。
然后这道题就是这么简单。判断给定数是不是4的倍数就可以：
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);
*/
今天的笔记就记录到这里，如果稍微帮到你了记得点个喜欢点个关注呦~！也祝大家工作顺顺利利，周末愉快！
网友评论