Day 12 周日和周一

本文主要是介绍Day 12 周日和周一，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

每日博客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的操作数

直接无脑模拟就可以了，两个正整数是一定可以相减为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

字符串的替换数字

其实这个题目还是有点难度

1. 数组的扩容
2. 利用的是双指针的方式求解

#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//说明遇到的是数字的情况{//numbers[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.提供一个工厂类

简单工厂模式的核心，它负责实现创建所有实例的内部逻辑。工厂类可以被外界直接调用，创建所需的产品对象。

2.提供一个抽象产品类

简单工厂模式所创建的所有对象的父类，它负责描述所有实例所共有的公共接口。

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;
}

这篇关于Day 12 周日和周一的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---