数据结构与算法相关

第二章 数据结构与算法相关

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

图

排序算法有哪些

查找算法

串

其他算法

由于简书文字受限，新的知识探索请移步下一篇文章哦