剑指 Offer 19. 正则表达式匹配

.请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof

class Solution {
public:
    
    bool isMatch(string s, string p) {
        int n=s.length();
        int m=p.length();
        vector<vector<bool>> dp(n+1,vector<bool>(m+1,false));

        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++)
            {
                if(j==0){
                    dp[i][j]=i==0;
                }else{
                    if(p[j-1]=='*'){
                        if(j>=2){//0
                            dp[i][j]= dp[i][j]|dp[i][j-2];
                        }
                        if(j>=2&&i>=1&&(s[i-1]==p[j-2]||p[j-2]=='.')){//n
                            dp[i][j]= dp[i][j]|dp[i-1][j];
                        }
                    }else {
                        if(i>=1&&(s[i-1]==p[j-1]||p[j-1]=='.'))
                            dp[i][j]=dp[i-1][j-1];
                    }
                }
            }
        }
        return dp[n][m];
    }
};

动态规划或者递归
不过写得很不顺手， dp[i][j]= dp[i][j]|dp[i-1][j];写成dp[i-1][j-2]改了很久

转移方程
f[i] [j] 代表 A 的前 i 个和 B 的前 j 个能否匹配

对于前面两个情况，可以合并成一种情况 f[i][j] = f[i-1][j-1]

对于第三种情况，对于 c* 分为看和不看两种情况

不看：直接砍掉正则串的后面两个， f[i][j] = f[i][j-2]
看：正则串不动，主串前移一个，f[i][j] = f[i-1][j]
初始条件
特判：需要考虑空串空正则

空串和空正则是匹配的，f[0][0] = truef
空串和非空正则，不能直接定义 true 和 false，必须要计算出来。（比如A= ‘’ ‘’ ,B=abc*）
非空串和空正则必不匹配，f[1][0]=…=f[n][0]=false
非空串和非空正则，那肯定是需要计算的了。

作者：jerry_nju
链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/zhu-xing-xiang-xi-jiang-jie-you-qian-ru-shen-by-je/

剑指 Offer 20. 表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：

若干空格
一个小数或者整数
（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个整数
若干空格
小数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（’+’ 或 ‘-’）
下述格式之一：
至少一位数字，后面跟着一个点 ‘.’
至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
一个点 ‘.’ ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（’+’ 或 ‘-’）
至少一位数字
部分数值列举如下：

["+100", “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]
部分非数值列举如下：

[“12e”, “1a3.14”, “1.2.3”, “±5”, “12e+5.4”]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof

class Solution {
public:
    bool isNumber(string s) {
        int l=s.length();
        int i=0,j=0;
        while(i<l&&s[i]==' '){
            i++;
        }
        if(s[i]=='+'||s[i]=='-')i++;
        while(i<l&&(s[i]>='0'&&s[i]<='9')){
            i++,j++;
        }
        if(j==0){
            if(s[i]!='.'){
                return false;
            }
            i++;
            while(i<l&&(s[i]>='0'&&s[i]<='9')){
                 i++,j++;
            }
            if(j==0)return false;
        
        }else {
            j=0;
            if(s[i]=='.')i++;
            while(i<l&&(s[i]>='0'&&s[i]<='9')){
            i++,j++;
        }
        }
        if(s[i]=='e'||s[i]=='E'){
            i++;
            if(s[i]=='+'||s[i]=='-')i++;
            j=0;
            while(i<l&&(s[i]>='0'&&s[i]<='9')){
            i++,j++;
            }
            if(j==0)return false;
        }
        while(i<l){
            if(s[i]!=' ')return false;
            else i++;
        }
        return true;
        
    }
};

直接模拟，但是不够简洁，判断整数可以写一个函数
看题解有人用状态机，以前只有verilog时写过

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

class Solution {
public:
    void swap(int &a,int &b){
        int c;
        c=a;
        a=b;
        b=c;
    }

    vector<int> exchange(vector<int>& nums) {
        int n=nums.size();
        int l=0,r=n-1;
        while(l<r){
            while(l<r&& (nums[l]&1))l++;
            while(l<r&& !(nums[r]&1))r--;
           // cout<<l<<r<<endl;
            if(l<r){
                swap(nums[l],nums[r]);
                l++;r--;
            }
            
        }
        return nums;
    }
};

快慢双指针或者首尾双指针，时间复杂度O(n)
首尾代码见上
快慢：
定义快慢双指针 fast 和 low ，fast 在前， low 在后 .
fast 的作用是向前搜索奇数位置，low 的作用是指向下一个奇数应当存放的位置
fast 向前移动，当它搜索到奇数时，将它和 nums[low] 交换，此时 low向前移动一个位置 .
重复上述操作，直到 fast 指向数组末尾 .

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int low = 0, fast = 0;
        while (fast < nums.size()) {
            if (nums[fast] & 1) {
                swap(nums[low], nums[fast]);
                low ++;
            }
            fast ++;
        }
        return nums;
    }
};

作者：huwt
链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/solution/ti-jie-shou-wei-shuang-zhi-zhen-kuai-man-shuang-zh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *pre=head,*cur=head;
        for(int i=0;i<k;i++){
            cur=cur->next;
        }
        while(cur!=NULL){
            pre=pre->next;
            cur=cur->next;
        }
        return pre;
    }
    
};

双指针，间隔为k
栈：只要把原链表的结点全部压栈，然后再把栈中最上面的k个节点出栈，出栈的结点重新串成一个新的链表即可
递归

int size;

public ListNode getKthFromEnd(ListNode head, int k) {
    if (head == null)
        return head;
    ListNode node = getKthFromEnd(head.next, k);
    if (++size == k)
        return head;
    return node;
}

作者：sdwwld
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/solution/shu-ju-jie-gou-he-suan-fa-shuang-zhi-zhe-lbju/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。