每日力扣3

今日题目

正则表达式匹配
通配符匹配
复制带随机指针的链表
合并K个排序链表
最小覆盖子串

---

正则表达式匹配（动态规划）

题目链接
.匹配任意单个字符，要么匹配长度为0的子串要么匹配长度不为0的和前一个字符一样的子串。和上一题类似，我们用一个二维bool数组dp=new bool[m+1,n+1]来存储s中1到i，p中1到j的匹配情况。而dp[i,j]的递推公式，我们发现，当p[j-1]，即第j个字符为字母的时候，只要判断和当前的第i个字符是否匹配即可，即dp[i,j]=dp[i-1,j-1]&&s[i-1]==p[j-1];
当其为’.’的时候，直接i++,j++;当其为’‘的时候，我们先判断s[i-1]是否等于p[j-2]，如果不相等就等同于匹配长度为0的子串，即dp[i,j]=dp[i,j-2]，如果相等，就仍然和最开始的那样有两种选择。如果匹配长度为0的子串，直接dp[i,j]=dp[i,j-2]即可，如果匹配长度不为0的子串，则有以下的规律：
f[i][j]=f[i−1][j−2],if s[i]=p[j−1]
f[i][j]=f[i−2][j−2],if s[i−1]=s[i]=p[j−1]
f[i][j]=f[i−3][j−2],if s[i−2]=s[i−1]=s[i]=p[j−1]
⋯⋯
我们可以转成一个很巧妙的带有递归思想的式子：dp[i,j]=dp[i-1,j]，如果s[i-2]=p[j-2]的话，将继续触发dp[i-2,j]，如此往复直至到达这串相同字母的最左侧。
来看代码：

public class Solution {
    public bool IsMatch(string s, string p) {//正则表达式匹配
        int m = s.Length;
        int n = p.Length;
        bool[,] dp = new bool[m+1,n+1];
        dp[0,0] = true;
        for(int i = 0;i<m+1;i++){
            for(int j = 1;j<n+1;j++){
                if(p[j-1]=='*'){
                    dp[i,j]=dp[i,j-2];
                    if(match(s,p,i,j-1)){
                        dp[i,j]=dp[i,j]||dp[i-1,j];
                    }
                }else{
                    if(match(s,p,i,j)){
                        dp[i,j]=dp[i-1,j-1];
                    }
                }
            }
        }
        return dp[m,n];
    }
    public bool match(string s,string p,int i,int j){
        if(i==0)
           return false;
        if(p[j-1]=='.')
           return true;
        return s[i-1]==p[j-1];
    }
}

---

通配符匹配（动态规划）

题目链接
(和上面的类似，实在不想写了)
来看代码：

public class Solution {
    public bool IsMatch(string s, string p) {//通配符匹配
        int m = s.Length;
        int n = p.Length;
        bool[,] record= new bool[m+1,n+1];
        record[0,0]=true;
        for(int i = 1;i<n+1;i++){
            if(p[i-1]=='*'){
                record[0,i]=true;
            }else{
                break;
            }
        }
        for(int i = 1;i<m+1;i++){
            for(int j = 1;j<n+1;j++){
                if(p[j-1]=='*'){
                    record[i,j]=(record[i,j-1]||record[i-1,j]);//要么不匹配，要么匹配
                }else if(p[j-1]=='?'||p[j-1]==s[i-1]){
                    record[i,j]=record[i-1,j-1];
                }
            }
        }
        return record[m,n]==true;
    }
}

---

复制带随机指针的链表（链表、哈希表）

题目链接
使用哈希表存储新链表中结点和旧链表的对应关系，同时我们可以通过HashMap.get(p.random)直接获取对应的q.random
来看代码：

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {//复制带随机指针的链表-Java
        Node p = head;//
        Node q = new Node(0);
        Node res = q;
        Node tempRandom = new Node(0);//指向random的指针
        HashMap<Node,Node> record = new HashMap<>();
        while(p!=null){//录入新旧链表中结点的对应关系
             q.next = new Node(p.val);
             record.put(p,q.next);
             p=p.next;
             q=q.next;
        }   
        p=head;
        q=res.next;
        while(p!=null){
             tempRandom=record.get(p.random);
             q.random=tempRandom;
             p=p.next;
             q=q.next;
        }  
        return res.next;
    }
}

---

合并K个升序链表（链表、分治法）

题目链接
分治法的思路就是用相同的步骤将大的问题分解成多个小问题解决。这个题我们将多个链表进行分组，每个组只有一个链表或两个链表，将两个链表合并成一个链表，如此递归向上直至返回结果。
来看代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {//排序链表-分治法：化大为小，思路统一
          if(lists.Length==0)//如果没有链表
            return null;
          return FenZhi(lists,0,lists.Length-1);
    }
    public ListNode FenZhi(ListNode[] lists,int left, int right){
         if(left==right)//如果就一个链表了
            return lists[left];
         if(left>right)
            return null;
         int m = right+left>>1;//实际上就是(r+l)/2,利用了运算符优先级
         return merge(FenZhi(lists,left,m),FenZhi(lists,m+1,right));//将几个链表拆分到最小组，然后递归merge
    }
    public ListNode merge(ListNode l1,ListNode l2){
        if(l1==null)
          return l2;
        if(l2==null)
          return l1;
        ListNode res= new ListNode();//新链表的头结点，res.next才是结果的头结点
        ListNode temp = res;//指向当前插入位置的前一个结点
        while(l1!=null&&l2!=null){//如果两个链表都不为空
            if(l1.val<l2.val){
                temp.next=l1;
                l1=l1.next;
            }else{
                temp.next=l2;
                l2=l2.next;
            }
            temp=temp.next;
        }
        if(l1!=null){
            temp.next=l1;
        }else{
            temp.next=l2;
        }
        return res.next;
    }
}

---

最小覆盖子串（滑动窗口）

题目链接
滑动窗口的核心思路就是反复调整左右边界以实现目的。在本题中如果当前窗口满足条件了（包含t中的所有字符），就收缩左边界直至不满足条件了，然后右边界扩张直至满足条件，如此循环。
来看代码：

public class Solution {
    public string MinWindow(string s, string t) {
        char[] S = s.ToCharArray();
        char[] T = t.ToCharArray();//匹配的时候用这俩数组和字典，截取的时候用 res=s.Substring()
        //字典是这个题的要素，字典内的值有两种，一种是缺省值Int32.MaxValue，用来判断当前字母在t里有没有
        //另一种是会变化的，用来表示滑动窗口内至少应该包含多少个该类字母，如果右边界右扩的时候遇到需要的字母，对应的值就会-1，表示收集到了一个这类字母，而左边界右缩的时候如果遇到了该类字母，对应的值就要+1，表示该类字母在滑动窗口内的需求量+1。
        Dictionary<char,int> dict = new Dictionary<char,int>();
        int l = S.Length;
        int min = Int32.MaxValue;
        string res = "";
        int threshold = 0;
        int cnt = 0;//cnt用于统计当前滑动窗口内的目标字母集齐了多少个，cnt++的触发条件是字典中t里包含的字母对应的数量变为0，即滑动窗口内有和t一样多的该字母
        int left = 0;
        int right = 0;
        for(int i = 0;i< T.Length;i++){
            if(!dict.ContainsKey(T[i])){
                dict.Add(T[i],0);
            }
            int val = dict[T[i]]+1;
            if(val==1)
              threshold++;//指的是有t里有多少种字母
            dict[T[i]]=val;
        }
        while(right<l){
            if(!dict.ContainsKey(S[right])){
                dict.Add(S[right],Int32.MaxValue);
            }
            int rval = dict[S[right]];
            if(rval == Int32.MaxValue){
                right++;
                continue;
            }
            if(--rval==0){//怎么着都要减，如果这个字母的数量减为0了，说明滑动窗口内该字母的数量达到要求，也就是集齐了这个字母
                cnt++;
            }
            dict[S[right]]=rval;
            while(cnt==threshold && left<=right){
                int length = right - left+1;
                if(length<min){
                    min = length;
                    res=s.Substring(left,length);
                }
                int lval = dict[S[left]];
                if(lval==Int32.MaxValue){//如果left指向的字母t里没有，说明没啥用，可以继续缩小左边界
                    left++;
                    continue;
                }
                if(lval==0){//如果left指向的字母在滑动窗口内的数量刚好满足要求，然而left右移会导致滑动窗口内缺一个该字母，导致滑动窗口不满足要求，从而触发当前while循环终止，进入right右扩循环
                    cnt--;
                }
                dict[S[left]]=++lval;//能执行到这里的都是left指向的字母在t里有，left右扩会导致窗口需要更多的该字母，所以字典内对应的值+1
                left++;
            }
            right++;
        }
        return res;
    } 
}

---

Donate