前言
题目来源参考阿秀学长的刷题笔记，小戴只是把 C++的题解改成了 Java版本，并整理了其他思路，便于自己的学习~
如果解题有更好的方法，本文也会及时进行更新~
希望对你有帮助~ 一起加油哇~
???? 1、二维数组中的查找
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
给定 target = 7，返回 true
给定 target = 3，返回 false
思路
从右上角度往左下角不断查找，
如果右上角值比 target 小，就往下走，值比 taget 大，就往右走，值相等的话，返回 true，依次类推…
如果到了左下角，还没有找到和 tatget 相等的值，就返回 false~
public class Solution {
public boolean Find(int target, int [][] array) {
if(array.length==0 || array[0].length==0){
return false;
}
int row = array.length; // 行
int col = array[0].length; // 列
int i = 0; // 行
int j = col - 1; // 列
while(i<row && j>=0){
if(array[i][j] < target){
i++;
}else if(array[i][j] > target){
j--;
}else{
return true;
}
}
return false;
}
}
???? 2、替换空格
题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy
思路
新建一个 StringBuilder 动态字符串数组存放替换之后的字符串，
遍历 str ， 如果 字符为空格，采用 StringBuilder 中的 append 方法在动态字符串数组中添加 %20 ，否则添加原字符
public class Solution {
public String replaceSpace(StringBuffer str) {
StringBuilder newStr = new StringBuilder();
for(int i=0; i<str.length(); i++){
char c = str.charAt(i);
if(c == ' '){
newStr.append("%20");
}else{
newStr.append(c);
}
}
return newStr.toString();
}
}
???? 3、从尾到头打印链表
题目描述
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）
思路一（反转函数）
新建一个 ArrayList ，遍历链表，从前往后保存每个节点的值到数组，
最后 反转函数reverse() 将数组反转
import java.util.*;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList();
ListNode temp = listNode;
while(temp != null){
list.add(temp.val);
temp = temp.next;
}
Collections.reverse(list); // 直接翻转链表
return list;
}
}
思路二（递归）
从表头开始往后递归进入每一个节点，遇到尾节点后开始返回，每次返回依次添加一个值进入输出数组，直到递归返回表头
import java.util.ArrayList;
public class Solution {
//递归函数
public void recursion(ListNode head, ArrayList<Integer> res){
if(head != null){
//先往链表深处遍历
recursion(head.next, res);
//再填充到数组就是逆序
res.add(head.val);
}
}
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<Integer>();
//递归函数解决
recursion(listNode, res);
return res;
}
}
思路二（栈）
顺序遍历链表，将链表的值push到栈中
然后再依次弹出栈中的元素，加入到数组中，即可实现链表逆序
import java.util.*;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> arr = new ArrayList<Integer>();
Stack<Integer> s = new Stack<Integer>();
while(listNode!=null){
s.push(listNode.val);
listNode = listNode.next;
}
while(!s.isEmpty()){
arr.add(s.pop());
}
return arr;
}
}