剑指offer（01-03）题解-阿里云开发者社区

剑指offer（01-03）题解

2022-11-09 85

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 剑指offer（01-03）题解

01题解–二维数组中的查找

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路解析

重点是切记不要把这个数组当成是一直递增的，他只是保证左到右递增，上到下递增，并没有保证整体

内部都是递增，举个例子

[1,2,3,4]

[2,3,4,5]

[3,4,5,6]

[4,5,6,7]所以不能想着将它转换成一个数组然后通过二分比较来查找，这里因为里面可能有重复的元素，所以我选择的是讲个数组重新存入一个Hashset之中，这样既能排除掉重复元素，而且能直接调用Hsahset.contains()方法进行验证。

源代码

import java.util.HashSet;
public class Solution {
    public boolean Find(int target, int [][] array) {
      boolean flag=false;
      HashSet<Integer>set1=new HashSet<Integer>();
      for(int i=0;i<array.length;i++)
      {
        for(int j=0;j<array[0].length;j++)
        {
          set1.add(array[i][j]);
        }
      }
      if(set1.contains(target))
        flag=true;
    return flag;
   }
}

02题解–替换空格

题目描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are

Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路解析

这里我主要是通过记录空格出现位置，并且将他们存入list之中，之后通过数学规律来计算出重新插入字符的位置，但是其中有一点是需要注意的，就是在插入之前，我们需要先删除原有的空格，否则还是会出错。这里就先忽略删除空格的操作，先将插入的规律，除了第一个插入是可以直接在空格的位置进行插入，之后的插入都会出现位置的后移，这个通过下面的图来理解

只有第一个空是直接在原来的位置插入的，但是之后的空插入可以明显发现位置已经发生后移操作，并且可以得出，该空之前每插入一个空，就会后移两格。所以后续空插入的位置适合之前有几个空有关的。

源代码

import java.util.ArrayList;
import java.util.List;
public class Solution {
     public String replaceSpace(StringBuffer str) {
      List<Integer>list=new ArrayList<Integer>();
      for(int i=0;i<str.length();i++)
      {
        if(str.charAt(i)==' ')
          list.add(i);
      }
      for(int i=0;i<list.size();i++)
      {
        if(i==0)
        {
          str.delete(list.get(i), list.get(i)+1);
          str.insert(list.get(i), "%20");
        }
        else 
        {
          int offset=list.get(i)+2*i;
          str.delete(offset, offset+1);
          str.insert(offset, "%20");
        }
      }
      return str.toString();
    }
}

03题解–从头到尾打印链表

题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

思路解析

很明显这里我们这里就是要将链表反转，我们可以通过栈来实现，栈的特性大家都知道，就是先进后出。

源代码

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer>list=new ArrayList<Integer>();
        Stack<Integer>stack=new Stack<Integer>();
        while(listNode!=null)
        { 
              stack.push(listNode.val);
              listNode=listNode.next;
        }  
        while (!stack.empty()) {
      list.add(stack.pop());
    }
        return list;
    }
}