Nadav's 算法之旅

《算法与数据结构：线性搜索算法》

线性搜索算法

当我们谈论搜索算法时，线性搜索算法因其简单性和直接性而占据了一个重要的位置。这种算法在编程和数据处理中非常常见，尤其是在处理未排序的数据集时。本文将详细介绍线性搜索算法的基本原理，并提供 Java 语言的实现示例。

简介

线性搜索，又被称为顺序搜索，是一种在数据结构（如数组或列表）中查找特定元素的方法。这种搜索从数据结构的一端开始，顺序检查每个元素，直到找到所需的元素或搜索完所有元素为止。

《算法与数据结构：二分搜索算法》

简介

二分搜索算法是一种在有序数组中查找特定元素的有效方法。其基本思想是通过将搜索区间分成两半，然后根据目标值与中间元素的比较结果来选择搜索的半区，从而逐步缩小搜索范围，直到找到目标值或确定目标值不存在。

二分搜索的工作原理

二分搜索（又称二分查找）是一种在有序数组中查找特定元素的算法。在 Java 中实现二分搜索，你可以遵循以下步骤：

确定查找范围：设置两个指针，low 和 high，分别表示数组的起始和结束位置 nums [low,high) 左闭右开区间。

计算中间位置：在每次迭代中，计算中间位置 mid = low + (high - low) / 2。

比较和移动指针：

• 如果 arr [mid] 等于目标值，返回 mid。
• 如果 arr [mid] 小于目标值，说明目标值在数组的右半部分，将 low 更新为 mid + 1。
• 如果 arr [mid] 大于目标值，说明目标值在数组的左半部分，将 high 更新为 mid。

重复步骤 2 和 3，直到 low 超过 high，表示找不到目标值，返回 -1。

《算法与数据结构：HeapSort》

简介

堆排序是一种高效的排序算法，它利用了堆的数据结构特性来排序元素。在堆排序中，首先将待排序的序列构造成一个堆，然后将堆顶的最大（或最小）元素与堆尾元素交换，然后调整堆结构，继续选择堆顶的元素，直到序列排序完成。

堆的类型和性质

• 最大堆：父节点的值总是大于或等于子节点的值。在数组中，对于每个元素 i，其子节点位于 2 * i + 1 和 2 * i + 2。
• 最小堆：父节点的值总是小于或等于子节点的值。同样地，子节点的位置与最大堆相同。
• 性质：堆总是一棵完全二叉树。这意味着除了最底层，每层都是完全填满的，而最底层则尽可能地从左到右填满。

堆的实现

堆前置知识

在 Java 中，可以使用数组来实现堆。数组中的每个位置对应堆中的一个节点，父节点和子节点的位置关系可以通过数组索引轻松找到。这种数据结构使得堆操作的时间复杂度保持在对数级别。

《算法与数据结构：字符串搜索算法》

引言

字符串匹配是计算机科学中一个基础而重要的问题，它涉及在一个文本字符串中寻找一个子字符串的过程。这一问题在许多领域都有广泛的应用，包括文本编辑、生物信息学、数据检索等。在众多解决字符串匹配问题的算法中，KMP（Knuth-Morris-Pratt）算法因其高效的匹配过程而著称。不同于传统的朴素匹配方法，KMP 算法利用已匹配的部分信息避免从头开始匹配，大大提高了搜索效率。本文旨在为初学者提供一个关于 KMP 算法的入门指南，介绍其基本概念、工作原理及应用场景。

字符串匹配基础

字符串匹配是指在一个较长的文本字符串中查找一个指定的子字符串的过程。这个问题看似简单，实则是许多计算机应用的核心部分，例如，在一个大型文档中查找特定单词，或者在网页搜索中定位关键词。字符串匹配的效率直接影响到这些应用的性能和用户体验。

《如何写 LeetCode 刷题笔记》

选择题目

1. 多样化度级别

• 初级：从简单的题目开始，帮助初学者建立信心。这些题目通常涉及基本的数据结构和算法。
• 中级：包括中等难度的题目，这些题目通常需要更复杂的算法和数据结构，如动态规划、树、图等。
• 高级：为更有经验的读者提供高难度题目。这些题目可能需要高级算法技巧和深入的问题分析。

《LeetCode:[04] 寻找两个正序数组的中位数》

力扣（LeetCode）官网 - 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O (log (m+n)) 。

《LeetCode:[02] 两数相加》

力扣（LeetCode）官网 - 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

《算法与数据结构：Binary Search Tree BST 二叉搜索树》

简介

二分搜索树（Binary Search Tree，简称 BST）是一种基于二叉树的数据结构，它在数据存储、检索和管理方面具有独特的优势。每个节点都有一个键（和相应的值）及最多两个子节点。它的关键特性是，对于树中的任意节点 X，其左子树中的所有键都小于 X 的键，而右子树的键都大于 X 的键。这一特性使得二分搜索树在执行查找、插入和删除操作时效率较高，是许多高级数据结构和算法的基础。

定义和特性

• 定义：二分搜索树是一个二叉树，其中每个节点都含有一个可比较的键（及与之关联的值），并且对于任何节点，其左子树中的所有键都小于该节点的键，其右子树的所有键都大于该节点的键。
• 特性：
• 有序性：通过中序遍历二分搜索树，可以获得一个有序的键序列。
• 动态数据结构：二分搜索树可以在运行时动态地插入和删除节点，从而适应数据集的变化。
• 效率：在平衡的情况下，二叉搜索树的操作（如查找、插入、删除）可以在 O (log n) 时间内完成，其中 n 是树中的节点数。

节点结构

每个节点通常包含以下几个基本组成部分：

• 键（Key）：节点的唯一标识符，用于节点间的比较。
• 值（Value）：与键相关联的数据。
• 左子节点（Left Child）：指向左侧子节点的指针，该子节点的键小于当前节点。
• 右子节点（Right Child）：指向右侧子节点的指针，该子节点的键大于当前节点。

二叉搜索树是一种特殊的二叉树，它满足以下条件：

1. 节点的左子树只包含小于当前节点的数。
2. 节点的右子树只包含大于当前节点的数。
3. 左右子树也必须是二叉搜索树。
4. 不存在两个节点具有相同的值。