剑指 Offer Java 实现

2018-02-27

Tips

注意考虑边界条件、特殊输入以及错误处理，一定要对输入值做判断。
采用画图将抽象问题形象化、举例将抽象问题具体化和分解问题将复杂问题简单化的方法来理清思路

1. 实现 Singleton 模式

+ (instanceType *)sharedInstance {
    static instanceType *sharedInstance = nil;
    static dispatch_once_t onceToken;
    dispatch_once(&onceToken, ^{
        sharedInstance = [[instanceType alloc] init];
    });
    
    return sharedInstance;
}

线程安全，保证在应用的 lifetime 中只生成一次。其他一些语言实现需要加同步锁如 Java

private static MyObject instance;

public static synchronized MyObject getInstance() {
    if (instance == null){
        instance = new MyObject();
    }
    
    return instance;
}

2.数组中重复的数字

/**
 * Created by qingliu on 2/27/18.
 */

// 面试题3（一）：找出数组中重复的数字
// 题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，
// 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，
// 那么对应的输出是重复的数字2或者3。
public class DuplicationInArray {
    public static void main(String args[]){
        int a[] = {2,1,3,4,2};
        duplicate(a);
    }

    public static boolean duplicate(int[] numbers){
        //判断是否为空和长度是否为 0
        if (numbers == null || numbers.length <= 0){
            return false;
        }

        //数组每个值要符合 0~n-1
        for (int i = 0; i < numbers.length; i++){
            if (numbers[i] < 0 || numbers[i] > numbers.length -1){
                return false;
            }
        }

        for (int i = 0; i < numbers.length; i++){
            while (numbers[i] != i){
                //如果当前位置的值定于以该值为下标处的值则找到了重复的
                if (numbers[i] == numbers[numbers[i]]){
                    System.out.println("找到的其中一个值为：" +  numbers[i]);
                    return true;
                }

                //若不等于则交互两个位置的值，这样数组下标值就等于当前存储的值
                int tempNumber = numbers[i];
                numbers[i] =  numbers[tempNumber];
                numbers[tempNumber] =  tempNumber;

            }
        }
        System.out.println("没有找到任何一个重复数字");
        return  false;
    }
}

3.二维数组中的查找

package com.company;

/**
 * Created by qingliu on 2/27/18.
 */
 
// 面试题4：二维数组中的查找
// 题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按
// 照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个
// 整数，判断数组中是否含有该整数。

public class FindNumInMatrix {

    public static void main(String args[]){
        int[][] testData = {{1,2,8,9},{3,6,10,13},{4,5,11,14},{5,8,12,15}};
        int[][] num = new int[4][4];
        boolean result = Found(testData,4,4,5);
        if(result){
            System.out.println("Found it");
        }
        else {
            System.out.println("Not Found");
        }
    }

    public static boolean Found(int[][] data,int rows,int columns,int targetNum){
        boolean found = false;
        if (data != null && rows > 0 && columns > 0){
            int row = 0;
            int column = columns - 1;
            while (row < rows && column >=0){
                if (data[row][column] == targetNum){
                    found = true;
                    break;
                }
                else if (data[row][column] > targetNum){ //右上角元素大于目标数字则剔除所在列
                    column--;
                }
                else {      //否则目标数组大于该数字，行数增加
                    row++;
                }
            }
        }

        return found;
    }
}

4.替换空格

package com.company;

/**
 * Created by qingliu on 2/27/18.
 */

/*
* 面试题5：替换空格
* 题目：请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入“We are happy.”，
* 则输出“We%20are%20happy.”。
**/

public class ReplaceSpace {

    public static void main(String args[]){
        String testData = "Hello World! #$#$!!@!@";
        char[] test = new char[testData.length() + 4];
        char[] testDataArray = testData.toCharArray();
        for (int i = 0; i < testDataArray.length; i++){
            test[i] = testDataArray[i];
        }
        replace(test,testData.length(),testData.length() + 4);
    }

    public static void replace(char[] testStr,int strLength,int storeLength){

        if (testStr == null || testStr.length == 0){
            return;
        }

        int length = strLength;
        int numberOfBlank = 0; //空格计数
        for (int i = 0; i < strLength; i++){
            if (testStr[i] == ' '){
                numberOfBlank++;
            }
        }

        int newStrLength = length + numberOfBlank*2;
        if (newStrLength > storeLength){ //若给定空间不够存储则直接返回
            return;
        }

        int indexOfOriginal = length - 1;
        int indexOfNew = newStrLength -1;
        while (indexOfOriginal >=0 && indexOfNew > indexOfOriginal){
            if (testStr[indexOfOriginal] == ' '){  //若前面指针已经找到空格则后面的指针开始填充
                testStr[indexOfNew--] = '0';
                testStr[indexOfNew--] = '2';
                testStr[indexOfNew--] = '%';
            }
            else {
                testStr[indexOfNew--] = testStr[indexOfOriginal]; //若没找到则将前面指针的值拷贝到后面指针存储
            }

            indexOfOriginal--;
        }

        String result = String.valueOf(testStr);
        System.out.println(result);
    }
}

5.从尾到头打印链表

package com.company;

/**
 * Created by qingliu on 2/28/18.
 */

// 面试题6：从尾到头打印链表
// 题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。
    
public class PrintListInReversedOrder {

    public static void main(String args[]){
        Node one = new Node();
        Node two = new Node();
        Node three = new Node();
        Node four = new Node();

        one.item = 1;
        one.next = two;
        two.item = 2;
        two.next = three;
        three.item = 3;
        three.next = four;
        four.item = 4;

        printReverseList(one);
    }

    private static class Node{
        int item;
        Node next;
    }

    public static void printReverseList(Node listNode){
        Stack<Integer> nodes = new Stack<>();

        Node node = listNode;
        while (node != null){
            nodes.push(node.item);
            node = node.next;
        }

        while (!nodes.isEmpty()){
            int outputNode = nodes.pop();
            System.out.println(outputNode);
        }
    }

}

栈的实现

package com.company;

import java.util.Iterator;

/**
 * Created by qingliu on 2/28/18.
 */
public class Stack<Item> implements Iterable<Item> {

    private Node first; // top of the stack
    private int N; //numbers of item

    private class Node{
        Item item;
        Node next;
    }

    public boolean isEmpty(){ return first == null; }
    public int size(){ return N; }

    public void push(Item item){
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        N++;
    }

    public Item pop(){
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }

    @Override
    public Iterator<Item> iterator() {
        return new ListIterator();
    }

    private class ListIterator implements Iterator<Item>{
        private Node current =  first;

        public boolean hasNext(){
            return current != null;
        }
        public void remove(){ }

        @Override
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}