数据结构与算法学习：其实并不复杂

发表时间: 2023-02-27 15:01

曾有人说，数据结构这个东西，如果你不去学，可能一辈子都感受不到它的好。但一旦掌握，就会被它的强大威力所折服。

它是底层开发的重要一环，保证底层系统的稳定性和高效性；......

总的来说，从功利角度，它是大厂必考，你不可避免，从长远角度，它将决定你的技术上限。

一旦拿下了数据结构与算法，就如同站在巨人的肩膀上，在开发江湖占有一席之地。所以说难也得好好学

一. 初识算法

1.1 什么是算法？

定义

在数学和计算机科学领域，算法是一系列有限的严谨指令，通常用于解决一类特定问题或执行计算

In mathematics and computer science, an algorithm (/ˈælɡərɪðəm/) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation.

Introduction to Algorithm

不正式的说，算法就是任何定义优良的计算过程：接收一些值作为输入，在有限的时间内，产生一些值作为输出。

Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output in a finite amount of time.

1.2 什么是数据结构？

定义

在计算机科学领域，数据结构是一种数据组织、管理和存储格式，通常被选择用来高效访问数据

In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data

Introduction to Algorithm

数据结构是一种存储和组织数据的方式，旨在便于访问和修改

A data structure is a way to store and organize data in order to facilitate access and modifications

接下来我们通过对一个非常著名的二分查找算法的讲解来认识一下算法

1.3 二分查找

二分查找算法也称折半查找，是一种非常高效的工作于有序数组的查找算法。不妨用它作为入门。

二分查找基础版

需求：在有序数组 AA 内，查找值 targettarget

如果找到返回索引
如果找不到返回 −1

算法描述
前提	给定一个内含 nn 个元素的有序数组 AA，满足 A_{0}\leq A_数据结构与算法\leq A_最大路径\leq \cdots \leq A_{n-1}A0≤A1≤A2≤⋯≤An−1，一个待查值 targettarget
1	设置 i=0i=0，j=n-1j=n−1
2	如果 i \gt ji>j，结束查找，没找到
3	设置 m = floor(\frac {i+j}最大路径)m=floor(2i+j) ，mm 为中间索引，floorfloor 是向下取整（\leq \frac {i+j}最大路径≤2i+j 的最小整数）
4	如果 target < A_{m}target<Am 设置 j = m - 1j=m−1，跳到第2步
5	如果 A_{m} < targetAm<target 设置 i = m + 1i=m+1，跳到第2步
6	如果 A_{m} = targetAm=target，结束查找，找到了

java 实现

i,j 对应着搜索区间 [0,a.length-1][0,a.length−1]（注意是闭合的区间），i<=j 意味着搜索区间内还有未比较的元素，i,j 指向的元素也可能是比较的目标

思考：如果不加 i==j 行不行？
回答：不行，因为这意味着 i,j 指向的元素会漏过比较

m 对应着中间位置，中间位置左边和右边的元素可能不相等（差一个），不会影响结果
如果某次未找到，那么缩小后的区间内不包含 m

上面应该看懂了吧，入门数据结构与算法下面这个课程比较丰富，最近新扒拉来的。刚刷了20来小节，极易吸收，一起卷吧，涉及数据结构与算法的各个方面，包括数组、链表、递归、队列、栈、堆、二叉树、查找算法、排序算法、回溯、贪心、分治、动态规划等等。

黑马程序员2023新版Java数据结构与算法视频教程

除了学习刷题也是很重要的，力扣经典算法题

1. Two Sum (两数之和), Easy, 11757 likes
2. Add Two Numbers (两数相加), Medium, 6524 likes
3. Longest Substring Without Repeating Characters (无重复字符的最长子串), Medium, 5845 likes
4. Median of Two Sorted Arrays (寻找两个正序数组的中位数), Hard, 4303 likes
5. Longest Palindromic Substring (最长回文子串), Medium, 3896 likes
15. 3Sum (三数之和), Medium, 3582 likes
53. Maximum Subarray (最大子序和), Easy, 3533 likes
7. Reverse Integer (整数反转), Easy, 2970 likes
11. Container With Most Water (盛最多水的容器), Medium, 2659 likes
42. Trapping Rain Water (接雨水), Hard, 2552 likes
20. Valid Parentheses (有效的括号), Easy, 2544 likes ✔️
10. Regular Expression Matching (正则表达式匹配), Hard, 2273 likes
26. Remove Duplicates from Sorted Array (删除有序数组中的重复项), Easy, 2146 likes ✔️
136. Single Number (只出现一次的数字), Easy, 1958 likes
22. Generate Parentheses (括号生成), Medium, 1946 likes
206. Reverse Linked List (反转链表), Easy, 1886 likes ✔️
21. Merge Two Sorted Lists (合并两个有序链表), Easy, 1832 likes ✔️
70. Climbing Stairs (爬楼梯), Easy, 1791 likes ✔️
300. Longest Increasing Subsequence (最长递增子序列), Medium, 1773 likes
121. Best Time to Buy and Sell Stock (买卖股票的最佳时机), Easy, 1766 likes
72. Edit Distance (编辑距离), Hard, 1743 likes
14. Longest Common Prefix (最长公共前缀), Easy, 1707 likes
198. House Robber (打家劫舍), Medium, 1585 likes
9. Palindrome Number (回文数), Easy, 1568 likes
146. LRU Cache (LRU 缓存机制), Medium, 1544 likes
19. Remove Nth Node From End of List (删除链表的倒数第 N 个结点), Medium, 1494 likes ✔️
33. Search in Rotated Sorted Array (搜索旋转排序数组), Medium, 1493 likes
46. Permutations (全排列), Medium, 1484 likes
101. Symmetric Tree (对称二叉树), Easy, 1483 likes
84. Largest Rectangle in Histogram (柱状图中最大的矩形), Hard, 1472 likes
39. Combination Sum (组合总和), Medium, 1466 likes
13. Roman to Integer (罗马数字转整数), Easy, 1436 likes
23. Merge k Sorted Lists (合并K个升序链表), Hard, 1436 likes ✔️
17. Letter Combinations of a Phone Number (电话号码的字母组合), Medium, 1436 likes
322. Coin Change (零钱兑换), Medium, 1414 likes
32. Longest Valid Parentheses (最长有效括号), Hard, 1400 likes
287. Find the Duplicate Number (寻找重复数), Medium, 1325 likes
122. Best Time to Buy and Sell Stock II (买卖股票的最佳时机 II), Easy, 1306 likes
160. Intersection of Two Linked Lists (相交链表), Easy, 1302 likes ✔️
55. Jump Game (跳跃游戏), Medium, 1292 likes
76. Minimum Window Substring (最小覆盖子串), Hard, 1280 likes
200. Number of Islands (岛屿数量), Medium, 1270 likes
78. Subsets (子集), Medium, 1269 likes
31. Next Permutation (下一个排列), Medium, 1260 likes
96. Unique Binary Search Trees (不同的二叉搜索树), Medium, 1257 likes
148. Sort List (排序链表), Medium, 1248 likes
236. Lowest Common Ancestor of a Binary Tree (二叉树的最近公共祖先), Medium, 1238 likes
25. Reverse Nodes in k-Group (K 个一组翻转链表), Hard, 1230 likes
6. ZigZag Conversion (Z 字形变换), Medium, 1226 likes
152. Maximum Product Subarray (乘积最大子数组), Medium, 1223 likes
215. Kth Largest Element in an Array (数组中的第K个最大元素), Medium, 1211 likes
8. String to Integer (atoi) (字符串转换整数 (atoi)), Medium, 1168 likes
41. First Missing Positive (缺失的第一个正数), Hard, 1163 likes
283. Move Zeroes (移动零), Easy, 1162 likes
141. Linked List Cycle (环形链表), Easy, 1161 likes ✔️
98. Validate Binary Search Tree (验证二叉搜索树), Medium, 1156 likes
124. Binary Tree Maximum Path Sum (二叉树中的最大路径和), Hard, 1152 likes
105. Construct Binary Tree from Preorder and Inorder Traversal (从前序与中序遍历序列构造二叉树), Medium, 1149 likes
34. Find First and Last Position of Element in Sorted Array (在排序数组中查找元素的第一个和最后一个位置), Medium, 1137 likes ✔️
239. Sliding Window Maximum (滑动窗口最大值), Hard, 1114 likes
142. Linked List Cycle II (环形链表 II), Medium, 1097 likes ✔️
139. Word Break (单词拆分), Medium, 1097 likes
45. Jump Game II (跳跃游戏 II), Medium, 1094 likes
169. Majority Element (多数元素), Easy, 1089 likes
234. Palindrome Linked List (回文链表), Easy, 1072 likes ✔️
62. Unique Paths (不同路径), Medium, 1072 likes
189. Rotate Array (旋转数组), Medium, 1057 likes
94. Binary Tree Inorder Traversal (二叉树的中序遍历), Easy, 1052 likes ✔️
56. Merge Intervals (合并区间), Medium, 1051 likes
88. Merge Sorted Array (合并两个有序数组), Easy, 1041 likes ✔️
560. Subarray Sum Equals K (和为K的子数组), Medium, 1036 likes
279. Perfect Squares (完全平方数), Medium, 1035 likes
35. Search Insert Position (搜索插入位置), Easy, 1005 likes
24. Swap Nodes in Pairs (两两交换链表中的节点), Medium, 996 likes
85. Maximal Rectangle (最大矩形), Hard, 983 likes
28. Implement strStr() (实现 strStr()), Easy, 982 likes
92. Reverse Linked List II (反转链表 II), Medium, 980 likes
155. Min Stack (最小栈), Easy, 979 likes
79. Word Search (单词搜索), Medium, 979 likes
27. Remove Element (移除元素), Easy, 967 likes
51. N-Queens (N 皇后), Hard, 965 likes
75. Sort Colors (颜色分类), Medium, 961 likes
102. Binary Tree Level Order Traversal (二叉树的层序遍历), Medium, 960 likes ✔️
48. Rotate Image (旋转图像), Medium, 960 likes
95. Unique Binary Search Trees II (不同的二叉搜索树 II), Medium, 955 likes
64. Minimum Path Sum (最小路径和), Medium, 954 likes
406. Queue Reconstruction by Height (根据身高重建队列), Medium, 947 likes
226. Invert Binary Tree (翻转二叉树), Easy, 941 likes
437. Path Sum III (路径总和 III), Medium, 937 likes
104. Maximum Depth of Binary Tree (二叉树的最大深度), Easy, 937 likes
237. Delete Node in a Linked List (删除链表中的节点), Easy, 936 likes ✔️
337. House Robber III (打家劫舍 III), Medium, 929 likes
18. 4Sum (四数之和), Medium, 918 likes
91. Decode Ways (解码方法), Medium, 904 likes
207. Course Schedule (课程表), Medium, 897 likes
37. Sudoku Solver (解数独), Hard, 897 likes
175. Combine Two Tables (组合两个表), Easy, 891 likes
416. Partition Equal Subset Sum (分割等和子集), Medium, 886 likes
238. Product of Array Except Self (除自身以外数组的乘积), Medium, 885 likes
114. Flatten Binary Tree to Linked List (二叉树展开为链表), Medium, 877 likes