本文主要是介绍求职Leetcode题目（9），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.通配符匹配
题解：
其中，横轴为string s，纵轴为pattern p
这个表第(m,n)个格子的意义是:【p从0位置到m位置】这一整段，是否能与【s从0位置到n位置】这一整段匹配
也就是说，如果表格的下面这一个位置储存的是T(True)：
说明，"adcb"和"a*b"这一段是可以匹配的，你不用管前面发生了什么，你只要知道，这两段是匹配的，这就是动态规划为什么很棒棒
描述：如果这一行是"*"，可以从上一行的任意T出发，向下、右铲平这一行的任意道路
在讲解另一个狠角色"?"之前，我们再往下走两步，巩固一下之前的知识。
接下来我们在pattern里遇到了一个b，它是一个普通字母，所以只能从上一行某个T往右下角走到达，而且字母匹配才能记录T，于是我们发现可以走这两步：
描述：如果这一行是"?"，从上一行某个T也只能向右下角走，但不必匹配字母就能记录T
示例：
class Solution {public boolean isMatch(String ss, String pp) {int n = ss.length(), m = pp.length();// 技巧：往原字符头部插入空格，这样得到 char 数组是从 1 开始，而且可以使得 f[0][0] = true，可以将 true 这个结果滚动下去ss = " " + ss;pp = " " + pp;char[] s = ss.toCharArray();char[] p = pp.toCharArray();// f(i,j) 代表考虑 s 中的 1~i 字符和 p 中的 1~j 字符 是否匹配boolean[][] f = new boolean[n + 1][m + 1];f[0][0] = true;for (int i = 0; i <= n; i++) {for (int j = 1; j <= m; j++) {if (p[j] == '*') {f[i][j] = f[i][j - 1] || (i - 1 >= 0 && f[i - 1][j]);} else {f[i][j] = i - 1 >= 0 && f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '?');}}}return f[n][m];}
}2.解码方法
我们先来理解一下题目的解码规则，如样例所示，s = "226"，可以分为两种情况：
1、将每一位数字单独解码，因此可以解码成"BBF"(2 2 6)。
2、将相邻两位数字组合起来解码（组合的数字范围在10 ~ 26之间），因此可以解码成"BZ"(2 26), "VF"(22 6)。
两种情况是或的关系，互不影响，将其相加，那么226共有3种不同的解码方式，下面来讲解动态规划的做法。
状态表示：f[i]表示前i个数字一共有多少种解码方式，那么，f[n]就表示前n个数字一共有多少种不同的解码方式，即为答案。
设定字符串数组为s[](数组下标从1开始)，考虑最后一次解码方式，因此对于第i - 1和第i 个数字，分为两种决策：
1、如果s[i]不为0，则可以单独解码s[i]，由于求的是方案数，如果确定了第i个数字的翻译方式，那么解码前i个数字和解码前i - 1个数的方案数就是相同的，即f[i] = f[i - 1]。(s[]数组下标从1开始)
2、将s[i]和s[i - 1]组合起来解码（ 组合的数字范围在10 ~ 26之间 ）。如果确定了第i个数和第i - 1个数的解码方式，那么解码前i个数字和解码前i - 2个数的方案数就是相同的，即f[i] = f[i - 2]。(s[]数组下标从1开始)
最后将两种决策的方案数加起来，因此，状态转移方程为： f[i] = f[i - 1] + f[i - 2]。
class Solution {public int numDecodings(String s) {int n = s.length();int[] f = new int[n + 10];f[0] = 1;for(int i = 1; i <= n;i ++){if(s.charAt(i - 1) != '0') f[i] = f[i - 1]; //单独解码s[i - 1]if(i >= 2){int t = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';if(t >= 10 && t <= 26) f[i] += f[i - 2]; //将s[i - 2] 和 s[i - 1]组合解码}}return f[n];}
}3.反转链表 ||
这里首先讲解一下如何反转一个链表
public ListNode reverseList(ListNode head) { //1ListNode prev = null; // 2ListNode curr = head; // 3while (curr != null) { //4ListNode nextTemp = curr.next; //5curr.next = prev; // 6 prev = curr; //7curr = nextTemp; //8} return prev; //9
}
第一行代码图解
public ListNode reverseList(ListNode head) { //1我们顺着题目描述意思，假设链表就有1、2、3个元素吧，后面还跟着一个null，又因为输入是ListNode head，所以这个即将要反转的链表如下:
ListNode prev = null; // 2将null赋值给prev，即prev指向null，可得图如下：
ListNode curr = head;将链表head赋值给curr，即curr指向head链表，可得图如下：
循环部分代码图解
while (curr != null) { //4ListNode nextTemp = curr.next; //5curr.next = prev; // 6 prev = curr; //7curr = nextTemp; //8}
循环部分是链表反转的核心部分，我们先走一遍循环，图解分析一波。
因为curr指向了head，head不为null，所以进入循环。先来看第5行：
ListNode nextTemp = curr.next; //5把curr.next 赋值给nextTemp变量，即nextTemp 指向curr的下一节点（即节点2），可得图如下：
curr.next = prev; // 6 
然后我们看执行到第7行
prev = curr; //7把curr赋值给prev，prev指向curr，图解如下：
接着，我们执行到第8行：
curr = nextTemp; //8 把nextTemp赋值给curr，即curr指向nextTemp，图解如下：
至此，第一遍循环执行结束啦，回到循环条件，curr依旧不为null，我们继续图解完它。
执行完ListNode nextTemp = curr.next;后：
执行完curr.next = prev;后：
大概是这么个思路，依次循环。
接下来详细讲解本题：
- 第 1 步：先将待反转的区域反转；
- 第 2 步：把 pre 的 next 指针指向反转以后的链表头节点，把反转以后的链表的尾节点的 next 指针指向 succ
接下来是这道题的完整代码：
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {// 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论ListNode dummyNode = new ListNode(-1);dummyNode.next = head;ListNode pre = dummyNode;// 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点// 建议写在 for 循环里，语义清晰for (int i = 0; i < left - 1; i++) {pre = pre.next;}// 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点ListNode rightNode = pre;for (int i = 0; i < right - left + 1; i++) {rightNode = rightNode.next;}// 第 3 步：切断出一个子链表（截取链表）ListNode leftNode = pre.next;ListNode curr = rightNode.next;// 注意：切断链接pre.next = null;rightNode.next = null;// 第 4 步：同第 206 题，反转链表的子区间reverseLinkedList(leftNode);// 第 5 步：接回到原来的链表中pre.next = rightNode;leftNode.next = curr;return dummyNode.next;}private void reverseLinkedList(ListNode head) {// 也可以使用递归反转一个链表ListNode pre = null;ListNode cur = head;while (cur != null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}}
}
这篇关于求职Leetcode题目（9）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
