[数据结构与算法][java刷算法]牛客—剑指offer链表复习、手写简易正则匹配

• 🧛?♂?个人主页：杯咖啡
• 💡进步是今天的活动，明天的保证！
• ?目前正在学习：SSM框架,算法刷题
• 👉本文收录专栏 ： java刷算法牛客—剑指offer
• 🙌牛客网，刷算法过面试的神级网站，用牛客你也牛。 👉免费注册和我一起学习刷题👈
• 🐳希望大家多多支持🥰一起进步呀！
• 😎The man who fears losing has already lost.
  怕输的人已经输了。 - 《权力的游戏》

?今日三剑

JZ17 打印从1到最大的n位数
JZ18 删除链表的节点
JZ19 正则表达式匹配

JZ17 打印从1到最大的n位数

题目描述

思路详解

这里我们考虑到输出的数组，最后的一位数n为几就是几个9。为了方便我们先找出n个10相乘，再减去1，就是我们数组最后一位数了。然后再遍历加入数组就可以。

代码与结果

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 最大位数
     * @return int整型一维数组
     */
    public int[] printNumbers (int n) {
        //找到该n+1位数的最小数字
        int end = 1;
        for(int i = 1; i <= n; i++)
            end *= 10;
        //从1遍历到n+1位数的最小数字输出
        int[] res = new int[end - 1];
        for(int i = 1; i < end; i++)
            res[i - 1] = i;
        return res;
    }
}

JZ18 删除链表的节点

题目描述

思路详解

本题主要考察链表。
思路比较简单，我们只需要遍历找到该节点，之后把该节点的前节点的next，修改为该节点的后节点，那么就跳过了该节点。

代码与结果

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param val int整型 
     * @return ListNode类
     */
    public ListNode deleteNode (ListNode head, int val) {
        //加入一个头节点
        ListNode res = new ListNode(0);
        res.next = head;
        //前序节点
        ListNode pre = res;
        //当前节点
        ListNode cur = head;
        //遍历链表
        while(cur != null){
            //找到目标节点
            if(cur.val == val){
                //断开连接
                pre.next = cur.next;
                break;
            }
            pre = cur;
            cur = cur.next;
        }
        //返回去掉头节点
        return res.next;
    }
}

JZ19 正则表达式匹配

题目描述

思路详解

本题相当于手写了简易正则。
考虑到多种情况，那么我们考虑使用动态规划进行解题。
设dp[i][j]表示str前i个字符和pattern前j个字符是否匹配。（需要注意这里的i，j是长度，比对应的字符串下标要多1）
（初始条件） 首先，毋庸置疑，两个空串是直接匹配，因此dp[0][0]=true。然后我们假设str字符串为空，那么pattern要怎么才能匹配空串呢？答案是利用’‘字符出现0次的特性。遍历pattern字符串，如果遇到’‘意味着它前面的字符可以出现0次，要想匹配空串也只能出现0，那就相当于考虑再前一个字符是否能匹配，因此dp[0][i]=dp[0][i?2]。
（状态转移） 然后分别遍历str与pattern的每个长度，开始寻找状态转移。首先考虑字符不为’‘的简单情况，只要遍历到的两个字符相等，或是pattern串中为’.‘即可匹配，因此最后一位匹配，即查看二者各自前一位是否能完成匹配，即dp[i][j]=dp[i?1][j?1]。然后考虑’‘出现的情况：
pattern[j - 2] == ‘.’ || pattern[j - 2] == str[i - 1]：即pattern前一位能够多匹配一位，可以用’*'让它多出现一次或是不出现，因此有转移方程dp[i][j]=dp[i?1][j]∣∣dp[i][j?2]
不满足上述条件，只能不匹配，让前一个字符出现0次，dp[i][j]=dp[i][j?2].

代码与结果

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        int n1 = str.length();
        int n2 = pattern.length();
        //dp[i][j]表示str前i个字符和pattern前j个字符是否匹配
        boolean[][] dp = new boolean[n1 + 1][n2 + 1];
        //遍历str每个长度
        for(int i = 0; i <= n1; i++){ 
            //遍历pattern每个长度
            for(int j = 0; j <= n2; j++){
                //空正则的情况
                if(j == 0){
                    dp[i][j] = (i == 0 ? true : false);
                //非空的情况下 星号、点号、字符
                }else{
                    if(pattern.charAt(j - 1) != '*'){
                        //当前字符不为*，用.去匹配或者字符直接相同
                        if(i > 0 && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.')){
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    }else{
                        //碰到*
                        if(j >= 2){
                            dp[i][j] |= dp[i][j - 2];
                        }
                        //若是前一位为.或者前一位可以与这个数字匹配
                        if(i >= 1 && j >= 2 && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.')){
                            dp[i][j] |= dp[i - 1][j];
                        }
                    }
                }
            }
        }
        return dp[n1][n2];
  }
}

$原创不易，还希望各位大佬支持一下$

$点赞，你的认可是我创作的动力！$

$收藏，你的青睐是我努力的方向！$

$评论，你的意见是我进步的财富！$