网络服务有点问题_玖云建站系统_有创意的网络营销案例_广告网站留电话不用验证码

本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。 通过本专栏的深入学习，你可以了解并掌握算法。

💓博主csdn个人主页：小小unicorn
⏩专栏分类：算法从入门到精通
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

题目1:移动0

本题来源为：

移动0

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

题目解析

这个题目要实现的其实就是将0移动到后面，

要注意三点：

1. 0 要移动到数组的末尾
2. 保持非零元素的相对顺序
   这个怎么理解呢？举个例子：
   
   在这个示例中，未移动前非0元素的顺序为1 3 12，那么移动0之后非0元素也要保持一个1 3 12的顺序。
3. 不能开辟一个新的数组，要原地操作。

算法原理

对于移动0本题来说，是一个很典型的题目，本题还可以规划到数组划分（或者数组分块）这一类。
什么是数组划分呢？数组划分就是将一个原数组划分为不同区域。

如下图所示，可以将数组划分为若干个区域，而对于本题而言：
就是将原数组划分为两个区域：非0元素区间与0元素区间。
而解决数组划分这一类题，我们最容易想到也是最简单解决的办法----双指针算法。

那么什么是双指针算法呢？

双指针算法就是定义两个指针，通过模拟两个指针的走向来解决问题，化繁为简。但是并不是说双指针就要必须强行定义两个指针，双指针是一个思想，用数组下标也可以来充当指针，定义两个变量也可以充当指针。

对于本题而言：
两个指针的作用可以这样定义：

1. cur：从左往右扫描数组，达到遍历数组
2. dest:已处理的区间内，非0元素的最后一个位置。

通过双指针我们可以将这个数组分为二大个区间：
处理过的区间与未处理的区间，在处理过的区间内可以又分成两个区间：非0元素区间与0元素区间。
不停向后遍历，知道cur遍历完整个数组为止。

下面我们用具体示例来模拟一下这个过程：

通过动图，我们可以总结双指针式如何做到的：
在cur从前往后遍历数组时：

1. 遇到非0元素：cur++
2. 遇到非0元素：
   先交换dest+1与cur的位置，然后让dest++,cur++;
   注意：dest的起始位置是-1（没进行遍历前还不知道非0元素具体在哪一个位置）。

代码实现

class Solution 
{
public:void moveZeroes(vector<int>& nums) {for(int cur=0,dest=-1;cur<nums.size();cur++){ //处理非0元素if(nums[cur]){dest++;//交换dest+1与cur的位置swap(nums[dest],nums[cur]);}}}
};

题目2:颜色分类

题目描述

题目解析

算法原理

代码实现

class Solution 
{
public:void sortColors(vector<int>& nums) {int n=nums.size();int left=-1,right=n,i=0;while(i<right){if(nums[i]==0)swap(nums[++left],nums[i++]);else if(nums[i]==1)i++;elseswap(nums[--right],nums[i]);}}
};

运行结果：

题目3:The Blocks Problem(***)

题目描述

题目描述

PDF

输入格式

输出格式

样例 #1

样例输入 #1

10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit

样例输出 #1

0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:

题面翻译

题目解析

我们以动图的方式来描述一下这个题目：

算法原理

本质是一个模拟题，我们可以用vector来进行模拟，注意细节问题。

代码实现

#include<iostream>
#include<vector>using namespace std;
const int N=30;
typedef pair<int,int> PII;int n;
vector<int> p[N];//创建n个放木块的槽 PII find(int x)
{for(int i=0;i<n;i++){//第i个槽的大小 for(int j=0;j<p[i].size();j++){if(p[i][j]==x){return {i,j};}}}
}
void clean(int x,int y)
{//把[x,y]以上的木块归位for(int j=y+1;j<p[x].size();j++){int t=p[x][j];p[t].push_back(t);}p[x].resize(y+1); 
} void move(int x1,int y1,int x2)
{//把[x1,y1]及其以上的木块放在x2上面for(int j=y1;j<p[x1].size();j++) {p[x2].push_back(p[x1][j]);}p[x1].resize(y1);
}int main()
{cin>>n;//初始化for(int i=0;i<n;i++){p[i].push_back(i);} string op1,op2;int a,b;while(cin>>op1>>a>>op2>>b){//查找a和b的位置PII pa=find(a);int x1=pa.first,y1=pa.second;PII pb=find(b);int x2=pb.first,y2=pb.second;if(x1==x2)continue;//处理不合法的操作if(op1=="move")//把a上方归位{clean(x1,y1);} if(op2=="onto"){clean(x2,y2); }move(x1,y1,x2);}//打印for(int i=0;i<n;i++){cout<<i<<":";for(int j=0;j<p[i].size();j++){cout<<" "<<p[i][j];}cout<<endl;} 
}