剑指offer系列题目解析，来源牛客网。
很多算法可能并不高明，代码仅供参考，之后再刷的时候可能会有所改进👊🏻。
本章题目：1. 二维数组中的查找， 2. 替换空格，3. 从尾到头打印链表
1. 二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：一个比较简单的思路是从该二维数组的左下角P开始，与T进行比较，若比P>T，则T在P上方；若P<T，则T在P右侧；P==T，返回true。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public boolean Find(int target, int [][] array) {
int rows = array.length, cols = array[0].length;
int i = rows - 1, j = 0;
while(i >= 0 && j <= cols - 1){
if(array[i][j] == target) return true;
else if(array[i][j] > target && i >= 0) i--;
else if(array[i][j] < target && j <= cols - 1) j++;
}
return false;
}
}
2. 替换空格
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路： 先获取字符串中空格数量space_count，由此可知需要增加的长度，例如字符串有2个空格，则该字符串长度需要增加4。替换时从字符串末尾开始替换，可以避免字符被多次移动。从字符串末尾开始查找，若字符不为空格，则该字符往后移动2*space_count个位置；字符为空格，则根据位置规律，将后面的相应位置替换为%20。
例：‘Hello world’，中间含有两个空格。
0 1 2 3 4 5 6 7 8 9 10 11
H e l l o w o r l d
->
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
H e l l o w o r l d
->
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
H e l l o % 2 0 w o r l d
->
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
H e l l o % 2 0 % 2 0 w o r l d
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public String replaceSpace(StringBuffer str) {
int count = 0;
char[] strlist = str.toString().toCharArray();
for(char w : strlist){
if(w == ' ') count++;
}
char[] res = new char[strlist.length + 2 * count];
for(int i = strlist.length - 1; i >= 0; i--){
if(strlist[i] != ' ') res[i + 2 * count] = strlist[i];
else{
count--;
res[i + 2*count] = '%';
res[i + 2*count + 1] = '2';
res[i + 2*count + 2] = '0';
}
}
return new String(res);
}
}
3. 从尾到头打印链表
输入一个链表，从尾到头打印链表每个节点的值。
思路： 利用递归实现（缺点是效率并不高，比较简洁），判断节点的next是否为NULL，若是NULL则开始返回val的值。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
private ArrayList<Integer> res = new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode == null) return res;
if(listNode.next != null) printListFromTailToHead(listNode.next);
res.add(listNode.val);
return res;
}
}