“Limitations live only in our minds. But if we use our imaginations, our possibilities become limitless.”
1. 二维数组的查找
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解决思路：
思路1： 将每一行看成是有序递增的数组，利用二分查找，通过遍历每一行得到答案，时间复杂度是nlogn。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public boolean Find(int target, int [][] array) {
boolean result = false;
int rows = array.length;
for(int i = 0; i < rows; i++){
//1. 可以利用Arrays.binarySearch方法
// int status = Arrays.binarySearch(array[i], target);
// if(status >= 0){
// result = true;
// break;
// }
//2. 自己实现二分查找
int low = 0;
int high = array[i].length - 1;
while(low <= high){
int mid = (low + high) >>> 1;
if(target > array[i][mid])
low = mid + 1;
else if(target < array[i][mid])
high = mid - 1;
else
return true;
}
}
return result;
}
思路2： 因为矩阵是有序的，从左下角来看，向上数字递减，向右数字递增。所以从左下角元素往上查找，右边元素是比这个元素大，上边的元素是比这个元素小。所以，target比这个元素小就往上找，比这个元素大就往右找。如果出了边界，则说明二维数组中不存在target这个元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean Find(int target, int [][] array) {
int rows = array.length;
int cols = array[0].length;
int i=rows-1,j=0;
while(i>=0 && j<cols){
if(target<array[i][j])
i--;
else if(target>array[i][j])
j++;
else
return true;
}
return false;
}
2. 替换空格
题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解决思路：(很明显，这里不是考察java的replaceAll函数，那样将毫无意义)
思路1：利用StringBuilder/StringBuffer的append拼接函数(将字符串转换为字符数组，再将字符进行拼接与之同样道理)
1
2
3
4
5
6
7
8
9
10
11
12
public static String replaceSpace(StringBuffer str){
if(str == null) return null;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < str.length(); i++){
if(String.valueOf(str.charAt(i)).equals(" ")){
sb.append("%20");
}else{
sb.append(str.charAt(i));
}
}
return sb.toString();
}
思路2： 我们先遍历一次字符串，找到字符串中空格的数目，然后计算出替换后的新字符串的长度，每替换一个空格，字符串长度增加2(这里使用str.setLength()方法来扩大str的长度，也可以通过当每次遍历到一个空格时，在字符串尾部填充两个任意字符使得字符串的长度等于替换后的长度)。然后我们从字符串后面开始复制，准备两个指针，indexOld和indexNew。indexNew指向新字符串的末尾，indexOld指向旧字符串的末尾。通过向前移动indexOld完成字符复制的过程，每个字符只需要移动一次，效率会更高一点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static String replaceSpace(StringBuffer str){
if(str == null || str.length() <= 0){
return "";
}
int spaceNum = 0; //统计字符串出现空格的次数
for(int i = 0; i < str.length(); i++){
if(str.charAt(i) == ' ')
spaceNum++;
}
int indexOld = str.length() - 1; //indexOld为替换前的str下标
int newLength = str.length() + 2 * spaceNum; //计算空格换成%20之后的str下标
int indexNew = newLength - 1; //indexNew为把空格替换为%20之后的str下标
str.setLength(newLength); //使得str的长度扩大到转换成%20之后的长度，防止下标越界
for(;indexOld >= 0 && indexOld < indexNew;--indexOld){
if(str.charAt(indexOld) == ' '){
str.setCharAt(indexNew--, '0');
str.setCharAt(indexNew--, '2');
str.setCharAt(indexNew--, '%');
}else{
str.setCharAt(indexNew--, str.charAt(indexOld));
}
}
return str.toString();
}
3. 从尾到头打印链表
题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList.
解题思路：
思路1：当我看到题目第一眼，脑海里想的是这其实就是一个翻转问题，要么翻转链表，要么对遍历链表后的ArrayList进行翻转,所以我给出了下面的解决方案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ArrayList<Integer> printListFromTailToHead(ListNode listNode){
ArrayList<Integer> temp = new ArrayList<Integer>();
if(listNode == null){
return temp;
}
if(listNode.next == null){
temp.add(listNode.val);
return temp;
}
ListNode tempNode = listNode;
while(tempNode != null){
temp.add(tempNode.val);
tempNode = tempNode.next;
}
Collections.reverse(temp); //利用java.util.Collections类
return temp;
}
思路2： 链表反转(刚好这里说一下利用迭代法反转单链表的思路——所谓的单链表反转，就是把每个节点的指针域由原来的指向下一个节点变为指向前一个节点。但是由于单链表没有指向前一个节点的指针域，因此我们需要增加一个指向前一个节点的指针pre,用于存储每一个节点的前一个节点。此外，还需要定义一个保存当前节点的指针cur,以及下一个节点的next。定义好这三个指针后，遍历单链表，将当前节点的指针域指向前一个节点，之后将定义三个指针往后移动，直至遍历到最后一个节点停止。)再依次遍历链表存储到ArrayList.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<Integer>();
ListNode pre = null; //前一个节点指针
ListNode cur = listNode;
ListNode next = null; //下一个节点指针
while(cur != null){
next = cur.next; //next 指向下一个节点
cur.next = pre; //将当前节点的next域指向前一个节点
pre = cur; // pre指针向后面移动
cur = next; // cur指针向后面移动
}
//遍历链表获取结果
while(pre != null){
list.add(pre.val);
pre = pre.next;
}
return list;
}
思路3：借助于栈的先进后出特点，遍历的时候入栈，完了弹栈加入到ArrayList中。
1
2
3
4
5
6
7
8
9
10
11
12
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<Integer>();
Deque<Integer> stack = new ArrayDeque<Integer>();
while (listNode != null){
stack.push(listNode.val);
listNode = listNode.next;
}
while(!stack.isEmpty()){
list.add(stack.pop());
}
return list;
}
思路4： 递归解法，本质上其实也是一个栈结构，要实现反过来输出链表，我们每访问到一个节点的时候，先递归输出它后面的节点，再输出该节点本身即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<>();
helper(list,listNode);
return list;
}
private void helper(ArrayList<Integer> res, ListNode head){
if(head != null){
if(head.next != null){
helper(res,head.next);
}
res.add(head.val);
}
}
4. 重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假如输入的前序遍历和后序遍历的结果都不包含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
解题思路：(二叉树天然的递归特性，使得我们可以利用递归算法对二叉树进行遍历和重建)
思路1：在二叉树的前序遍历序列(
根-左-右)中，第一个数字总是树的根节点的值。但在中序遍历序列(左-根-右)中，根节点的值在序列的中间，左子树的节点的值位于根节点的值的左边，而右子树的节点的值位于根节点的值的右边。因此，我们需要扫描中序遍历序列，确定出左右子树。以给出的题目为例子：前序遍历序列的第一个数字1就是根节点的值。扫描中序遍历序列，就能确定根节点的值的位置，根据中序遍历的特点，在根节点的值1前面的3个数字都是左子树节点的值，位于1后面的数字都是右子树节点的值。由于在中序遍历序列中，有3个数字是左子树节点的值，因此左子树总共有3个左子节点。同样，在前序遍历的系列中，根节点后面的3个数字就是3个左子树节点的值，再后面的所有数字就是右子树节点的值。所以，这样就在前序和中序遍历的两个序列中，分别找到了左右子树对应的子序列。我们已经分别找到了左右子树的前序遍历和中序遍历，这样我们就可以用同样的办法去构建左右子树，实现递归。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public TreeNode reConstuctBinaryTree(int[] pre, int[] in){
TreeNode root = reConstructBinaryTree(pre,0, pre.length - 1,in, 0, in.length - 1);
return root;
}
//前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
private TreeNode reConstructBinaryTree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd){
if(preStart > preEnd || inStart > inEnd){
return null;
}
TreeNode root = new TreeNode(pre[preStart]); //根节点是数组的第一个
for(int i = inStart; i <= inEnd; i++){
if(in[i] == pre[preStart]){ //找到二叉树根节点
//左子树，其中i- inStart为中序排序中左子树节点的个数，preStart + 它，就是前序中左子树结束节点在前序数组中的索引，i - 1就是中序的左子树末端节点索引
root.left = reConstructBinaryTree(pre, preStart+1, preStart+i-inStart, in, inStart, i - 1);
//右子树，类似，[前序最左节点的索引](i - inStart + preStart) + 1,为右子树根节点索引， i+1 为右子树的起始中序节点索引
root.right = reConstructBinaryTree(pre, preStart + i - inStart + 1, preEnd, in, i+1, preEnd);
}
}
return root;
}
或许有些人说这个找起始索引的过程有点晕，为了让你稍微清晰的了解一下，我们可以通过在迭代过程中传入相当于提取出来的左右子树的方式(以内存空间增加的方法突出清晰的表现)，给出以下解题代码。(理论都是一样的)
1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length == 0 || in.length == 0){
return null;
}
TreeNode node = new TreeNode(pre[0]);
for(int i = 0; i < in.length; i++){
if(pre[0] == in[i]){
node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1,in.length));
}
}
return node;
}
当然，还有一种优化策略，利用HashMap存储值和索引，使得查找根节点时速度加快。如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.HashMap;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre == null || in == null){
return null;
}
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i=0;i<in.length;i++){
map.put(in[i],i);
}
return preIn(pre, 0, pre.length-1, in, 0, in.length-1, map);
}
public TreeNode preIn(int[] pre, int p1, int p2, int[] in, int i1, int i2, HashMap<Integer,Integer> map){
if(p1>p2){
return null;
}
TreeNode parent = new TreeNode(pre[p1]);
int parentInIndex = map.get(pre[p1]);
parent.left = preIn(pre, p1+1, p1+parentInIndex-i1, in, i1, parentInIndex-1, map);
parent.right = preIn(pre, p1+parentInIndex-i1+1, p2, in, parentInIndex+1, i2, map);
return parent;
}
}
那么，除了这种递归调用的方法之外，有没有别的方法来解决这个问题呢？给出思路2的解法如下：
思路2：让前序遍历的序列拥有中序遍历的索引，在遍历(前序遍历)的过程中按照二叉排序树的方法插入即可。
原理解释：(参考自(数据结构：关于重建二叉树的三种思路)[https://blog.csdn.net/lemon_tree12138/article/details/49798221])
给出具体数据的例子如下所示：
- 前序： A B D E H I C F G
- 中序： D B H E I A F C G
则让前序遍历拥有中序遍历的索引表如下所示(Index很直观，就是取了某一个节点的下标，并保存)：
| 序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 前序 | A | B | D | E | H | I | C | F | G |
| INDEX | 5 | 1 | 0 | 3 | 2 | 4 | 7 | 6 | 8 |
| 中序 | D | B | H | E | I | A | F | C | G |
其实在已知的遍历序列中，如果含有中序遍历结果，那么我们都可以直接采用上面的这种创建索引函数的方式来简化重建过程。具体原因解释之前我们先来看一下下图：
我们可以把之前的中序遍历二叉树过程平摊开，就可以获取上图这样的一个顺序序列。从上图我们可以发现这样一个现象，那就是某一个节点的左孩子一定是在这个节点的左边，其右孩子一定是在这个节点的右边(中序遍历的定义)，也就是节点Node的左孩子left的值(index)一定是比Node的值小，而Node右孩子Right的值一定是比Node的值大。
很明显，二叉排序树正是这样定义的。这样，我们来看一下二叉树的前序遍历。因为是前序，所以我们在遍历节点Node的孩子节点之前，必定是已经遍历过Node节点。这样也可以理解成是一种临近遍历的过程。这样前序 + 中序 = 二叉排序树，所以我们可以重建二叉排序树。(延伸到该题，解法代码如下所示：)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.*;
public class Solution {
TreeNode root = null;
Map<Integer,Integer> indexMap = new HashMap<>();
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
int[] index = recordArray(pre, in);
if(root == null){
root = new TreeNode(pre[0]);
}
//构建前序遍历元素与索引之间的映射
for(int i = 0; i < pre.length; i++){
indexMap.put(pre[i],index[i]);
TreeNode insertNode = new TreeNode(pre[i]);
insert(insertNode);
}
return root;
}
private void insert(TreeNode insertNode){
TreeNode currentNode = root;
while(true){
if(indexMap.get(insertNode.val) < indexMap.get(currentNode.val)){
if(currentNode.left == null){
currentNode.left = insertNode;
break;
}else {
currentNode = currentNode.left;
}
}else if(indexMap.get(insertNode.val) > indexMap.get(currentNode.val)){
if(currentNode.right == null){
currentNode.right = insertNode;
break;
}else{
currentNode = currentNode.right;
}
}else{
break;
}
}
}
private int[] recordArray(int[] pre, int[] in){
if(pre == null || pre.length == 0 || in == null || in.length == 0){
return null;
}
int[] record = new int[pre.length];
for(int i = 0; i < pre.length; i++){
record[i] = index(in, pre[i]);
}
return record;
}
//计算前序遍历元素在中序遍历数组中的位置
private int index(int[] in, int label){
for(int i = 0; i < in.length; i++){
if(label == in[i]){
return i;
}
}
return -1;
}
}
最后，补充一下关于二叉树的一些相关概念：
5. 用两个栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。
解题思路：
两个栈stack1和stack2,开始时，每次添加队尾元素到stack1中。当弹出时，当 stack2 不为空，弹出 stack2 栈顶元素，如果 stack2 为空，将 stack1 中的全部数逐个出栈入栈 stack2，再弹出 stack2 栈顶元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if(stack1.empty()&&stack2.empty()){
throw new RuntimeException("Queue is empty!");
}
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
6. 旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1.(NOTE: 给出的所有元素都大于0，若数组大小为0，请返回0)。
解题思路：(非递减排序数组，很明显得出本题想要考的是二分法，但是为了展示解题的解法，这里给出几种解题的方法。)
Note: 非递减数组的含义是指对每一个元素均有array[i] <= array[i+1]。
思路1：暴力法直接寻找，因为在两段范围内都是非递减排序，当不符合这个规律时，就找到了最小数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int n = array.length;
if(n == 0){
return 0;
}
for(int i=0;i<n-1;i++){
if(array[i] >array[i+1]){
return array[i+1];
}
}
return array[0];
}
}
思路2：排序法，利用Arrays工具类的排序函数，默认的排序规则是从小到大，排序后的数组的第一个值就是最小值。
1
2
3
4
5
6
7
public int minNumberInRotateArray(int[] array){
if(array.length == 0){
return 0;
}
Arrays.sort(array);
return array[0];
}
思路3：利用优先队列，将数组元素挨着丢进优先队列，优先队列默认为最小堆，弹出的第一个数就是整个数组的最小值。
1
2
3
4
5
6
7
8
9
10
11
public int minNumberInRotateArray(int[] array){
int n = array.length;
if(n == 0) {
return 0;
}
PriorityQueue<Integer> queue = new PriorityQueue<>();
for(int i = 0; i < n; i++){
queue.add(array[i]);
}
return queue.poll();
}
思路4：利用二分法进行求解。旋转后的数组实际上可以划分为两个有序的数组——前面子数组的大小都大于后面子数组中的元素。注意到实际上最小的元素就是两个子数组的分界线。本题目给出的数组在一定程度上是排序的，因此我们试着用二分查找法寻找这个最小的元素。
具体思路如下：
- 我们用两个指针left,right分别指向数组的第一个元素和最后一个元素。按照题目的旋转的规则，第一个元素应该是大于最后一个元素的(假设没有重复的元素时)，但是如果不是旋转，第一个元素肯定小于最后一个元素。
- 找到数组的中间元素。中间元素大于第一个元素，则中间元素是属于前面的递增子数组，此时最小元素位于中间元素的后面。我们可以让第一个指针left指向中间元素，移动之后，第一个指针仍然位于前面的递增数组中；当中间元素小于第一个元素，则中间元素是属于后面的递增子数组，此时最小元素位于中间元素的前面。我们可以让第二个指针right指向中间元素，移动之后，第二个指针仍然位于后面的递增数组中，这样就可以缩小寻找的范围。
- 按照上述思路，第一个指针left总是指向前面递增的元素，第二个指针right总是指向后面递增的数组元素。为此，
最终第一个指针将指向前面数组的最后一个元素，第二个指针指向后面数组的第一个元素。也就是说他们将指向两个相邻的元素，而第二个指针指向的刚好是最小的元素，这也是循环的结束条件。 - 上面是在
没有重复元素的假设下进行的，然而现实情况是有特殊情况的，比如：{1,0,1,1,1}和{1,1,1,0,1}都可以看成是递增排序数组{0,1,1,1,1}的旋转。在这种情况下，我们就没法利用上面提到的解法去解决，因为在这两个数组中第一个数字、最后一个数字、中间数字都是1。第一种情况下，中间数字位于后面的子数组，第二种情况下，中间数字位于前面的子数组。因此当两个指针指向的数字和中间数字相同的时候，我们无法确定中间数字1是属于前面还是属于后面的子数组，因此也就无法移动指针来缩小查找的范围。为此，就需要通过线性查找的方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public int minNumberInRotateArray(int[] array){
int size = array.length;
if(size == 0){
return 0;
}
int left = 0;
int right = size - 1;
int mid = 0;
//array[left] >= array[right] 确保数据旋转
while(array[left] >= array[right]){
//分界点
if(right - left == 1){
mid = right;
break;
}
mid = left + (right - left) / 2;
//array[left], array[right], array[mid]三者相等的时候，无法确定中间元素是属于前面还是后面的递增子数组，只能顺序查找
if (array[left] == array[right] && array[left] == array[mid]){
return MinOrder(array,left,right);
}
//中间元素位于前面的递增子数组，此时最小的元素位于中间元素的后面
if(array[mid] >= array[left]){
left = mid;
}
else{
//中间元素位于后面的递增子数组，此时最小元素位于中间元素的前面
right = mid;
}
}
return array[mid];
}
private int MinOrder(int[] array, int left, int right){
int result = array[left];
for(int i = left + 1; i < right; i++){
if(array[i] < result){
result = array[i];
}
}
return result;
}
感觉上面的文字描述太过于复杂繁琐，为此，给出同样思路的另一种解释说明如下：
采用二分法解答这个问题，mid = low + (high - low)/2,需要考虑三种情况：
- array[mid] > array[high]:出现这种情况的array类似于{3,4,5,6,0,1,2}，此时最小数字一定在mid的右边，所以low = mid + 1;
- array[mid] == array[high]：出现这种情况array类似于{1,0,1,1,1}或者{1,1,1,0,1}，此时最小数字不好判断在mid的右边还是左边，这时只好一个一个尝试，所以high = high - 1;
- array[mid] < array[high]:出现这种情况的array类似于{2,2,3,4,5,6,6}，此时最小数字一定是在mid的左边，因为右边必然是递增的，所以high = mid。
注意：如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字。比如array = [4,6],array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ; 如果high = mid - 1，就会产生错误， 因此high = mid,但是low = mid + 1就不会出错。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int minNumberInRotateArray(int [] array) {
int low = 0 ; int high = array.length - 1;
while(low < high){
if(array[low] < array[high]){
return array[low];
}
int mid = low + (high - low) / 2;
if(array[mid] > array[high]){
low = mid + 1;
}else if(array[mid] == array[high]){
high = high - 1;
}else{
high = mid;
}
}
return array[low];
}
7. 斐波那契数列
题目描述
大家都知道斐波那契数列，现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始，第0项为0， n<=39>)。
解题思路：
思路1：常用的递归法。斐波那契数列的标准公式为：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*），根据公式直接写出答案。
1
2
3
4
5
6
7
8
public class Solution {
public int Fibonacci(int n) {
if(n<=1){
return n;
}
return Fibonacci(n-1) + Fibonacci(n-2);
}
}
还有一种尾递归的解决思路，如下所示：(但是实际上JVM并没有对尾递归进行优化)
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int Fibonacci(int n) {
return Fibonacci(n,0,1);
}
private static int Fibonacci(int n,int acc1,int acc2){
if(n==0) return 0;
if(n==1) return acc2;
else
return Fibonacci(n - 1, acc2, acc1 + acc2);
}
}
思路2：迭代法。很明显递归容易超时，那是递归在计算的时候，计算过很多次已经计算过的结果，可以保存下来。迭代的时候，只关注当前的数的前一个和前两个，每次用变量临时纪录起来，那么只需相加即可，而不是像递归那样重复计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int Fibonacci(int n) {
if(n <= 1){
return n;
}
int sum = 0;
int two = 0;
int one = 1;
for(int i=2;i<=n;i++){
sum = two + one;
two = one;
one = sum;
}
return sum;
}
}
我们在观察上面的代码其实可以发现，sum只在每次计算第n项的时候用一下，其实还可以用sum来存储第n-1项，例如当计算完 f(5) 时 sum 存储的是 f(5) 的值，当需要计算 f(6) 时，f(6) = f(5) + f(4)，sum 存储的 f(5)，f(4) 存储在 one 中，由 f(5)-f(3) 得到。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
public int Fibonacci(int n) {
if(n <= 1){
return n;
}
int sum = 1;
int one = 0;
for(int i=2;i<=n;i++){
sum = sum + one;
one = sum - one;
}
return sum;
}
//或者更简洁的写法
public int FibonacciOptimize2(int n)
{
int f = 0, g = 1;
while(n -- > 0)
{
g += f;
f = g - f;
}
return f;
}
}
思路3：矩阵链乘法。具体思路查看下面文章。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//简单实现方阵的乘法
public static int[][] matrixMul(int[][] m, int[][] n){
int[][] ret = new int[m.length][m.length];
for(int i = 0; i < m.length; i++){
for(int j = 0; j < m.length; j++){
for(int k = 0; k < m.length; k++){
ret[i][j] += m[i][k]*n[k][j];
}
}
}
return ret;
}
// 矩阵的快速幂
public static int[][] matrixPow(int[][] m, int n){
//构建2*2单位矩阵
int[][] ret = { { 1,0 }, { 0,1 } };
while (n > 0){
if((n & 1) > 0){
ret = matrixMul(m,ret);
}
m = matrixMul(m,m);
n >>= 1;
}
return ret;
}
public static int Fibonacc(int n){
if(n == 0){
return 0;
}
int[][] matrix = { {1,1}, {1,0} };
int[][] unit = { {1,0},{0,0} };
int[][] ret = matrixMul(matrixPow(matrix, n-1),unit);
return ret[0][0];
}
8. 跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
解题思路：
思路1：按照斐波那契数列的解题思路。
分析：青蛙每次只有一阶或者两阶两种跳法，那么：
- 假设第一次跳的是一阶，那么剩下的n-1个台阶，跳法是f(n-1)
- 假设第一次跳的是两阶，那么剩下的n-2个台阶，跳法是f(n-2)
- 由以上两种假设可得：f(n) = f(n-1) + f(n-2)
- 由实际情况可知：f(1) = 1, f(2) = 2。为此，可以得出这是一个斐波那契数列问题。
1
2
3
| 1, n = 1
f(n) = | 2, n = 2
| f(n-1) + f(n-2)
为此，就可以采用上一题的解决方案(矩阵的快速幂、递归、动态规划)，给出其中一种方案如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public int JumpFloor(int target) {
if(target <= 2){
return target;
}
int pre2 = 1, pre1 = 2;
for (int i = 3; i <= target; i++){
int cur = pre2 + pre1;
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
}
思路2：排列组合
青蛙可以跳上1级台阶，也可以跳上2级台阶。对于n级台阶来说，青蛙它最多可以跳n/2次2级台阶，也就是说总的跳法数是跳0次2级台阶跳法，1次2级台阶跳法，2次2级跳阶跳法…n/2次2级台阶跳法数的总和。现在问题就变成了求跳指定次数2级台阶的跳法数。
假设有n级台阶，指定要跳m次2级台阶，还剩下n-2m个1级台阶，则青蛙一共要跳n-2m+m = n-m次才能跳完。即在n-m从跳跃中选择m次跳2级台阶，有多少种跳法数呢？C(n-m,m)种。所以我们求出C(n-1,1),C(n-2,2),C(n-3,3),..,C(n-n/2,n/2)，然后将其相加，记得再加上1(选0个2级台阶，1中跳法),也就是总的跳法数。
其实，计算上述公式可以存在一定的优化策略：
- 如果C(n,m)的结果用java的int类型存储，则最大值为2^31^-1，如果按照公式依次计算分子和分母，可能分子或分母会超过2^31^-1，从而造成异常。所以优化为分子和分母的计算同步进行，当判断分子除以分母可以除整的时候，就先相除，避免累计数过大。后面的代码会有对应注释;
- 可以省略的计算就省略.比如求解C(5,4)，其中的4 * 3 * 2，分子分母可以直接相约，本来分子分母的计算都需要连乘4次，现在只需要连乘1次.
给出代码实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//求解C(n,m)
public static int c(int n, int m){
int count = m;
int nf = 1, mf = 1;
if(m >= n-m+1){
//对应优化2，只需要连乘以n-m次
count = n - m;
}
for(int i = 0; i < count; i++){
nf *= (n - i);
mf *= (i+1);
//对应优化1，可以整除的时候就先除
if(nf % mf == 0){
nf = nf / mf;
mf = 1;
}
}
return nf / mf;
}
public static int jumpFloor(int number){
int ret = 1;
int count = number / 2;
for (int i = 1; i <= count; i++) {
ret += c(number-i,i);
}
return ret;
}
参考文章：
9. 变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解题思路
分析：用f(n)表示青蛙跳上n阶台阶的跳法数，设定f(0) = 1;
- 当n = 1时，只有一种跳的方式，一阶跳,f(1) = 1;
- 当n = 2时，有两种跳的方式，一阶跳或者二阶跳,f(2) = 2;
- 当n = 3时，有三种跳的方式，第一次跳出一阶后，后面还有f(3-1)中跳法；第一次跳出二阶后，后面还有f(3-2)中跳法；第一次跳出三阶后，后面还有f(3-3)种跳法，f(3) = f(2) + f(1) + f(0) = 2 + 1 + 1 = 4;
- 当n = n时，第一次跳出一阶后，后面还有f(n-1)中跳法； 第一次跳出二阶后，后面还有f(n-2)中跳法……第一次跳出n阶后，后面还有 f(n-n)中跳法，即：f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-n) = f(0) + f(1) + … + f(n-1).
又因为f(n-1) = f(0) + f(1) + … + f(n-2)，所以两个式子相减得到：f(n) = 2 * f(n-1) (n >= 2).所以：
1
2
3
| 0, n = 0
f(n) = | 1. n = 1
| 2*f(n-1), n >= 2
给出代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
public static int jumpFloor(int target) {
if (target <= 0) return 0;
if (target == 1) return 1;
int a = 1;
int b = 2;
for (int i = 2; i <= target; i++) {
b = 2 * a;
a = b;
}
return b;
}
其实，更快的解法是f(n) = 2^(n-1)的递推公式
1
2
3
4
5
6
7
8
public class Solution {
public int JumpFloorII(int target) {
// if(target < 0)return 0;
// if(target == 1) return 1;
// return 2 <<(target - 2);
return 1<<(target - 1);
}
}
拓展延伸：
这个问题还有一个延伸：一次最多跳M个台阶，共有N个台阶，问有多少种方法？
不妨将跳法数记为f(m,n),我们可以这样来思考：第一次跳1个台阶，剩下f(m,n-1)个台阶跳法;第一次跳2个台阶，剩下f(m,n-2)个跳法;………第一次跳m个台阶，剩下f(m,n-m)个跳法。
所以f(m,n) = f(m,n-1) + f(m,n-2) + … + f(m,n-m),跳出递归的边界是当n==1的时候，f(1,1)=1 ,其实f(m,1)总是等于1； f(1,2)=1;f(2,2)=2;
在计算f(m,n)的时候，用上面的递归公式就可以了(需要注意一点的是：当m>=n的时候，问题就变成了 变态跳台阶 这个问题了，也就是最多跳N阶，共有N阶)给出实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 表示每次最多跳N个，共N个台阶。就是原本的变态跳台阶问题
public int JumpFloorII(int target) {
if(target < 0)return 0;
if(target == 1) return 1;
return 2 <<(target - 2);
}
// 表示每次可以跳M个，共N个台阶
public int JumpFloor(int m, int n){
if(n == 1){
return 1;
}
if(n == 2 && m == 1){
return 1;
}
if(m == 2 && n == 2){
return 2;
}
int count = 0;
if(m >= n){
return JumpFloorII(n); // 1 <<(n - 1)
}else{
for(int i = 1; i <= m; i++){
count += JumpFloor(m,n-i);
}
}
return count;
}
给出一种动态规划的解题方法，用map存储中间结果：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int JumpFloor(int n, int m, Map<Integer, Integer> map) {
int count = 0;
if (n== 0) {
return 1;
}
if (map.containsKey(n)) {
return map.get(n);
} else if (n>= m) {
for (int i = 1; i <= m; i++) {
count += JumpFloor(n- i, m, map);
}
} else {
//如果n小于m，则将一步最大台阶数缩小为n，重新递归
count = JumpFloor(n, n, map);
}
map.put(n, count);
return count;
}
10. 矩形覆盖
题目描述
我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形，请问用n个2 * 1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
解题思路
分析：2 * n的大矩形，和n个2 * 1的小矩形，其中target * 2为大矩阵的大小，其有以下几种情况：
- (1)target <= 0 时，大矩形为 <= 2 * 0,直接return 0;
- (2)target = 1时，大矩形为 2 * 1，只有一种摆放位置，return 1；
- (3)target = 2时，大矩形为2 * 2,有两种摆放方法， return 2;
- (4)target = n时，大矩形为2 * n，分成两步考虑：
第一次摆放一块2 * 1的小矩形，则摆放方法共有f(target-1)种：
第一次摆放一块1 * 2的小矩形，则摆放方法总共有f(target - 2)种。因为，摆放了一块1 * 2的小矩形(用√√表示)，对应下方的1*2（用××表示）摆放方法就确定了，所以为f(targte-2)
很明显就是典型的斐波那契数列问题。为此，给出代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public int RectCover(int target) {
if(target <= 1){
return target;
}
int pre2 = 1, pre1 = 1;
for(int i = 2; i <= target; i++){
int cur = pre1 + pre2;
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
}
11. 矩阵中的路径
题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如：
1
2
3
a b c e
s f c s
a d e e
上述矩阵中包含一条字符串“bcced”的路径，但是矩阵中不包含“abcb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入改格子。
解题思路
回溯法的典型例题。首先，在矩阵中任选一个格子作为路径的起点。假设矩阵中某个格子的字符为ch，并且这个格子将对应于路径上的第i个字符。如果路径上的第i个字符不是ch，那么这个格子不可能处于路径上的第i个位置。如果路径上的第i个字符正好是ch，那么到相邻的格子寻找路径上的第i+1个字符。除了矩阵边界上的格子之外，其他格子都有4个相邻的格子，重复这个过程，直到路径上的所有字符都在矩阵中找到相应的位置。
由于回溯法的递归特性，路径可以被看成是一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在于第n个字符对应的格子的周围都没有找到第n+1个字符，这个时候只好在路径上回到第n-1个字符，重新定位第n个字符。并且，由于路径不能重复进入矩阵的格子，所以还需要定义和字符矩阵大小一样的布尔型矩阵，用来标识路径是否已经进入了每个格子。
为此，给出实现的基本思想如下：
- 根据给定数组，初始化一个标志位数组，初始化为false,表示未走过，true表示已经走过，不能走第二次；
- 根据行数和列数，遍历数组，先找到一个与str字符串的第一个元素相匹配的矩阵元素，进入judge;
- 根据i和j先确定一维数组的位置，因为给定的matrix是一个一维数组；
- 确定递归终止条件：越界、当前找到的矩阵值不等于数组对应位置的值、已经走过的，这三类情况就直接false，表明这条路不通；
- 若k，也就是带判定的字符串str的索引已经判断到了最后一位，此时说明匹配是成功的，返回true;
- 精髓所在，递归不断地寻找周围四个格子是否符合条件，只要有一个格子符合条件，就继续再找这个符合条件的格子四周是否存在符合条件的格子，直到k到达末尾或者不满足递归条件就停止。
- 如果上一步未找到，那么走到这一步，说明本次是不成功的，我们要还原一下标志位数组index处的标志位，进入下一轮的判断。
给出递归的回溯法代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
//标志位，初始化为false
boolean[] flag = new boolean[matrix.length];
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
//循环遍历二维数组，找到起点等于str第一个元素的值，再递归判断四周是否有符合条件的----回溯法
if(judge(matrix,i,j,rows,cols,flag,str,0)){
return true;
}
}
}
return false;
}
//judge(初始矩阵，索引行坐标i，索引纵坐标j，矩阵行数，矩阵列数，待判断的字符串，字符串索引初始为0即先判断字符串的第一位)
private boolean judge(char[] matrix,int i,int j,int rows,int cols,boolean[] flag,char[] str,int k){
//先根据i和j计算匹配的第一个元素转为一维数组的位置
int index = i*cols+j;
//递归终止条件
if(i<0 || j<0 || i>=rows || j>=cols || matrix[index] != str[k] || flag[index] == true)
return false;
//若k已经到达str末尾了，说明之前的都已经匹配成功了，直接返回true即可
if(k == str.length-1)
return true;
//要走的第一个位置置为true，表示已经走过了
flag[index] = true;
//回溯，递归寻找，每次找到了就给k加一，找不到，还原
if(judge(matrix,i-1,j,rows,cols,flag,str,k+1) ||
judge(matrix,i+1,j,rows,cols,flag,str,k+1) ||
judge(matrix,i,j-1,rows,cols,flag,str,k+1) ||
judge(matrix,i,j+1,rows,cols,flag,str,k+1) )
{
return true;
}
//走到这，说明这一条路不通，还原，再试其他的路径
flag[index] = false;
return false;
}
}
上面给出了递归的写法，下面我们给出一种非递归形式的标准DFS(带记忆的BFS或者DFS，需要辅助容器帮助记录路径，选用栈stack或队列，还需要标记是否遍历过，用boolean[] visited)，其具体思路如下：
- DFS深度优先
- 进：peek一次，str的位子index++，对应位子visited[j + i * cols]=true，并且把周围合适的点（上下左右&&字符匹配&&未遍历）加入到stack中
- 退：当前遍历过，复位：visited设为false，并且s.pop移除当前元素，str的位置减一
- 如果str匹配成功则返回true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//标准的DFS，非递归写法，需要辅助容器帮助记录路径，选用栈stack，还需要标记是否遍历过，用boolean[] visited
public boolean hasPath(char[] matrix, int rows, int cols, char[] str){
if(matrix == null || matrix.length != rows * cols
|| str == null || str.length == 0
|| str.length > matrix.length ){
return false;
}
boolean[] visited = new boolean[matrix.length];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if(dfs(matrix,rows,cols,str,i,j,visited)){
return true;
}
}
}
return false;
}
//这里方便遍历上下左右
private static int[] x = {0,1,0,-1}; //顺时针
private static int[] y = {1,0,-1,0};//顺时针
private boolean dfs(char[] matrix, int rows, int cols, char[] str,int i, int j, boolean[] visited){
//第一个字符必须相等
if(matrix[j + i*cols] != str[0]){
return false;
}
Stack<Integer> s = new Stack<>(); //存坐标
int index = 0; //当前str的索引
s.push(j + i * cols);
while (!s.empty()){
int location = s.peek();
if(visited[location] == true){
//访问过的话，全部复位
visited[location] = false; //取消访问记录
s.pop(); //退出该节点
if (--index < 0){
return false;
}
continue; //防止该路径再次被遍历
}
visited[location] = true; //标记访问过
if (++index == str.length){
//如果这个字符恰好是最后一个字符，直接返回true
return true;
}
/*将当前节点周围(上下左右符合标准的点加入到s中)
1. 边界条件：j = location % cols i = location / cols ,i和j判断边界
2. 必须未遍历过visited[cur] == false
3. 当前字符匹配matrix[cur] == str[index]
*/
for (int k = 0; k < 4; k++){
int xn = location / cols + x[k];
int yn = location % cols + y[k];
int cur = yn + xn * cols;
if(xn >= 0 && xn < rows && yn >= 0 && yn < cols && visited[cur] == false && matrix[cur] == str[index]){
s.push(cur);
}
}
}
return false;
}
12. 机器人的运动范围
题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
解题思路
解法1：回溯法(不算是严格意义上的回溯，其实就是图的遍历)。和上一题类似，这个方格也可以看成是一个m*n的矩阵。同样，在这个矩阵中，除了边界上的格子之外，其他格子都有4个相邻的格子。机器人从坐标(0,0)开始移动，当它准备进入坐标为(i,j)的格子时，通过检查坐标的数位和来判断机器人是否能够进入。如果机器人能够进入坐标为(i,j)的格子，则再判断它能否进入4个相邻的格子(i,j-1)、(i-1,j)、(i,j+1)、(i+1,j)。写出回溯法的代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int movingCount(int threshold, int rows, int cols) {
boolean[][] visited = new boolean[rows][cols];
return countingSteps(threshold,rows,cols,0,0,visited);
}
public int countingSteps(int limit,int rows,int cols,int r,int c,boolean[][] visited){
if (r < 0 || r >= rows || c < 0 || c >= cols
|| visited[r][c] || bitSum(r) + bitSum(c) > limit) return 0;
visited[r][c] = true;
return countingSteps(limit,rows,cols,r - 1,c,visited)
+ countingSteps(limit,rows,cols,r,c - 1,visited)
+ countingSteps(limit,rows,cols,r + 1,c,visited)
+ countingSteps(limit,rows,cols,r,c + 1,visited)
+ 1;
}
public int bitSum(int t){
int count = 0;
while (t != 0){
count += t % 10;
t /= 10;
}
return count;
}
解法2：动态规划写法。用dp[i][j]表示是否可达，统计dp数组中数字中true的个数，即为可达的格子数。(dp[i][j]能否到达其实是由dp[i-1][j]与dp[i][j-1]及其本身行列坐标之和是否小于等于阈值所决定)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//动态规划解法,dp[i][j]能否到达其实是由dp[i-1][j]与dp[i][j-1]及其本身行列坐标之和是否小于等于阈值所决定
public int movingCount1(int threshold, int rows, int cols){
if(threshold < 0 || rows < 0 || cols < 0){
return 0;
}
boolean[][] dp = new boolean[rows+1][cols+1];
dp[0][0] = true;
//dp数组初始化
for (int i = 1; i <= rows; i++){
if(dp[i-1][0] && canReach(threshold,i,0)){
dp[i][0] = true;
}else {
dp[i][0] = false;
}
}
for (int i= 1; i <= cols;i++){
if(dp[0][i-1] && canReach(threshold,0,i)){
dp[0][i] = true;
}else {
dp[0][i] = false;
}
}
for(int i = 1; i<= rows; i++){
for (int j = 1; j <= cols; j++){
if((dp[i-1][j] && canReach(threshold,i,j)) || (dp[i][j-1] && canReach(threshold,i,j))){
dp[i][j] = true;
}else {
dp[i][j] = false;
}
}
}
int count = 0;
for(int i = 0; i < rows;i++){
for (int j = 0; j < cols; j++) {
if(dp[i][j]){
count++;
}
}
}
return count;
}
private boolean canReach(int threshold, int x, int y){
int sum = 0;
while (x != 0){
sum += x % 10;
x /= 10;
}
while (y != 0){
sum += y % 10;
y /= 10;
}
return sum <= threshold;
}
解法3：其实该题的算法本质就是DFS BFS求连通分量的过程。
对于该题，假设我们把矩阵的每一个“格子”抽象成一个“结点”，把“格子相邻”抽象为“结点连通”(结点之间存在无向边)，把“无法进入的格子”抽象成为“与所有普通结点都不连通(不存在无向边)的孤点”，则整个问题就可以抽象成为：从某个节点出发，寻找无向图的连通分量的节点个数。很显然，使用DFS或者BFS就可以进行实现。(DFS的实现其实就是解法1的实现，下面还是给出DFS与BFS的实现策略)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//DFS的实现
public int movingCount(int threshold, int rows, int cols) {
if(threshold <= 0) {
return 0;
}
boolean[][] visited = new boolean[rows][cols];
return movingCount(threshold, 0, 0, rows, cols, visited);
}
public int movingCount(int threshold, int i, int j, int rows, int cols, boolean[][] visited) {
if (i < 0 || i >= rows || j < 0 || j >= cols || visited[i][j] || countNum(i) + countNum(j) > threshold){
return 0;
}
visited[i][j] = true;
return 1 + movingCount(threshold, i - 1, j, rows, cols, visited) + movingCount(threshold, i + 1, j, rows, cols, visited) +
movingCount(threshold, i, j - 1, rows, cols, visited) + movingCount(threshold, i, j + 1, rows, cols, visited);
}
public int countNum(int target){
int count = 0;
while(target != 0) {
count += (target % 10);
target = target / 10;
}
return count;
}
//BFS的实现，利用队列
public int movingCount2(int threshold, int rows, int cols){
if(threshold < 0 || rows < 0 || cols < 0){
return 0;
}
LinkedList<Point> queue = new LinkedList<>();
boolean[][] visited = new boolean[rows][cols];
visited[0][0] = true;
queue.add(new Point(0,0));
int count = 0;
while (!queue.isEmpty()){
Point curPoint = queue.poll();
count++;
int x = curPoint.x;
int y = curPoint.y;
if(isAvailable(x-1,y,rows,cols,threshold,visited)){
queue.add(new Point(x-1,y));
visited[x-1][y] = true;
}
if (isAvailable(x + 1, y, rows, cols, threshold, visited)) {
queue.add(new Point(x + 1, y));
visited[x + 1][y] = true;
}
if (isAvailable(x, y - 1, rows, cols, threshold, visited)) {
queue.add(new Point(x , y - 1));
visited[x][y - 1] = true;
}
if (isAvailable(x, y + 1, rows, cols, threshold, visited)) {
queue.add(new Point(x, y + 1));
visited[x][y + 1] = true;
}
}
return count;
}
public boolean isAvailable(int x, int y , int rows, int cols, int threshold, boolean[][] visited) {
return (x >= 0 && x < rows && y >= 0 && y < cols && !visited[x][y] && countNum(x) + countNum(y) <= threshold);
}
13. 剪绳子
题目描述
给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
解题思路
解法1：动态规划。f(n)定义为将长度为n的绳子分成若干段后的各段长度的最大乘积（最优解），在剪第一刀时有n-1种剪法，可选择在0 < i < n处下刀。在i处下刀，分成长度为i的左半绳子和长度为n-i的右半绳子，对于这两根绳子，定义最优解为f(i)和f(n-i)，于是f(n) = max(f(i) * f(n-i))，即求出各种相乘可能中的最大值就是f(n)的最优解。就这样从上到下的分下去，但是问题的解决从下到上。即先求出f(2)、f(3)的最优解，然后根据这两个值求出f(4)、f(5)…直到f(n)。 f(2) = 1，因为只能分成两半，f(3) = 2，因为分成两段2 * 1大于分成三段的1 * 1* 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int cutRope(int target) {
// n<=3的情况，m>1必须要分段，例如：3必须分成1、2；1、1、1 ，n=3最大分段乘积是2,
if(target < 2){
return 0;
}
if(target == 2){
return 1;
}
if(target == 3){
return 2;
}
int[] dp = new int[target + 1];
/*下面4行是n>=4的情况，跟n<=3不同，4可以分很多段，比如分成1、3，
这里的3可以不需要再分了，因为3分段最大才2，不分就是3。记录最大的。
*/
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
int max = 0;
for (int i = 4; i <= target; i++){
max = 0;
for (int j = 1; j <= i / 2; ++j){
max = Math.max(max, dp[j]*dp[i-j]);
}
dp[i] = max;
}
return dp[target];
}
解法2：贪心法。如果我们按照如下的策略来剪绳子，则得到各段绳子的长度的乘积将最大：当n>=5时，我们尽可能地剪长度为3的绳子；当剩下的绳子长度为4时，把绳子剪成两段长度为2的绳子。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int cutRope(int target) {
// 长度为1时不满足题意，返回0
if (target < 2) {
return 0;
}
// f(2)
if (target == 2) {
return 1;
}
// f(3)
if (target == 3) {
return 2;
}
// 统计能分出多少段长度为3的绳子
int timesOf3 = target / 3;
// 如果最有只剩下长度为1的绳子，需要退一步，得到长度为4的绳子，重新分成2*2的
if (target - timesOf3 * 3 == 1) {
timesOf3--;
}
// 到这步length - timesOf3 * 3的值只可能是0,2,4，所以timesOf2只可能是0, 1, 2
int timesOf2 = (target - timesOf3 * 3) / 2;
return (int) Math.pow(3, timesOf3) * (int) Math.pow(2, timesOf2);
}
牛客网上还看到一个很好的分析贪心的案例如下：
#include <iostream>
#include <cmath>
using namespace std;
/**
* 题目分析：
* 先举几个例子，可以看出规律来。
* 4 ： 2*2
* 5 ： 2*3
* 6 ： 3*3
* 7 ： 2*2*3 或者4*3
* 8 ： 2*3*3
* 9 ： 3*3*3
* 10：2*2*3*3 或者4*3*3
* 11：2*3*3*3
* 12：3*3*3*3
* 13：2*2*3*3*3 或者4*3*3*3
*
* 下面是分析：
* 首先判断k[0]到k[m]可能有哪些数字，实际上只可能是2或者3。
* 当然也可能有4，但是4=2*2，我们就简单些不考虑了。
* 5<2*3,6<3*3,比6更大的数字我们就更不用考虑了，肯定要继续分。
* 其次看2和3的数量，2的数量肯定小于3个，为什么呢？因为2*2*2<3*3，那么题目就简单了。
* 直接用n除以3，根据得到的余数判断是一个2还是两个2还是没有2就行了。
* 由于题目规定m>1，所以2只能是1*1，3只能是2*1，这两个特殊情况直接返回就行了。
*
* 乘方运算的复杂度为：O(log n)，用动态规划来做会耗时比较多。
*/
long long n_max_3(long long n) {
if (n == 2) {
return 1;
}
if (n == 3) {
return 2;
}
long long x = n % 3;
long long y = n / 3;
if (x == 0) {
return pow(3, y);
} else if (x == 1) {
return 2 * 2 * (long long) pow(3, y - 1);
} else {
return 2 * (long long) pow(3, y);
}
}
14. 二进制中1的个数
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
解题思路
解法1：整体思路就是判断整数二进制表示中最右边一位是不是1，接着我们把输入的整数整体右移一位，此时原来处于从右边数起的第二位就被移到最右边了，再判断是不是1；这样每次移动一位，直到整个整数变成0为止。我们也知道判断一个数最右边是不是1只需要与1做位与运算就可以。注意，这里输入整数存在负数，所以我们需要进行无符号右移(»>)。
1
2
3
4
5
6
7
8
9
10
public int NumberOf1(int n) {
int count = 0;
while(n != 0){
if((n & 1 ) == 1){
count++;
}
n = n >>> 1;
}
return count;
}
解法2：我们可以不右移输入的数字n，我们可以对1进行左移。其思路是：我们首先把n与1做与运算，判断n的最低位是不是1.接着把1左移一位得到2，再和n做与运算，就能判断n的次低位是不是1……这样反复左移，每次都能判断n的其中一位是不是1.
1
2
3
4
5
6
7
8
9
10
11
public int NumberOf1(int n) {
int count = 0;
int flag = 1;
while (flag != 0) {
if ((n & flag) != 0) {
count++;
}
flag = flag << 1;
}
return count;
}
解法3：把一个整数减去1，再和原整数做与运算，会把该整数最右边的1变成0.那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。(极其巧妙)
1
2
3
4
5
6
7
8
9
10
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n!= 0){
count++;
n = n & (n - 1);
}
return count;
}
}
15. 数值的整数次方
题目描述
给定一个double类型的浮点数base,和int类型的整数exponent.求base的exponent次方。保证base和exponent不同时为0.
解题思路
解法1：常规解法。本题考查的目的就在于边界值的考虑。例如，当指数为负数的时候，需要先对指数求绝对值，算出次方的结果后再取倒数。既然求倒数，自然就需要排除base是0且指数是负数的情况。并且我们知道0的0次方在数学上没有意义，且题目也给出了这两者不同时为0.为此，给出下面直接进行累乘的方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public double Power(double base, int exponent) {
if (base == 0.0){
return 0.0;
}
// 前置结果设为1.0，即当exponent=0 的时候，就是这个结果
double result = 1.0d;
// 获取指数的绝对值
int e = exponent > 0 ? exponent : -exponent;
// 根据指数大小，循环累乘
for(int i = 1 ; i <= e; i++){
result *= base;
}
// 根据指数正负，返回结果
return exponent > 0 ? result : 1 / result;
}
}
解法2： 快速幂算法。在常规解法中，如果输入的指数exponent为32，那么我们需要在循环中做31次乘法。但是，其实我们可以换一种思路考虑：我们的目标是求一个数字的32次方，如果我们知道了它的16次方，那么只要在16次方的基础上再平方一次就可以了。而16次方又是8次方的平方。这样依次类推，我们求32次方只需要做5次乘法：先求平方，在平方的基础上求4次方，在4次方的基础上求8次方，8次方基础上求16次方，最后求32次方。
根据上面的描述，可以用下面公式求a的n次方：
- 当n为偶数，a^n =（a^n/2）*（a^n/2）；
- 当n为奇数，a^n = a^[(n-1)/2] * a^[(n-1)/2] * a
我们下面给出求快速幂的一个案例。例如，我们对于n可以用二进制表示，以14为例子。14 = 1110，则m的n次方可以表示为：
可以发现一个规律，指数n的二进制从低位到高位依次对应着底数m的1次方，2次方，4次方，8次方…，当该二进制位是1的时候，则乘以底数对应的次方数，如果该二进制位是0，则表示乘以1.使用快速幂后，原本需要14次连乘，现在只需要4次连乘。为此，我们可以用与运算与右移操作，例如14 = 1110
- 和1按位与得到0，即第一个二进制位是0
- 1110右移一位，得到0111，和1按位与得到1，即第二个二进制位是1
- 0111右移一位，得到0011，和1按位与得到1，即第三个二进制位是1
- 0011右移一位，得到0001，和1按位与得到1，即第四个二进制位是1
- 0001右移一位，得到0000，等于0则，算法结束
为此，给出本题的两种解法：递推和递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//1. 递推法
public class Solution {
public double Power(double base, int exponent) {
double res = 1.0;
boolean flag = false;
if(exponent < 0){
if(base == 0){
throw new RuntimeException("分母不能为0");
}
flag = true;
exponent = -exponent;
}else if(exponent == 0){
return 1;
}
while (exponent != 0){
if((exponent & 1) == 1){
res *= base;
}
base *= base;
exponent >>= 1;
}
return flag ? 1 / res : res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//2. 递归写法
public class Solution {
public static double Power(double base, int exp) {
boolean flag = exp < 0;
if (flag) {
exp = -exp;
}
double result = getPower(base, exp);
return flag ? 1 / result : result;
}
public static double getPower(double base, int exp) {
if (exp == 0) {
return 1;
}
if (exp == 1) {
return base;
}
double ans = getPower(base, exp >> 1);
ans *= ans;
if ((exp & 1) == 1) {
ans *= base;
}
return ans;
}
}
16. 打印从1到最大的n位数
题目描述
输入数字n,按顺序打印从1到最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数999.
解题思路
解法1： 在字符串上模拟数字加法。在用字符串表示数字的时候，最直观的方法就是字符串里每个字符都是’0’~’9’之间的某一个字符，用来表示数字中的某一位。我们需要构建一个长度为n的字符串，初始化每一位都为’0’，然后每一次都为字符串表示的数字加1，再打印出来。在这其中，有两个坑。
1.首先我们需要知道在什么时候来停止在number上加1。我们注意到只有对“9999…99”加1的时候，才会在第一个字符(下标为0)的基础上产生进位，而其他所有情况都不会在第一个字符上产生进位。因此，当我们发现在加1的时候第一个字符产生了进位，则已经是最大的n位情况了，可以退出循环了；
2.在打印字符的时候，我们前面提到当数字不够n位的时候，我们在数字的前面补0，打印的时候这些补位的0不应该打印出来。因此，在打印函数的时候，只有在碰到第一个非0的字符之后我们才开始打印，直到字符的末端。
给出代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public void printFrom1ToMaxOfDigit(int n){
if(n <= 0){
return;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n;i++){
sb.append("0");
}
while (stillIncrease(sb,n)){
print(sb);
}
System.out.println();
}
private boolean stillIncrease(StringBuilder sb, int len){
//进位，应该要给下一位进行相加
int toTen = 0;
// 从个位开始相加，如果有进位就看十位。。。如果到最高位还有进位，说明溢出
for (int i = len - 1;i >= 0; i--){
int sum = sb.charAt(i) - '0' + toTen;
//在个位上，先自增
if(i == len - 1){
sum++;
}
if(sum == 10){
//进位溢出
if (i == 0){
return false;
}else {
sb.setCharAt(i, '0');
toTen = 1;
}
}else {
sb.setCharAt(i,(char)(sum + '0'));
// 在某位上自增后不再进位，自增完成立即退出循环
break;
}
}
return true;
}
private void print(StringBuilder sb){
int start = sb.length();
//找到第一个不为0的索引
for (int i = 0; i < sb.length(); i++){
if(sb.charAt(i) != '0'){
start = i;
break;
}
}
//如果全是0,就不打印
if(start < sb.length()){
System.out.print(sb.substring(start) + " ");
}
}
解法2：递归解法，将问题变成数字排列的解法。我们可以换一种思路来思考这个问题，如果我们在数字前面补0，就会发现n位所有十进制数其实就是n个从0到9的全排列。也就是说，我们把数字的每一位都从0到9排列一遍，就得到了所有的十进制数。只是我们在打印的时候，排在前面的0不打印出来而已。全排列用递归很容易表达，数字的每一位都可能是0~9中的一个数，然后设置下一位。递归结束的条件是我们已经设置了数字的最后一位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
private void print(StringBuilder sb){
int start = sb.length();
//找到第一个不为0的索引
for (int i = 0; i < sb.length(); i++){
if(sb.charAt(i) != '0'){
start = i;
break;
}
}
//如果全是0,就不打印
if(start < sb.length()){
System.out.print(sb.substring(start) + " ");
}
}
//第二种解法，递归解法
public void printFrom1ToMaxOfDigitRecur(int n){
if(n <= 0){
return;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++){
sb.append("0");
}
printRecur(sb,n,0);
}
private void printRecur(StringBuilder sb, int len, int index){
//递归结束条件
if(index == len - 1){
print(sb);
return;
}
for (int i = 0; i < 10; i++){
sb.setCharAt(index, (char)(i + '0'));
printRecur(sb,len,index+1);
}
}
17. 删除链表的节点
题目描述
在O(1)时间内删除链表节点。给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。
解题思路
在单向链表中删除一个节点，常规的做法是从链表的头节点开始，顺序遍历查找要删除的节点，并在链表中删除该节点。然而这种思路由于需要顺序查找，时间复杂度自然是O(n).传统做法中，我们之所以需要从头开始查找，是因为我们需要得到被删除节点的前一个节点。在单向链表中，节点没有指向前一个节点的指针，所以只好从链表的头节点开始顺序查找。
然而，实际上我们可以不一定要得到被删除节点的前一个节点。因为我们能很方便地得到要删除节点的下一个节点。如果我们把下一个节点的内容复制到需要删除的节点上覆盖原有的内容，再把下一个节点删除，其实就相当于把当前需要删除的节点删除了。(BST中删除节点就存在这样的一种思路，查找到后继节点替换被删除节点的值)当然，这里还要考虑删除的节点位于链表的尾部的情况(这种情况，就只能从链表的头部开始顺序遍历到该节点的前序节点，完成删除操作)和链表只有一个节点的情况(在删除完节点之后，还需要将头指针设置为null)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
private class Node{
int val;
Node next;
}
public void deleteNode(Node head, Node toBeDel){
if (head == null || toBeDel == null){
return;
}
//要删除的节点不是尾节点时
if(toBeDel.next != null){
Node pNext = toBeDel.next;
toBeDel.val = pNext.val;
toBeDel.next = pNext.next;
}else if(head == toBeDel){
//是头节点且是尾结点
head = head.next;
}else {
//仅仅是尾结点，即在含有多个节点的链表中删除尾结点
Node cur = head;
while (cur.next != toBeDel){
cur = cur.next;
}
cur.next = null;
}
}
拓展延伸
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。注意重复的结点不保留：并不是将重复结点删除到只剩一个，而是重复结点的全部会被删除。所以 链表1->2->3->3->4->4->5不是1->2->3->4->5。
解法1：哑结点加上快慢指针。我们从头遍历整个链表，如果当前节点的值与下一个节点的值相同，那么它们就是重复的节点，都可以被删除。为了保证删除之后的链表仍然是相连的，我们要把当前节点的前一个节点与后面值比当前节点的值大的节点相连。我们要确保前一个节点始终与下一个没有重复的节点连接在一起。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public ListNode deleteDuplication(ListNode pHead)
{
if(pHead == null || pHead.next == null){
return pHead;
}
//建立一个哑结点替代原来的head
ListNode first = new ListNode(pHead.val - 1);
first.next = pHead;
//当前节点的前一个节点
ListNode pre = first;
//当前节点
ListNode cur = pHead;
while (cur != null && cur.next != null){
if(cur.val == cur.next.val){
int val = cur.val;
while (cur != null && cur.val == val){
cur = cur.next;
}
pre.next = cur;
}else {
pre = cur;
cur = cur.next;
}
}
return first.next;
}
解法2：递归解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ListNode deleteDuplication_2(ListNode pHead){
if(pHead == null ){
return pHead;
}
if(pHead.next != null && pHead.val == pHead.next.val){
while (pHead != null && pHead.next != null && pHead.val == pHead.next.val){
pHead = pHead.next;
}
//去掉所有重复的数字后，进行递归
return deleteDuplication_2(pHead);
}else {
pHead.next = deleteDuplication_2(pHead.next);
}
return pHead;
}
18. 正则表达式匹配
题目描述
请实现一个函数用来匹配包含’.’和’ * ‘的正则表达式。模式中的字符’.’表示任意一个字符，而’ * ‘表示它前面的字符可以出现任意次(包含0次)。在本题中，匹配是指字符串中的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配,但是与”aa.a”和”ab*a”均不匹配。
解题思路
每次从字符串中拿出一个字符去和模式串中的字符去匹配。先来分析如何匹配一个字符，如果模式中的字符ch是’.’，那么他可以匹配字符串中的任意字符。如果模式中的字符ch不是’.’,而且字符串中的字符也是ch，那么它们相互匹配。当字符串中的字符和模式串中的字符相匹配时，接着匹配后面的字符。
相对而言，当模式中的第二个字符不是’*‘时，问题要简单的多。如果字符串中的第一个字符和模式中的第一个字符相匹配，那么在字符串和模式串上都向后移动一个字符，然后匹配剩余的字符串和模式。如果字符串中的第一个字符和模式中的第一个字符不相匹配，则直接返回false.
当模式中的第二个字符是’*‘时，问题要复杂一些，因为可能有多种不同的匹配方式。一种是选择是在模式上向后移动两个字符。这相当于’*‘和它前面的字符被忽略了，因为’*‘可以匹配字符串中的0个字符。如果模式中的第一个字符和字符串中的第一个字符相匹配，则在字符串上向后移动一个字符，而在模式上有两种选择：可以在模式上向后移动两个字符，也可以保持模式不变。
对于上面’*‘的说明也许不太清晰，我们给出图的形式来说明：
为此，根据上面图示的思路，我们可以直接给出代码的实现：
1
2
3
4
5
6
7
8
9
10
11
12
public boolean match(char[] str, char[] pattern)
{
if (pattern.length <= 0){
return str.length <= 0;
}
boolean match = (str.length > 0 && (str[0] == pattern[0] || pattern[0] == '.'));
if(pattern.length > 1 && pattern[1] == '*'){
return match(str,Arrays.copyOfRange(pattern,2,pattern.length)) || (match && match(Arrays.copyOfRange(str,1,str.length),pattern));
}else {
return match && match(Arrays.copyOfRange(str,1,str.length),Arrays.copyOfRange(pattern,1,pattern.length));
}
}
解法1：在经历过上面的分析过后，总结了别人的解法，为此先归纳出递归的两种解法。
- 先看’*‘再看匹配：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* 思路1：先看*再看匹配
* 前提：当pattern遍历完，return取决于str是否遍历完，str恰好遍历完才返回true,再接下来讨论。
* 1. 若当前字符存在下一个字符，看下一个字符是否是'*'。如果是，则分为两种情况
* 一： 当前字符匹配
* 1.1 match(str,i+1,pattern,j) // 跳过str
* 1.2 match(str,i,pattern, j+2) // 跳过pattern
* 二： 当前不匹配
* match(str,i,pattern,j+2) // 跳过
* 2. 下一个字符不是'*'
* 当前匹配 return match(str, i+1, pattern, j+1)
*/
private boolean match(char[] str,int i,char[] pattern, int j){
// pattern遍历完了
if(j == pattern.length){
// 如果str也完了，返回true，不然false
return str.length == i;
}
//注意数组越界问题,下一个字符是'*'时
if(j < pattern.length - 1 && pattern[j+1] == '*'){
//成功匹配
if (str.length != i && (str[i] == pattern[j] || pattern[j] == '.')){
return match(str,i,pattern,j+2) || match(str, i+1,pattern,j);
}else {
return match(str,i,pattern,j+2);
}
}
// 下一个不是'*'的时候，当前匹配
if(str.length != i && (str[i] == pattern[j] || pattern[j] == '.')){
return match(str,i+1,pattern,j+1);
}
return false;
}
public static boolean match(char[] str, char[] pattern)
{
if(str == null || pattern == null)
return false;
return match(str, 0, pattern, 0);
}
- 先看匹配，再看’*‘(其实两种解法一样，都是基本情况的考虑)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 思路2：反过来，先看匹配，再看'*'
* 前提： 当pattern遍历完，return取决于str是否遍历完，再接下来讨论
* 1. 先看当前字符是否匹配，记录first_isMatch
* 2. 再看下一个字符是否为'*'
* 2.1 当前匹配 first_isMatch && match(str,i+1,pattern,j)
* 2.2 无论匹配与否,match(str,i,pattern,j+2)//跳过
* 3. 不匹配'*'，当前字符匹配的前提下，进入到下一个循环，first_Match && match(str,i+1,pattern,j+1)
*/
private boolean match(char[] str,int i,char[] pattern, int j){
if(j == pattern.length){
return str.length == i;
}
boolean first_isMatch = (i != str.length) && (str[i] == pattern[j] || pattern[j] == '.');
if(j < pattern.length - 1 && pattern[j+1] == '*'){
return match(str,i,pattern,j+2) || (first_isMatch && match(str,i+1,pattern,j));
}else {
return first_isMatch && match(str,i+1,pattern,j+1);
}
}
解法2： 带备忘录的递归解法。
我们先来考虑自顶向下的算法。为了方便起见，假定使用符号s[i:]表示字符串s中从第i个字符到最后一个字符组成的子串，p[j:]则表示模式串p中,从第j个字符到最后一个字符组成的子串，使用match(i,j)表示s[i:]与p[j:]的匹配情况，如果能成功匹配，则置为true，否则置为false。这就是各个子问题的状态。
那么对于match(i,j)的值，取决于p[j+1]是否为’*‘。
curMatch = i < s.length() && s[i] == p[j] || p[j] == ‘.’;
- p[j+1] != ‘*’, match(i,j) = curMatch && match(i+1,j+1)
-
p[j+1] == ‘*’, match(i,j) = match(i,j+2) (curMatch && match(i+1, j))
我们以s = "aab"; p = "c*a*b"为例子，先构建一个二维状态空间来存储中间计算得出的状态值。横向的值代表i，纵向的值代表j，match(0,0)的值即为问题的解，用 f 代表 false,t 代表 true.
接下来描述一下后续的计算过程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
1. 求match(0,0): i = 0; j = 0; curMatch = false;
2. p[1] == '*' -> match(0,0) = match(0,2) || false && match(1,0)
3. 转换为求解子问题match(0,2)
4. 求match(0,2): i = 0; j = 2; curMatch = true;
5. p[3] == '*' -> match(0,2) = match(0,4) || true && match(1,2)
6. 求match(0,4): i = 0; j = 4; curMatch = false;
7. j + 1 == 5 >= p.length() -> match(0,4) = curMatch = false;
8. match(0,4) = fasle;
9. 回溯到第5步，求match(1,2): i = 1, j = 2; curMatch = true;
10. p[3] == '*' -> match(1,2) = match(1,4) || true && match(2,2)
11. 求match(1,4): i = 1, j = 4; curMatch = false;
12. j + 1 == 5 >= p.length() -> match(1,4) = curMatch = false;
13. match(1,4) = false;
14. 回溯到第10步，求match(2,2): i = 2, j = 2, curMatch = false;
15. p[3] == '*' -> match(2,2) = match(2,4) || false && match(3,2)
16. 求match(2,4): i = 2, j = 4; curMatch = true;
17. j + 1 == 5 >= p.length() -> match(2,4) = curMatch = true;
18. match(2,4) = true;
19. 回溯到第15步。
20. match(2,2) = true;
21. 回溯到第10步。
22. match(1,2) = true;
23. 回溯到第5步。
24. match(0,2) = true;
25. 回溯到第2步。
26. match(0,0) = true;
27. 问题解决。
给出带备忘录的递归解法如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public enum Result {
TRUE,FALSE
}
class Solution{
//存储状态的数组
Result[][] memo;
public boolean isMatch1(char[] str, char[] pattern){
memo = new Result[str.length + 1][pattern.length + 1];
return match(0,0,str,pattern);
}
public boolean match(int i, int j, char[] str, char[] pattern){
if(memo[i][j] != null){
return memo[i][j] == Result.TRUE;
}
boolean ans;
if(j == pattern.length){
ans = i == str.length;
}else {
boolean curMatch = (i < str.length && (pattern[j] == str[i] || pattern[j] == '.'));
if(j + 1 < pattern.length && pattern[j+1] == '*'){
ans = (match(i,j+2,str,pattern) || curMatch && match(i+1,j,str,pattern));
}else {
ans = curMatch && match(i+1,j+1,str,pattern);
}
}
memo[i][j] = ans ? Result.TRUE : Result.FALSE;
return ans;
}
}
解法3：动态规划解法。这种方法的思路很简单粗暴，即从最后一个字符开始反向匹配，还是以刚才的例子，从i = 3, j = 5开始依次往左往上开始循环计算，match(3,5) = true。其中核心的逻辑并没有变，因为最边缘的值的匹配都是可以直接计算出来的，下面给出推算过程中的一部分：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
1. 求match(3,5) = true;
2. 求match(3,4): i = 3, j = 4; curMatch = false;
3. j + 1 == 5 >= p.length() -> match(3,4) = curMatch = false;
4. match(3,4) = false;
5. 求match(3,3): i = 3; j = 3; curMatch = false;
6. p[4] == b -> match(3,3) = curMatch = false;
...match(3，j)都为false
17. match(3,0) = false;
18. 求match(2,4): i = 2, j = 4; curMatch = true;
19. j + 1 == 5 >= p.length() -> match(2,4) = curMatch = true;
20. 求match(2,3): i = 2, j = 3; curMatch = false;
21. p[4] == b -> match(2,3) = curMatch = false;
22. 求match(2,2): i = 2, j = 2; curMatch = false;
23. p[3] == * -> match(2,2) = match(2,4) || false && match(3,2)
24. match(2,2) = true;
25. 求match(2,1): i = 2, j = 1; curMatch = false;
26. p[2] == a -> match(2,1) = curMatch = false;
27. 求match(2,0): i = 2, j = 0; curMatch = false;
28. p[1] == * -> match(2,0) = match(2,2) || false && match(3,0)
29. match(2,0) = true;
30. 求match(1,4): i = 1, j = 4; curMatch = false;
31. j + 1 == 5 >= p.length() -> match(1,4) = curMatch = false;
32. match(1,4) = false;
33. 求match(1,3): i = 1, j = 3; curMatch = false;
34. p[4] == b -> match(1,3) = curMatch = false;
35. 求match(1,2): i = 1, j = 2; curMatch = true;
36. p[3] == * -> match(1,2) = match(1,4) || true && match(2,2)
37. match(1,2) = true;
38. 求match(1,1): i = 1, j = 1; curMatch = false;
39. p[2] == a -> match(1,1) = curMatch = false;
40. 求match(1,0): i = 1, j = 0; curMatch = false;
41. p[1] == * -> match(1,0) = match(1,2) || false && match(2,0)
42. match(1,0) = true;
43. 求match(0,4): i = 0, j = 4; curMatch = false;
44. j + 1 == 5 >= p.length() -> match(0,4) = curMatch = false;
45. 求match(0,3): i = 0, j = 3; curMatch = false;
46. p[4] == b -> match(0,3) = curMatch = false;
47. 求match(0,2): i = 0, j = 2; curMatch = true;
48. p[3] == * -> match(0,2) = match(0,4) || true && match(1,2)
49. match(0,2) = true;
50. 求match(0,1): i = 0, j = 1; curMatch = false;
51. p[2] == a -> match(0,1) = curMatch = false;
52. 求match(0,0): i = 0, j = 0; curMatch = false;
53. p[1] == * -> match(0,0) = match(0,2) || false && match(1,0)
54. match(0,0) = true;
55. 问题解决
给出动态规划的代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isMatch(char[] str, char[] pattern){
boolean[][] memo = new boolean[str.length+1][pattern.length+1];
memo[str.length][pattern.length] = true;
for (int i = str.length; i >= 0; i--){
for (int j = pattern.length - 1; j >= 0; j--){
boolean curMatch = (i < str.length && (str[i] == pattern[j] || pattern[j] == '.'));
if(j + 1 < pattern.length && pattern[j+1] == '*'){
memo[i][j] = memo[i][j+2] || (curMatch && memo[i+1][j]);
}else {
memo[i][j] = curMatch && memo[i+1][j+1];
}
}
}
return memo[0][0];
19. 表示数值的字符串
题目描述
请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如，字符串“+100”，“5e2”,“-123”，“3.1416”和“-1E-16”都表示数值。但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。
解题思路
解法1：正则表达式的解法。
1
2
3
4
5
6
7
8
9
//正则表达式解法
public boolean isNumeric(char[] str) {
//构建正则表达式
if(str == null){
return false;
}
String regex = "[+-]?[0-9]*(\\.[0-9]*)?([eE][+-]?[0-9]+)?";
return new String(str).matches(regex);
}
下面解释一下正则表达式：
1
2
3
4
[+-]? -> 正或负符号出现与否
[0-9]* -> 整数部分是否出现，如-.34 或 +3.34均符合
(\\.[0-9]*)? -> 如果出现小数点，那么小数点后面可以跟或者不跟数字，但是整个部分职能出现一次或不出现
([eE][+-]?[0-9]+)? -> 如果存在指数部分，那么e或E肯定出现，+或-可以不出现，紧挨着必须跟着整数；或者整个部分都不出现
解法2：表示数值的字符串遵循模式
A[.[B]][e|EC],其中A为数值的整数部分，B紧跟着小数点为数值的小数部分，C紧跟着’e’或者’E’为数值的指数部分。在小数里可能没有数值的整数部分，因此A不是必需的。且上述的A和C都有可能是以’+’或’-‘开头的0~9的数位串；B也是0~9的数位串，但是前面不能有正负号。
为此，判断一个字符串是否符合上述模式时，首先尽可能多地扫描0~9的数位(有可能在起始处有’+’或者’-‘)，也就是前面模式中表示数值整数的A部分。如果遇到小数点’.’，则开始扫描表示数值小数部分的B部分。如果遇到’e’或’E’,则开始扫描表示数值指数的C部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//剑指offer解法
private int index = 0;
// 数字的格式可以用A[.[B]][e|EC]来表示，其中A和C都是整数(可以有正负号，也可以没有)，而B是一个无符号整数
public boolean isNumeric(char[] str){
if(str == null){
return false;
}
boolean flag = scanInteger(str);
//如果出现'.'，则接下来的是数字的小数部分
if(index < str.length && str[index] == '.'){
index++;
// 下面一行代码用||的原因：
// 1. 小数点可以没有整数部分，如.123等于0.123
// 2. 小数点后面可以没有数字，例如223.等于223.0
// 3. 当然，小数点前面和后面可以都有数字，如233.666
flag = scanUnsignedInteger(str) || flag;
}
// 如果出现'e'或'E',则接下来的是数字的指数部分
if (index < str.length && (str[index] == 'E' || str[index] == 'e')){
index++;
//下面一行代码用&&的原因：
// 1.当e或E前面没有数字时，整个字符串不能表示数字，如.e1,e1
// 2.当e或E后面没有整数时，整个字符串不能表示数字，如12e、12e+5.4
flag = flag && scanInteger(str);
}
return flag && index == str.length;
}
private boolean scanInteger(char[] str){
if(index < str.length && (str[index] == '+' || str[index] == '-')){
index++;
}
return scanUnsignedInteger(str);
}
private boolean scanUnsignedInteger(char[] str){
int start = index;
while (index < str.length && str[index] >= '0' && str[index] <= '9'){
index++;
}
//是否存在整数
return start < index;
}
解法3：暴力法。
解题思路是：
12e说明e的后面必须有数字，不能有两个e+-5说明符号位要么出现一次在首位，要么出现一次在e的后一位，其他地方都不能有12e4.3说明e的后面不能够有小数，1.2.3说明不能有两个小数点1a3.14说明不能有其他的非法字符，比如这里的a
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public boolean isNumeric(char[] str){
//null或者空字符串不是数字
if(str == null || str.length == 0){
return false;
}
//长度为1，必须是0-9之间
if(str.length == 1){
return str[0] >= '0' && str[0] <= '9';
}
boolean hasDot = false;
boolean hasE = false;
boolean hasSign = false;
for (int i = 0; i < str.length; i++) {
if (str[i] == '+' || str[i] == '-') {
//第二次出现正负号,那么后面能出现符合的地方只有紧贴着e的后面一位，不是则不通过
if (hasSign && str[i-1] != 'e' && str[i-1] != 'E'){
return false;
}
//第一次出现，如果不是出现在第一位，那么还是判断一下是不是出现在e的后面一位
if(!hasSign && i > 0 && str[i-1] != 'e' && str[i-1] != 'E'){
return false;
}
hasSign = true;
}else if(str[i] == '.'){
// 只能出现一次'.'，e和E之后不可出现'.'
if(hasDot || hasE){
return false;
}
hasDot = true;
}else if(str[i] == 'e' || str[i] == 'E'){
// e或E后面必须有数字
if( i == str.length - 1){
return false;
}
//只能有一个e或者E
if(hasE){
return false;
}
hasE = true;
}else if(str[i] < '0' || str[i] > '9'){
// 最后判断如果+-eE.之外的字符，不匹配
return false;
}
}
return true;
}
解法4：利用状态机，其是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模式。
给出本题状态机转移图如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//状态机迁移解法
char[] arr = "+-n.ne+-n".toCharArray();
int[][] turn = {
// + - n . n e + - n
{1,1,1,0,0,0,0,0,0}, //# start
{0,0,1,1,0,0,0,0,0}, // +
{0,0,1,1,0,0,0,0,0}, // -
{0,0,1,1,0,1,0,0,0}, // n
{0,0,0,0,1,0,0,0,0}, // .
{0,0,0,0,1,1,0,0,0}, // n
{0,0,0,0,0,0,1,1,1}, // e
{0,0,0,0,0,0,0,0,1}, // +
{0,0,0,0,0,0,0,0,1}, // -
{0,0,0,0,0,0,0,0,1} // n
};
public boolean isNumberic(char[] str){
int cur = 0;
for (int j, i = 0; i < str.length; i++){
for (j = 0; j < 9;j++){
if(turn[cur][j] == 1){
if( arr[j] == 'n' && (str[i] >= '0' && str[i] <= '9')
|| arr[j] == 'e' && (str[i] == 'E' || str[i] == 'e')
|| str[i] == arr[j]){
cur = j + 1;
break;
}
}
}
if(j == 9){
return false;
}
}
if(cur == 3 || cur == 4 || cur == 5 || cur == 9){
return true;
}
return false;
}
20. 调整数组顺序使得奇数位于偶数前面
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解题思路
解法1：利用空间换时间的做法。创建额外数组(一个或者两个数组分别对应不同解法，原理一样)，最后合并。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public void reOrderArray(int[] array) {
if (array == null || array.length == 0) {
return;
}
int len = array.length;
int p = 0;
int[] temp = new int[len];
//从左向右扫描数组,先只存入奇数
for (int i = 0; i < array.length; i++) {
if (isOdd(array[i])) {
temp[p++] = array[i];
}
}
//从左向右扫描数组,后只存入偶数
for (int i = 0; i < array.length; i++) {
if (!isOdd(array[i])) {
temp[p++] = array[i];
}
}
//覆盖原来的数组
for (int i = 0; i < len; i++) {
array[i] = temp[i];
}
}
private boolean isOdd(int val) {
return (val & 1) == 1;
}
解法2： 冒泡排序的解法，如果该元素是偶数，下一个数是奇数就进行交换，也可以保持相对位置不变(稳定排序)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void reOrderArray(int[] array) {
if (array == null || array.length == 0) {
return;
}
for (int i = 0; i < array.length; i++) {
//构建变量status来判断是否已经全部有序
boolean status = true;
for (int j = 0; j < array.length - i - 1; j++) {
if ((array[j] & 1) == 0 && (array[j + 1] & 1) == 1) {
swap(array, j, j + 1);
status = false;
}
}
if (status) {
break;
}
}
}
private void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
解法3： 插入排序的解法，保持数组的稳定性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void reOrderArray(int [] array) {
if (array == null || array.length < 2) {
return;
}
for (int i = 1; i < array.length; i++) {
if (array[i] % 2 != 0) {
int value = array[i];
int cur = i;
while (cur > 0 && (array[cur - 1] % 2 == 0)) {
array[cur] = array[cur - 1];
cur--;
}
array[cur] = value;
}
}
}
解法4： 另外一种插入排序的变种算法。
解题思路是：
- 用两个下标i,j进行遍历;
- 若
a[j]为偶数，j++前进，直到碰到奇数a[j]对应的奇数插入到a[i]位置，j经过的j-1个偶数依次后移
- 如果j==len-1时还没碰到奇数，证明i和j之间都为偶数了，完成整个移动。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public void reOrderArray(int[] array) {
if (array == null || array.length < 2) {
return;
}
int len = array.length;
int i = 0;
while (i < len) {
//如果i所指的元素是偶数
if ((array[i] & 1) != 1) {
//当i遇到偶数停下时，j从i的后一位开始走
int j = i + 1;
//当j所指的元素也是偶数时，则j向后移动
while (array[j] % 2 == 0) {
//当j移到队尾，则说明i到队尾全是偶数，已满足题目的奇偶分离要求
if (j == len - 1){
return;
}
j++;
}
//此时j为奇数，i为偶数，用temp保存array[j]的值
int temp = array[j];
//把i到j-1的元素往后移一位
while (j > i){
array[j] = array[j-1];
j--;
}
//把保存在temp中的原第j个元素的值赋给i，此时i就变成奇数了，并进入下个循环
array[i] = temp;
}
i++;
}
}
21. 链表中倒数第k个结点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
解题思路
解法1：快慢指针解法。两个指针都指向头节点，让一个指针先走k-1个节点，然后两个指针一起走，直到一个指针到达尾部。时间复杂度为 O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode FindKthToTail(ListNode head, int k) {
if(k <= 0 || head == null){
return null;
}
ListNode a = head;
ListNode b = head;
//先让第一个指针先移动k-1步
for(int i = 0; i < k -1; i++){
//如果k的值比链表节点数还大，直接排除
if(a.next == null){
return null;
}
a = a.next;
}
//两个指针同时移动
while (a.next != null){
a = a.next;
b = b.next;
}
return b;
}
解法2： 利用辅助空间(栈或者集合都行)，或者对链表遍历两次的解法都可以。只是相比较于双指针解法，增加了空间复杂度或者时间复杂度。下面给出辅助栈的解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//通过一个辅助栈，利用栈的后进先出特点，所有结点进栈，再出栈k个
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null){
return null;
}
if(k<0){
return null;
}
Stack <ListNode> stack=new Stack<ListNode> ();
ListNode nodek=null; //记录第k个结点
ListNode current =head;
int size=0;//记录结点的个数
while(current!=null){
stack.push(current);
current=current.next;
size++;
}
if(k>size){
return null;
}
for(int i=0;i<k;i++){
nodek= stack.pop();
}
return nodek;
}
22. 链表中环的入口结点
题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
解题思路
