目录
前言
一、查找算法
1.顺序查找（线性查找）
2.二分查找
二、排序算法
1.冒泡排序
2.直接选择排序
3.插入排序
4.直接插入排序
·
·
·
三、链表的基础操作
1.链表的创建
2.移除链表元素
3.设计链表
4.ListNode temp = head 与 ListNode dumpyNode = new ListNode(0) 的区别
四、树的基础操作
1.二叉树的定义
2.二叉树的递归遍历，前中后
3.层序遍历
4.求树的最大高度
前言
做一些基础数据结构算法汇总，便于日后复习。
一、查找算法
1.顺序查找（线性查找）
依据数组的下标按顺序进行查找，然后返回数组下标。对于数据量较小的情况，比较适用。但是如果数据量较大，花费的时间就比较多。
2.二分查找
二分查找 Binary Search
二分查找的使用，要有一个前提条件：要查找的数必须在一个有序数组里。在这个前提下，取中间位置数作为比较对象：
- 若要查找的值和中间数相等，则查找成功。
- 若小于中间数，则在中间位置的左半区继续查找。
- 若大于中间数，则在中间位置的右半区继续查找。
不断重复上述过程，直到查找成功或者查找区域变为 0，查找失败。
public static int binarySearch(int[] nums, int left, int right, int target){
if (left>right){ //没有查找到
return -1;
}
int mid =( left+right)/2;//找区间中间值
if (nums[mid]>target){
return binarySearch(nums,left,mid-1,target);//找左区间
}else if (nums[mid]<target){
return binarySearch(nums,mid+1,right,target);//找右区间
}else {
return mid; //找到
}
}二、排序算法
1.冒泡排序
按从小到大排序举例：
1.比较相邻的两个元素，若前边的元素大于后边的元素则交换。
2.每一对相邻元素都要进行比较。每一个轮次，将最大的排到最后。
3.针对剩余的元素，重复上述步骤
4.没有元素交换，完成排序。
public void bubbleSort(int[] arr) {
int temp = 0;
boolean flag;
for (int i = arr.length - 1; i > 0; i--) { // 每次需要排序的长度
flag = false;
for (int j = 0; j < i; j++) { // 从第一个元素到第 i 个元素,即对剩余元素进行处理
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
}
if (!flag){ //如果为flase 则没有发生交换，排序结束
break;
}
}
}
2.直接选择排序
- 第一趟，程序将记录定位在第一个数据上，拿第一个数据依次和后面的数据进行比较，如果第一个数据大，交换，依次类推。经过第一趟比较，这组数据中最小的数据被选出来，排在第一位。
- 第二趟，程序将记录定位在第二个数据上，拿第二个数据依次和后面的数据比较，同样地，第二个数据大就交换。经过第二次比较，这轮最小的书被选出来，放在了第二位。
这样经过n-1次比较，这组数据就会变得有序。文章来源：https://www.toymoban.com/news/detail-443531.html
private static void selectSort(int[] arr) {
for(int i = 0;i < arr.length;i++) {
//将当前索引（即“待排序数组”的首位）定为最小值索引
int min = i;
//通过循环找出最小值索引。注意：此处未发生交换
for(int j = i + 1;j < arr.length;j++) {
if(arr[j] < arr[min]) {
min = j;
}
}
//若最小值索引不为i，则交换
if(min != i) {
int tmp = arr[min];
arr[min] = arr[i];
arr[i] = tmp;
}
}
}3.插入排序
4.直接插入排序
·
·
·
三、链表的基础操作
1.链表的创建
public class ListNode {
// 结点的值
int val;
// 下一个结点
ListNode next;
// 节点的构造函数(无参)
public ListNode() {
}
// 节点的构造函数(有一个参数)
public ListNode(int val) {
this.val = val;
}
// 节点的构造函数(有两个参数)
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}2.移除链表元素
/**
* 添加虚节点方式
* 时间复杂度 O(n)
* 空间复杂度 O(1)
* @param head
* @param val
* @return
*/
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return head;
}
// 因为删除可能涉及到头节点，所以设置dummy节点，统一操作
ListNode dummy = new ListNode(-1, head);
ListNode pre = dummy;
ListNode cur = head;
while (cur != null) {
if (cur.val == val) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return dummy.next;
}
/**
* 不添加虚拟节点方式
* 时间复杂度 O(n)
* 空间复杂度 O(1)
* @param head
* @param val
* @return
*/
public ListNode removeElements(ListNode head, int val) {
while (head != null && head.val == val) {
head = head.next;
}
// 已经为null，提前退出
if (head == null) {
return head;
}
// 已确定当前head.val != val
ListNode pre = head;
ListNode cur = head.next;
while (cur != null) {
if (cur.val == val) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return head;
}3.设计链表
//单链表
class ListNode {
int val;
ListNode next;
ListNode(){}
ListNode(int val) {
this.val=val;
}
}
class MyLinkedList {
//size存储链表元素的个数
int size;
//虚拟头结点
ListNode head;
//初始化链表
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
//获取第index个节点的数值
public int get(int index) {
//如果index非法，返回-1
if (index < 0 || index >= size) {
return -1;
}
ListNode currentNode = head;
//包含一个虚拟头节点，所以查找第 index+1 个节点
for (int i = 0; i <= index; i++) {
currentNode = currentNode.next;
}
return currentNode.val;
}
//在链表最前面插入一个节点
public void addAtHead(int val) {
addAtIndex(0, val);
}
//在链表的最后插入一个节点
public void addAtTail(int val) {
addAtIndex(size, val);
}
// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果 index 大于链表的长度，则返回空
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
if (index < 0) {
index = 0;
}
size++;
//找到要插入节点的前驱
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
ListNode toAdd = new ListNode(val);
toAdd.next = pred.next;
pred.next = toAdd;
}
//删除第index个节点
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
size--;
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
pred.next = pred.next.next;
}
}
//双链表
class MyLinkedList {
class ListNode {
int val;
ListNode next,prev;
ListNode(int x) {val = x;}
}
int size;
ListNode head,tail;//Sentinel node
/** Initialize your data structure here. */
public MyLinkedList() {
size = 0;
head = new ListNode(0);
tail = new ListNode(0);
head.next = tail;
tail.prev = head;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
if(index < 0 || index >= size){return -1;}
ListNode cur = head;
// 通过判断 index < (size - 1) / 2 来决定是从头结点还是尾节点遍历，提高效率
if(index < (size - 1) / 2){
for(int i = 0; i <= index; i++){
cur = cur.next;
}
}else{
cur = tail;
for(int i = 0; i <= size - index - 1; i++){
cur = cur.prev;
}
}
return cur.val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
ListNode cur = head;
ListNode newNode = new ListNode(val);
newNode.next = cur.next;
cur.next.prev = newNode;
cur.next = newNode;
newNode.prev = cur;
size++;
}
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
ListNode cur = tail;
ListNode newNode = new ListNode(val);
newNode.next = tail;
newNode.prev = cur.prev;
cur.prev.next = newNode;
cur.prev = newNode;
size++;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
if(index > size){return;}
if(index < 0){index = 0;}
ListNode cur = head;
for(int i = 0; i < index; i++){
cur = cur.next;
}
ListNode newNode = new ListNode(val);
newNode.next = cur.next;
cur.next.prev = newNode;
newNode.prev = cur;
cur.next = newNode;
size++;
}
/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
if(index >= size || index < 0){return;}
ListNode cur = head;
for(int i = 0; i < index; i++){
cur = cur.next;
}
cur.next.next.prev = cur;
cur.next = cur.next.next;
size--;
}
}4.ListNode temp = head 与 ListNode dumpyNode = new ListNode(0) 的区别
文章来源地址https://www.toymoban.com/news/detail-443531.html
四、树的基础操作
1.二叉树的定义
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}2.二叉树的递归遍历，前中后
// 二叉树的前序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preorder(root, result);
return result;
}
public void preorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
}
}
// 二叉树的中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root, res);
return res;
}
void inorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
inorder(root.left, list);
list.add(root.val); // 注意这一句
inorder(root.right, list);
}
}
// 二叉树的后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postorder(root, res);
return res;
}
void postorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
postorder(root.left, list);
postorder(root.right, list);
list.add(root.val); // 注意这一句
}
}3.层序遍历
public List<List<Integer>> resList = new ArrayList<List<Integer>>();
public void checkFun02(TreeNode node) {
if (node == null) return;
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(node);
while (!que.isEmpty()) {
List<Integer> itemList = new ArrayList<Integer>();
int len = que.size();
while (len > 0) {
TreeNode tmpNode = que.poll();
itemList.add(tmpNode.val);
if (tmpNode.left != null) que.offer(tmpNode.left);
if (tmpNode.right != null) que.offer(tmpNode.right);
len--;
}
resList.add(itemList);
}
}
4.求树的最大高度
/**
* 递归法
*/
public int maxdepth(treenode root) {
if (root == null) {
return 0;
}
int leftdepth = maxdepth(root.left);
int rightdepth = maxdepth(root.right);
return math.max(leftdepth, rightdepth) + 1;
}
/**
* 迭代法，使用层序遍历
*/
public int maxdepth(treenode root) {
if(root == null) {
return 0;
}
deque<treenode> deque = new linkedlist<>();
deque.offer(root);
int depth = 0;
while (!deque.isempty()) {
int size = deque.size();
depth++;
for (int i = 0; i < size; i++) {
treenode poll = deque.poll();
if (poll.left != null) {
deque.offer(poll.left);
}
if (poll.right != null) {
deque.offer(poll.right);
}
}
}
return depth;
}到了这里，关于JAVA 基础算法汇总（持续更新）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
