文档章节

2016腾讯实习生在线笔试的两道编程题

JoshuaShaw
 JoshuaShaw
发布于 2016/04/05 14:58
字数 1064
阅读 620
收藏 7

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

我的github page:http://joshshaw.github.io/

0x00第一题(回形矩阵)

0x01描述

输入矩阵的边长,如5,然后生成如下的回形矩阵,最后一行行地输出。

 1  2  3  4  5
16 17 18 19  6
15 24 25 20  7
14 23 22 21  8
13 12 11 10  9

0x02思路

定义上下左右四个方向,递增地往当前方向走,判断越界或者是否已经被占用,是则向右走, 再一次判断是否可以走,可以则走,不可以说明已经全部走完,程序结束。 于是在代码中最主要的方法为boolean hasNext(),同时对越界的判断要仔细。

<!-- more -->

0x03代码

import java.util.Scanner;
import static java.lang.System.in;
import static java.lang.System.out;

public class Main {

	enum Direction {
		UP, DOWN, LEFT, RIGHT
	}
	private Direction direction = Direction.RIGHT;

	private int o[][] = null;
	private int n;
	private int i=0, j=-1;

	public Main(int n) {
		this.n = n;
		o = new int [n][n];

	}

	private boolean hasNext() {
		switch(direction){
		case RIGHT:
			++j;
			if(j>=n || o[i][j]!=0){
				direction = Direction.DOWN;
				--j; ++i;
			}
			break;
		case DOWN:
			++i;
			if(i>=n || o[i][j]!=0){
				direction = Direction.LEFT;
				--i; --j;
			}
			break;
		case LEFT:
			--j;
			if(j<0 || o[i][j]!=0){
				direction = Direction.UP;
				++j; --i;
			}
			break;
		case UP:
			--i;
			if(i<0 || o[i][j]!=0){
				direction = Direction.RIGHT;
				++i; ++j;
			}
			break;
		}
		if(o[i][j]!=0)return false;
		else return true;
	}

	private void next(int put) {o[i][j]=put;}

	public void init() {
		int t = 1;
		while(hasNext())
			next(t++);
	}

	public void print() {
		for(int x=0; x<n; ++x)
			for(int y=0; y<n; ++y)
				out.print(""+o[x][y]+" ");
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(in);
		int input = scanner.nextInt();
		Main m = new Main(input);
		m.init();
		m.print();
	}
}

0x10第二题(求最长回文串长度)

0x11描述

找出一个字符串中的最大回文子串的长度。子串不需要连续。

input: xafedgkdfe

output: 5

reason: fd(g/k)df

0x12思路

设该字符串为str, 长度为len, 最大回文子串的长度为maxLen[i][j],i为该字符串的最左下标,j为最右下标。 那么maxLen[0][len-1]为最终解。 并且有状态转移方程:

               | 1                                       str[i]==str[j], i==j
maxLen[i][j] = | 2 + maxLen[i+1][j-1]                    str[i]==str[j], i>j且i+1>j-1
               | 2                                       str[i]==str[j], i+1<j-1
               | max( maxLen[i+1][j], maxLen[i][j-1] )   str[i]!=str[j]

上述的状态转移方程说明:

  1. 每个字符本身就是一个回文串,那么长度为1
  2. 当前后两个字符相等时,其最大长度就是2加上除去这两个字符所包含的子串的最大回文长度
  3. 在情况2的基础上,如果这两个字符是相邻的,那么最大长度就是2
  4. 当前后两个字符不相等,那么其最大长度由舍去前面字符的最大长度和舍去最后字符的最大长度中的最大值决定。 拥有状态转移方程,当然可以用动态规划来做,就是代码编写的难度比较大,其外使用递归的方法实现是简单易懂,缺点是 嵌套递归过多,重复子过多。

0x13代码

0x14递归实现

import java.util.Scanner;

public class M {

	static int MaxLength(char str[], int i, int j)   
	{   
	    if (i == j)    
	        return 1;     
	    else if (i > j)   
	        return 0;     
	    else {   
	        if (str[i] == str[j]) {   
	            return 2 + MaxLength(str, i + 1, j - 1);   
	        } else {   
	            return Math.max(MaxLength(str, i + 1, j), MaxLength(str, i, j - 1));   
	        }   
	    }   
	}   
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
	    char str[];

	    str = s.nextLine().toCharArray();   
	    System.out.println( MaxLength(str, 0, str.length-1) );

	}  
}

0x15动态规划

import java.util.Scanner;

public class M2 {
	private char str[];
	private int slen;
	private int maxlen[][];   

	public M2(String string) {
		slen = string.length();
		str = string.toCharArray();
		maxlen = new int [slen][slen];
	}

	int LongestLen() {   
	    int i, j, len;   
	    for (i = 0; i < slen; i++)     
	        maxlen[i][i] = 1;     
	    for (len = 1; len < slen; len++) {   
	        for (i = 0; i < slen - len; i++) {   
	            j = i + len;   
	            if (str[i] == str[j]) {   
	                if (i + 1 > j - 1)      
	                    maxlen[i][j] = 2;     
	                else  
	                    maxlen[i][j] = 2 + maxlen[i + 1][j - 1];   
	            } else {   
	                maxlen[i][j] = Math.max(maxlen[i + 1][j], maxlen[i][j - 1]);   
	            }  
	            //print();

	        }   
	    }   
	    return maxlen[0][slen - 1];   
	}   
	public void print() {
		for(int i=0;i<slen;++i) {
			for(int j=0;j<slen;++j){
				System.out.print(""+maxlen[i][j]+" ");
			}System.out.println();
		}
		System.out.println();
	}
	public static void main(String arg[]) {   
	    Scanner s = new Scanner(System.in);
	    String string = s.nextLine();
	    int l = new M2(string).LongestLen();
	    System.out.println(l);
	}  
}

0xFF总结

其实问题不难,就是在线笔试不能用IDE,效率骤降,调试也较难。

References & Thx:http://blog.csdn.net/eclipse88/article/details/6473804(里面的代码有点问题,不过整体思路是一样的,十分感谢)

© 著作权归作者所有

JoshuaShaw
粉丝 5
博文 27
码字总数 15604
作品 0
湛江
程序员
私信 提问
90 道名企笔试和算法题 (含答题讨论)

(点击上方公众号,可快速关注) 节选自「算法爱好者」微信公号的精选算法题和名企笔试题。 问:如何获取题目列表? 答:① 长摁二维码关注「算法爱好者」,② 然后给它发送 名企笔试 或 算法...

Python开发者
2018/01/21
0
0
[转载]9个offer,12家公司,35场面试,从微软到谷歌,应届计算机毕业生的2012求职之路

1,简介 毕业答辩搞定,总算可以闲一段时间,把这段求职经历写出来,也作为之前三个半月的求职的回顾。 首先说说我拿到的offer情况: 微软,3面->终面,搞定 百度,3面->终面,口头offer 搜狗...

蟋蟀哥哥
2013/01/10
9K
51
(已拿offer)腾讯实习生笔试到面试总结(附带华为阿里面试经历)

导读:快到暑假了,有不少读者还是学生,想找一份实习,好的公司,只能说是好的起点,不能代表全部。公司强大,不代表个人一定强大,小公司同样也有大牛,不羡慕,不虚浮,脚踏实地,今天,分...

我最喜欢三大框架
06/12
11
0
机器学习实习生面试总结(阿里 腾讯等)

今年来一直在找暑期实习,现在基本已经确定了,前后历经差不多2个月吧,发现了很多自己的缺点,同时也希望写出来供需要的人参考了解 先说下我自己的情况吧,决定去腾讯TEG的机器学习岗实习了...

Gavin__Zhou
2017/05/01
0
0
2018腾讯制片助理&阿里视频运营经验分享

先介绍下本人的背景: 985硕士,传媒类专业;有视频网站、影视公司的2项实习经历。 春招参加了腾讯的制片助理岗面试,顺利拿到offer。 阿里参加了视频运营的笔试,因为先拿到腾讯offer,个人...

牛客网
2018/05/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

006-ELK的二进制安装

二进制安装ELKstack 本次搭建属于单点,在同一台机器上进行安装 基础组件部署 curl -o /etc/yum.repos.d/CentOS-Base.repo http://mirrors.aliyun.com/repo/Centos-7.repo wget -O /etc/yu...

伟大源于勇敢的开始
8分钟前
1
0
OSChina 周四乱弹 —— 浙江台的电话号码倒是记得挺牢

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @巴拉迪维 :《Out On The Streets》 一直不理解北欧人对重金属和死亡摇滚的热情,听完这首歌好像理解了。#今日歌曲推荐# 《Out On The Stre...

小小编辑
今天
6
0
Leetcode PHP题解--D121 21. Merge Two Sorted Lists

D121 21. Merge Two Sorted Lists 题目链接 21. Merge Two Sorted Lists 题目分析 合并两个有序链表。 思路 逐个遍历两个链表,把小的数字塞入数组里。之后再拼起来。 最终代码 <?php/** *...

skys215
今天
5
0
mars-config 动态配置管理

mars-config 码云地址:https://gitee.com/fashionbrot/mars-config 介绍 spring mvc 、springboot 动态配置系统。http 轮训方式 更新 动态配置 软件架构 软件架构说明 后端使用技术 :sprin...

fashionbrot
今天
14
0
女朋友玩吃鸡手游被开挂老哥骗炮,我见义勇为将骗子绳之以法

大家好,我是乔哥。 晚上10点以后下班后我回到自如出租房里面,开始处理公众号粉丝发来的消息,一条一条处理,突然看到了这么几条消息,吸引了我的眼球: 然后我就和这位女粉丝小红(化名)聊...

gzc426
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部