剑指

作者: 西二旗老司机 | 来源:发表于2019-04-22 19:33 被阅读0次

1. 二维数组中查找

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

思路：
选择该二维数组的最右上角的那个数开始扫描，当target小于该值时，可以清除一列，当target大于该值时，可以清除一行

public class Solution {
    public boolean Find(int target, int [][] array) {
        if (null == array) {
            return false;
        }
        int i = 0;//表示第一行
        int j = array[0].length;//表示该二维数组的列数
        int start;
        while (i < array.length && j > 0) {
            start = array[i][j-1];//每次清除一行或一列后的最右上角的元素
            if (target < start) {
                j--;
            } else if (target > start) {
                i++;
            } else {
                return true;
            }
        }
        return false;
    }
}

2. 替换空格

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

思路：

将每个空格替换成“%20”，则相当于每一个空格都需要新加两个字符的位置；如果考虑输入的是一个数组，为了能够让每个字符只移动一次，则可以预先预留出来足够的正合适的空间，

同时用两个指针从分别从旧的末尾和新的末尾开始向前遍历，可做到每个字符只移动一次

public class Solution {
    public String replaceSpace(StringBuffer str) {
        if (null == str || str.length() == 0) {
            return "";
        }
        int strOldLength = str.length();//最开始的字符串长度
        int blankNumber = 0;//记录空白字符的个数
        for (int i = 0; i < strOldLength; i++) {
            if (' ' == str.charAt(i)) {
                ++blankNumber;
                // 每遇到一个空格，StringBuffer都在末尾新增两个空的位置
                str.append(' ').append(' ');
            }
        }
        // 如果扫描完字符串的数组没有发现空格，则直接返回
        if (0 == blankNumber) {
            return str.toString();
        }
 
        int strNewLength = str.length();
        int firstPoint = strOldLength-1;  // 旧的末尾索引
        int lastPoint = strNewLength-1;  // 新的末尾索引
        // 当所有的空格都替换后，两个节点会相遇
        while (firstPoint >= 0 && lastPoint > firstPoint) {
            if (' ' ==  str.charAt(firstPoint)) {
                str.setCharAt(lastPoint--, '0');  // 设置当前索引位置的值为0，通过指针
                str.setCharAt(lastPoint--, '2');
                str.setCharAt(lastPoint--, '%');
            } else {
                str.setCharAt(lastPoint--, str.charAt(firstPoint));
            }
            firstPoint--;
        }
        return str.toString();
    }
}

3. 从尾到头打印链表

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

思路：
有多种解答方案：1，递归(本博客列出的代码实例) 2，栈 3，倒转链表指针，再从头到尾打印

/**
*    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 = new ArrayList();
        if (listNode == null) {
            return arrayList;
        }
        printListFromTailToHead(arrayList, listNode);
        return arrayList;
    }
    
    public void printListFromTailToHead(ArrayList array, ListNode listNode) {
        
        
        if (listNode.next == null) {//当到达链表尾部时，将值添加到ArrayList
            array.add(listNode.val);
        }else {
            printListFromTailToHead(array, listNode.next);//进入下一个节点
            array.add(listNode.val);//自己的下一个节点执行完，回退到本节点时再将值添加进ArrayList
        }
    }

4. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：
二叉树的前序序列中第一个节点永远是根节点root，中序序列中root所在的位置的左边序列，都是当前root节点的左子树，右边都是root节点的右子树，
因此，前序序列的root节点的下一位又是它的左子树的根节点，同样的规则适用于它的左右子树，所以这里我们可以用递归来实现

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        // 如果数组为空或者两个数组的长度不一致，则输入有误
        if (pre == null || in == null || pre.length < 0 || in.length < 0 || pre.length != in.length) {
            System.out.println("数组不能为空或者两个数组长度不一致");
            return null;
        }
        // 之所以需要四个位置变量，是因为需要记录前序序列的开始和结束位置，也要记录
        return reConstructBinaryTree(pre, in, 0, pre.length-1, 0, in.length-1);
        // 中序序列的开始和结束位置
    }
    // fStart表示前序序列开始节点， fStop表示前序序列结束节点，mStart表示中序序列开始节点，mStop表示中序序列结束节点
    public TreeNode reConstructBinaryTree(int [] pre, int [] in, int fStart, int fStop, int mStart, int mStop) {
 
        int rootValue = pre[fStart];
        TreeNode root = new TreeNode(rootValue);//先创建根节点
        root.left = null;
        root.right = null;
        //判断是否是只有一个节点
        if (fStart == fStop) {
            if (mStart == mStop) {
                return root;
            }else { //其实上面做了判断，这里就不会走到else子句中来
                System.out.println("两个数组输入有误");
                return null;
            }
        }
        int mm = mStart; //用一个变量记录二叉树的root节点在中序序列中的位置
        //直到在中序序列中找到root，或者遍历完中序序列数组
        while (in[mm] != rootValue && mm <= mStop) {
            ++mm;
        }
        //此时还不相等的话，说明中序序列中没有此时的root
        if (in[mm] != rootValue) {
            System.out.println("中序序列中没有与前序序列中确定的root节点相等的节点值");
            return null;
        }
        //这里一定要这样写，记录移动的位置
        int mLengh = mm - mStart;
        //前序序列当前的树开始的节点位置+移动的位置就等于当前树的子树的结束位置
        int fLeftSubTreeStop = fStart + mLengh;
 
        if (mm > mStart) {
            root.left = reConstructBinaryTree(pre, in, fStart+1, fLeftSubTreeStop, mStart, mm-1);
            //(前序序列数组，中序序列数组，前序序列当前树开始节点的后一位，
            //前序序列当前树的子树结束的位置，中序序列当前树开始的位置，中序序列root位置的前一位)
        }
        if (mm < mStop) {  
            root.right = reConstructBinaryTree(pre, in, fLeftSubTreeStop+1, fStop, mm+1, mStop);
            //(前序序列数组，中序序列数组，前序序列当前树的子树结束的位置的前一位，
            //前序序列中当前树结束的位置，中序序列root位置的后一位，中序序列中当前树结束的位置
        }
        return root;
    }
}

5. 用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

思路：

将stack1当做入队列，将stack2当做出队列，当队列需要push入队列一个元素的时候，直接push到stack1就可以了；当队列需要pop出队列时

首先判断stack2是否为空，如果为空，则将stack1中的元素全部pop出来并依次push到stack2中，再让stack2来pop一下就可以了；如果不为空，stack2直接pop一下就行。


import java.util.Stack;
 
public class Solution {//思路：将stack1当做入队列，将stack2当做出队列，当队列需要push入队列一个元素的时候，直接push到stack1就可以了；当队列需要pop出队列时
    //，首先判断stack2是否为空，如果为空，则将stack1中的元素全部pop出来并依次push到stack2中，再让stack2来pop一下就可以了；如果不为空，stack2直接pop一下就行。
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if (stack2.size() == 0) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        if (stack2.size() == 0) {//当stack1和stack2都长度为0的时候，运行到这里还是会出现stack2的长度为0，所以要做异常处理
            System.out.println("stack1和stack2的长度都为0，不能进行pop操作，抛出异常");
            return -1;
        }
        return stack2.pop();
    }
}

6. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

思路：对一个n长度的非减排序数组进行旋转有两种情况：

第一：旋转了1～n-1个数字，会形成两个非减排序的子数组，如： 4 5 和 1 2 3；它的最小值是在第二个子数组的开头，同时，第一个子数组的所有元素都大于或者等于第二个子数组，可以利用二分查找法来处理；

第二：旋转了0个数字，得到的旋转数组仍然是原数组：1 2 3 4 5，最小值就是第一个元素

注意：第二种情况里面：当数组头节点=尾节点=中间节点的时候，无法用二分查找来缩小查找范围，如：0 1 1 1 1 1 ，旋转 0 1 1 1 1变成：1 0 1 1 1 1,，只能用顺序查找

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if (null == array || array.length == 0) {
            return 0;
        }
        int n = array.length - 1;
        int first = 0;//二分查找的开头元素位置索引
        int min = first;//用一个新的元素记录最小值，是为了方便如果是第二种情况，就不需要循环直接返回首节点
        int last = n-1;//二分查找的末尾元素位置索引
        int middle = 0;//中间节点位置索引
        while (array[first] >= array[last]) {//当数组的开头节点大于等于数组的末尾节点时，需要进行循环判断
            if (last - first == 1) {//当二分查找的结束索引与开始索引之间相邻的时候，说明就找到了最小元素，
                //而且最小元素是结束索引上的元素(因为first指针总会指向第一个子数组，而第二个子数组总会指向第二个子数组)
                min = last;
                break;
            }
            middle = first + (last-first)/2;
            if (array[first] == array[middle] && array[middle] == array[last]) {//此时无法用二分查找
                // return 。。。
                //此处省略顺序查找的方法
            }
            if (array[middle] >= array[first]) {//当中间元素大于等于二分查找数组的开头元素时，说明中间元素落在了第一个子数组中，最小元素要去后面找
                first = middle;
            }else if (array[middle] <= array[last]) {//否则当中间元素小于等于二分查找数组的末尾元素时，说明中间元素落在了第二个子数组中，最小元素去前面找
                last = middle;
            }
        }
        //如果数组的第一个元素小于最后一个元素，说明：非减排序的数组的旋转数组是它本身：1 2 3 4 5，这时第一个元素就是最小元素
        return array[min];
    }
}

剑指

1. 二维数组中查找

2. 替换空格

3. 从尾到头打印链表

4. 重建二叉树

5. 用两个栈实现队列

6. 旋转数组的最小数字

7.

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读