目录
第一章 序章
第二章 数据结构
数据结构（data structure）：是数据的组织、管理和存储格式，其使用的目的是为了高效地访问和修改数据。
数据结构组成方式：
- 线性结构
线性结构是最简单的数据结构，包括数组、链表、以及由他们衍生出来的栈、队列、哈希表。
树
树是相对复杂的数据结构，其中比较有代表性的是二叉树，由它衍生出了二叉堆之类的数据结构。
图
图是更为复杂的数据结构，因为在图中会呈现出多对多的关联关系。
- 其他数据结构
除次之外，还有很多其他的数据结构。但是他们都是由基本数据结构变形而来，用于解决某些特定的关系，如跳表、哈希链表、位图等。
物理结构和逻辑结构：
一维
数组(array)
1. 什么是数组
- 数组 array 是由相同类型的变量所组成的有序集合，数组中的每个变量称为元素，数组是最基本最简单的数据结构
- 内存是由一个个连续内存单元组成的，每一个内存单元都有自己的地址。数组中的每一个元素，都存储在小小的内存单元中，并且元素直接紧密排列，既不能打乱元素的存储顺序，也不能跳过某个存储单元进行存储。
2. 数组的创建
int[] array1 = new int[3];int[] array2 = new int[]{1,2,3};
3. Arrays
1）sort()
sort()方法用来对数组进行排序，该方法要求数组的元素要实现Comparable接口。如果排序的元素不是String或者基本数据类型，就需要主动实现Comparable接口（基本数据类型和String本身已经实现了Comparable接口）。 ```java String[] strs = {“沉”, “默”,”王”, “二”};
Arrays.sort(strs); System.out.println(Arrays.toString(strs)); // 输出[二, 沉, 王, 默]
2）binarySearch()<br />binarySearch()方法用来对数组进行二分查找（返回值所在的下标，未找到的话返回-1），调用该方法之前必须要先排序。```javaString[] strs = {"沉", "默","王", "二"};Arrays.sort(strs);System.out.println(Arrays.binarySearch(strs, "二"));// 排序后的结果为[二, 沉, 王, 默]// 二分查找的结果范围0
由于sort()方法排序后的结果为[二, 沉, 王, 默]，所以Arrays.binarySearch(strs, “二”)返回下标值0。
4. array & list 相互转换
�
// List to ArrayList<String> stringList = new ArrayList<>();// 此方法存在强制转换时会抛异常final Object[] objects = stringList.toArray();// 推荐使用此方法进行list to array 操作final String[] strings = stringList.toArray(new String[stringList.size()]);// Array to ListString[] stingArray = {"array,list"};// 错误操作:返回的list是Arrays里面的一个静态内部类，该类并未实现add,remove方法，因此在使用时存在局限性List<String> list = Arrays.asList(stingArray);// 正确转换List<String> list1 = new ArrayList<>(Arrays.asList(stingArray));List<String> list2 = new ArrayList<String>(stingArray.length);Collections.addAll(list2,stingArray);
5. 数组基本操作
数组遍历：通过数组下标直接获取元素
数组更新：直接根据数组下标修改元素
数组新增：中间插入，需要把插入位置到元素全部后移
数组删除：中间删除，需要把元素从删除位置每个向前移动一个
/*** 数据结构 —— 数组* 数组的基本 操作* 数组获取 lookup O(1)* 数组新增 insert O(n)* 尾部插入 lookup O(1)* 中间插入 O(n)* 超范围插入 O(n)* 数组删除 delete O(n)* 数组更新 update O(1)*/public class ArrayDemo {private int[] array;private int size;private ArrayDemo(int capacity) {this.array = new int[capacity];size = 0;}/*** 获取数组元素 直接通过下标获取即可，时间复杂度O(1)** @param array* @param i* @return*/public int getElement(int[] array, int i) {if (size <= 0)throw new IndexOutOfBoundsException("超出数组实际 元素范围！");return array[i];}/*** 尾部插入数组添加元素** @param element* @param index* @return*/public void add(int element, int index) {if (index < 0 || index > size) {throw new RuntimeException("");}for (int i = size - 1; i >= index; i--) {array[i + 1] = array[i];}array[index] = element;size++;}/*** 超出范围新增** @param element* @param index*/public void addOutArray(int element, int index) {if (index < 0 || index > size) {throw new IndexOutOfBoundsException("超出数组实际 元素范围！");}if (size > array.length) {grow();}for (int i = size - 1; i >= index; i--) {array[i + 1] = array[i];}array[index] = element;size++;}/*** 数组扩容*/private void grow() {// 扩容2倍int[] newArray = new int[array.length >> 1];// 从旧数组复制到新数组System.arraycopy(array, 0, newArray, 0, array.length);array = newArray;}/*** 删除元素** @param index* @return*/private int delete(int index) {if (index < size || index > size) {throw new IndexOutOfBoundsException("超出数组实际 元素范围！");}//从左往右遍历,将数组元素向前移动int deleteElement = array[index];for (int i = index; i < size; i++) {array[i] = array[i + 1];}size--;return deleteElement;}/*** list 和 array 转换*/public void ListToArray() {// List to ArrayList<String> stringList = new ArrayList<>();// 此方法存在强制转换时会抛异常final Object[] objects = stringList.toArray();// 推荐使用此方法进行list to array 操作final String[] strings = stringList.toArray(new String[stringList.size()]);// Array to ListString[] stingArray = {"array,list"};// 错误操作:返回的list是Arrays里面的一个静态内部类，该类并未实现add,remove方法，因此在使用时存在局限性List<String> list = Arrays.asList(stingArray);// 正确转换List<String> list1 = new ArrayList<>(Arrays.asList(stingArray));List<String> list2 = new ArrayList<String>(stingArray.length);Collections.addAll(list2, stingArray);}
6. array 常用API
// 对数组进排序Arrays.sort（）// 将一个数组复制到新的数组中Arrays.copyOf(int[] original, int newLength)//Object src : 原数组int srcPos : 从元数据的起始位置开始Object dest : 目标数组int destPos : 目标数组的开始起始位置int length : 要copy的数组的长度System.arraycopy(Object src, int srcPos, Object dest, int destPos,int length)
链表(linked list)
适用新增和删除，时间复杂度为O(1), 遍历时间复杂度为O(n)
1.什么是链表
链表是一种物理上非连续、非顺序的数据结构，由若干个节点(Node)组成。
2.常见链表
单链表：单向链表的每一个节点包含两部分，一部分是存放数据的变量data,另一部分是指向下一个节点的next指针
双向链表：在单链表的基础上，每个节点多了指向前置节点到指针。
循环链表：
3.链表基本操作
查找节点：链表查找不像数组那样可以直接通过数组下标获取元素，只能从头节点开始向后一个一个节点逐一查找
更新节点：如果不考虑查找节点的过程，链表的更新过程会像数组那样简单，直接把旧数据替换成新数据即可
插入节点：
和数组类似，链表插入主要分为三种情况：头部插入、中间插入、尾部插入
尾部插入：是最简单的操作，将最后一个节点的next指针指向新插入节点
头部插入：
- 把新节点的next 指针指向原先的头节点
把新节点变为链表的头节点
<br />中间插入： 中间插入主要分为两步<br />第一步：新节点的next指针，指向插⼊位置的节点<br />第二步：插⼊位置前置节点的next指针，指向新节点。<br /> <br />**删除节点：**<br />头部删除：把链表的头节点设为原先头节点的next指针即可。<br /> 
尾部删除：最简单的操作，把链表倒数第2个节点的next指针指向空即可
中间删除：把要删除节点的前置节点的next指针，指向要删除元素的下⼀个节点即可。
4.代码操作
/*** 单链表基本定义*/public class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}// 头节点ListNode head;// 尾节点ListNode tail;// 链表大小int size;/*** 新增** @param data* @param index*/private void insert(int data, int index) {if (index < size || index > size) {throw new IndexOutOfBoundsException("越界");}ListNode newListNode = new ListNode(data);if (size == 0) {// 空链表head = newListNode;tail = newListNode;} else if (index == 0) {// 头部插入newListNode.next = head;head = newListNode;} else if (index == size) {// 尾部插入tail.next = newListNode;tail = newListNode;} else {// 插入中间ListNode preNode = get(index - 1);newListNode.next = preNode.next;preNode.next = newListNode;}size++;}/*** 移除元素** @param index*/private ListNode remove(int index) {if (index < size || index > size) {throw new IndexOutOfBoundsException("越界");}ListNode removeNode = null;if (index == 0) {// 头部删除removeNode = head;head = head.next;} else if (index == size) {// 尾部删除final ListNode preNode = get(index - 1);removeNode = preNode.next;preNode.next = null;tail = preNode;} else {// 删除中间节点final ListNode preNode = get(index - 1);ListNode nextNode = preNode.next.next;removeNode = preNode.next;preNode.next = nextNode;}size--;return removeNode;}/*** 链表获取元素** @param index* @return*/private ListNode get(int index) {if (index < size || index > size) {throw new IndexOutOfBoundsException("越界");}ListNode temp = head;for (int i = 0; i < index; i++) {temp = temp.next;}return temp;}}
5.博客地址
leetcode: https://mp.weixin.qq.com/s/Ym7MhhJ—NcaRRnj1y1vFA
栈
队列(queue)
双端队列(deque)
集合 set
集合 map
二维
树(tree)
图(graph)
二叉搜索树
堆(Heap)
并查集 disjoint set
字典树 Trie
特殊数据结构
位运算 Bitwise
布隆过滤器
LRU Cache
第三章 算法专题
一、数组
第四章 LeetCode题解
一、数组
1. 两数之和
题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
解题思路
- 暴力解决： 两次for 循环寻找和为target 的下标并返回
- 使用哈希表：利用空间换时间，提高效率。Map 存放数组元素和下标，通过判断key 是否存在目标值结束循环
代码
/*** 解法一： 暴力解法* @param nums* @param target* @return*/public int[] twoSum1(int[] nums, int target) {for (int i = 0; i < nums.length; i++) {for (int j = i+1; j < nums.length; j++) {if(nums[i]+nums[j] == target){return new int[]{i,j};}}}return new int[0];}/*** 解法二：使用hash 表* @param nums* @param target* @return*/public int[] twoSum2(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {if(map.containsKey(target - nums[i])){return new int[]{map.get(target - nums[i]),i};}map.put(nums[i],i);}return new int[0];}
2.寻找两个正序数组的中位数
题目
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
解题思路
- 暴力解决： 合并两个数组，然后进行排序，最后对排序后的数组按照中位数计算公式进行计算
- 二分查找：
- 分治法：
代码
/*** 暴力解法* 1.合并数组API* 2.排序数组API* 3.计算注意强转成double,不然返回整数* @param nums1* @param nums2* @return*/public static double findMedianSortedArrays(int[] nums1, int[] nums2) {int size = nums1.length+nums2.length;if(size == 0){return 0;}int[] result = Arrays.copyOf(nums1, nums1.length + nums2.length);System.arraycopy(nums2, 0, result, nums1.length, nums2.length);if (size == 1){return result[0];}Arrays.sort(result);if( size % 2 == 0 ){return ((double)result[(size/2)-1] + result[size/2])/2;}else {return result[size/2];}}
3.删除有序数组中的重复项
题目
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成
解题思路
题目
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
解题思路
- 同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2，进位值为 carry，则它们的和为 n1+n2+carry；其中，答案链表处相应位置的数字为 (n1+n2+carry) mod 10，而新的进位值为n1+n2+carry/10
- 如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 00 。
- 此外，如果链表遍历结束后，有carry>0，还需要在答案链表的后面附加一个节点，节点的值为 carry。
代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode tail=null, head = null;int carry = 0;while (l1 != null || l2 != null) {//1. 同时遍历两个 ListNode, 如果同位置链表为空用 0 代替int n1 = l1 != null ? l1.val : 0;int n2 = l2 != null ? l2.val : 0;int sum = n1 + n2 + carry;if (head == null) {head = tail = new ListNode(sum % 10);} else {tail.next = new ListNode(sum % 10);tail = tail.next;}carry = sum / 10;if (l1 != null) {l1 = l1.next;}if (l2 != null) {l2 = l2.next;}}// 3. 如果 carray >0 则if (carry > 0) {tail.next = new ListNode(carry);}return head;}}
第五章 算法
算法基础
if-else,switch -> branch
for, while loop -> Iteration
递归 Recursion
搜索 Search: 深度优先搜索 Depth first search, 广度优先搜索 Breadth first serarch
动态规划 Dynamic Programming
二分查找 Binary Search
贪心 Greedy
数学 Math,几何 Geometry
常用算法
1. 滑动窗口
什么是滑动窗口
滑动窗口算法是在给定特定窗口大小的数组或字符串上执行需求的操作。
该算法可以将一部分问题中的嵌套循环转变为一个单循环，因此减少时间复杂度。
基本示列
举个例子：如下图所示，设定滑动窗口（window）大小为 3，当滑动窗口每次划过数组时，计算当前滑动窗口中元素的和，得到结果 res。
可以用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。由于区间连续，因此当区间发生变化时，可以通过旧有的计算结果对搜索空间进行剪枝，这样便减少了重复计算，降低了时间复杂度。往往类似于“ 请找到满足 xx 的最 x 的区间（子串、子数组）的 xx ”这类问题都可以使用该方法进行解决。
需要注意的是，滑动窗口算法更多的是一种思想，而非某种数据结构的使用。
滑动窗口的基本框架
2. 动态规划
3. 中心扩展
若有收获，就点个赞吧
0 人点赞
