剑指 Offer（第 2 版）7/12 18-20

1.剑指 Offer 18. 删除链表的节点 简单

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
 class Solution {
    
        public ListNode deleteNode(ListNode head, int val) {
    
            if (head.val == val)return head.next;
            ListNode temp = head;
            while (temp != null){
    
                if (temp.next != null && temp.next.val == val){
    
                    temp.next = temp.next.next;
                    return head;
                }
                temp = temp.next;
            }
            return head;
        }
    }

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

class Solution {
    
        public boolean isMatch(String s, String p) {
    
            int n = s.length();
            int m = p.length();
            //dp[i][j] 表示s中以i为末尾，p中以j为末尾的串可以互相匹配
            boolean[][] dp = new boolean[n + 1][m + 1];
            //初始化
            dp[0][0] = true;//s为空且p为空表示可以匹配成功
            for (int i = 1; i <= m; i++) {
    
                if (p.charAt(i - 1) == '*')dp[0][i] = dp[0][i - 2];
            }
            for (int i = 1; i <= n; i++) {
    
                for (int j = 1; j <= m; j++) {
    
                    if (p.charAt(j - 1) == '*'){
    
                        dp[i][j] = dp[i][j - 2] //不需要*与前面的一个字母也能匹配时
                        ||
                        //s中前i-1个字母与p中前j个字母匹配，且可以重复p中的前一个字母时
                        (dp[i - 1][j] && (p.charAt(j - 2) == '.' || s.charAt(i - 1) == p.charAt(j - 2)));
                    }else if (p.charAt(j - 1) == '.'){
    
                        dp[i][j] = dp[i - 1][j - 1];
                    }else {
    
                        //p中第j个字符是普通字母
                        //如果s中第i个字母与p中第j个字母相同 && dp[i - 1][j - 1]前面的串也互相匹配则可置为true
                        dp[i][j] = (s.charAt(i - 1) == p.charAt(j - 1)) && dp[i - 1][j - 1];
                    }
                }
            }
            return dp[n][m];
        }
    }

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

暴力 逐个条件判断

class Solution {
    
        public boolean isNumber(String s) {
    
            boolean res = false;
            s = s.trim();//去除前后空格
            if (s.length() == 0)return false;//特殊情况
            //一个数值的三个部分: 整数/小数 + e + 整数
            int i = 0;
            //寻找e的位置
            for (i = 0; i < s.length(); i++) {
    
                if (s.charAt(i) == 'e' || s.charAt(i) == 'E')break;
            }
            if (i < s.length()){
    //代表存在e
                //判断e之前是否合法，当满足小数或整数时合法
                if (!(isZhengShu(s,0,i - 1) || isXiaoShu(s,0,i - 1)))return false;
                //e之后是否合法
                if (i + 1 >= s.length())return false;//e之后无数字
                return isZhengShu(s,i + 1,s.length() - 1);
            }else {
    //代表不存在e符号
                //只需判断整个串是否满足数值或小数
                return isZhengShu(s,0,s.length() - 1)
                        || isXiaoShu(s,0,s.length() - 1);
            }
        }

        //判断是否为整数
        private boolean isZhengShu(String s, int start, int end) {
    
            if (start > end)return false;//防止e之前没有数值
            boolean flag = false;//开头是否存在正负号
            if (s.charAt(start) == '-' || s.charAt(start) == '+')flag = true;
            if (flag){
    //以正负号开头
                start++;//start指针后移扫面下一个字符
                if (start > end)return false;//只有一个正负号,不符合整数
                for (int i = start; i <= end; i++) {
    
                    if (!(s.charAt(i) >= '0' && s.charAt(i) <= '9'))return false;
                }
            }else {
    //不已正负号开头
                for (int i = start; i <= end; i++) {
    
                    if (!(s.charAt(i) >= '0' && s.charAt(i) <= '9'))return false;
                }
            }
            return true;
        }
        //判断是否为小数
        private boolean isXiaoShu(String s, int start, int end) {
    
            if (start > end)return false;
            boolean flag = false;//开头是否存在正负号
            if (s.charAt(start) == '-' || s.charAt(start) == '+')flag = true;
            int count = 0;//小数点的数量
            if (flag){
    //以正负号开头
                start++;//start指针后移扫面下一个字符
                if (start > end)return false;//只有一个正负号,不符合语法
                for (int i = start; i <= end; i++) {
    
                    if (!((s.charAt(i) >= '0' && s.charAt(i) <= '9')  || s.charAt(i) == '.'))return false;
                    if (s.charAt(i) == '.'){
    
                        if (count == 0){
    
                            count++;
                            //只要 . 前后至少有一个数字则合理
                            if (!((i - 1 >= start && (s.charAt(i - 1) >= '0' && s.charAt(i - 1) <= '9'))
                                    || (i + 1 <= end && (s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9'))))return false;

                        }else {
    
                            return false;
                        }
                    }
                }
            }else {
    //不已正负号开头
                for (int i = start; i <= end; i++) {
    
                    if (!((s.charAt(i) >= '0' && s.charAt(i) <= '9')  || s.charAt(i) == '.'))return false;
                    if (s.charAt(i) == '.'){
    
                        if (count == 0){
    
                            count++;
                            //只要 . 前后至少有一个数字则合理
                            if (!((i - 1 >= start && (s.charAt(i - 1) >= '0' && s.charAt(i - 1) <= '9'))
                                    || (i + 1 <= end && (s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9'))))return false;

                        }else {
    
                            return false;
                        }
                    }
                }
            }
            return true;
        }
    }