【Java数据结构和算法】001-前言与数据结构和算法介绍

àì夳堔傛蜴生んèń 2023-10-05 12:48 1阅读 0赞

# **目录** #

一、前言

1、一吐为快

2、感谢

二、几个经典的数据结构面试题

1、字符串匹配问题

要求：

2、汉诺塔游戏

要求：

3、八皇后问题

描述：

4、马踏棋盘算法

三、算法的特点

四、数据结构和算法的重要性

--------------------

# 一、前言 #

## 1、一吐为快 ##

我终于来灭你了，数据结构和算法！对于大厂的面试，我一直都感到底气不足，这底气就是数据结构和算法！我本身文科生，专科学的是电子商务，专升本之后本科学了信息管理与信息系统，虽然大学期间有数据结构这门课，但我从来没听过，因为老师教的我从来不学！这也许是我的一个问题，本来我对某一领域挺感兴趣的，但是只要它成为了一门课，老师讲台讲，学生下面学，还有作业和考试，那么我就瞬间对这个领域失去的兴趣，简单地说就是老师教的我从来不学！当然，数据结构本身就晦涩难懂、毫无乐趣可言！我常常听说哪些大厂的笔试和面试，那些高级的问题和高级的回答我一窍不通，我内心充满对面试的恐惧！我没有勇气去大厂面试，计划先从小公司入手，慢慢积累！但现在，我不这么觉得了，我要学数据结构和算法了！我来灭你了！凡是阻挡我的，必将被我灭亡！恐惧、懒惰是我的敌人，让拳头打在敌人的脸上！

## 2、感谢 ##

感谢尚硅谷免费提供的教程，感谢韩顺平老师，感谢B站！

视频地址：[https://www.bilibili.com/video/BV1E4411H73v][https_www.bilibili.com_video_BV1E4411H73v]

# 二、几个经典的数据结构面试题 #

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

### 要求： ###

> 1、有一个字符串 str1= ""硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好""，和一个子串 str2="尚硅谷你尚硅你"；  
> 2、现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1；  
> 3、要求用最快的速度来完成匹配；  
> 你的思路是什么？

傻瓜方式：暴力匹配；

正解：KMP算法；

## 2、汉诺塔游戏 ##

### 要求： ###

> 1、将A塔的所有圆盘移动到C塔；
> 
> 2、并且规定小圆盘上不能放大圆盘；
> 
> 3、在三根柱子之间一次只能移动一个圆盘；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70][]

使用到分治算法；

## 3、八皇后问题 ##

### 描述： ###

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

使用到回溯算法；

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

## 4、马踏棋盘算法 ##

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

![20201029162253771.png][]

# 三、算法的特点 #

算法很重要、算法很有趣、学习算法有一定难度；

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

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

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

3、拿实际工作经历来说, 在Unix下开发服务器程序，功能是要支持上千万人同时在线， 在上线前，做内测，一切OK，可上线后，服务器就支撑不住了，公司的CTO对代码进行优化，再次上线，坚如磐石。你就能感受到程序是有灵魂的，就是算法。 目前程序员面试的门槛越来越高，很多一线IT公司(大厂)，都会有数据结构和算法面试题(负责的告诉你，肯定有的)；

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

[https_www.bilibili.com_video_BV1E4411H73v]: https://www.bilibili.com/video/BV1E4411H73v
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201029161328958.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[20201029162253771.png]: https://img-blog.csdnimg.cn/20201029162253771.png