目录
1. 二维数组的查找
2. 替换空格
3. 从尾到头打印链表
4. 链表中环的入口节点
5. 重建二叉树
写在前面: 本随笔中包含五道题: 题目描述, 题目思路以及对应解法.
1. 二维数组的查找
在一个二维数组中(每个一维数组的长度相同), 每一行都按照从左到右递增的顺序排序, 每一列都按照从上到下递增的顺序排序. 请完成一个函数, 输入这样的一个二维数组和一个整数, 判断数组中是否含有该整数.
找到最大或最小值, 然后以此为界, 进行查找.
1, 暴力解:
- public class Solution {
- public boolean Find(int target, int [][] array) {
- int n=array[0].length;
- for(int i=0;i<n;i++){
- for(int j=0;j<n;j++){
- if(array[i][j]==target){
- return true;
- }
- }
- }
- return false;
- }
- }
2, 从左下开始比较:
- public class Solution {
- public boolean Find(int target, int [][] array) {
- int rowLen=array[0].length;// 列数
- int colLen=array.length;// 行数
- // 从左下角开始, 大于则向右找, 小于则向上
- int j=0;
- for(int i=colLen-1;i>=0;i--){
- if(j<rowLen){
- if(target>array[i][j]){
- j++;
- i++;// 右移, i 不变, 该步抵消 i--
- }else if(target==array[i][j]){
- return true;
- }
- }
- }
- return false;
- }
- }
2. 替换空格
请实现一个函数, 将一个字符串中的每个空格替换成 " ". 例如, 当字符串为 We Are Happy. 则经过替换之后的字符串为 We Are Happy.
重点是考虑边界问题, 全为空格; 末尾有空格等情况
1, 遍历:
- public class Solution {
- public String replaceSpace(StringBuffer str) {
- String demo=str.toString();
- String temp="";
- for(int i=0;i<demo.length();i++){
- if(demo.charAt(i)==' '){
- temp+=" ";
- }else{
- temp+=demo.charAt(i);
- }
- }
- return temp;
- }
- }
2, 如果要求在原字符串上进行操作. 则先计算新字符串的长度进行扩展. 然后从后向前依次替换空格.
- public class Solution {
- public String replaceSpace(StringBuffer str) {
- int spaceNum=0;
- // 计算空格数量,
- for(int i=0;i<str.length();i++){
- if(str.charAt(i)==' '){
- spaceNum++;
- }
- }
- int indexOld=str.length()-1;
- str.setLength(str.length()+spaceNum*2);
- int indexNew=str.length();// 扩容后长度
- for(int i=indexNew-1;i>=0 && indexOld>=0;i--){// 从末尾开始
- if(str.charAt(indexOld)==' '){
- str.setCharAt(i,'0');
- str.setCharAt(i-1,'2');
- str.setCharAt(i-2,'%');
- i=i-2;
- indexOld--;
- }else{
- str.setCharAt(i,str.charAt(indexOld));
- indexOld--;
- }
- }
- return str.toString();
- }
- }
3. 从尾到头打印链表
输入一个链表, 按链表从尾到头的顺序返回一个 ArrayList.
暴力解或递归
1, 暴力解:
- import java.util.ArrayList;
- public class Solution {
- public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
- ArrayList<Integer> al=new ArrayList<Integer>();
- if(listNode==null){// 判空
- return al;
- }
- al.add(listNode.val);
- while(listNode.next!=null){
- listNode=listNode.next;
- al.add(listNode.val);
- }
- ArrayList<Integer> result=new ArrayList<Integer>();
- for(int i=al.size()-1;i>=0;--i){
- result.add(al.get(i));
- }
- return result;
- }
- }
- // 注: ArrayList 的 add(int index,E element)方法在添加时会将 index 处元素后移
2, 递归:
- import java.util.*;
- public class Solution {
- ArrayList<Integer> list = new ArrayList();
- public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
- // 从最后一个节点开始加入列表
- if(listNode!=null){
- printListFromTailToHead(listNode.next);
- list.add(listNode.val);
- }
- return list;
- }
- }
4. 链表中环的入口节点
给一个链表, 若其中包含环, 请找出该链表的环的入口结点, 否则, 输出 null.
先判断是否有环(快慢指针, 相遇则有环), 若有环, 则令两个指针, 一个从头节点, 一个从相遇点分别开始走, 再次相遇的点即环的入口节点.
1, 双指针:
- public ListNode EntryNodeOfLoop(ListNode pHead)
- {
- if(pHead==null||pHead.next==null){
- return null;
- }
- // 判断有无环
- ListNode slow=pHead;
- ListNode fast=pHead;
- boolean flag=false;
- while(fast!=null&&fast.next!=null){
- fast=fast.next.next;
- slow=slow.next;
- if(fast==slow){
- flag=true;
- }
- break;
- }
- // 两者相遇时循环结束, 此时开始计算环中结点的数目
- int count=0;
- while(fast.next!=slow){
- count++;
- fast=fast.next;
- }
- count++;// 环的节点数
- ListNode fir=pHead;
- ListNode sec=pHead;
- for(int i=0;i<count;i++){
- fir=fir.next;
- }// 第一个指针走了 count 步
- // 两者开始一起走, 相遇的点即入口点. 第二个指针与入口点的距离 = 总结点数 - 环中的结点数
- // 因为第一个指针走了环中结点数, 所以两者必在入口点相遇. 第二个指针到达入口节点时第一个指针走了一圈到达入口结点.
- while(fir!=sec){
- fir=fir.next;
- sec=sec.next;
- }
- return fir;
- }
5. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果, 请重建出该二叉树. 假设输入的前序遍历和中序遍历的结果中都不含重复的数字. 例如输入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列{4,7,2,1,5,3,8,6}, 则重建二叉树并返回.
一般情况下树的题目都可以考虑递归方法, 找到递归的退出条件(本题即: 前序和中序序列只剩下一个节点), 在完成的基础上对代码进行优化.
1, 递归:
- /**
- * 递归解决
- * 跳出条件是只剩下一个节点, 返回赋值给上一个根节点的左或右子树
- * @param pre
- * @param in
- * @return
- */
- public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
- // 前序: 根左右; 中序: 左根右
- /*if(pre==null || in == null ){
- return null;
- }*/
- TreeNode root=new TreeNode(pre[0]);// 根节点
- if(pre.length==in.length && pre.length==1){// 若前序和中序遍历都只剩下一个节点则返回该节点
- return root;
- }
- int mid=0;
- // 找到中序遍历中根节点的位置
- for(int i=0;i<in.length;i++){
- if(in[i]==root.val){
- mid=i;
- }
- }
- int left=mid;// 左子树的节点个数
- int right=in.length-mid-1;// 右子树的节点个数
- // 递归
- if(left>0){
- int leftpre[]=new int[left];
- int leftin[]=new int[left];
- for(int i=0;i<left;i++){
- leftpre[i]=pre[i+1];
- leftin[i]=in[i];
- }
- root.left=reConstructBinaryTree(leftpre,leftin);// 左子树的前序遍历和左子树的中序遍历
- }
- if(right>0){
- int rightpre[]=new int[right];
- int rightin[]=new int[right];
- for(int i=0;i<right;i++){
- rightpre[i]=pre[i+1+left];
- rightin[i]=in[i+left+1];
- }
- root.right=reConstructBinaryTree(rightpre,rightin);// 右子树的前序遍历和左子树的中序遍历
- }
- return root;
- }
2, 递归精简版:
- public TreeNode reConstructBinaryTree1(int [] pre,int [] in) {
- TreeNode root=reConstructBinaryTree1(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 reConstructBinaryTree1(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
- if(startPre>endPre||startIn>endIn)
- return null;
- TreeNode root=new TreeNode(pre[startPre]);
- for(int i=startIn;i<=endIn;i++)
- if(in[i]==pre[startPre]){
- /*startPre+i-startIn 是 startPre + 左子树的节点个数 得到前序序列的末尾位置 */
- root.left=reConstructBinaryTree1(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
- root.right=reConstructBinaryTree1(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
- break;
- }
- return root;
- }
如有错误, 欢迎指正
来源: https://www.cnblogs.com/lfz1211/p/12678422.html