数据结构与算法相关
第二章 数据结构与算法相关
1.常用的数据结构有哪些？
数组、栈、队列、链表（单链表、双向链表、循环链表）、树、散列表、堆、图
image.png
数组：
数组是可以在内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。
栈：
栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。栈的特点是：先进后出，或者说后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。
队列：
队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作成为入列，取出元素为出列。
链表
链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域(内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表、双向链表、循环链表等。
树
树是一种数据结构，它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说根朝上，而叶朝下。
散列表
散列表，也称哈希表，是根据关键码和值(key和value)直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。
堆
堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
图
图是由节点的有穷集合V和边的集合E组成，其中，为了与树形结构加以区别，在图结构中常常将节点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
数组相关
1.编写冒泡排序和选择排序
//冒泡排序时间复杂度是O(n^2)
public static void bubbleSort(int[] arr) {
boolean didSwap;
for (int i = 0, len = arr.length; i < len - 1; i++) {
didSwap = false;//当给定的数组是排过顺序的，直接退出
for (int j = 0; j < len - i - 1; j++) {
//从小到大排序
if (arr[j + 1] < arr[j]) {
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
didSwap = true;
}
}
if (didSwap == false)
return;
}
}
//选择排序时间复杂度是O(n^2)
public static void selectSort(int[] arr) {
boolean didSwap;
for (int i = 0, len = arr.length; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
2.给一个乱序数组，使得奇数放在前面，偶数放在数组后面，并且保证奇偶数在原数组的相对位置不变
public static void arraySort(int[] a) {
int leng = a.length;
int i = 0, j;
while (i < leng) {
if (a[i] % 2 == 0) {
i++;
} else {
//此时的i指的是奇数
j = i + 1;
while (a[j] % 2 == 1) {
if (j == leng - 1) {
return;
}
j++;
}
//j指的是偶数
int temp = a[j];
while (j > i) {
a[j] = a[j - 1];
j--;
}
a[i] = temp;
}
}
System.out.println(Arrays.toString(a));
}
3.数据交换
public static void swap(int[] arr,int a,int b)
{
int temp = arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
4.给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
public static int searchInsert(int[] nums,int target){
int n = nums.length;
int left = 0, right = n - 1, ans = n;
while (left <= right) {
int mid = ((right - left) / 2) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
5.给定一个正整数n，生成一个包含1到n²所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
public class test0319 {
public static void main(String[] args) {
Solution S = new Solution();
int n = 4;
int[][] a = S.generateMatrix(n);
for(int i = 0; i < 4;i++) {
for(int j = 0; j < 4; j++) {
System.out.print(a[i][j]+ "\t");
}
System.out.println();
}
}
}
class Solution {
public int[][] generateMatrix(int n) {
int[][] a = new int[n][n];
int count = 1;
int i = 0;
while(count <= n*n){
//关键就是要把行列下标以及行列长度的关系搞清楚
for( int j = i; j < n - i; j++){
//上边
a[i][j] = count;
count ++;
}
for( int j = i + 1; j < n - i; j++ ){
//右边
a[j][n - i -1] = count ;
count ++;
}
for(int j = n - 2- i; j >= i;j-- ){
//下边
a[n - i -1][j] =count;
count++;
}
for(int j = n- i - 2; j > i; j--){
//左边
a[j][i] = count;
count ++;
}
i++;
}
return a;
}
}
6.给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true；否则返回false。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] letter1 = new int[123];
int[] letter2 = new int[123];
for (int i = 0; i < ransomNote.length(); i++){
letter1[ransomNote.charAt(i)]++;
}
for (int i = 0; i < magazine.length(); i++){
letter2[magazine.charAt(i)]++;
}
for (int i = 0; i < ransomNote.length(); i++){
if (letter1[ransomNote.charAt(i)] > letter2[ransomNote.charAt(i)]){
return false;
}
}
return true;
}
}
7.删除排序数组的重复项（给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。）
示例 1:
给定数组 nums = [1, 1, 2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
class Solution {
public int removeDuplicates(int[] nums) {
// 小于的直接返回
if (nums.length < 2) return 1;
//左指针
int left = 1;
//右指针
int right = 1;
for (; right < nums.length; right++) {
// 当右边指针指向的元素不等于它上一个的时候，就证明不是重复，否则重复的直接跳过，右指针一直往前移，直至找到不重复元素为止
if (nums[right] != nums[right - 1]) {
//将该元素复制到左边的指针位置
nums[left] = nums[right];
// 复制后，左指针往前移一位，用来接收下一个元素
left++;
}
//右指针继续往前移一位，right++
}
return left;
}
}
8.给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
image.png
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int index=0;
for(int i=m;i<m+n;i++)
{
nums1[i]=nums2[index];
index++;
}
auto begin=nums1.begin();
sort(begin,begin+m+n);
}
};
链表相关
1.相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
image.png
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
image.png
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
image.png
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
image.png
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
//暴力解法
class Solution {
public int getL(ListNode cur)
{
if(cur==null) return 0;
int len=0;
while(cur!=null)
{
cur=cur.next;
len++;
}
return len;
}
public ListNode findFirstCommonNode(ListNode headA, ListNode headB) {
if(headA==null||headB==null) return null;
int lenA=getL(headA);
int lenB=getL(headB);
if(lenA>lenB)
{
while(lenA-lenB>0)
{
headA=headA.next;
lenA--;
}
}else if(lenA<lenB){
while(lenB-lenA>0)
{
headB=headB.next;
lenB--;
}
}
while(headA!=headB)
{
headA=headA.next;
headB=headB.next;
}
return headA;
}
}
//双指针
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p=headA;
ListNode q=headB;
while(p!=q)
{
if(p!=null)
{
p=p.next;
}else{
p=headB;
}
if(q!=null)
{
q=q.next;
}else{
q=headA;
}
}
return p;
}
}
2.反转链表
1).反转一个单链表。
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null) return null;
ListNode prev=null,cur=head,curNext=null;
while(cur!=null)
{
curNext=cur.next;
cur.next=prev;
prev=cur;
cur=curNext;
}
return prev;
}
}
2).给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode newHead=new ListNode(-1);
newHead.next=head;
ListNode a=newHead;
for(int i=0;i<left-1;i++)
{
a=a.next;
}
ListNode b=a.next,c=b.next;
for(int i=0;i<right-left;i++)
{
ListNode d=c.next;
c.next=b;
b=c;
c=d;
}
a.next.next=c;
a.next=b;
return newHead.next;
}
}
3.删除链表的倒数第N个节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head==null)
return head;
ListNode p = head;
ListNode q =head;
//用count记录走了多少步，和最终链表的长度
int count=0;
while(q.next!=null){
count++;
//前n步只让q指针走
if(count<=n){
q=q.next;
}else{
q=q.next;
p=p.next;
}
}
//循环结束时p到达了倒数n个元素的前面一个元素
//两个特殊情况，即链表只有一个元素和要删除的为头节点的情况
if(head.next==null || count+1 == n){
head=head.next;
}else{
p.next=p.next.next;
}
return head;
}
}
4.输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack = new Stack<>();
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> list = new ArrayList<>();
while (!stack.isEmpty()) {
list.add(stack.pop());
}
return list;
}
}
5.输入一个链表，反转链表后，输出新链表的表头。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head==null)
return null;
//head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null；
ListNode pre = null;
ListNode next = null;
//当前节点是head，pre为当前节点的前一节点，next为当前节点的下一节点
//需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2
//即pre让节点可以反转所指方向，但反转之后如果不用next节点保存next1节点的话，此单链表就此断开了
//所以需要用到pre和next两个节点
//1->2->3->4->5
//1<-2<-3 4->5
while(head!=null){
//做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
//如此就可以做到反转链表的效果
//先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
next = head.next;
//保存完next，就可以让head从指向next变成指向pre了，代码如下
head.next = pre;
//head指向pre后，就继续依次反转下一个节点
//让pre，head，next依次向后移动一个节点，继续下一次的指针反转
pre = head;
head = next;
}
//如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
//直接输出pre就是我们想要得到的反转后的链表
return pre;
}
}
5.输入一个链表，输出该链表中倒数第k个结点。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode list,int k) {
if (list == null) return list;
ListNode node = list;
int count = 0;
while (node != null) {
count++;
node = node.next;
}
if (count < k) return null;
ListNode p = list;
for (int i = 0; i < count - k; i++) {
p = p.next;
}
return p;
}
}
队列&堆栈
二叉树
HashMap
图
排序算法有哪些
查找算法
串
其他算法
由于简书文字受限，新的知识探索请移步下一篇文章哦
