写在前面：

- 找工作好难啊啊啊啊！救命！

剑指offer

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public class Solution {
        public boolean Find(int target, int [][] array) {
            int i = 0;
            int j = array[0].length - 1;
            while(i < array.length && j >= 0){
                if(target == array[i][j]){
                    return true;
                }else if(target > array[i][j]){ //target大，右移
                    i++;
                    continue;
                }else{ //target小，上移
                    j--;
                    continue;
                }
            }
            return false;
        }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    # -*- coding:utf-8 -*-
    class Solution:
        # array 二维列表
        def Find(self, target, array):
            i = 0
            j = len(array[0]) - 1
            while i < len(array) and j>= 0:
                if target < array[i][j]:
                    j-=1 //此处要分清 j-- 和 j-=1 的区别
                elif target > array[i][j]:
                    i+=1
                else:
                    return True
            return False

思路：矩阵有序，从上到下，从左到右变大，因此从左下角查找比较合适。

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

    1
    2
    3
    4
    5
    6
    7
    # -*- coding:utf-8 -*-
    class Solution:
        # s 源字符串
        def replaceSpace(self, s):
            # write code here
            s = s.replace(' ','%20')
            return s
    1
    2
    3
    4
    5
    6
    public class Solution {
        public String replaceSpace(StringBuffer str) {
        
            return str.toString().replaceAll(" " , "%20");
        }
    }

    java: 看了大佬的思路，先遍历字符串找到有多少个空格（也就是需要多少空间），然后从后往前替换。原因是从前往后替换每次替换都要移动空格后面的字符串一次。（大佬nb！但我好懒不想写了- -，记录一下意思意思）

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    import java.util.ArrayList;
    import java.util.Stack;
    public class Solution {
        
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            Stack<Integer> stack = new Stack<Integer>();
            while(listNode!=null){
                stack.push(listNode.val);
                listNode = listNode.next;
            }
            ArrayList<Integer> array_list = new ArrayList<Integer>();
            while(!stack.isEmpty()){
                array_list.add(stack.pop());
            }
            return list;
        }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        stack = []
        array_list = []
        while listNode:
            stack.append(listNode.val)
            listNode = listNode.next
        while stack:
            array_list.append(stack.pop())
        return array_list

    class ListNode(object):
        def __init__(self, x):
            self.val = x
            self.next = None

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    /**
    * 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){
                return null;
            }
            TreeNode root = new TreeNode(pre[0]); //前序遍历第一个元素一定是root
            for(int i = 0; i < in.length; i++){
                if(pre[0] == in[i]){ //中序遍历root左边就是left children, 右边是right children
                    root.left = reConstructBinaryTree(
                        Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i)); //递归找到所有的结点以及他们的孩子
                    root.right = reConstructBinaryTree(
                            Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
                }
            }
            return root;
        }
    }

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    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() { //若stack2非空，直接pop stack2，若为空，将stack1中元素push到stack2，再popstack2
            if(stack2.empty()){
                while(!stack1.empty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    # -*- coding:utf-8 -*-
    class Solution:

        def __init__(self):
            self.stack1 = []
            self.stack2 = []

        def push(self, node):
            self.stack1.append(node)

        def pop(self):
            if not self.stack2: 
                while self.stack1:
                    self.stack2.append(self.stack1.pop())
            return self.stack2.pop()