文章目录
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]; } }
