剑指Offer Java题解（前3道题）

目录

1. 二维数组中的查找

2. 替换空格

3. 从尾到头打印链表

1. 二维数组中的查找

题目链接：传送。

方法一，暴力枚举。

参考代码：

package problem01;

/**
 * @Author syrdbt
 * @Date 2019/7/3 14:05
 * 二维数组中的查找
 * 方法一，暴力枚举
 */
public class Solution {
    public boolean Find(int target, int [][] array) {
        if (array == null) {
            return false;
        }

        int rows = array.length;
        int columns = array[0].length;

        if(rows == 0 || columns == 0) {
            return false;
        }

        for (int i=0; i<rows; i++) {
            if (array[i][0] > target || array[i][columns-1]<target) {
                continue;
            }
            for (int j=0; j<columns; j++) {
                if (array[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

运行截图：

方法二，二分查找。

package problem01;

/**
 * @Author syrdbt
 * @Date 2019/7/12 14:57
 * 二维数组中的查找
 * 方法二，二分查找
 */
public class Solution01 {
    public boolean Find(int target, int [][] array) {
        if (null == array) {
            return false;
        }

        int rows = array.length;
        int columns = array[0].length;

        if(rows <= 0 || columns <= 0) {
            return false;
        }

        for (int i=0; i<rows; i++) {
            if (array[i][0] > target || array[i][columns-1]<target) {
                continue;
            }
            if(findInLine(target, array[i])) {
                return true;
            }
        }
        return false;
    }

    /**
     * 在一行中进行二分查找
     * @param target 目标值
     * @param array 一行数组
     * @return 查找到返回 true，否则返回 false
     */
    public boolean findInLine(int target, int [] array) {
        int right = array.length;
        int left = 0;
        int mid = (right+left)/2;
        while(left < right) {
            if(array[mid] < target) {
                left = mid+1;
            } else {
                right = mid;
            }
            mid = (left+right)/2;
        }
        if(array[left] == target) {
            return true;
        } else {
            return false;
        }
    }
}

运行截图：

方法三：从左下角，向上递减，向右递增。  如果当前数字比带查找值小，向右移动 ， 如果当前数字比带查找值大，向上移动。

参考代码：

package problem01;

/**
 * @Author syrdbt
 * @Date 2019/7/12 15:00
 * 二维数组中的查找
 * 方法三，利用它的条件
 * 每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序
 * 从左下角，向上递减，向右递增。
 * 如果当前数字比带查找值小，向右移动
 * 如果当前数字比带查找值大，向上移动
 */
public class Solution02 {
    public boolean Find(int target, int[][] array) {
        if (null == array) {
            return false;
        }
        int rows = array.length;
        int columns = array[0].length;
        if (rows == 0 || columns == 0) {
            return false;
        }

        int i=rows-1, j=0;
        while (i>=0 && j<columns) {
            if (array[i][j] == target) {
                return true;
            } else if (array[i][j] < target) {
                ++j;
            } else {
                --i;
            }
        }
        return false;
    }
}

运行截图：

2. 替换空格

题目链接：传送。

方法一：手写替换，使用 StringBuilder 。

package problem02;

/**
 * @Author syrdbt
 * @Date 2019/7/3 14:34
 */
public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuilder result = new StringBuilder();
        for(int i=0; i<str.length(); i++) {
            if (str.charAt(i) == ' ') {
                result.append("%20");
            } else {
                result.append(str.charAt(i));
            }
        }
        return result.toString();
    }
}

运行截图：

方法二：string 的 replace 函数。

参考代码：

package problem02;

/**
 * @Author syrdbt
 * @Date 2019/7/12 15:47
 */
public class Solution01 {
    public String replaceSpace(StringBuffer str) {
        return str.toString().replaceAll(" ", "%20");
    }
}

运行截图：

3. 从尾到头打印链表

题目链接：传送

参考代码：

package problem03;

import java.util.ArrayList;

/**
 * @Author syrdbt
 * @Date 2019/7/12 15:58
 */

//class ListNode {
//    int val;
//    ListNode next = null;
//
//    ListNode(int val) {
//        this.val = val;
//    }
//}

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        while (listNode != null) {
            arrayList.add(0, listNode.val);
            listNode = listNode.next;
        }
        return arrayList;
    }
}

运行截图：