283. 移动零

第一反应是冒泡

class Solution {
public:void moveZeroes(vector& nums) {int size=nums.size();if(size==1)return ;for(int i=0;ifor(int j=0;jif(nums[j]==0&&nums[j+1]!=0){int temp = nums[j+1];nums[j+1]=nums[j];nums[j]=temp;}}}return ;}
};

很慢内
评论区大佬的思路:

一定要反过来想,不要只盯着0,可以设置一个指针,就是专业收集不是零的数 收集一遍后,后面的一定是0,就再将空出来的位置设置为0,就解决问题了

class Solution {
public:void moveZeroes(vector& nums) {int size=nums.size();if(size==1)return ;int s=0;//收集不为0的数组下标for(int i=0;iif(nums[i]!=0)nums[s++]=nums[i];}for(int i=s;inums[i]=0;}return ;}
};

题解中的方法是
双指针法
左指针指向已处理的数列的尾部
右指针指向未处理数列的头部
左指针为0时，左右指针指向的数字交换

class Solution {
public:void moveZeroes(vector& nums) {int n = nums.size(), left = 0, right = 0;while (right < n) {if (nums[right]) {swap(nums[left], nums[right]);left++;}right++;}}
};

290. 单词规律

没什么思路
大佬的做法是双哈希法

1 个 map 记录模式与字符串的匹配关系，另外一个 map 记录字符串和模式的匹配关系。为什么需要记录双向的关系呢？因为 Example 4 中，a 对应了 dog，这个时候 b 如果再对应 dog 是错误的，所以这里需要从 dog查询它是否已经和某个模式匹配过了。所以需要双向的关系。

c++中没有split()函数，没法很简洁地分开一句里的单词，所以实现一下

istringstream strs(str);
vector words;
string word;
while(strs>>word){words.push_back(word);
}

整体代码如下

class Solution {
public://题解：双哈希bool wordPattern(string pattern, string str) {//C++ splitistringstream strs(str);vector words;string word;while(strs>>word){words.push_back(word);}if(pattern.size()!=words.size())return false;map m1;//建立 <字符，单词> 的映射map m2;//建立 <单词，字符> 的映射for(int i=0;i//若pat的字符在m1中，但该字符对应的单词与word不相等，返回false a->dog a->fishif(m1.count(pattern[i])&&m1[pattern[i]]!=words[i])return false;//若单词在m2中，单该单词对应的字符用pat[i]不相等，返回false，a->dog b->dogif(m2.count(words[i])&&m2[words[i]]!=pattern[i])return false;//都不在，则建立映射m1[pattern[i]]=words[i];m2[words[i]]=pattern[i];}return true;}
};

292. Nim 游戏

不会捏
数学推理
如果石头堆中只有一块、两块、或是三块石头，那么在你的回合，你就可以把全部石子拿走，从而在游戏中取胜；如果堆中恰好有四块石头，你就会失败。因为在这种情况下不管你取走多少石头，总会为你的对手留下几块，他可以将剩余的石头全部取完，从而他可以在游戏中打败你。因此，要想获胜，在你的回合中，必须避免石头堆中的石子数为 4 的情况。
我们继续推理，假设当前堆里只剩下五块、六块、或是七块石头，你可以控制自己拿取的石头数，总是恰好给你的对手留下四块石头，使他输掉这场比赛。但是如果石头堆里有八块石头，你就不可避免地会输掉，因为不管你从一堆石头中挑出一块、两块还是三块，你的对手都可以选择三块、两块或一块，以确保在再一次轮到你的时候，你会面对四块石头。显然我们继续推理，可以看到它会以相同的模式不断重复 n=4,8,12,16,…，基本可以看出如果堆里的石头数目为 4 的倍数时，你一定会输掉游戏。
如果总的石头数目为 4 的倍数时，因为无论你取多少石头，对方总有对应的取法，让剩余的石头的数目继续为 4 的倍数。对于你或者你的对手取石头时，显然最优的选择是当前己方取完石头后，让剩余的石头的数目为 4 的倍数。假设当前的石头数目为 x，如果 x 为 4 的倍数时，则此时你必然会输掉游戏；如果 x 不为 4 的倍数时，则此时你只需要取走 x mod 4 个石头时，则剩余的石头数目必然为 4 的倍数，从而对手会输掉游戏。

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