【Java数据结构与算法】基本概述

经典面试题

字符串匹配

BF(暴力检索)或KMP算法或BM算法

给定两个字符串str1=“adc bcd abcdcdabd”,str2=“abc”；

条件：str1是否包含str2，若包含就返回第一次出现的位置，不包含就返回-1

汉诺塔

分治算法

汉诺塔问题源自印度一个古老的传说，印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱，其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘。梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上，移动过程中必须遵守以下规则：

• 每次只能移动柱子最顶端的一个圆盘；
• 每个柱子上，小圆盘永远要位于大圆盘之上；

八皇后问题

回溯算法

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法；

马踏棋盘

深度优先(DFS)+贪心算法(优化)

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

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

数据结构与算法

数据结构与算法的重要性

1. 程序=数据结构+算法；
2. 算法是程序的灵魂，优秀的程序可以在海量数据计算时，依旧保持高速计算；
3. 程序会使用内存计算框架(如：Spark)和缓存技术(如：Redis)来优化程序，而这些框架的核心功能还是算法；
4. 程序员门槛变高，很多一线IT公司都会有数据结构和算法面试题；

数据结构与算法的关系

• 数据结构是一门研究组织数据方式的学科，有了编程语言也就有了数据结构，学好数据结构可以编写出更有效率的代码；
• 学以致用，学习数据结构的同时也要用程序去解决实际问题；
• 数据结构是算法的基础，想要学好算法，需要把数据结构学到位；

线性结构和非线性结构

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

线性结构

• 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系；
• 线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的；
• 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息；
• 常见的线性结构有：数组、队列、链表和栈；

非线性结构

包括：二位数组，多维数组，广义表，树结构，图结构；