常见算法题整理

左手的ㄟ右手 2022-10-16 09:54 203阅读 0赞

# 算法题： #

*  数据结构：数组、链表、字符串、树、数学、栈、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. 两数相加][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 个结点][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. 环形链表][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. 回文链表][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. 最长回文子串][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. 二叉树的中序遍历][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. 零钱兑换][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、如何聪明的穷举
    
     *  用备忘录消除重叠子问题，写出自动向下解法
     *  进一步，可以写出自动向下解法
     *  再进一步，可能可以优化空间复杂度

[2.]: https://leetcode-cn.com/problems/add-two-numbers/
[19. _ N]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
[141.]: https://leetcode-cn.com/problems/linked-list-cycle/
[02.06.]: https://leetcode-cn.com/problems/palindrome-linked-list-lcci/
[5.]: https://leetcode-cn.com/problems/longest-palindromic-substring/
[94.]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
[322.]: https://leetcode-cn.com/problems/coin-change/