LeetCode刷题总结 -- 数组篇

示例 1:

给定数组 nums = [1,1,2], 
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

[
  [-1, 0, 1],
  [-1, -1, 2]
]

[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]

[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]

[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

void setZeroes(vector<vector<int>>& matrix) {
    if(matrix.empty())
        return;
    int r = matrix.size();
    int c = matrix[0].size();

    set<int> rs;
    set<int> cs;
    set<int>::iterator sit;

    //将有0的行列提取出来
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            if (matrix[i][j] == 0)
            {
                rs.insert(j);
                cs.insert(i);
            }
        }
    }

    if (!cs.empty())
    {
        int a = c;
        vector<int> temp;
        while (a > 0)
        {
            temp.push_back(0);
            a--;
        }
        
        //将行清零
        for (sit = cs.begin(); sit != cs.end(); sit++)
        {
            matrix[*sit] = temp;
        }
    }

    //将列清零
    if (!rs.empty())
    {
        for (sit = rs.begin(); sit != rs.end(); sit++)
        {
            for (int k = 0; k< r; k++)
            {
                matrix[k][*sit] = 0;
            }
        }
    }
}

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

vector<vector<string>> groupAnagrams(vector<string>& strs) 
{
    vector<vector<string>> res;
    map<string,vector<string>> vec;
    if(strs.empty()) return res;
    for(int i=0;i<strs.size();i++)
    {
        string temp=strs[i];
        sort(temp.begin(),temp.end());
        vec[temp].push_back(strs[i]);
    }
    map<string,vector<string>>::iterator it;
    for(auto it=vec.begin();it!=vec.end();it++)
    {
        res.push_back(it->second);
    }
    return res;
}

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

#include <vector>
using namespace std;

#include<vector>

//创建vector
vector<int> test;	//初始化一个Vector实例，用于存放int型数据，实例名字叫test
vector<int> test2 = test;	//以test1为标准创建test2

vector<int>test3(10);	//像这种，少用。上次用的时候，往里面插了一个数据之后就没办法插入了。何况STL会自己给你分配空间，用不着你操心。

//插入数据
test.insert(test.begin()+i,a);	//在第i个元素前插入a
test.insert(test.begin()+i,te2.begin(),te2.end());	
//插入一段相同数据类型数据，第一个参数放插入位置（指针/迭代器形式），第二三个参数放待插入元素起始位置

test.push_back(a);	//往尾部插入
//一般我们就用尾部插入

//删除元素
test.erase(test.begin());
test.erase(test.begin(),test.begin()+5);//删除区间(第一个元素到第五个元素)

test.clear();	//清空

test.pop_back();	//删除尾部元素

/*
遍历元素
当然，你可以使用数组下标形式访问元素，因为vector重载了 [] 操作，很方便，但是有诸多限制。
还有一个叫at()的函数，这个好用。

也可以使用迭代器：
*/

vector<int>::iterator it;	//初始化一个vector<int>类型的迭代器
for(it = test.begin();it!=test.end();it++)	//从头遍历到尾
{
	cout<<*it<<endl;	//取出内容
}


//排序
#include<algorithm>
/*test.*/sort(test.begin(),test.end());	//从头到尾，默认从小到大排序
这里要非常注意，前面那个test. 被我注释掉了，因为sort是属于算法范畴，不是容器的类方法。

//一般排序都是要自定义排序的：
bool Comp(const int &a,const int &b)
{
    return a>b;
}
sort(test.begin(),test.end(),Comp);	//这样就降序排序。