![[学习笔记-C++篇]day11 lintcode50](http://www.mshxw.com/aiimages/31/768745.png "[学习笔记-C++篇]day11 lintcode50")
50+100+针对训练。
感谢大佬几款优秀的支持C、C++在线编译器
此外，教程网站：九章算法课-免费试听可以闲的时候过渡一下，换换思路听着。
另，十大排序算法需要整理一下，参考：1.0 十大经典排序算法
再另，string也要整理，参考：c++中的string常用函数用法总结
stage2——7天进阶阶段
在线编译器：compile c++ gcc online
刷题网站：阶段1第一关：基本数据类型
day1 planA
lintcode 3-4
教程完成度40%
Q&A
1.旋转数组2.回文数23.杨辉三角4.翻转数组5.移动零6.数组第二大数7.分解质因数8.加一9.冰雹猜想10.翻转字符串11.判断数列中整除3的数字个数（其他题）
1.旋转数组class Solution {
public:
vector rotate(vector &nums, int k) {
// Write your code here
#if 0
vector r;
vector t(nums);//复制nums
//可以循环
k=k%nums.size();
if(k=0||nums.size()==1) return nums;
else
{
while(k>0)
{
r.clear();
r.push_back(t[nums.size()-1]);
for(int i=0;i t;
int tmp[nums.size()];
for (int i = 0; i < nums.size(); ++i) {
tmp[(i+k)%nums.size()]=nums[i];
}
for(int j=0;j
前两个是相似思路，但是第1个在运行到94%的地方会卡住，难道是内存出错吗，等待大神解惑。
第2个简化了循环步骤，但是如果直接用向量无法对应调整元素位置，所以用数组过渡一下。
第三个更灵活，需要掌握。
2.回文数2
将数字表示为二进制判断回文
但是看用例是不考虑前面的0位的，所以最好用除法求余。
class Solution {
public:
bool isPalindrome(int n) {
// Write your code here
vector tmp;
while(n>1)
{
tmp.push_back(n%2);
n=n/2;
}
tmp.push_back(1);
//现在需要判断tmp是否回文
//判断tmp翻转是否与原来一样
vector tt(tmp);
reverse(tt.begin(),tt.end());
if(tt==tmp) return true;
else return false;
}
};
3.杨辉三角
最大障碍竟是读不懂题…
之前整理过一般三角形怎么绘制，见day10。
class Solution {
public:
vector> calcYangHuisTriangle(int n) {
// write your code here
vector> p(n);
for(int i=0;i
4.翻转数组
快速解决问题。
class Solution {
public:
void reverseArray(vector &nums) {
// write your code here
reverse(nums.begin(),nums.end());
}
};
5.移动零
不能自动排序然后移动，那么只能冒泡排序了。
class Solution {
public:
void moveZeroes(vector &nums) {
// write your code here
int tmp;
for(int i=0;i
但这是一个暴力解，消耗很大。下面参考解题思路。
先确定0的个数，然后找出0，删除这里的元素，在向量最后插入0。
还是需要熟悉vector的函数。
class Solution {
public:
void moveZeroes(vector &nums) {
// write your code here
int num = count(nums.begin(), nums.end(), 0);
for(int i=0;i::iterator it = find(nums.begin(), nums.end(), 0);
nums.erase(it);
nums.push_back(0);
}
}
};
这个办法稍微改善了一点消耗，但还是有点长。
参考解题思路
class Solution {
public:
void moveZeroes(vector &nums) {
vectorv(nums.size(),0);
for(int i = 0,j = 0;i
该方法目前消耗最小。一般来说不要循环会小一点。
6.数组第二大数
升序排序取倒二。
class Solution {
public:
int secondMax(vector &nums) {
// write your code here
sort(nums.begin(),nums.end());
return nums[nums.size()-2];
}
};
7.分解质因数
暴力解理论上没问题，但会超时。
class Solution {
public:
vector primeFactorization(int num) {
// write your code here
#if 0
int tmp=num;
int x=tmp-1;
vector z;
int m=1;
while(x>1)
{
if(tmp%x==0)
{
z.push_back(tmp/x);
m*=(tmp/x);
tmp=x;
}
x--;
}
z.push_back(num/m);
sort(z.begin(),z.end());
return z;
#endif
vector z;
int tmp=num;
for(int i=2;i*i<=num;i++)
{
while(tmp%i==0)
{
z.push_back(i);
tmp/=i;
}
}
if(tmp!=1) z.push_back(tmp);
return z;
}
};
第2种方法，就大大削减了次数，从2开始递增除数，其实只要被除数小于等于除数的平方就可以了，最后要记得判断一下商是不是1，不是的话也要保存下来。
8.加一
刚开始想差了，其实不是每一位加1，而是最后一位加1。不过为了逻辑好算，先翻转会好一点，先独立判断首位加1结果，然后循环判断每一位累加结果。
class Solution {
public:
vector plusOne(vector &digits) {
// write your code here
vector t(digits);
reverse(t.begin(),t.end());
int add=0;//进位量
if(t[0]==9)
{
t[0]=0;
add=1;
}
else
{
t[0]++;
reverse(t.begin(),t.end());
return t;
}
for(int i=1;i
实不相瞒，被判断条件绕晕了。
9.冰雹猜想
题目就是思路。
class Solution {
public:
int getAnswer(int num) {
// write your code here.
int t=0;
while(num!=1)
{
if(num%2==0) num/=2;
else num=num*3+1;
t++;
}
return t;
}
};
10.翻转字符串
太不熟悉string了！
参考解题思路
//author: batgod
class Solution {
public:
string reverseWords(string &s) {
string res = "";
s += " ";
int start = 0;
bool flag = false;
for(int i=0; i
11.判断数列中整除3的数字个数（其他题）
整理一个牛客题。
数列1，12，123，1234，…，12345678910，…
给定范围l和r，判断第l到第r个数组中整除3的数字个数。
起初想的太简单了，只判断数字是否3的倍数，没有构造数列，所以超出9就会报错。
#include
using namespace std;
int main()
{
while(cin >> l >> r)
{
int p;
p=0;
int count;
count=0;
for(int j=1;j
但更为正确的做法是构建数列，每次把上一次的数字乘以10或10的n次方，然后判断能否整除3。
#include
using namespace std;
int find_bit_num(int num)
{
int n = 10;
while(num / 10)//每次递增一个数量级，就要乘以相应数量级，这样才能正确累加
{
n *= 10;
}
return n;
}
int main(void)
{
int l, r;
//cin>>l>>r;
l=10;
r=15;
int num = 0, res = 0;
for(int i = 1; i <= r; i++)
{
cout << find_bit_num(i)<= l)
if(num % 3 == 0)
res++;
}
cout<
