常见算法题整理

2023-10-27

算法题：

数据结构：数组、链表、字符串、树、数学、栈、hash表、图
动态规划、中心扩散、回溯算法、递归、迭代、贪心算法、
从整体到细节，自顶向下，从抽象到具体的框架思维是通用的，不只是学习数据结构和算法，学习其他任何知识都是高效的。

一、数组：

技巧：

双指针

二、链表：

技巧：

链表问题一般先定义一个哑结点，将特殊清除处理掉

链表反转

private  Node reverse(Node node) {
        Node pre = null, cur = node, tem = null;
        while (cur != null) {
            tem = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tem;
        }
        return pre;
    }

2. 两数相加

难度中等 6174

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

/**
 * 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) {
        // 特判：
        if(l1==null)return l2;
        if(l2==null)return l1;

        int carry=0;
        ListNode dummy =new ListNode(0);// 定义个哑结点，便于处理
        ListNode pre=dummy; // 指向哑结点的地址、最终返回pre.next;

        while(l1!=null && l2!=null){
            int sum =l1.val+l2.val+carry;
            carry =sum/10;
            ListNode node =new ListNode(sum%10);
            dummy.next=node;
            l1=l1.next;
            l2=l2.next;
            dummy=dummy.next;
        }
        while(l1!=null){
            int sum =l1.val+carry;
            carry =sum/10;
            ListNode node =new ListNode(sum%10);
            dummy.next=node;
            l1=l1.next;
            dummy=dummy.next;
        }
       while(l2!=null){
            int sum =l2.val+carry;
            carry =sum/10;
            ListNode node =new ListNode(sum%10);
            dummy.next=node;
            l2=l2.next;
            dummy=dummy.next;
        }
        if(carry>0){
            dummy.next=new ListNode(carry); 
        }
        return pre.next;
    }
}

看清题意，有时候需要做链表的反转。

19. 删除链表的倒数第 N 个结点

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        // 方式1： 遍历一遍,统计元素个数总和 ，再遍历
        // 方式2： 快慢指针

        // 定义一个哑结点，使得链表中所有的结点都有前驱结点
        ListNode dummy = new ListNode(0,head);
        // 定义快慢指针都指向哑结点
        ListNode fast=dummy, slow=dummy;
        // 让快指针先往前移动 n+1 步
        for(int i=0;i<n+1;i++){
            fast=fast.next;
        }
        // 同时移动快慢指针，直到快指针指向null
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        // 不清理要删除元素所占的空间。
        // slow.next=slow.next.next;
        // 清理待删除元素所占的空间
        ListNode delNode =slow.next;
        slow.next=delNode.next;
        delNode.next=null;
        
        return dummy.next;
    }
}

寻找链表的中间结点：

// 快慢指针，慢指针一次走一步，快指针一次走两步。最终慢指针指向就为中间结点
private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

141. 环形链表

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while (head != null) {
            if (!seen.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }
}

面试题 02.06. 回文链表

其中包括获取中间结点的方法
链表反转的方法。
最终达到

class Solution {
    public boolean isPalindrome(ListNode head) {
// 方式3：反转后半段链表，然后比较前后半段链表的值
        // 1、通过快慢指针，找出链表的中间结点，慢指针的next结点为后半部分的开始
        ListNode firstTail = getFirstHalf(head);
        if(firstTail==null) return true ;
        //2、反转后半部分链表
        ListNode nextHalf= reversal(firstTail.next);
        //3、比较将原链表和后半部分值比较。（不同return false， 相同返回true）
        while(nextHalf!=null){
            if(head.val!=nextHalf.val){
                return false;
            } else{
                head=head.next;
                nextHalf=nextHalf.next;
            }
        }
        return true;
    }
    // 获取链表中间结点的方法
    private ListNode getFirstHalf(ListNode head){
        ListNode fast =head,slow =head;
        while(fast!=null&&fast.next!=null&& fast.next.next!=null){
            fast =fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    // 链表反转
    private ListNode reversal(ListNode node){
        ListNode pre = null, cur=node,tem=null;
        while(cur!=null){
            tem =cur.next;
            cur.next=pre;
            pre=cur;
            cur=tem;
        } 
        return pre;
    }
}

三、字符串：

字符串问题一般转换成char数组，去操作数组，省的每次操作字符串的str.charAt(i)

1、验证子串是否为回文串

// char[] charArr =str.toCharArray();// 字符串转换成char数组

private static boolean validateSubstring(char[] charArr, int left ,int right){
  while(left<right){
    if(charArr[left]!=charArr[right]){
      return false;
    }
    left++;
    right--;
  }
  return true;
}

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd”
输出：“bb”
示例 3：

输入：s = “a”
输出：“a”
示例 4：

输入：s = “ac”
输出：“a”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

class Solution {
    public String longestPalindrome(String s) {
        // 特判
        if(null==s || s.length()<2) return s;
        // 中心扩散法
        int res =1; //最大长度
        int ll=0;   //最大回文串的左指针
        int rr=0;   //最大回文串的右指针
        //将字符串转成char数组，不在循环中去使用str.charAt(i)
        char[] chArr =s.toCharArray();

        // 开始遍历char数组
        for(int i =0; i<chArr.length; i++){
            // 以i为中心向两边扩散，寻找最长子串（通俗：回文串为奇数长度i为中心）
            int l =i-1;
            int r =i+1;

            while(l>=0 && r<chArr.length && chArr[l]==chArr[r]){
                int len =r-l+1;
                if(len>res){
                    res=len;
                    ll=l;
                    rr=r;
                }
                l--;
                r++;
            }
            // 以i为左指针，i+1为右指针（通俗：回文串为偶数长度）
            l=i;
            r=i+1;
            while(l>=0 && r<chArr.length && chArr[l]==chArr[r]){
                int len =r-l+1;
                if(len>res){
                    res=len;
                    ll=l;
                    rr=r;
                }
                l--;
                r++;
            }
        } 
        return s.substring(ll,rr+1);
    }
}

四、树：

技巧：

递归最简单，一般树的问题都可以通过递归来解决。（需要再学下迭代，迭代是显示维护一个栈）
前序遍历：根左右；中序遍历：左根右；后序遍历：左右根。

94. 二叉树的中序遍历

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // 中序遍历：左 根 右
        List<Integer> list = new ArrayList<Integer>();
        leftOrder(root,list);
        return list;
    }
    private void leftOrder(TreeNode node, List list){
        if(null==node) return;

        leftOrder(node.left,list);
        list.add(node.val);
        leftOrder(node.right,list);

    }
}

五、栈：

六、Hash表

七、图

八、动态规划（labuladong）

动态规划的特点：

重叠子问题
状态转义方程（最关键）
最优子结构

题型：

求最值
核心：穷举：不要小看暴力穷举

解题套路：

明确【状态】
明确【选择】
明确dp函数、数组的定义
明确base case。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RsFw2FXi-1622290180636)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524104147868.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EqdphKC2-1622290180639)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524104228806.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lMB5LyEx-1622290180641)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524104255133.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iv9SXKeI-1622290180645)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524110029673.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-onKZYvFS-1622290180646)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524110123303.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4RaL0PV6-1622290180648)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524110307321.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DuZMyq2H-1622290180649)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524111455743.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lSizQQ5a-1622290180649)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210523234630863.png)]

空间换时间。引入数组备忘录，占用数组大小的空间。
自底向上：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EtPHrtHP-1622290180650)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524130837926.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QXdBtZBI-1622290180651)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524130804245.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tdIKRMnf-1622290180652)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524131015765.png)]

优秀的算法都是慢慢演变来的，就像系统架构一样，不是一开始就很优，都是慢慢演变的

509：斐波那契数列

class Solution {
    public int fib(int n) {
        // 方式1：直接递归 ，但是时间复杂度较高，多了很多重复的计算。
         /*// 方式2：带备忘录的递归。将所有计算过的值缓存下来，递归中直接返回。（自顶向下推，然后自底向上回溯）
       // 初始化备忘录。
         int[] notes =new int[n+1];
        // 进行带备忘录的递归。
        return helper(notes, n);*/

       /* // 方式3：dp数组迭代法 （自底向上）
        if(n==0) return 0;
        int[] dp =new int[n+1];
        // base case 
        dp[0]=0; dp[1]=1;
        // 状态转移
        for(int i=2; i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];*/
        //方式4： 优化空间复杂度，求第n个数，其实只需要知道他的前两个数就可以了 ，
        // 因此可以定义两个变量去表示它的前两个数的值，依次来优化空间复杂度
        if(n==0) return 0;
        int pre=0,curr=1;
        for(int i=2;i<=n;i++){
            int sum=pre+curr;
            pre =curr;
            curr=sum;
        }
        return curr;
    }
    private int helper(int[] notes,int n){
        if(n==0|| n==1) return n; //base case
        if(notes[n]!=0) return notes[n];
        notes[n] =helper(notes,n-1)+helper(notes,n-2);
        return notes[n];
    }
}

322. 零钱兑换

动态规划是用于求最值的问题。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-l8LPzpXZ-1622290180652)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524131921580.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-inO9cJ24-1622290180653)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524131725872.png)]

自顶向下的递归（带备忘录）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cDrON8qK-1622290180654)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524132417304.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PfYzUeuZ-1622290180655)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524132746801.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-byRez0zV-1622290180655)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524133054887.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4xp2AyzG-1622290180656)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%98.assets/image-20210524133112429.png)]

动态规划问题的本质：

1、如何穷举
- 写出状态转移方程，暴力穷举所有可行解。
2、如何聪明的穷举
- 用备忘录消除重叠子问题，写出自动向下解法
- 进一步，可以写出自动向下解法
- 再进一步，可能可以优化空间复杂度

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构与算法

算法