为了之后找工作不被虐，每天刷3道《剑指offer》Day-1

本文已收录于专栏 🌻 《刷题笔记》

前言

题目来源参考阿秀学长的刷题笔记，小戴只是把 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;}
}