数据结构和算法内容介绍

港控/mmm° 2021-07-25 01:32 327阅读 0赞

# 一 几个经典的算法面试题 #

## 1 字符串匹配问题 ##

a 有一个字符串 str1= "how are you,hello how do you do "，和一个子串 str2="how do"

b 现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1

c 要求用最快的速度来完成匹配

常用解法

a 暴力匹配——简单，但是效率低

b KMP 算法——使用"部分匹配表"

## 2 汉诺塔游戏, ##

请完成汉诺塔游戏的代码，要求：

a 将 A 塔的所有圆盘移动到 C 塔

b 小圆盘上不能放大圆盘

c 在三根柱子之间一次只能移动一个圆盘

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

## 3 八皇后问题 ##

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。

这里要使用回溯算法。一共有92种摆法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1][]

网上八皇后小游戏：[http://www.7k7k.com/swf/49842.htm][http_www.7k7k.com_swf_49842.htm]

# 4 马踏棋盘算法介绍和游戏演示 #

a 马踏棋盘算法也被称为骑士周游问题

b 将马随机放在国际象棋的 8×8 棋盘 Board\[0～7\]\[0～7\]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部 64 个方格。

c 游戏演示: [http://www.4399.com/flash/146267\_2.htm][http_www.4399.com_flash_146267_2.htm]

d 会使用到 图的深度优化遍历算法(DFS) + 贪心算法优化

![20210228105540955.png][]

# 二 数据结构和算法的重要性 #

1 算法是程序的灵魂，优秀的程序可以在海量数据计算时，依然保持高速计算。

2 一般来讲，程序会使用了内存计算框架(比如 Spark)和缓存技术(比如 Redis 等)来优化程序,再深入的思考一下，这些计算框架和缓存技术， 它的核心功能是哪个部分呢？

3 拿实际工作经历来说, 在 Unix 下开发服务器程序，功能是要支持上千万人同时在线，在上线前，做内测，一切OK,可上线后，服务器就支撑不住了, 公司的 CTO 对代码进行优化，再次上线，坚如磐石。你就能感受到程序是有灵魂的，就是算法。

4 目前程序员面试的门槛越来越高， 很多一线 IT 公司(大厂)，都会有 数据结构和算法面试题(负责的告诉你，肯定有的)。

5 如果你不想永远都是代码工人,那就花时间来研究下数据结构和算法。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/9ca3dcac15794963bfad2e637d4add3e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1]: /images/20210724/b95f8d8767434c7487ccf3824697c2d2.png
[http_www.7k7k.com_swf_49842.htm]: http://www.7k7k.com/swf/49842.htm
[http_www.4399.com_flash_146267_2.htm]: http://www.4399.com/flash/146267_2.htm
[20210228105540955.png]: /images/20210724/eb0feeb73092486789fe425eebcb06d9.png