数据结构与算法内容介绍

经典算法面试题

字符串匹配的问题:

  1. 有一个字符串str1= “硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好”, 和一个子串 str2=”尚硅谷你尚硅你”
  2. 现在要判断str1 是否含有str2 ,如果存在, 就返回第一次出现的位置,如果没有,则返回-1
  3. 要求用最快的速度来完成 匹配
  4. 你的思路是什么?
  • 暴力匹配[简单,但是效率低]
  • KMP算法 <部分匹配表>

    汉诺塔游戏:

    请完成汉诺塔游戏的代码,要求:
  1. 将A塔的所有圆盘移动到C塔
  2. 并且规定小圆盘上不能放大圆盘
  3. 在三根柱子之间一次只能移动一个圆盘

image.png

八皇后问题:

八皇后问题, 是一个古老而著名的问题,是回溯算法的经典案例,该问题是国际西洋棋棋手马克思.贝瑟尔于1848年提出: 在8X8的国际象棋上摆放8个皇后, 使其不能互相攻击, 即任意两个皇后都不能处于同一行, 同一列或同一条斜线上, 问有多少种摆法
[92种] => 分治算法
image.png

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

  1. 马踏棋盘算法也被称之为骑士周游问题
  2. 将马随机放在国际象棋的8X8棋盘Board[0~7][0~7]的某个方格中, 马按走棋规则(马走日字)进行移动, 要求每个方格只进入一次, 走遍棋盘上全部的64个方格
  3. 游戏演示: http://www.4399.com/flash/146267_2.htm
  4. 会使用到图的深度优化遍历算法(DFS) + 贪心算法优化

image.png

数据结构与算法的重要性

  1. 算法是程序的灵魂, 优秀的程序可以在海量数据计算时, 依旧保持高速计算
  2. 一般来说 程序会使用了内存计算框架(比如Spark)和缓存技术(比如Redis)来优化程序, 再深入的思考一下,这种计算框架和缓存技术, 它的核心功能是哪个部分呢?
  3. 拿实际工作经历来说, 在Unix下开发服务器程序, 功能是要支持上千万人同时在线, 在上线前, 做内测, 一切OK, 可上线后, 服务器就撑不住了, 公司的CTO对代码进行优化, 再次上线, 坚如磐石, 你就能感受到程序是有灵魂的, 那就是算法
  4. 目前程序员面试的门槛越来越高, 很多一线IT公司(大厂), 都会有数据结构和算法面试题(负责的告诉你, 肯定是有的)

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

    学习步骤

    应用场景 -> 数据结构或算法->剖析原理->分析实践步骤(图解)->代码实现
    比如[: 八皇后问题和动态规划算法]

    数据结构和算法概述

    数据结构和算法的关系

  6. 数据data结构(structure)是一门研究组织数据方式的学科, 有了编程语言也就有了数据结构, 学好数据结构可以编写出更加漂亮,更加有效率的代码

  7. 要学习好数据结构就要多多考虑如何将生活中遇到的问题,用程序去实现解决
  8. 程序 = 数据结构 + 算法

  9. 数据结构是算法的基础,换言之,要想学好算法, 需要把数据结构学到位

    几个实际编程中遇到的问题

    字符串替换问题

    image.png
    小结: 需要使用到单链表数据结构

    一个五子棋程序

    image.png
    如何判断游戏的输赢, 并可以完成存盘退出和继续上局的功能

  10. 棋盘 二维数组=>(稀疏数组)->写入文件 [存档功能]

  11. 读取文件->稀疏数组->二位数组->棋盘 [继续上局]

    约瑟夫(Josephu)问题(丢手帕问题)

  12. Josephu 问题为: 设编号为1, 2, ….. N的N个人围坐一圈, 约定编号为k(1<=k <=n) 的人从1开始报数. 数到m的那个人出列, 它的下一位又从1开始报数, 数到m的那个人又出列, 依次类推, 直到所有人出列为止, 由此产生一个出队编号的序列

  13. 提示: 用一个不带头节点的循环链表来处理Josephu问题, 先构成一个有n个节点的单循环链表(单向循环链表),然后由k节点起从1开始计数, 计到m时, 对应节点从链表中移除,然后从被删除节点的下一个节点又从1开始计数, 直到最后一个节点从链表中移除算法结束

  14. 小结: 完成约瑟夫问题, 需要使用到单向环形链表 这个数据结构

    其他常见算法问题

    image.png

  15. 修路问题 => 最小生成树(加权值)[数据结构] + 普利姆算法

  16. 最短路径问题 => 图 + 弗洛伊德算法
  17. 汉诺塔 => 分支算法

  18. 八皇后问题 => 回溯算法

    线性结构和非线性结构

    数据结构包括: 线性结构和非线性结构

    线性结构

  19. 线性结构作为最常用的数据结构, 其特点是数据元素之间存在一对一的线性关系

  20. 线性结构有两种不同的存储结构, 即顺序存储结构(数组)和链式存储结构(链表), 顺序存储的线性表称为顺序表, 顺序表中存在的存储元素是连续的
  21. 链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息
  22. 线性结构常见的有: 数组, 队列, 链表, 栈, 后续会详细讲解

    非线性结构

    非线性结构包括: 二位数组, 多维数组, 广义表, 树结构, 图结构