数组
要求
实现一个支持动态扩容的数组
实现一个大小固定的有序数组，支持动态增删改操作
实现两个有序数组合并为一个有序数组
学习哈希表思想，并完成leetcode上的两数之和(1)及Happy Number(202)！(要求全部用哈希思想实现！)
哈希表 ： 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
散列函数设计原则：
计算简单：散列函数的计算时间不应该超过其他查找技术与关键字比较的时间。
散列地址分布均匀：尽量让散列地址均匀地分布在存储空间中，这样可以保证存储空间的有效利用，并减少为处理冲突而耗费的时间
1.Three Sum（求三数之和）
英文版：https://leetcode.com/problems/3sum/
中文版：https://leetcode-cn.com/problems/3sum/
```
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
map<int,int> temp;
vector<vector<int>> ans;
set<set<int>> anss;
int len = nums.size();
int n = 0;
sort(nums.begin(), nums.end());
for (int i = 0; i < len; i++)
{
temp[nums[i]] = i;
}
for (int i = 0; i < len; i++){
for (int j = i+1; j < len; j++)
{
int num = -nums[i] - nums[j];
if (num>0) continue;
map<int, int> ::iterator add = temp.find(num);
if (add == temp.end() || add->second <= j) continue;
set<int> t;
t.insert(nums[i]);
t.insert(nums[j]);
t.insert(add->first);
//cout << nums[i] << nums[j] << add->first << endl;
if (anss.count(t) == 0)
{
anss.insert(t);
vector<int> t;
t.push_back(nums[i]);
t.push_back(nums[j]);
t.push_back(add->first);
ans.push_back(t);
cout << nums[i] << nums[j] << add->first << endl;
}
}
}
return ans;
}
};
```
2.Majority Element（求众数）
英文版：https://leetcode.com/problems/majority-element/
中文版：https://leetcode-cn.com/problems/majority-element/
刚开始理解C++，先用个简单方法吧，时间仓仓仓仓促。将数组给定区间的所有元素进行排序之后返回数量大于n/2的元素。（排序后还出现在中点，那一定是有很多个了）
```
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums[nums.size()/2];
}
};
```
https://leetcode-cn.com/problems/majority-element/
3.Missing Positive（求缺失的第一个正数）
英文版：https://leetcode.com/problems/first-missing-positive/
中文版：https://leetcode-cn.com/problems/first-missing-positive/
```
class Solution {public:
intfirstMissingPositive(vector& nums) {
intn = nums.size();
for(inti =0; i < n; ++i) {
while(nums[i] >0&& nums[i] <= n && nums[nums[i] -1] != nums[i]) {
swap(nums[i], nums[nums[i] -1]);
}
}
for(inti =0; i < n; ++i) {
if(nums[i] != i +1)returni +1;
}
returnn +1;
}
};
```
https://leetcode-cn.com/problems/first-missing-positive/
字符串
实现一个字符集，只包含 a～z 这 26 个英文字母的 Trie 树
实现朴素的字符串匹配算法
1.Reverse String （反转字符串）
英文版：https://leetcode.com/problems/reverse-string/
中文版：https://leetcode-cn.com/problems/reverse-string/
```
class Solution {
public:
void reverseString(vector<char>& s) {
int length=s.size();
if(length<2)
return;
//reverse()会将区间[beg,end)内的元素全部逆序；
reverse(s.begin(),s.end());
}
};
```
https://leetcode-cn.com/problems/reverse-string/
2.Reverse Words in a String（翻转字符串里的单词）
英文版：https://leetcode.com/problems/reverse-words-in-a-string/
中文版：https://leetcode-cn.com/problems/reverse-words-in-a-string/
将字符串中的每个单词反转一下。对C++比C友好太多了！！
```
class Solution {
public:
string reverseWords(string s) {
int last = 0, now = 0;
//翻转每个单词，同时翻转整个字符串，则对应单词拼写正确
while (s[now])
{
while (s[now] == ' ') now++;
last = now;
while (s[now] != ' ' && s[now] != '\0') now++;
reverse(s[now], s[now-1]);
}
reverse(s[0], s[now-1]);
last = 0;
//删除多余的空格
for (int i = 0; i < now; i++)
{
if (!isblank(s[i]) || (last && s[last - 1] != s[i]))
s[last++] = s[i];
}
s[last] = 0;
if (last && s[last - 1] == ' ')
s[last - 1] = 0;
}
};
```
3.String to Integer (atoi)（字符串转换整数 (atoi)）
英文版：https://leetcode.com/problems/string-to-integer-atoi/
中文版：https://leetcode-cn.com/problems/string-to-integer-atoi/
```
class Solution {
public:
int myAtoi(string str) {
const int maxint=0x7fffffff;
const int minint=0x80000000;
const long long max=0x100000000;
long long ans=0;
bool flag=false;
int st=0;
while(st<str.length()&&str[st]==' '){
st++;
}
if(st<str.length()&&str[st]=='+'){
st++;
}else{
if(st<str.length()&&str[st]=='-'){
flag=true;
st++;
}
}
for(int i=st;i<str.length();i++){
if(str[i]<='9'&&str[i]>='0'){
ans=ans*10+str[i]-'0';
if(ans>maxint) ans=max;
}else{
break;
}
}
if(flag) ans=-ans;
if(ans>maxint) ans=maxint;
if(ans<minint) ans=minint;
return ans;
}
};
```
网友评论