第一题：字母异位词分组
第一想法：哈希表
哈希表的键为字符串，值存见过的次数
键的字符串可以按照英文字母排序好，保证键唯一
class Solution{
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>>ans;
if(strs.size()==0||strs.size()==1){
ans.push_back(strs);
return ans;
}
unordered_map<string,vector<string>>map;
for(string str:strs){
string old_str=str;
sort(str.begin(),str.end());
map[str].push_back(old_str);
}
for(auto group:map){
ans.push_back(group.second);
}
return ans;
}
};
通过，注意插入是push_back()，没有insert()
第二题：移动零
第一想法：非零数往前挪，后面直接补0
循环遍历数组，一个变量来记录非零数的当前位置，然后在遍历到非零数时候插入到上一个非零数后面，再把记录非零数的位置往后挪。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int sign=0;
int n=nums.size();
for(int i=0;i<n;i++){
if(nums[i]!=0){
nums[sign]=1;
sign++;
}
}
if(sign==n){
return;
}
for(int i=sign;i<n;i++){
nums[i]=0;
}
return;
}
};
if 面试官问我还有没有别的想法呢？
第二想法：双指针
一个遍历数组，一个记录0的最左边位置，遍历到非零数的时候，非零数和0交换，然后0的最左边位置更新
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n=nums.size();
if(n==1){
return;
}
int left=0;
for(int right=0;right<n;right++){
if(nums[right]!=0){
swap(nums[right],nums[left]);
left++;
}
}
return;
}
};
第三题：盛最多水的容器
第一想法：这题真是印象深刻。
思路就是我想让长宽尽可能大，就先从最长的开始，左右指针直接放两边。
然后检查哪一边的宽更大，把较小的宽往里面挪，知道指针不能移动，返回最大面积。
class Solution{
public:
int maxArea(vector<int>& height){
int right=height.size()-1;
int left=0;
int res=0;
while(right-left>0){
int vol=min(height[left],height[right])*(right-left);
res=max(res,vol);
if(height[left]<height[right]){
left++;
}else{
right--;
}
}
return res;
}
};
第四题：无重复字符的最长子串
滑动窗口思想
用窗口来框住子串
如果有不重复的字符，右边界就不断拓展
如果发现有重复的字符，我们要检查一下这个字符上次出现的位置在哪里，如果就在窗口内部（也就是左边界右边），那我们就更新左边界的位置，也就是上次出现的位置+1
如果上次出现的位置不在窗口内，那就不用管了
为了方便，我们可以用哈希表来存字符和位置
class Solution{
public:
int lengthOfLongestSubstring(string s) {
int n=s.length();
if(n==0||n==1){
return n;
}
unordered_map<char,int>map;
int left=0;
int res=0;
for(int right=0;right<n;right++){
left=max(left,map[s[right]]);
map[s[right]]=right+1;
res=max(res,right-left+1);
}
return res;
}
};
再次做这道题，我发现循环里面真的顺序和为什么这么存都是有理由的。
（1）为什么第一步是left=max(left,map[s[right]]);？？
A：因为left是找当前左边界和遍历到的这个字符的上一个出现位置中的最右边。
捋一下，如果我们现在遍历到的s[right]它不是重复出现的字符，那么map[s[right]]就是0，左边界left就不用动。
如果我们现在遍历到的s[right]它是重复出现的字符，那么我们就要考虑左边界和s[right]这个字符上一次出现的位置关系。
如果左边界<s[right]这个字符上一次出现的位置，说明左边界在s[right]的左边，也就是说left和right之间已经有了一个s[right]，那我们必须要把窗口挪到上一次出现s[right]字符的右边一格，这样我们新拓展的窗口才能只含有现在right遍历到的s[right].
（2）为什么第二步是map[s[right]]=right+1;？？
左边界的判断你需要上一个map[s[right]]存的位置，所以左边界判断第一步，更新这个字符出现的新位置是第二步。
为什么要存right+1而不是right呢？
……如果你存的是right，那如果你新拓展的字符是属于重复字符的话，左边界不就是和你新拓展的这个字符相同了吗
滑动窗口内部和边界上的字符不能相同，所以存right+1
这道题我一开始做的时候想到了哈希表，也想到了如果发现有重复的字符，我们要检查一下这个字符上次出现的位置在哪里，问题是我忘了维持左边界这个东西，唉
滑动窗口的思想没想起来。
第五题：和为K的子数组
前缀和。
该死的前缀和。
我们先计算前缀和存在哈希表中，要是哈希表中有和-k的组合存在
注意如果有正好的单个数是k，我们需要初始一下哈希表是{0,1}
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n=nums.size();
unordered_map<int,int>map{{0,1}};
int res=0;
int sum=0;
for(int i=0;i<n;i++){
sum+=nums[i];
if(map.count(sum-k)!=0){
res+=map[sum-k];
}
map[sum]++;
}
return res;
}
};
第六题：螺旋矩阵
设置上下左右四个边界
螺旋的时候就更新边界
要是边界之间重叠了
那就结束了
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int>res;
int row=matrix.size();
if(row==0){
return res;
}
int col=matrix[0].size();
int u=0;
int d=row-1;
int l=0;
int r=col-1;
while(true){
//上面的横着走
for(int i=l;i<=r;i++){
res.push_back(matrix[u][i]);
}
//上边界更新
if(++u>d){
break;
}
//右边的下着走
for(int i=u;i<=d;i++){
res.push_back(matrix[i][r]);
}
//更新右边界
if(--r<l){
break;
}
//下边的左着走
for(int i=r;i>=l;i--){
res.push_back(matrix[d][i]);
}
//更新下边界
if(--d<u){
break;
}
//左边的上着走
for(int i=d;i>=u;i--){
res.push_back(matrix[i][l]);
}
//更新左边界
if(++l>r){
break;
}
}
return res;
}
};
第七题：相交链表
我吹过你吹过的晚风，那我们算不算相拥~
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==nullptr||headB==nullptr){
return nullptr;
}
ListNode *a=headA;
ListNode *b=headB;
while(a!=b){
a=a==nullptr?headB:a->next;
b=b==nullptr?headA:b->next;
}
return a;
}
};
这道题再写的时候，很奇妙的一点就是，不管这两个链表有没有相交，他俩都会有相同的时候，哪怕是空也会一起空。
其实不相交的，也可以看成这俩链表的最后一个节点都是空节点，相交在空节点嘛。
第八题：反转链表
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *pre=nullptr;
ListNode *cur=head;
if(head==nullptr){
return nullptr;
}
while(cur!=nullptr){
ListNode *temp=cur->next;
cur->next=pre;
pre=cur;
cur=temp;
}
return pre;
}
};
写代码的过程中，return的是pre，而不是cur，因为在最后一个while循环中，cur==nullptr是跳出边界。
第九题：二叉树的中序遍历
中序遍历：左 中 右
首先是递归：
class Solution {
public:
void inorder(TreeNode *root,vector<int>&res){
if(root!=nullptr){
inorder(root->left,res);
res.push_back(root->val);
inorder(root->right,res);
}
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int>res;
inorder(root,res);
return res;
}
};
如果不用递归的话，那么就是用栈
栈的特性是先进后出
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*>st;
vector<int>res;
while(root!=nullptr||!st.empty()){
while(root!=nullptr){
st.push(root);
root=root->left;
}
root=st.top();
res.push_back(root->val);
st.pop();
root=root->right;
}
return res;
}
};