剑指offer算法题1

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

　　利用题干给的条件：右边元素是比这个元素大，上边是的元素比这个元素小。于是，从左下角元素往上查找，target比这个元素小就往上找，比这个元素大就往右找。如果出了边界，则说明二维数组中不存在target元素。

public class Solution {
    public boolean Find(int target, int [][] array) {
        int rows = array.length;//该二维数组一共多少行
        int cols = array[0].length;//一共多少列
         
        int row = rows - 1;
        int col = 0;
        while(row>=0 && col <cols){
            if(target > array[row][col]){
                col++;
            }else if(target < array[row][col]){
                row --;
            }else
                return true;
        }
        return false;
    }
}

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

　　看别人的思路大多都是从前往后记录“ ”的数量，从后往前插入“%20”，也不知道用Java String的API有没违背出题人的初衷

public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuffer result = new StringBuffer();
        for(int i = 0;i < str.length(); i++){
            if(String.valueOf(str.charAt(i)).equals(" ")){
                result.append("%20");
                continue;
            }
            result.append(str.charAt(i));
        }
        return result.toString();
    }
}

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

　　看到这种逆序的，第一时间要想到用栈。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode == null){
            return new ArrayList();
        }
         
        Stack<Integer> s = new Stack<Integer>();
        while(listNode != null){
            s.push(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> result = new ArrayList();
        while(!s.isEmpty()){
            result.add(s.pop());
        }
        return result;
    }
}

用递归程序更简洁：

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

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

　　给出前序中序，重建二叉树，给张图便于理解：

剑指offer算法题1

找准root，左子树，右子树的下标，递归调用自己，不用递归的还不知道怎么写

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length == 0 || in.length == 0){
            return null;
        }
        TreeNode treeNode = new TreeNode(pre[0]);
        for(int i = 0;i < pre.length; i++){
            if(pre[0] == in[i]){
                treeNode.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                treeNode.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
                break;
            }
        }
        return treeNode;
    }
}

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

　　一个栈先进，出队列的时候判断另一个栈是否为空，为空栈一先出再由栈二弹出即能达到效果，不为空直接弹出

import java.util.Stack;
 
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
     
    public void push(int node) {
        stack1.push(node);
    }
     
    public int pop() {
        if(stack1.isEmpty()&& stack2.isEmpty()){
            throw new RuntimeException("Queue is empty!");
        }
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                int temp = stack1.pop();
                stack2.push(temp);
            }
        }
        return stack2.pop();
    }
}

相关推荐