在校招题解的算法篇中，还整理了部分《剑指offer》原题，这里均用Java实现。

• 校招面试题解
• 剑指offer题解(部分)

1.校招面试题解

注：题目源于2019Android秋招提前批面试总结之数据结构&算法

Q：怎样了解数据结构？

• 技术点：数据结构
• 思路：数据结构的定义、分类
• 参考答复：研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构依然是原来的结构类型。
  • 按照逻辑结构分类
    • 线性结构：线性表、栈、队列
    • 非线性结构：树、图
  • 按照存储结构分为顺序结构、链式结构、索引结构、哈希结构

Q：什么是斐波那契数列？

• 技术点：递归和循环
• 思路：斐波那契数列的定义
• 参考答复：斐波那契数列指的是这样的数列1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...即这个数列从第3项开始，每一项都等于前两项之和，数学表示F(1)=1，F(2)=1, F(3)=2,F(n)=F(n-1)+F(n-2)（n>=4，n∈N*）

Q：迭代和递归的特点，并比较优缺点

• 技术点：递归和循环
• 参考答复：递归和迭代都是循环的一种，特点：
  • 递归就是通过重复调用函数自身实现循环；满足终止条件时会逐层返回来结束循环
  • 迭代通过函数内某段代码实现循环；使用计数器结束循环

Q：理解哪些查找算法，时间复杂度都是多少？

• 技术点：查找
• 参考答复：代码详见java实现常见查找算法

Q：理解哪些排序算法，并比较一下，以及适用场景

• 技术点：排序
• 参考答复：代码详见十大经典排序算法最强总结（含JAVA代码实现）

（要求排序结果从小到大）

Q：快排的基本思路是什么？最差的时间复杂度是多少？如何优化？

• 技术点：排序

• 参考答复：快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小；再分别对这两部分记录继续进行排序，以达到整个序列有序的目的。当待排序列有序时会出现最坏时间复杂度O(n2)。几种优化方式：

  • 当待排序序列的长度较小时采用直接插入排序
  • 优化所选取数轴的计算方法，如三数取中
  • 迭代取代递归，效率高
  • 存储数轴值，节省无必要的交换

Q：二叉排序树插入或者删除一个节点的过程是怎么的？

• 技术点：查找
• 参考答复：
  • 二叉排序树插入操作：先查找该元素能否存在于二叉排列树中并记录其根节点，若没有则比较其和根节点大小后插入相应位置
  • 二叉排序树删除操作：
    • 待删除节点是叶子节点，直接删除就可
    • 待删除节点是仅有左或者右子树的节点 ，上移子树就可
    • 待删除节点是左右子树都有的节点 ，用删除节点的直接前驱或者直接后继来替换当前节点

Q：什么是红黑树？

• 技术点：查找
• 参考答复：红黑树是一种自平衡二叉查找树，包含性质：
  • 节点是红色或者黑色
  • 根节点是黑色
  • 叶子节点是黑色
  • 每个红色节点的两个子节点都是黑色
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

Q：100盏灯问题

• 题目说明：100盏灯问题
• 思路：最后亮着的灯是被拉动次数为奇数次的；因为只有完全平方数的约数个数为奇数，故本题转换为求100内完全平方数的个数

Q：7瓶水1瓶有毒3只老鼠，怎样找有毒的水，再加个条件，必需要求第二天出结果

• 技术点：查找
• 思路：若无时间限制，可采用相似二分查找的思路；若要求第二天出结果，用二进制编码的思路
• 参考答复：
  • 二分查找思路，每次均分两组，每组各取一滴水混合成新溶剂喂给老鼠，继续对导致老鼠死亡的一组水进行同上操作。如果是第1瓶有毒，过程演绎如下，第一只老鼠死于前一堆（mid=(0+6)/2=3，即服用了第1、2、3、4瓶的混合溶剂），第二只老鼠死于前一堆（mid=(0+3)/2=1，即服用了第1、2瓶的混合溶剂），第三只老鼠随便试一瓶，根据服用后状态就可判断有毒的水。
  • 二进制编码思路，对每瓶水二进制编码，所需编码位数正好为三位，将第一位是1的水混为新溶剂喂给第一个老鼠，以此类推，看三只老鼠服用状态（死亡=1，存活=0）得出对应的编码，找到对应的水就可。如果是第1瓶有毒，编码之后，让第一只老鼠服用第4、5、6、7瓶的混合溶剂，第二只老鼠服用第2、3、6、7瓶的混合溶剂，第三只老鼠服用第1、3、5、7瓶的混合溶剂，最终第一只和第二只老鼠存活，第三只老鼠死亡，对应编码为001，对应的水是第一瓶，故此瓶有毒。
    **
    第一瓶水 001
    第二瓶水 010
    第三瓶水 011
    第四瓶水 100
    第五瓶水 101
    第六瓶水 110
    第七瓶水 111
    **

Q：海量数据问题

• 技术点：海量数据问题
• 思路：分治、哈希、bit、堆
• 参考答复：海量数据解决面试题集锦

Q：（手写算法）二分查找

• 技术点：查找
• 参考代码：

public static int binarySearch(int[] a, int key) {    int low, mid, high;    low = 0;//最小下标    high = a.length - 1;//最大小标    while (low <= high) {        mid = (high + low) / 2;//折半下标        if (key > a[mid]) {            low = mid + 1; //关键字比折半值大，则最小下标调成折半下标的下一位        } else if (key < a[mid]) {            high = mid - 1;//关键字比折半值小，则最大下标调成折半下标的前一位        } else {            return mid; //关键字和折半值相等时返回折半下标        }    }    return -1;}

Q：（手写算法）反转链表

• 技术点：链表
• 思路：
  • 方法1：重复将首节点的下一个节点调整到最前面，如链表1->2->3->4，调整过程为2->1->3->4，3->2->1->4，4->3->2->1
  • 方法2：递归，使链表从尾节点开始指向前一个节点
• 参考代码：

//节点类public class ListNode {     int val;     ListNode next = null;     ListNode(int val) {          this.val = val;    }}//方法1public ListNode reverseLinkedList(ListNode head){        if (head == null || head.next == null){            return head;        }        ListNode p = new ListNode(-1);//拟一个头节点    p.next = head;        ListNode nextNode = head.next;        while (nextNode != null){                //后一个节点调整到最前            head.next = nextNode.next;            nextNode.next = p.next;            p.next = nextNode;            nextNode = head.next;        }        return p.next;}//方法2，递归public ListNode reverseLinkedList(ListNode head) {    if (head == null || head.next == null) {         return head;    }     ListNode pNode = reverseLinkedList(head.next);    head.next.next = head;    head.next = null;    return pNode;   }

Q：（手写算法）用两个栈实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

• 技术点：栈和队列
• 思路：
  • 入队：将元素进栈A

  • 出队：判断栈B能否为空，假如为空，则将栈A中所有元素pop，并push进栈B，栈B出栈， 反之栈B直接出栈

    
    
• 参考代码：

public class Solution {    Stack<Integer> stack1 = new Stack<Integer>();    Stack<Integer> stack2 = new Stack<Integer>();     //入队     public void add(int node) {        stack1.push(node);    }    //出队     public int poll() {        if(stack1.empty()&&stack2.empty()){            throw new RuntimeException("Queue is empty!");        }        if(stack2.empty()){            while(!stack1.empty()){                stack2.push(stack1.pop());            }        }        return stack2.pop();    }}

Q：（手写算法）用两个队列实现一个栈，完成栈的Push和Pop操作。 队列中的元素为int类型。

• 技术点：栈和队列
• 思路：
  • 入栈：将元素进队列A

  • 出栈：判断队列A中元素的个数能否为1，假如等于1则直接出队列A，否则将队列A中的元素依次出队列并放入队列B、直到队列A中只剩一个原色，而后队列A出队列，再把队列B中的元素以此出队列并放入队列A

    
    
• 参考代码：

public class Solution {     Queue<Integer> queue1 = new ArrayDeque<Integer>();    Queue<Integer> queue2 = new ArrayDeque<Integer>();        //入栈    public void push(int node) {        queue1.add(node);    }      //出栈    public int pop() {         if(queue1.isEmpty()&&queue2.isEmpty()){            throw new RuntimeException("Stack is empty!");         }         if(queue1.isEmpty()){            while(!queue2.isEmpty()){                queue1.add(queue2.poll());            }          }         if(queue1.size()!=1){             while(queue1.size()!=1){                queue2.add(queue1.poll());             }                 }         return queue1.poll();    }}

Q：（手写算法）用三个线程，顺序打印字母A-Z，输出结果是1A、2B、3C、1D 2E...

• 技术点：线程同步
• 思路：加锁进行限制，并配合wait()和notifyAll()
• 参考代码：

private static char c = 'A';private static int i = 0;public static void main(String[] args) {            Runnable runnable = new Runnable() {           public void run() {              synchronized (this) {//加锁                try {                    int threadId = Integer.parseInt(Thread.currentThread().getName());                    while (i < 26) {                         if (i % 3 == threadId - 1) {                             System.out.println(threadId +""+ (char) c++);                             i++;                             notifyAll();// 唤醒处于等待状态的线程                         } else {                             wait();// 释放当前锁并进入等待状态                         }                    }                } catch (InterruptedException e) {                    e.printStackTrace();                }              }//执行结束释放当前锁           }        };        Thread t1 = new Thread(runnable, "1");        Thread t2 = new Thread(runnable, "2");        Thread t3 = new Thread(runnable, "3");        t1.start();        t2.start();        t3.start();}

Q：（手写算法）如何判断一个链有环，请找出该链表的环的入口结点，否则输出null

• 技术点：链表
• 思路：用p1、p2指向链表头部，而后p1每次走一步、p2每次走两步；显然，当p1和p2第一次相遇时，p2正好比p1多走了一个环；设p2此时走了2x步，p1走了x步，则环长=2x-x=x，因而p1和p2相遇点正好是环的入口点，只需找到p1==p2时的节点就可
• 参考代码：

//节点类ListNode同上public class Solution {    public ListNode EntryNodeOfLoop(ListNode pHead){        if(pHead == null || pHead.next == null){            return null;        }        ListNode p1 = pHead;        ListNode p2 = pHead;        while(p2 != null && p2.next != null ){            p1 = p1.next;//p1每次走一步            p2 = p2.next.next;//p2每次走两步            if(p1 == p2){                p2 = pHead;                while(p1 != p2){                    p1 = p1.next;                    p2 = p2.next;                }                if(p1 == p2){                    return p1;//p1和p2相遇点正好是环的入口点                }            }        }        return null;    }}

Q：（手写算法）如何判断两条链交叉

• 技术点：链表
• 思路：分别考虑链表上能否存在环的情况
• 参考代码：JAVA 判断两个单链表能否相交并求交点

Q：（手写算法）快速从一组无序数中找到第k大的数（或者前k个大的数）

• 技术点：排序
• 思路：利用快排思想，直至找到一个排在第k位置的枢轴，由于左边所有数据都比它大，右边都比它小。
• 参考代码：

public class QuickSort {        public int partition(int[] arr,int low,int high){        int temp=arr[low];        while(low<high){            while(arr[high]<=temp&&high>low){                high--;            }            arr[low]=arr[high];            while(arr[low]>=temp&&low<high){                low++;            }            arr[high]=arr[low];        }        arr[high]=temp;        return high;            }    public void findK(int k,int[] arr,int low,int high){        int temp=partition(arr,low,high);        if(temp==k-1){            System.out.print("第"+k+"大的数是："+arr[temp]);        }else if(temp>k-1){            findK(k,arr,low,temp-1);                    }else{            findK(k,arr,temp+1,high);        }    }}

Q：（手写算法）从字符串中找出一个最长的不包含重复数字的子字符串的长度。例如在字符串中”arabcacfr”，最长非重复子字符串为“rabc”或者”acfr”，长度为4。

• 技术点：字符串
• 思路：使用动态规划。先用长度为26的数组positions来存储当前字符上次出现的位置；再定义字符串长度的数组lines表示以当前字母为结尾的最长不含重复字符的子字符串的长度。依次遍历字符串中的字符：
  • 若当前字符是第一次出现，说明可以直接增加到前一个非重复子字符串，因而lines[i]=lines[i-1]+1；
  • 若当前字符非第一次出现，需计算当前字符与它上次出现位置之间的距离d：
    • 若d大于lines[i-1]，说明前一个非重复子字符串中没有包含当前字符，可以增加当前字符到前一个非重复子字符串中，因而lines[i]=lines[i-1]+1；
    • 若d小于或者等于f(i-1)，说明假如加入当前字符会存在重复字符串，需要把上次出现的字符截开，因而lines[i] = d
• 参考代码：

private int findLongestSubstringLength(String string){        if (string == null || string.equals("")) {            return 0;        }        int maxLength = 0;//最长不重复子字符串的长度        int[] positions = new int[26];//存储当前字符上次出现的位置，-1表示没有出现过        for (int i = 0; i < positions.length; i++){            positions[i] = -1;         }        int[] lines = new int[string.length()];//存储以当前字符为尾的最长不重复子字符串的长度        lines[0]=1;        positions[string.charAt(0) - 'a']=0;        for (int i = 1; i < string.length(); i++){            int prePosition = positions[string.charAt(i) - 'a'];            if(prePosition>=0){//当前字符非第一次出现                if((i-prePosition)>lines[i-1]){                    lines[i]=lines[i-1]+1;                }else{                    lines[i]=i-prePosition;//若加入当前字符会出现重复，需要截断                }            }else{//当前字符是第一次出现                lines[i]=lines[i-1]+1;            }            positions[string.charAt(i) - 'a'] = i;            if(lines[i]>maxLength){                maxLength=lines[i];            }        }        return maxLength;}

2.剑指offer题解

注：题目源于牛客网_剑指Offer

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

• 技术点：链表
• 思路：通过递归实现链表节点从尾到头依次插入到ArrayList
• 参考代码：

//节点类ListNode同上import java.util.ArrayList;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;    }}

Q：在一个排好序的链表中存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，并返回链表头指针。 例如，链表1->2->3->3->4->4->5 解决后为 1->2->5。

• 技术点：链表
• 思路：从头节点开始假如下个节点与当前节点重复，则找到第一个与当前不同的节点开始递归，反之，保留当前结点并从下一个结点开始递归
• 参考代码：

//节点类ListNode同上public class Solution {    public ListNode deleteDuplication(ListNode pHead)    {        if (pHead == null || pHead.next == null) {             return pHead;//中止递归条件        }        if (pHead.val == pHead.next.val) {            //假如下个节点与当前节点重复，则找到第一个与当前不同的节点开始递归            ListNode pNode = pHead.next;            while (pNode != null && pNode.val == pHead.val) {                pNode = pNode.next;            }            return deleteDuplication(pNode);         } else {             //反之，保留当前结点，并从下一个结点开始递归            pHead.next = deleteDuplication(pHead.next);             return pHead;        }    }}

Q：输入一个链表，输出该链表中倒数第k个结点。

• 技术点：链表
• 思路：用p1、p2指向链表头部，先让p1走(k-1)步到达第k个节点，此时p1和p2相隔k个节点；而后p1、p2同时往后移动，当p1到达链尾时，p2所在位置正是倒数第k个节点
• 参考代码：

//节点类ListNode同上public class Solution {    public ListNode FindKthToTail(ListNode head,int k) {        if(head==null||k<=0){            return null;        }        ListNode p1=head;        ListNode p2=head;               //p1先到达第k个节点处        for(int i=1;i<k;i++){            if(p1.next!=null){                p1=p1.next;            }else{                return null;            }        }        //p1走到链尾时p2正为倒数第k个节点        while(p1.next!=null){            p1=p1.next;            p2=p2.next;        }        return last;    }}

Q：输入两个单调递增的链表，输出两个链表合成后的链表，并保证满足单调不减规则。

• 技术点：链表
• 思路：每次都取俩链表中最靠前的俩元素中的更小元素到重组链表中，被取走元素的旧链表后移一个元素继续进行“车轮战”；注意假如只剩一条未结束链表要记得一律插入到重组链表的最后
• 参考代码：

//方法1:非递归public class Solution {    public ListNode Merge(ListNode list1,ListNode list2) {        //新建一个头节点，用来存合并的链表        ListNode head=new ListNode(-1);        head.next=null;        ListNode root=head;        while(list1!=null&&list2!=null){            if(list1.val<list2.val){                head.next=list1;                head=list1;                list1=list1.next;            }else{                head.next=list2;                head=list2;                list2=list2.next;            }        }        //把未结束的链表连接到合并后的链表尾部        if(list1!=null){            head.next=list1;        }        if(list2!=null){            head.next=list2;        }        return root.next;     }}//方法2:递归public class Solution {    public ListNode Merge(ListNode list1,ListNode list2) {       if(list1 == null){           return list2;       }       if(list2 == null){           return list1;       }       if(list1.val <= list2.val){           list1.next = Merge(list1.next, list2);           return list1;       }else{           list2.next = Merge(list1, list2.next);           return list2;       }           }}

Q：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。假设输入数组{2,3,4,2,6,2,5,1}及滑动窗口大小3，那么一共存在6个滑动窗口： {[2,3,4],2,6,2,5,1}、 {2,[3,4,2],6,2,5,1}、 {2,3,[4,2,6],2,5,1}、 {2,3,4,[2,6,2],5,1}、 {2,3,4,2,[6,2,5],1}、 {2,3,4,2,6,[2,5,1]}，且他们的最大值分别为{4,4,6,6,6,5}。

• 技术点：栈和队列
• 思路：用一个双端队列（头尾都可push和pop）保存下标值，且队头保存当前窗口最大值的下标。遍历数组，先从队头开始把不存在当前窗口的都移除队列；而后从队尾开始把比当前元素小的都移除队列；最后把当前元素的下标值插入到队列中。时间复杂度O(n)。
• 参考代码：

public class Solution {    public ArrayList<Integer> maxInWindows(int [] num, int size)    {        ArrayList<Integer> res = new ArrayList<>();        if(size == 0){            return res;        }        int begin;         ArrayDeque<Integer> q = new ArrayDeque<>();//双端队列        for(int i = 0; i < num.length; i++){            begin = i - size + 1;//表示当前窗口最左元素在原始数组中的下标            if(q.isEmpty()){                q.add(i);            }            //从队头开始把不存在当前窗口的都移除队列            while((!q.isEmpty()) &&begin > q.peekFirst()){                q.pollFirst();            }            //从队尾开始把比当前元素小的都移除队列            while((!q.isEmpty()) && num[q.peekLast()] <= num[i]){                q.pollLast();            }            q.add(i);              //窗口有效时插入最大值            if(begin >= 0){                res.add(num[q.peekFirst()]);            }        }        return res;    }}

Q：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度为O（1））。

• 技术点：栈
• 思路：自己设置一个最小元素栈，进行push操作时, 假如压入的元素小于等于栈顶元素, 则压入最小元素栈；进行pop操作时, 假如弹出的元素和栈顶元素相等, 就把最小元素栈顶也弹出。
• 参考代码：

public class Solution {     Stack<Integer> dataStack = new Stack<Integer>();    Stack<Integer> minStack = new Stack<Integer>();        public void push(int node) {        dataStack.push(node);        if(minStack.isEmpty() || node <= minStack.peek()){            minStack.push(node);        }    }     public void pop() {        if(dataStack.peek()==minStack.peek()){            minStack.pop();        }        dataStack.pop();    }    public int top() {        return dataStack.peek();    }    public int min() {        return minStack.peek();    }}

Q：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列能否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1、2、3、4、5是某栈的压入顺序，序列4、5、3、2、1是该压栈序列对应的一个弹出序列，而4、3、5、1、2不可能是该压栈序列的弹出序列。

• 技术点：栈
• 思路：借用一个辅助栈。遍历压栈顺序，将元素放入辅助栈，而后判断栈顶元素与弹出顺序第一个元素相等，若相等则出栈并将弹出顺序向后移动一位，直到不相等；最后若辅助栈不为空，说明弹出序列不是该栈的弹出顺序
• 参考代码：

public class Solution {    public boolean IsPopOrder(int [] pushA,int [] popA) {        if(pushA.length == 0 || popA.length == 0)            return false;        Stack<Integer> s = new Stack<Integer>();//辅助栈        int popIndex = 0;//用于标识弹出序列的位置        for(int i = 0; i< pushA.length;i++){            s.push(pushA[i]);            //假如栈不为空且栈顶元素等于弹出序列，则出栈并将弹出序列向后移动一位            while(!s.empty() &&s.peek() == popA[popIndex]){                s.pop();                popIndex++;            }        }        return s.empty();    }}

Q：翻转单词顺序列，如输入“student. a am I”，输出“I am a student.”

• 技术点：字符串
• 思路：先翻转整个句子，再依次翻转每个单词，根据空格来确定单词的起始和终止位置
• 参考代码：

//方法1public class Solution {    public String ReverseSentence(String str) {        char[] chars = str.toCharArray();        reverse(chars,0,chars.length - 1);//整体翻转        int blank = -1;        for(int i = 0;i < chars.length;i++){            if(chars[i] == ' '){                 int nextBlank = i;                reverse(chars,blank + 1,nextBlank - 1);//各个单词翻转                blank = nextBlank;            }        }        reverse(chars,blank + 1,chars.length - 1);//最后一个单词单独进行反转        return new String(chars);             }    public void reverse(char[] chars,int low,int high){        while(low < high){            char temp = chars[low];            chars[low] = chars[high];            chars[high] = temp;            low++;            high--;        }    }}//方法2:使用java提供的字符串方法splitpublic class Solution {    public String ReverseSentence(String str) {        if(str==null||str.trim().equals("")){            return str;        }        //将字符串按照空格分割成字符串数组        String[] a = str.split(" ");        StringBuffer o = new StringBuffer();        int i;        //倒序输出字符串数组        for (i = a.length; i >0;i--){            o.append(a[i-1]);            if(i > 1){                o.append(" ");            }        }        return o.toString();    }}

Q：请实现一个函数用来找出字符流中第一个只出现一次的字符，若没有返回#。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"；当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

• 技术点：字符串
• 思路：相似哈希表，key-value对英于出现字符-出现次数
• 参考代码：

public class Solution {        int[] hashtable=new int[256];    StringBuffer s=new StringBuffer();    public void Insert(char ch)    {        s.append(ch);        hashtable[ch]++;    }    public char FirstAppearingOnce()    {        char[] str=s.toString().toCharArray();        for(char c:str){          if(hashtable[c]==1)              return c;        }        return '#';    }}

Q：在一个字符串（一律由字母组成）中找到第一个只出现一次的字符，并返回它的位置，假如没有则返回 -1（需要区分大小写）。

• 技术点： 字符串
• 思路：
• 参考代码：

public class Solution {    public int FirstNotRepeatingChar(String str) {        HashMap <Character, Integer> map = new HashMap<Character, Integer>();        for(int i=0;i<str.length();i++){            if(map.containsKey(str.charAt(i))){                int time = map.get(str.charAt(i));                map.put(str.charAt(i), ++time);            }            else {                map.put(str.charAt(i), 1);            }        }        int pos = -1;          int i=0;        for(;i<str.length();i++){            char c = str.charAt(i);            if (map.get(c) == 1) {                return i;            }        }        return pos;    }}

Q：输入一个字符串，按字典序打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符abc所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

• 技术点：字符串

• 思路：基于回溯法思想

  
  
• 参考代码：

public class Solution {    public ArrayList<String> Permutation(String str) {        List<String> resultList = new ArrayList<>();        if(str.length() == 0){            return (ArrayList)resultList;        }        fun(str.toCharArray(),resultList,0);//递归的初始值为（str数组，空的list，初始下标0）        Collections.sort(resultList);        return (ArrayList)resultList;    }         private void fun(char[] ch,List<String> list,int i){        if(i == ch.length-1){            if(!list.contains(new String(ch))){                list.add(new String(ch));                return;            }        }else{            //回溯法             for(int j=i;j<ch.length;j++){                swap(ch,i,j);                fun(ch,list,i+1);                swap(ch,i,j);            }        }    }     private void swap(char[] str, int i, int j) {            if (i != j) {                char t = str[i];                str[i] = str[j];                str[j] = t;            }        }    }

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

• 技术点： 数组
• 思路：从左下角开始查找，当比关键字小时右移，反之上移
• 参考代码：

public class Solution {    public boolean Find(int target, int [][] array) {        int rowCount = array.length;        int colCount = array[0].length;        int i,j;        for(i=rowCount-1,j=0;i>=0&&j<colCount;){            if(target == array[i][j]){                return true;            }else if(target < array[i][j]){                i--;                continue;            }else if(target > array[i][j]){                j++;                continue;            }        }        return false;    }}

Q：找出数组中有出现的次数超过数组长度的一半的数字，假如不存在则输出0。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}，因为数字2在数组中出现了5次，超过数组长度的一半，因而输出2。

• 技术点： 数组
• 思路：在遍历数组时保存两个值，一是数组中一个数字，一是次数；遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则减1；若次数为0，则保存下一个数字，并将次数置为1；遍历结束后，所保存的数字即为所求；而后再判断它能否符合条件就可。
• 参考代码：

public class Solution {    public int MoreThanHalfNum_Solution(int [] array) {        int length=array.length;        if(array==null||length<=0){            return 0;        }        //找到最后还留住的元素，可能是目标对象        int result=array[0];        int times=1;        for(int i=1;i<length;i++){            if(times==0){                result=array[i];                times=1;            }else{                if(array[i]==result){                    times++;                }else{                    times--;                }            }        }        //对可能的目标对象进行验证        times=0;        for(int i=0;i<length;i++){            if(result==array[i]){                times++;            }       }       if(times*2<=length){           result=0;       }       return result;    }}

Q：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

• 技术点： 数组
• 思路：通过一个比较器对数据进行两两比较，规则为若a＋b<b+a，则a排在前
• 参考代码：

public class Solution {    public String PrintMinNumber(int [] numbers) {        String s="";        ArrayList<Integer> list= new ArrayList<Integer>();        for(int i=0;i<numbers.length;i++){            list.add(numbers[i]);        }        Collections.sort(list, new Comparator<Integer>(){            public int compare(Integer str1,Integer str2){                String s1=str1+""+str2;                String s2=str2+""+str1;                return s1.compareTo(s2);//假如s1>s2，则str1和str2交换，反之不变            }        });        for(int j:list){            s+=j;        }        return s;    }}

Q：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，假如有多对数字的和等于S，输出两个数的乘积最小的。

• 技术点：数组
• 思路：用两个指针一头一尾；若加和比S大，则尾指针下移一个，若比S小，则头指针上移一个；最先找到的两个数，差最大乘积最小
• 参考代码：

public class Solution {    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {        ArrayList<Integer> list = new ArrayList<Integer>();        if (array == null || array.length < 2) {            return list;        }        int i=0,j=array.length-1;        while(i<j){            if(array[i]+array[j]==sum){                list.add(array[i]);                list.add(array[j]);                return list;            }else if(array[i]+array[j]>sum){                j--;            }else{                i++;            }           }        return list;    }}

Q：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分、所有的偶数位于数组的后半部分，并保证奇数和奇数、偶数和偶数之间的相对位置不变。

• 技术点：代码的完整性
• 思路：
  • 用排列：插排思想，假如当前数是奇数，就一直往前找，遇到偶数就往它前面插
  • 空间换时间：先统计奇数的个数；再新建一个等长数组，设置两个指针，奇数指针从0开始，偶数指针从奇数个数的末尾开始
• 参考代码：

//方法1:时间复杂度O(n2)、空间复杂度O(1)public class Solution {    public void reOrderArray(int [] array) {        if(array.length==0||array.length==1) return;        for(int i=1;i<array.length;i++){            int temp = array[i];            if(array[i] % 2 == 1){                int j = i;                while(j >= 1 && array[j-1] % 2 == 0){                    array[j] = array[j-1];                    j--;                }                array[j] = temp;            }        }    }}//方法2:时间复杂度O(n)、空间复杂度O(n)public class Solution {    public void reOrderArray(int [] array) {        if(array.length==0||array.length==1) return;        int oddCount=0,oddBegin=0;        int[] newArray=new int[array.length];        for(int i=0;i<array.length;i++){            if((array[i]&1)==1) oddCount++;//统计奇数个数        }        for(int i=0;i<array.length;i++){            if(array[i]%2==1){                newArray[oddBegin++]=array[i];//奇数项从0开始            }else{                newArray[oddCount++]=array[i];//偶数项从奇数个数的末尾开始             }        }        for(int i=0;i<array.length;i++){            array[i]=newArray[i];        }    }}

Q：实现从上到下按层打印二叉树，同一层结点从左至右输出，每一层输出一行。

• 技术点： 树
• 思路：BFS
• 参考代码：

//节点类TreeNodepublic class TreeNode {    int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {        this.val = val;    }public class Solution {    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {        ArrayList<ArrayList<Integer>> alist = new ArrayList<ArrayList<Integer>>();// 结果集        if (pRoot == null) return alist;        Queue<TreeNode> queue = new LinkedList<TreeNode>();// 队列        queue.add(pRoot);        while (!queue.isEmpty()) {            ArrayList<Integer> list = new ArrayList<Integer>();// 每层结果            int count=queue.size();//每层节点个数            for (int i = 0; i < count; i++) {                TreeNode node = queue.peek();                list.add(node.val);                if (node.left != null)  queue.add(node.left);                if (node.right != null)  queue.add(node.right);                queue.poll();            }            alist.add(list);        }        return alist;    }}

Q：给定一棵二叉搜索树，请找出其中的第k小的结点。例如（5，3，7，2，4，6，8）中第三小结点的值为4。

• 技术点： 树
• 思路：二叉搜索树的中序遍历结果正好是从小到大排序好的，按照中序遍历顺序找第k个节点
• 参考代码：

//节点类TreeNode同上public class Solution {    int index = 0; //计数器    TreeNode KthNode(TreeNode root, int k){        if(root != null){            TreeNode node = KthNode(root.left,k);            if(node != null) return node;//注意需要判断能否为空，否则假如找到符合要求的节点只能返回到上一层，而不能返回到顶层，使得输出结果为null            index ++;            if(index == k) return root;            node = KthNode(root.right,k);            if(node != null) return node;//理由同上        }        return null;    }}

Q：输入一棵二叉树，判断该二叉树能否是平衡二叉树。

• 技术点：树
• 思路：从下往上遍历，假如子树是平衡二叉树，则返回子树的高度，反之直接中止遍历，这样至多只对每个结点访问一次
• 参考代码：

//节点类TreeNode同上public class Solution {    public boolean IsBalanced_Solution(TreeNode root) {        return getDepth(root) != -1;    }    private int getDepth(TreeNode root) {        if (root == null) return 0;        int left = getDepth(root.left);        if (left == -1) return -1;        int right = getDepth(root.right);        if (right == -1) return -1;        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);    }}

Q：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

• 技术点： 递归和循环
• 思路：对于第n个台阶来说，只能从n-1或者n-2的台阶跳上来，因而跳到n阶的跳法=跳到n-1阶的方案+跳到n-2阶的方案，即F(n) = F(n-1) + F(n-2)，是个斐波拉契数序列
• 参考代码：

//递归法public class Solution {    public int JumpFloor(int target) {        if (target <= 2) {            return target;        } else {            return  JumpFloor(target-1)+JumpFloor(target-2);        }    }}//迭代法public class Solution {    public int JumpFloor(int target) {        if (target <= 2) {            return target;        }         int f1=1;        int f2=2;        int f=0;        for(int i=3;i<=target;i++){            f=f1+f2;            f1=f2;            f2=f;        }        return f;    }}

Q：我们可以用2*1的小矩形横着或者者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

• 技术点： 递归和循环

• 思路：2*n的覆盖方案=2*(n-1)的覆盖方案+2*(n-2)的覆盖方案，即F(n) = F(n-1) + F(n-2)，是个斐波拉契数序列

  
  
• 参考代码：代码同上

Q：地上有一个m行和n列的方格，一个机器人从坐标（0,0）的格子开始移动，每一次只能向左、右、上、下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如当k为18时，机器人能够进入方格（35,37），由于3+5+3+7 = 18；但是不能进入方格（35,38），由于3+5+3+8 = 19。请问该机器人能够达到多少个格子？

• 技术点： 知识迁移能力
• 思路：DFS
• 参考代码：

public class Solution {    public int movingCount(int threshold, int rows, int cols){        if(rows <= 0 || cols <= 0 || threshold < 0) return 0;        boolean[] visited = new boolean[rows * cols];        return dfs(threshold,rows,cols,visited,0,0);    }    private  int dfs(int threshold, int rows, int cols, boolean[] visited, int x, int y) {        //满足终止条件的格子：不属于方格、已经标记过、位数和大于阈值        if(x < 0 || x >= cols || y < 0 || y >= rows || getDigitSum(x) + getDigitSum(y) > threshold || visited[x + y * cols]) return 0;        visited[x + y * cols] = true;        return 1 + dfs(threshold, rows, cols, visited, x, y - 1)                 + dfs(threshold, rows, cols, visited, x + 1, y)                 + dfs(threshold, rows, cols, visited, x, y + 1)                 + dfs(threshold, rows, cols, visited, x - 1, y);    }    //位数和    private int getDigitSum(int i) {        int sum = 0;        while(i > 0) {            sum += i % 10;            i /= 10;        }        return sum;    }}

Q：求出从1 到 n 中1出现的次数。

• 技术点： 时间效率
• 思路：从1到n整数中1出现的次数：O(logn)算法

Q：把只包含质因子2、3和5的数称作丑数。例如6、8都是丑数，而14不是，由于它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

• 技术点： 时间空间效率的平衡
• 思路：对于第i个数，它肯定是之前已存在数的2倍、3倍或者5倍
• 参考代码：

public class Solution {    public int GetUglyNumber_Solution(int index) {        if (index < 7) return index;        int[] res=new int[index];        res[0] = 1;        int t2 = 0, t3 = 0, t5 = 0;        for (int i = 1; i < index; ++i){            res[i] = Math.min(res[t2] * 2, Math.min(res[t3] * 3, res[t5] * 5));            if (res[i] == res[t2] * 2) t2++;            if (res[i] == res[t3] * 3) t3++;            if (res[i] == res[t5] * 5) t5++;        }        return res[index - 1];    }}

Q：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。例如假如输入如下4 X 4矩阵， 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

• 技术点： 画图让笼统形象化
• 思路：用左上和右下的坐标定位出一次要旋转打印的数据，一次旋转打印结束后，往对角分别前进和后退一个单位。注意单行或者者单列的情况。
• 参考代码：

public class Solution {    public ArrayList<Integer> printMatrix(int [][] matrix) {        int row = matrix.length;        int col = matrix[0].length;        ArrayList<Integer> res = new ArrayList<>();        if (row == 0 || col == 0){            return res;        }        int left = 0, top = 0, right = col - 1, bottom = row - 1; // 定义四个关键变量，表示左上和右下的打印范围        while (left <= right && top <= bottom) {            for (int i = left; i <= right; ++i){                res.add(matrix[top][i]);//从左到右            }            for (int i = top + 1; i <= bottom; ++i){                res.add(matrix[i][right]);//从上到下            }            if (top != bottom)                for (int i = right - 1; i >= left; --i){                    res.add(matrix[bottom][i]);//从右到左                }            if (left != right)                for (int i = bottom - 1; i > top; --i){                    res.add(matrix[i][left]);//从下到上                }            left++;top++;right--;bottom--;//缩小一圈，重新定位打印范围        }        return res;    }}

（持续升级...）