剑指Offer——当当+搜狐+好未来笔试题+知识点总结
情景回想
- 时间:2016.9.21 15:00-21:00
- 地点:山东省网络环境智能计算技术重点实验室
事件:当当笔试、搜狐笔试、好未来笔试
3场笔试中好未来相对简单点。
好未来编程题
马踏棋盘(贪心算法)
马踏棋盘是经典的程序设计问题之中的一个,基本的解决方式有两种:一种是基于深度优先搜索的方法,还有一种是基于贪婪算法的方法。第一种基于深度优先搜索(DFS)的方法是比較经常使用的算法,深度优先搜索算法也是数据结构中的经典算法之中的一个。主要是採用递归的思想。一级一级的寻找,最后找到合适的解。而基于贪婪的算法则是根据贪婪算法的思想设置一种标准。然后根据标准进行选择,从而得到解。可是他不一定可以得到最优解。
关于马踏棋盘的基本过程:国际象棋的棋盘为8*8的方格棋盘。
现将”马”放在随意指定的方格中,依照”马”走棋的规则将”马”进行移动。要求每一个方格仅仅能进入一次。终于使得”马”走遍棋盘的64个方格。
深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止。并且每一个节点仅仅能訪问一次.(来自百度)基于深度优先搜索的算法就是根据当前点找到下一个可能的点,然后对这个点进行深度优先搜索,然后依次递归,当出现条件不满足时,退回来,採用其它的路径进行搜索。最后肯定可以得到相应的结果。
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说。不从总体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对全部问题都能得到总体最优解,但对范围相当广泛的很多问题他能产生总体最优解或者是总体最优解的近似解。(来自百度)
本题与经典的马踏棋盘问题的差别就是点可以反复走。
给定两点,推断是否走得通,并记录某次走通的路径。
package cn.edu.ujn.practice;
/**
* 贪心算法解决马踏棋盘问题
* 棋盘有64个位置,“日”字走法,刚好走满整个棋盘
* @author SHQ
* @date 2016-09-22
*/
public class HorseStep {
static final int[] dx = { -1, -2, -2, -1, 1, 2, 2, 1 }; // x方向的增量
static final int[] dy = { 2, 1, -1, -2, -2, -1, 1, 2 }; // y方向的增量
static final int N = 8;
static int[][] board = new int[N][N]; // 棋盘
// 计算结点出口
int waysOut(int x, int y) {
int tx, ty;
int count = 0;
// 结点位置非法或已踏过,返回-1
if (x < 0 || y < 0 || x >= N || y >= N || board[x][y] > 0) {
【推广】
免费学中医,健康全家人
原文地址:https://www.cnblogs.com/zsychanpin/p/7373783.html
- 推荐文章
- linux ifconfig 内容详解
- Delegate 多种写法总结
- Invoke和BeginInvoke 在Winform 中更新控件的用法说明
- Thread.Sleep(0)的妙用
- UI 假死的可能性和处理方法总结
- Linux 系统网络设置问题汇总
- 如何在linux下判断磁盘是否为raid
- 函数中{}输出格式详解(C#)
- C# 线程 01 ThreadStart 与 ParameterizedThreadStart
- MapKit教程:如何在Swift中将地图添加到iOS应用程序
- SnapKit教程:简化iOS App开发中的自动布局
- Swift中的Facade设计模式与代码示例
- 如何在Swift中创建漂亮的iOS图表
- 了解Swift中最流行的iOS设计模式
- 使用Koloda View在Swift中构建类似Tinder(国内的探探社交应用)的卡片
- 如何使用Swift中的Keychain保护用户数据
- 十大开源Swift库开始你的下一个iOS项目
- 完整的App Store提交清单
- JS中的类型和引用问题以及内存分配
- loadrunner取值方式
- 单选框和复选框(radiobox、checkbox)
- 三种alertconfirmprompt弹窗的处理方法
- iframe的切换
- python的class(类)中的object是什么意思?
- loadrunner12自带的机票预订服务,解决httpd: Could not reliably determine the server's fully qualified domain name 问题
- 使用错误的用户名和密码也能运行通过
- win10删除IE某些文件导致不可用恢复的方法
- win10系统删除需要Trustedlnstaller权限的文件
- loadrunner各版本对应的ie浏览器版本
- vue之vue-router加深印象