【刷题笔记】笔记一

1.自守数

牛客链接

解析：
1.自守数的结尾肯定是 0，1，5，6
2.把数字转换为string类（方便比较）
3.直接find在s2 里面 使用find查找另一个即可。

#include <iostream>
#include<string>
using namespace std;int fun(int n)
{int ret =0;for(int i=0;i<=n;i++){if(i%10 == 0 || i%10 == 5 ||i%10 == 6 ||i%10 ==1){long j =i*i;string s1 = to_string(i);string s2 = to_string(j);int pos = s2.size() - s1.size();if(s2.find(s1,pos) != string::npos){ret++;}}  }return ret;
}
int main() {int n;while (cin >> n) { cout<<fun(n)<<endl;}return 0;
}

知识点：
1，to_string()函数。
2，find的返回值 string::npos

2.返回小于 N 的质数个数

题目链接

#include <iostream>
using namespace std;
bool fun(int n){for(int i = 2; i*i <= n; i++){if(n%i == 0){return false;}}return true;
}int main() {int n;int ret = 0; while(cin>>n){ret =0;for(int i = 3; i<n; i+=2){if(fun(i)){ret++;}}}cout<<ret+1;return 0;
}

知识点：
1，除了2 质数只能是奇数。
1，验证N是否是质数的时候只需要从2验证到N开根号即可。

3.只出现一次的数字

oj链接

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(auto n :nums){ret ^= n;}return ret;}
};

4.杨辉三角（vector)

oj链接

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv;vv.resize(numRows);//不给初始化值，就会调用vector<int> 的默认构造。for(size_t i =0; i<vv.size();i++){vv[i].resize(i+1, 0);vv[i][0] = vv[i][vv[i].size()-1] = 1;}for(int i =0; i< vv.size(); i++){for(int j=0; j< vv[i].size(); j++){if(vv[i][j] == 0){vv[i][j] = vv[i-1][j] +vv[i-1][j-1];}}}return vv;}
};

这里使用c++ vector 很方便 比 C语言简单的多。
注意区分和c语言的区别。

5.电话号码的字母组合（递归）

oj题目

class Solution {string _numstr[10] = {"","","abc","def","ghi","jkl","mno", "pqrs", "tuv","wxyz"};
public:void combine(const string& digits,size_t i , vector<string>& ret, string tmp){if(i == digits.size()){ret.push_back(tmp);return;}size_t num = digits[i] - '0';for(auto ch :_numstr[num]){combine(digits, i+1, ret, tmp+ch);}}vector<string> letterCombinations(string digits) {//digits存放的是数字字符串vector<string> ret;//返回的值if(digits.empty()){return ret;}string tmp;//记录此深度的字符串组合size_t i =0;combine(digits,i,ret,tmp);return ret;}
};

深度体会递归的思想
这个题主要是，那些不够直观。
本质是一个二叉树的深度遍历

6.删除有序数组中的重复项

题目链接

class Solution {
public:int removeDuplicates(vector<int>& nums) {int i =0;for(auto n : nums)if(n != nums[i]) nums[++i] = n;return i+1;}
};

其实就是快慢指针（双指针）

7.只出现一次的数字 II

题目oj

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(int i = 0 ;i< 32; i++){int val =0;for(auto j : nums){val += (j>>i)&1;}if(val % 3 ){ret += (1<<i);}}return ret;}
};//法二：
class Solution {
public:int singleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int i = 0;while(i < nums.size()-1){if(nums[i] == nums[i+1] && nums[i+1]== nums[i+2]){i += 3;}else{return nums[i];}}return nums[i];}
};

8.只出现一次的数字 III

题目oj

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {vector<int> ret;int val = 0;for(int i : nums){val ^= i;}int i=0;for( i = 0; i <32 ;i++){if((val >> i )& 1 == 1){break;}}vector<int> v1;vector<int> v2;for(int a : nums){if((a>>i)&1 == 1){v1.push_back(a);}else{v2.push_back(a);}}int b =0;for(int a: v1){b^=a;}ret.push_back(b);b=0;for(int a: v2){b^= a;}ret.push_back(b);return ret;}
};

9.数组中出现次数超过一半的数字

题目链接

class Solution {
public:int MoreThanHalfNum_Solution(vector<int> numbers) {sort(numbers.begin(), numbers.end());return numbers[numbers.size()/2];}
};

学完vector后这个题目就很简单了，直接排序，取中即可。

10.最小的K个数

题目oj

class Solution {
public:vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {vector<int> ret ;sort(input.begin(),input.end());for(int i =0;i<k;i++){ret.push_back(input[i]);}return ret;}
};

知识点：
典型的topk问题，可以使用快排（sort的底层就是快排），堆排序（建立大小堆的问题）。