面试算法：

第一题：
一个机器人在m×n大小的地图的左上角（起点）。
机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？

示例：

输入：（2,1）
返回：1
输入：（2，2）
返回：2

    public int uniquePaths (int m, int n) {
// 动态规划，三行代码。
// 建立坐标系为起点(1, 1)，终点(m, n)。
// 到达m，n的路径是到达(m-1, n)的路径之和加上到达(m, n-1)的路径之和，当m或n为1时，
// 说明到达了边界，只有一条路径。
        if(m == 1 || n == 1)
            return 1;
        return uniquePaths(m-1, n) + uniquePaths(m, n-1);
    }

第二题：进制转化

• 给定一个十进制数M，以及需要转换的进制数N。将十进制数M转化为N进制数：
• 知识点：

1、栈：Stack<Integer> s = new Stack();
push、pop、peek
2、StringBuilder ：StringBuilder str = new StringBuilder();
str.append(字符串）；
3、数据转化为字符串：String.valueOf(数据)；

    public String solve (int M, int N) {
        // write code here
        Stack<Integer> s = new Stack();
        if(M == 0 || N == 10){
            return String.valueOf(M);
        }
        StringBuilder str = new StringBuilder();
        if(M < 0){
            str.append("-");
            M = Math.abs(M);
        }
        while(M != 0){
            s.push(M % N);
            M = M / N;
        }
        int n = s.size();
        for(int i = 0; i < n; i++){
            if(s.peek() > 9){
                str.append((char)(s.pop()-10+'A'));
            }else{
                str.append(s.pop());
            }
        }
        return String.valueOf(str);
    }

第三题：青蛙跳台阶

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

    public int JumpFloor(int target) {
        int a = 1;
        int b = 1;
        for(int i = 1; i < target; i++){
            a = a + b;
            b = a - b;
        }
        return a;
    }

第四题：判断链表是否是回文结构

• 给定一个链表，请判断该链表是否为回文结构
• 知识点：

ArrayList:
ArrayList<Integer> list = new ArrayList();
list.add(数据);
list.get(数组的下标)
比较链表的两个节点是否相等：node1.equals(node2)

    public boolean isPail2 (ListNode head) {
        // write code here
        ArrayList<Integer> list = new ArrayList();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        
        int l = 0;
        int h = list.size() -1;
        while(l < h){
            if(! list.get(l++).equals(list.get(h--))){
                return false;
            }
        }
        return true;
    }

//  仅供参考，不能通过全部用例（创建一个反转链表，将其与原数组进行比较）
    public boolean isPail (ListNode head){
        ListNode yk = resover(head);
        while(head != null){
            if(!yk.equals(head)){
                return false;
            }
            yk = yk.next;
            head = head.next;
        }
        return true;
    }
    
    public ListNode resover(ListNode head){
        if(head == null){
            return head;
        }
        ListNode current = head;
        ListNode previous = null;
        while(current != null){
            ListNode temp = current.next;
            current.next = previous;
            previous = current;
            current = temp;
        }
        return previous;
    }

第五题：判断链表是否有环

• 知识点：判断两个节点是否相同： head == head.next;

    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }

第六题：树节点的和

• 根节点到叶子节点的所有路径表示的数字之和，例如下图，求得结果25（12 + 13 = 25）：

  
  

    public int sumNumbers(TreeNode root) {
      if(root == null){
          return 0;
      }
      return sumOfTree(root,root.val);
    }
    public int sumOfTree(TreeNode root,int sum){
        if(root.left == null && root.right == null){
            return sum;
        }
        int yk = 0;
        if(root.left != null){
            yk += sumOfTree(root.left,sum * 10 + root.left.val);
        }
        if(root.right != null){
            yk += sumOfTree(root.right,sum * 10 + root.right.val);
        }
        return yk;
    }

第七题：树路径的最大值

• 一棵树，每个节点都有不同的赋值，计算各叶子节点到根节点的数值相加的最大值。
• 思路：递归算法在栈中的实现是倒过来的，最开始的递归调用被压到栈底，而越晚调用的方法越靠近栈顶，越先被调用。所以树在递归方法中总是叶子节点对应的递归方法被先执行。
• 递归：判断当前节点是否有左右孩子，如果有，则将左右孩子的值与当前节点的值分别相加，然后取大的一直最为返回值。

    public int sumNumbers (TreeNode root) {
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return root.val;
        }
        return Math.max(sumNumbers(root.right),sumNumbers(root.left)) + root.val;
    }

第八题:树路径的和

• 给定一个二叉树和一个值sum，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径

    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root==null){
            return false;
        }
        //处理叶子节点
        if(root.left==null && root.right==null){
            if(root.val==sum){
                return true;
            }else{
                return false;
            }
        }
        boolean leftHas=hasPathSum(root.left,sum-root.val);
        boolean rightHas=hasPathSum(root.right,sum-root.val);
        boolean cur=leftHas||rightHas;
        return cur;
    }

• 给定一个二叉树和一个值 sum，请找出所有的根节点到叶子节点的节点值之和等于sum 的路径：

    ArrayList<ArrayList<Integer>>  AllList = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        // 树空
        if(root==null){
            return AllList;
        }
        //1.初始当前的列表
        ArrayList<Integer> path = new ArrayList<>();
        //2.深度优先遍历
       dfs(AllList,path,root,sum); 
        //3.返回路径集合
        return AllList;
    }
    //一、对root进行深度优先遍历
    //result:所有路径和为sum的结果集  list：当前路径结点集  root：当前根节点  sum：当前所需的路径和
    public void dfs(ArrayList<ArrayList<Integer>> result,ArrayList<Integer> list,TreeNode root,int sum){
        if(root==null){
            return;
        }
        if(root.left==null && root.right==null){//为叶子节点
            if(sum-root.val==0){//加上该结点后，满足路径和sum
                list.add(root.val);//将当前结点加入list
                result.add(new ArrayList<>(list));//将当前路径 加入 结果集
                list.remove(list.size()-1); //去掉当前结点，继续下面的遍历
            }
            return;
        }
        list.add(root.val);
        dfs(result,list,root.left,sum-root.val);
        dfs(result,list,root.right,sum-root.val);
        list.remove(list.size()-1); 
    }

第八题：合并二叉树

• 已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替：

    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        if(t1 == null){
            return t2;
        }
        if(t2 == null){
            return t1;
        }
        t1.val = t1.val + t2.val;
        t1.left = mergeTrees(t1.left,t2.left);
        t1.right = mergeTrees(t1.right,t2.right);
        return t1;
    }

第九题:两个线程交替执行

• 两个线程交替打印0到100的奇偶数：

    public static void main(String[] args) {
        new Thread(new Runnable() {
            @Override
            public void run() {
                while (count < 100) {
                    synchronized (lock) {
                        if ((count & 1) == 0) {
                            System.out.println(Thread.currentThread().getName() + ":" + count++);
                        }
                    }
                }
            }
        }, "偶数线程").start();

        new Thread(new Runnable() {
            @Override
            public void run() {
                while (count < 100){
                    synchronized (lock){
                        if ((count & 1) == 1){
                            System.out.println(Thread.currentThread().getName() + ":" + count++);
                        }
                    }
                }
            }
        },"奇数线程").start();
    }

• 方法二：

    private static class ThreadTest implements Runnable{
        @Override
        public void run() {
            while (count < 100){
                synchronized (lock){
                    System.out.println(Thread.currentThread().getName() + ":" + count++);
                    lock.notify();
                    if (count < 100){
                        try {
                            lock.wait();
                        }catch ( InterruptedException e){
                            e.printStackTrace();
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        new Thread(new ThreadTest(),"偶数线程").start();
        new Thread(new ThreadTest(),"奇数线程").start();
    }

第十题：

• 将string转化为charArray： string.toCharArray()
• 将其他类型的数据转为字符串：String.valueOf(数据)

第十一题：逆波兰表达式求值

在反向波兰表示法中计算算术表达式的值,遇到操作符就计算前两个数值，例 ["2", "1", "+", "3", "*"] -> (2 + 1) * 3 -> 9

public int evalRPN(String[] tokens) {
    Stack<Integer> s = new Stack<Integer>();
    String operators = "+-*/";
    for (String token : tokens) {
        if (!operators.contains(token)) {
            s.push(Integer.valueOf(token));
            continue;
        }

        int a = s.pop();
        int b = s.pop();
        if (token.equals("+")) {
            s.push(b + a);
        } else if(token.equals("-")) {
            s.push(b - a);
        } else if(token.equals("*")) {
            s.push(b * a);
        } else {
            s.push(b / a);
        }
    }
    return s.pop();
}

第十二题：返回一个数组的前X个大的数

• 知识点:

PriorityQueue默认是一个小顶堆，然而可以通过传入自定义的Comparator函数来实现大顶堆。

public int[] topk(int[] nums, int k) {
    int[] result = new int[k];
    if (nums == null || nums.length < k) {
        return result;
    }
    Queue<Integer> pq = new PriorityQueue<>();
    for (int num : nums) {
        pq.add(num);
        if (pq.size() > k) {
            pq.poll();
        }
    }
    for (int i = k - 1; i >= 0; i--) {
        result[i] = pq.poll(); 
    }
    return result;
}

十三题：判断一棵树是否是二叉搜索树：

public boolean isValidBST(TreeNode root) {
    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValidBST(TreeNode root, long min, long max){
    if (root == null) {
        return true;
    }
    if (root.val <= min || root.val >= max){
        return false;
    }
    return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}

十四题：寻找二叉树第K小的值：

• 前提：树是二叉树

public int kthSmallest(TreeNode root, int k) {
    if (root == null) {
        return 0;
    }
//  获取左边节点的个数
    int leftCount = getCount(root.left);
//   进入左循环
    if (leftCount >= k) {
        return kthSmallest(root.left, k);
    } else if (leftCount + 1 == k) {
//   就是当前节点
        return root.val;
    } else {
//    进入右循环
        return kthSmallest(root.right, k - leftCount - 1);
    }
}
private int getCount(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return getCount(root.left) + getCount(root.right) + 1;
}

十五题：数组加一

• 给定一个非负数，表示一个数字数组，在该数的基础上+1，返回一个新的数组。该数字按照数位高低进行排列，最高位的数在列表的最前面。

  
  

public int[] plusOne(int[] digits) {
    int carries = 1;
    for(int i = digits.length - 1; i >= 0 && carries > 0; i--){  
        int sum = digits[i] + carries;
        digits[i] = sum % 10;
        carries = sum / 10;
    }
    if(carries == 0) {
        return digits;
    }
        
    int[] rst = new int[digits.length + 1];
    rst[0] = 1;
    for(int i = 1; i < rst.length; i++){
        rst[i] = digits[i - 1];
    }
    return rst;
}

十六题：数组删重复值

• 给定一个数组和一个值，在原地删除与值相同的数字，返回新数组的长度。

public int removeElement(int[] A, int elem) {
    if (A == null || A.length == 0) {
        return 0;
    }
    int index = 0;
    for (int i = 0; i < A.length; i++) {
        if (A[i] != elem) {
            A[index++] = A[i];
        } 
    }
    return index;
}

十七题：数组删值

• 在原数组中“删除”重复出现的数字，使得每个元素只出现一次，并且返回“新”数组的长度。

public int removeDuplicates(int[] A) {
    if (A == null || A.length == 0) {
        return 0;
    }
    int size = 0;
    for (int i = 0; i < A.length; i++) {
        if (A[i] != A[size]) {
            A[++size] = A[i];
        }
    }
    return size + 1;
}

十九题：给一个无序链表排序：

 public ListNode sortInList (ListNode head) {
     // write code here
     if(head == null || head.next == null)
         return head;
     
     ArrayList<Integer> list = new ArrayList<>();
     ListNode tmp = head;
     while(tmp != null){
         list.add(tmp.val);
         tmp = tmp.next;
     }
//   将list升序排序
     list.sort(Comparator.naturalOrder());
     
     ListNode temp = head;
     int i = 0;
     while(temp != null){
         temp.val = list.get(i++);
         temp = temp.next;
     }
     return head;
 }

二十题：数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

    public int FindGreatestSumOfSubArray(int[] array) {
        int max = array[0];
        for(int i = 1; i < array.length; i++){
            max = Math.max(arr[i] + max, 0);
        }
        return max;
    }

二十一题：判断一个数字是否是回文结构：

    public boolean isPalindrome (int x) {
        if(x < 0){
            return false;
        }
        int temp = 0;
        int y = x;
        while(y != 0){
            temp = temp * 10 + y % 10;
            y = y / 10;
        }
        return temp == x;
    }

二十二题：

• 取出字符串指定位置的字符：char a = str.charAt(i)；
• 在数值上，小写字母比大写字母打32；所以小写字母转大写字母：'A' = (char) ('a' - 32);
• 将字符串按照指定格式划分为数组，例：String[] a = str.split(" ");

二十三题：用一个升序数组创建平衡二叉树：

public TreeNode sortedArrayToBST (int[] num) {
        if(num == null){
            return null;
        }
        return createTree(num, 0, num.length - 1);
    }
    private TreeNode createTree(int[] num, int left, int right){
        if(left > right){
            return null;
        }
        int mid = left + (right - left + 1) / 2;
        TreeNode lNode = createTree(num, left, mid - 1);
        TreeNode rNode = createTree(num, mid + 1, right);
        TreeNode node = new TreeNode(num[mid]);
        if(lNode != null) node.left  = lNode;
        if(rNode != null) node.right = rNode;
        return node;
    }

二十四题：根据一颗二叉树的前序和中序遍历，创建二叉树：

• 知识点：Arrays.copyOfRange方法，在使用前必须导入 import java.util.Arrays; 使用方法：参数一输入原数组，参数二开始复制的下标，参数三结束复制的下标

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        // 在中序中找到前序的根
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                // 左子树，注意 copyOfRange 函数，左闭右开
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1),
                                                  Arrays.copyOfRange(in, 0, i));
                // 右子树，注意 copyOfRange 函数，左闭右开
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length),
                                                   Arrays.copyOfRange(in, i + 1, in.length));
                break;
            }
        }
        return root;
    }

最长回文子串：

//    字符串的最长回文子串
    public static int maxHuiwen(String str){
        int maxLength = 0;
        for (int i = 0; i < str.length() - 1; i ++){
            int len1 = huiWenLength(str,i, i);
            int len2 = huiWenLength(str,i, i + 1);
            maxLength = Math.max(maxLength,len1);
            maxLength = Math.max(maxLength,len2);
        }
        return maxLength;
    }
    public static int huiWenLength(String str, int left, int right){ 
        while (left > 0 && right < str.length() - 1){
            if (str.charAt(left) == str.charAt(right)){
                left --;
                right ++;
            }else {
                break;
            }
        }
        return right - left - 2 + 1;
    }