原创

剑指offer(一) 二维数组中的查找+替换空格+从尾到头打印链表

记录并复习一下剑指offer的部分题型~


二维数组中的查找

题目描述

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


从题目中可以看出是通过一个从左到右递增,从上到下递增的二维数组中寻找一个整数。 所以我们可以有一个思路,从下开始往上遍历,再从左往右遍历,即可得到需要的数。

public class Solution {
    public boolean Find(int target, int [][] array) {
        //二维数组长度为0或者内部一维数组长度为0直接返回false
        if(array.length == 0 || array[0].length == 0) return false;
        //从下开始往上遍历
        for(int i=array.length - 1; i >= 0; i--){
            //如果每个数组的第一个值就大于了目标值,直接进行下一轮循环
            if (array[i][0] > target){
                continue;
            }
            //然后再从左到右遍历数组,也就是从小到大
            for(int j=0;j<array[i].length; j++){
                //如果确认直接返回
                if(array[i][j] == target){
                    return true;
                }
                //如果大于则退出进入下一轮循环
                if(array[i][j] > target){
                    break;
                }
            }
        }
        //循环结束返回false;
        return false;
    }
}

替换空格

题目描述 请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。


替换空格,从后往前遍历字符串,如果遇到了空格,通过str.replace(index, index+1, targer) 进行替换

public class Solution {
    public String replaceSpace(StringBuffer str) {
        //获取字符串最后一位的下标
    	int length = str.length() - 1;
    	//只要坐标没有到-1则继续循环
        while (length >= 0){
            //当遍历得到" "的时候
            if (" ".equals(str.charAt(length)+"")){
                //通过replace进行替换空格为%20
                str.replace(length,length+1,"%20");
            }
            //下标-1
            length--;
        }
        //变为String类型返回
        String s = str.toString();
        return s;
    }
}

从尾到头打印链表

题目描述 输入一个链表,按链表从尾到头的顺序返回一个ArrayList。


最简单的可以创建一个ArrayList,然后遍历一个元素都放到下标0的位置就行。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //创建ArrayList
        ArrayList<Integer> list = new ArrayList<>();
        //当前node不为null时
        while(listNode != null){
            //往头部插入
            list.add(0, listNode.val);
            listNode = listNode.next;
        }
        //返回list
        return list;
    }
}

java
算法
链表
字符串

  • 作者:LinJy(联系作者)
  • 发表时间:2020-05-07 20:18
  • 版权声明:自由转载-非商用-非衍生-保持署名(null)
  • undefined
  • 评论

    留言