Google2015校园招聘在线笔试题2

下午去打了个酱油，就做出一道最简单的题，2048游戏，实在是太菜了，马上要找工作了，复习的不到位啊！ 解法： k记录要被放置的位置索引 1.k位置元素是0，将e[i]移到e[k] 2.k位置非零： （1）e[i]==e[k]相同，碰撞，e[k]×=2，k移到下一个位置（k或--k） （2

下午去打了个酱油，就做出一道最简单的题，2048游戏，实在是太菜了，马上要找工作了，复习的不到位啊！

解法：

PPT.CN,PPTCN,PPT.CN是什么,PPT.CN官网,PPT.CN如何使用

一键操作，智能生成专业级PPT

下载

k记录要被放置的位置索引
1.k位置元素是0，将e[i]移到e[k]
2.k位置非零：
  （1）e[i]==e[k]相同，碰撞，e[k]×=2，k移到下一个位置（++k或--k）
  （2）e[i]！=e[k]不同,k移到下一个位置（++k或--k），将e[i]移到e[k]

复杂度O(n^2),代码有点乱，没整理，如下：

#include <iostream>
#include <string>
inline void arrayMove(short (*val)[21],int n,std::string&dir){
	if(dir=="up"){
		for(int j=0;j<n;++j){
			int k=0;
			for(int i=1;i<=n-1;++i){
				if(0==val[i][j])
					continue;
				if(0==val[k][j]){
					val[k][j]=val[i][j];
					val[i][j]=0;
				}else if(val[i][j]==val[k][j]){
					val[k][j]=val[i][j]<<1;
					val[i][j]=0;
					++k;
				}else{
					++k;
					if(k!=i){
						val[k][j]=val[i][j];
						val[i][j]=0;
					}
				}
			}
		}
	}else if(dir=="down"){
		for(int j=0;j<n;++j){
			int k=n-1;
			for(int i=n-2;i>=0;--i){
				if(0==val[i][j])
					continue;
				if(0==val[k][j]){
					val[k][j]=val[i][j];
					val[i][j]=0;
				}else if(val[i][j]==val[k][j]){
					val[k][j]=val[i][j]<<1;
					val[i][j]=0;
					--k;
				}else{
					--k;
					if(k!=i){
						val[k][j]=val[i][j];
						val[i][j]=0;
					}
				}
			}
		}
	}else if(dir=="left"){
		for(int i=0;i<=n-1;++i){
			int k=0;
			for(int j=1;j<n;++j){
				if(0==val[i][j])
					continue;
				if(0==val[i][k]){
					val[i][k]=val[i][j];
					val[i][j]=0;
				}else if(val[i][j]==val[i][k]){
					val[i][k]=val[i][j]<<1;
					val[i][j]=0;
					++k;
				}else{
					++k;
					if(k!=j){
						val[i][k]=val[i][j];
						val[i][j]=0;
					}
				}
			}
		}
	}else if(dir=="right"){
		for(int i=0;i<=n-1;++i){
			int k=n-1;
			for(int j=n-2;j>=0;--j){
				if(0==val[i][j])
					continue;
				if(0==val[i][k]){
					val[i][k]=val[i][j];
					val[i][j]=0;
				}else if(val[i][j]==val[i][k]){
					val[i][k]=val[i][j]<<1;
					val[i][j]=0;
					--k;
				}else{
					--k;
					if(k!=j){
						val[i][k]=val[i][j];
						val[i][j]=0;
					}
				}
			}
		}
	}
}
int main(int argc,char**argv){
	int T=0;
	int N=0;
	int i=0;
	short (*val)[21]=new short[21][21];
	std::string dir;
	std::cin>>T;
	while(++i<=T){
		std::cin>>N;
		std::cin>>dir;
		for(int j=0;j<N;++j)
			for(int k=0;k<N;++k)
				std::cin>>val[j][k];
		
		arrayMove(val,N,dir);
		std::cout<<"Case #"<<i<<":"<<std::endl;
		for(int j=0;j<N;++j){
			
			std::cout<<val[j][0];
			for(int k=1;k<N;++k)
				std::cout<<" "<<val[j][k];
			std::cout<<std::endl;
		}
		
	}
}