本文介绍: 这个代码是肯定跑不了的，但是我个人最开始的想法确实是差不多这个样子的我感觉这个题目如果使用哈希表来做有点难，主要是去重操作，自己代码搞了半天我还不知道自己哪里有问题，感觉还是比较麻烦的。那个哈希表的创建还要在找到了去重了a之后再去创建，感觉有点难理解。
每日博客Day 12
每日算法
三数之和
这个代码是肯定跑不了的，但是我个人最开始的想法确实是差不多这个样子的
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//两层for循环来确定a+b的数值，然后再去哈希表中查找 是否存在另外一个数值
unordered_set<int> set_find;
vector<int> res2;
vector<vector<int>> res;
for (int num : nums)
{
set_find.insert(num);
}
int temp = 0;
for (int i = 0; i < nums.size(); i++)
{
for (int j = i+1; j < nums.size(); j++)
{
temp = nums[i] + nums[j];
int find_value = 0 - (temp);
if (set_find.find(find_value) != set_find.end())
{
res2.push_back(nums[i]);
res2.push_back(nums[j]);
res2.push_back(find_value);
res.push_back(res2);
}
}
}
return res;
}
};
我感觉这个题目如果使用哈希表来做有点难，主要是去重操作，自己代码搞了半天我还不知道自己哪里有问题，感觉还是比较麻烦的。
那个哈希表的创建还要在找到了去重了a之后再去创建，感觉有点难理解
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] > 0) return res;
if (i > 0 && nums[i] == nums[i - 1] ) continue;
unordered_set<int> m_set;
for (int j = i + 1; j < nums.size(); j++)
{
if (j > i + 2
&& nums[j] == nums[j - 1]
&& nums[j - 1] == nums[j - 2])
{
continue;
}
int find_c = 0 - (nums[i] + nums[j]);
if (m_set.find(find_c) != m_set.end())
{
res.push_back({ nums[i],nums[j],find_c });
m_set.erase(find_c); //对c的去重操作
}
else
{
m_set.insert(nums[j]);
}
}
}
return res;
}
};
利用双指针方式
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] > 0) return res;
//i-1这个判断肯定是要放在后面的位置的，因为当i=0的时候会出现越界的情况
if (i > 0 && nums[i] == nums[i - 1]) continue;
//此时确定了i的位置，要去寻找left和right的位置
int right = nums.size() - 1;
int left = i + 1;
if(left == right) return res;
while (right > left)
{
if (nums[i] + nums[left] +nums[right] > 0) right--;
else if (nums[i] + nums[left] +nums[right] < 0) left++;
else
{
res.push_back({ nums[i],nums[left],nums[right] });
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
return res;
}
};
四数之和
看了时评的讲解之后会感觉，没有什么特别难的感觉，就是在运行的时候要注意数据的大小范围，要加上long的范围
虽然代码数量看着比较多，但是理解代码的思路之后其实感觉其实还好，continue和break的使用要注意
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] > target && target >= 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.size(); j++)
{
if ((nums[i] + nums[j]) > target && target > 0) break;
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1;
int right = nums.size()-1;
while (left < right)
{
if ((long)nums[i] + nums[j] + nums[left] + nums[right] > target) right--;
else if ((long)nums[i] + nums[j] + nums[left] + nums[right] < target) left++;
else
{
result.push_back(vector<int>{ nums[i],nums[j],nums[left],nums[right] });
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
left++;
right--;
}
}
}
}
return result;
}
};
明天的时候再写一个总结，今天先简单的看一下哈希表的总结内容即可
得到0的操作数
class Solution {
public:
int countOperations(int num1, int num2)
{
int count = 0;
while(num1 && num2)
{
count++;
if(num1 >= num2) num1 -= num2;
else num2 -= num1;
}
return count;
}
};
找到最接近0的操作数
class Solution {
public:
int m_abs(int num)
{
if(num >= 0) return num;
else return -num;
}
int findClosestNumber(vector<int>& nums) {
int result = nums[0];
for(int num : nums)
{
if(m_abs(num) < m_abs(result) || m_abs(num) == m_abs(result)
&& num > result) result = num;
}
return result;
}
};
项目进度
因为我个人的基础问题，加上这个项目的学习阻力太大，基本上就是对着无脑的去码代码，实际上对我来说的学习和帮助是没有多少的，虽然前面投入了很多时间，但是综合考虑过来，决定了还是丢下这个MFC的项目，之后等自己的基础更好了或者有需要了再来完善这个项目。
当下的学习目标和重点还是可以放在基础的内容上面，把Linux系统编程的内容下面一部分看完
Day 13
字符串的替换数字
#include <iostream>
using namespace std;
void ReplaceNum(string &s)
{
if (s.size() == 0) return;
int count = 0;
//统计有多少个数字存在
for (int i = 0; i < s.size(); i++)
{
if (s[i] >= '0' && s[i] <= '9') count++;
}
int oldSize = s.size();
s.resize(oldSize + count * 5);
int newSize = s.size();
//这里开始替换
for (int i = oldSize - 1, j = newSize - 1; i < j; i--, j--)
{//分两种情况
if (s[i] > '9' || s[i] < '0')
{//说明这个属于字母的情况
s[i] = s[j];
}
else//说明遇到的是数字的情况
{//number
s[j] = 'r';
s[j - 1] = 'e';
s[j - 2] = 'b';
s[j - 3] = 'm';
s[j - 4] = 'u';
s[j - 5] = 'm';
i -= 5;
}
}
}
int main()
{
string s;
cin >> s; //在这里输入s的长度
ReplaceNum(s);
cout << s;
return 0;
}
KMP算法
KMP算法是用来解决字符串匹配的问题，它可以更加高效的进行字符串的匹配
如何暴力求解字符串匹配，其实就是前缀表的匹配过程，然后利用next数组来保存前缀表的内容
class Solution {
public:
void getnext(int* next, string target)
{
if (target.size() == 0) return;
int j = 0;
next[j] = 0;
for (int i = 1; i < target.size(); i++)
{
//当两者是不匹配的情况下,j必须要是大于0的情况下
while (target[i] != target[j] && j > 0)
{//回退到前面的前缀和位置，然后在进行判断是否相同，这样子就不需要一个一个位置的回退
j = next[j - 1];
}
if (target[i] == target[j]) j++;
next[i] = j;
}
}
int strStr(string haystack, string needle)
{
if (haystack.size() == 0 || needle.size() > haystack.size()) return -1;
int next_arr[needle.size()];
getnext(next_arr, needle);
int j = 0;
for (int i = 0; i < haystack.size(); i++)
{//用j来作为needle的下标
while (j > 0 && haystack[i] != needle[j]) j = next_arr[j - 1];
if (haystack[i] == needle[j]) j++;
//判断j的下标是否在最末尾了
if (j == needle.size())
{
return (i - needle.size() + 1);
}
}
return -1;
}
};
字符串判断
我觉得关于字符串的算法都比较难，对边界的处理啥的都不是特别的容易
在这里要注意这个string里面的find函数的返回值的结果
如果没有找到结果的话，返回的就是npos，这个表示的就是no position
class Solution {
public:
bool repeatedSubstringPattern(string s) {
string test = s + s;
test.erase(test.begin());
test.erase(test.end()-1);
auto p = test.find(s);
if (p != string::npos) return true;
return false;
}
};
移除元素
暴力解决方式，当然也可以直接调用库函数来解决，知识熟悉一下库函数的使用
class Solution {
public:
int removeElement(vector<int>& nums, int val)
{
if (nums.size() == 0) return 0;
int size = nums.size();
for (int i = 0; i < size; i++)
{//如果这里是i<nums.size是不可以通过的
if (nums[i] == val)
{
for (int j = i + 1; j < nums.size(); j++)
{
nums[j - 1] = nums[j];
}
size--;
i--;
}
}
return size;
}
};
双指针法
class Solution {
public:
int removeElement(vector<int>& nums, int val)
{
int slowIndex = 0;
int FastIndex = 0;
while (FastIndex < nums.size())
{//fast指向的是没有val的新数组
if (nums[FastIndex] != val)
{
nums[slowIndex++] = nums[FastIndex];
}
FastIndex++;
}
return slowIndex;
}
};
设计模式
简单工厂设计模式
1.提供一个工厂类
简单工厂模式的核心，它负责实现创建所有实例的内部逻辑。工厂类可以被外界直接调用，创建所需的产品对象。
简单工厂模式所创建的所有对象的父类，它负责描述所有实例所共有的公共接口。
3.提供一个具体产品类
//1.提供一个工厂类
//简单工厂模式的核心，它负责实现创建所有实例的内部逻辑。工厂类可以被外界直接调用，创建所需的产品对象。
//
//2.提供一个抽象产品类
//简单工厂模式所创建的所有对象的父类，它负责描述所有实例所共有的公共接口。
//
//3.提供一个具体产品类
//简单工厂模式所创建的具体实例对象
//抽象产品类
class AbstractProduct
{
public:
int left_value;
int right_value;
virtual int GetResult() = 0;
};
//具体产品类
class AddFun :public AbstractProduct
{
int GetResult()
{
return left_value + right_value;
}
};
class SubFun :public AbstractProduct
{
int GetResult()
{
return left_value - right_value;
}
};
class ChuFaFun :public AbstractProduct
{
int GetResult()
{
if(right_value != 0) return left_value - right_value;
else return -1;
}
};
class ChengFaFun :public AbstractProduct
{
int GetResult()
{
return left_value * right_value;
}
};
//抽象工厂类
class AbstractFactory {
public:
static AbstractProduct* CreateOperation(char c)
{
switch (c)
{
case '+':
return new AddFun;
break;
case '-':
return new SubFun;
break;
case '*':
return new ChengFaFun;
break;
case '/':
return new ChuFaFun;
break;
default:
break;
}
}
};
int main()
{
//创建一个抽象产品的指针指向工厂，来调用方法
//因为Create是静态的，所以可以直接从类中调用
AbstractProduct* pro = AbstractFactory::CreateOperation('+');
pro->left_value = 10;
pro->right_value = 20;
cout << pro->GetResult() << endl;
return 0;
}
原文地址:https://blog.csdn.net/m0_73202575/article/details/134658661
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_41354.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
