《剑指offer》刷题记录

二维数组的查找

标签：【数组】【查找】

题目描述

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

代码

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array==null || array.length==0){
            return false;
        }
        //二分查找
        for(int i=0;i<array.length;i++){
            int low=0;
            int high=array[i].length-1;
            while(low<=high){
                int mid=(low+high)/2;
                if(array[i][mid]<target){
                    low=mid+1;
                }
                else if(array[i][mid]>target){
                    high=mid-1;
                }
                else{
                    return true;
                }
            }
        }
        return false;
    }
}

替换空格

标签：【字符串】

题目描述

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

代码

public class Solution {
    public String replaceSpace(StringBuffer str) {
        if(str==null)
            return "";
        else
        {
            String result="";
            //注意split方法，传入"\\s"转义字符表示空格，-1为limit表示返回结果长度不做限制，否则不能返             //回分隔符是最后一个字符这种情况下分隔符后的""字符
            String[] res=str.toString().split("\\s",-1);
            for(String s :res)
            {
                result=result+s+"%20";
            }
            //substring方法左闭右开
            return result.substring(0,result.length()-3);
        }
    }
}

从尾到头打印链表

标签：【链表】

题目描述

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

代码

/**
*    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<Integer> res=new ArrayList<>();
        if(listNode==null){
            return res;
        }
        ListNode temp=listNode;
        //由题意，先进后出，即栈，利用ArrayList的add(position,value)方法，每次在0位置插入新值，然后         //从头输出即复合题意了
        while(temp!=null){
            res.add(0,temp.val);
            temp=temp.next;
        }
        return res;
    }
}

重建二叉树

标签：【树】

题目描述

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

代码

/**
 * Definition for binary tree
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */

import java.util.*;

public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        //安全带：递归退出条件
        if (pre == null || in == null || pre.length == 0 || in.length == 0) {
            return null;
        }
        //必要的一些处理
        TreeNode root = new TreeNode(pre[0]);
        int index = 0;
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                index = i;
                break;
            }
        }
        //开始递归
        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, index + 1), Arrays.copyOfRange(in, 0, index));
        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, index + 1, pre.length), Arrays.copyOfRange(in, index + 1, in.length));
        return root;
    }
}

用两个栈实现队列

标签：【队列】【栈】

题目描述

用两个栈来实现一个队列，完成队列的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 (stack2.size() == 0) {
            while (stack1.size() != 0) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

旋转数组的最小数字

标签：【查找】

题目描述

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

代码

import java.util.ArrayList;

public class Solution {
    public int minNumberInRotateArray(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        //二分查找
        int low = 0;
        int high = array.length - 1;
        while (low < high) {
            //非递减的数组提前返回
            if (array[low] < array[high]) {
                return array[low];
            }
            int mid = (low + high) / 2;
            //情况1，arr[mid] > target：4 5 6 1 2 3
			//arr[mid] 为 6， target为右端点 3， arr[mid] > target, 说明[first ... mid] 都是 			  //>= target 的，因为原始数组是非递减，所以可以确定答案为 [mid+1...last]区间,所以 first             //= mid + 1
            if (array[mid] > array[high]) {
                low = mid + 1;
            } 
            //情况2，arr[mid] < target:5 6 1 2 3 4
			//arr[mid] 为 1， target为右端点 4， arr[mid] < target, 说明答案肯定不在					//[mid+1...last]，但是arr[mid] 有可能是答案,所以答案在[first, mid]区间，所以last = 			//mid;
            else if (array[mid] < array[high]) {
                high = mid;
            } 
            //情况3，arr[mid] == target:
            //如果是 1 0 1 1 1， arr[mid] = target = 1, 显然答案在左边
			//如果是 1 1 1 0 1, arr[mid] = target = 1, 显然答案在右边
			//所以这种情况，不能确定答案在左边还是右边，那么就让last = last - 1;慢慢缩少区间，同时也			 //不会错过答案。
            else {
                high--;
            }
        }
        return array[low];
    }
}

斐波那契数列

标签：【递归】【动态规划】

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

n<=39

代码

public class Solution {
    public int Fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            //直接使用递归复杂度超高，采用记表法记录最近两位的值
            int sum = 1;
            int one = 0;
            while (n > 1) {
                sum = sum + one;
                one = sum - one;
                n--;
            }
            return sum;
        }

    }
}

跳台阶

标签：【递归】【动态规划】

题目描述

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

代码

public class Solution {
    public int JumpFloor(int target) {
        if (target == 0 || target == 1) {
            return target;
        }
        //动态规划，优化掉递归栈空间。常规方法是从上往下递归然后再从下往上回溯的，最后回溯的时候来合并子树		  //从而求得答案。那么动态规划不同的是，不用递归的过程，直接从子树求得答案。过程是从下往上。并且对空  		  //间复杂度也做了优化
        int a = 1;
        int b = 1;
        int c = 0;
        for (int i = 2; i <= target; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

变态跳台阶

标签：【动态规划】

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

代码

public class Solution {
    public int JumpFloorII(int target) {
        if (target == 0 || target == 1) {
            return target;
        }
        //可以采用递归，记忆化递归，动态规划，递推。这里采用递推的方式。
        int a = 1;
        int b = 0;
        for (int i = 2; i <= target; i++) {
            b = a << 1;
            a = b;
        }
        return b;
    }
}

矩形覆盖

标签：【递归】

题目描述

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

比如n=3时，2*3的矩形块有3种覆盖方法：

代码

public class Solution {
    public int RectCover(int target) {
        if (target == 0 || target == 1 || target == 2) {
            return target;
        }
        //动态规划
        int a = 1;
        int b = 2;
        int c = 0;
        for (int i = 3; i <= target; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

二进制中1的个数

标签：【数学】

题目描述

输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。

代码

public class Solution {
    public int NumberOf1(int n) {
        if (n == 0) {
            return 0;
        }
        //如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1         //就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影         //响。也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二         //进制有多少个1，就可以进行多少次这样的操作。(很像CSAPP里的各种技巧啊)
        int count = 0;
        while (n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }
}

数值的整数次方

标签：【数学】

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0

代码

public class Solution {
    public double Power(double base, int exponent) {
        if (base == 0.0) {
            return base;
        }
        //不直接用JDK自带的函数了
        double res = 1.0;
        int e = exponent > 0 ? exponent : -exponent;
        for (int i = 0; i < e; i++) {
            res = res * base;
        }
        return exponent > 0 ? res : 1 / res;
    }
}

调整数组顺序使奇数位于偶数前面

标签：【数组】

题目描述

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

代码

import java.util.*;

public class Solution {
    public void reOrderArray(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        //存放奇数的队列
        Queue<Integer> queue1 = new LinkedList<Integer>();
        //存放偶数的队列
        Queue<Integer> queue2 = new LinkedList<Integer>();
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 1) {
                queue1.add(array[i]);
            } else {
                queue2.add(array[i]);
            }
        }
        int j = 0;
        while (queue1.size() != 0) {
            array[j++] = queue1.remove();
        }
        while (queue2.size() != 0) {
            array[j++] = queue2.remove();
        }
    }
}

链表中倒数第k个结点

标签：【链表】

题目描述

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

代码

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/

import java.util.*;

public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k <= 0) {
            return null;
        }
        //常规做法是使用快慢指针，这里用优先级队列来实现复习一下（性能比快慢指针差些）
        Queue<Integer> queue = new PriorityQueue<Integer>(Collections.reverseOrder());
        Map<Integer, ListNode> temp = new HashMap<>();
        int i = 1;
        ListNode curr = head;
        while (curr != null) {
            temp.put(i, curr);
            queue.add(i);
            curr = curr.next;
            i++;
        }
        for (int j = 0; j < k - 1; j++) {
            queue.remove();
        }
        return temp.get(queue.peek());

    }
}

反转链表

标签：【链表】

题目描述

输入一个链表，反转链表后，输出新链表的表头。

代码

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        //3个指针:1）pre指针指向已经反转好的链表的最后一个结点，最开始没有反转，所以指向null; 2）cur           //指针指向待反转链表的第一个结点，最开始第一个结点待反转，所以指向head;3）nex指针指向待反转链表         //的第二个结点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存。然后调整各结         //点的next指向就可以了。
        ListNode pre;
        ListNode cur;
        ListNode next;
        pre = null;
        cur = head;
        next = head;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

合并两个排序的链表

标签：【链表】

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

代码

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {
        //哨兵结点，保证每个结点都有前驱结点
        ListNode head = new ListNode(-1);
        ListNode curr = head;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                curr.next = list1;
                list1 = list1.next;
                curr = curr.next;
            } else {
                curr.next = list2;
                list2 = list2.next;
                curr = curr.next;
            }
        }
        if (list1 == null) {
            curr.next = list2;
        } else if (list2 == null) {
            curr.next = list1;
        }
        return head.next;
    }
}

树的子结构

标签：【二叉树】【树】

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

代码

/**
 * public class TreeNode {
 * int val = 0;
 * TreeNode left = null;
 * TreeNode right = null;
 * public TreeNode(int val) {
 * this.val = val;
 * }
 * }
 */
public class Solution {
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        //两棵树根结点相等则判断是否B是A的子结构
        if (root1.val == root2.val) {
            if (judge(root1, root2)) {
                return true;
            }
        }
        //否则判断B是否是A的左子树的子结构或者右子树的子结构
        return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);

    }

    private boolean judge(TreeNode root1, TreeNode root2) {
        //B树遍历完了，则说明B是A的子结构
        if (root2 == null) {
            return true;
        }
        //B树还没有遍历完，A树就遍历完了，则B树肯定不是A树的子结构
        if (root1 == null) {
            return false;
        }
		//当两树根结点相等时，继续递归判断A的左子树跟B的左子树，A的右子树跟B的右子树是否也满足这种子结构         //关系
        if (root1.val == root2.val) {
            return judge(root1.left, root2.left) && judge(root1.right, root2.right);
        }
        //只要当前树的根结点不相等，就说明在当前跟结点下B不是A的子结构了
        return false;

    }
}

二叉树的镜像

标签：【树】

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

> 输入描述:
> 二叉树的镜像定义：源二叉树 
>     	    8
>     	   /  \
>     	  6   10
>     	 / \  / \
>     	5  7 9 11
>     	镜像二叉树
>     	    8
>     	   /  \
>     	  10   6
>     	 / \  / \
>     	11 9 7  5
>

代码

/**
 * public class TreeNode {
 * int val = 0;
 * TreeNode left = null;
 * TreeNode right = null;
 * <p>
 * public TreeNode(int val) {
 * this.val = val;
 * <p>
 * }
 * <p>
 * }
 */
public class Solution {
    public void Mirror(TreeNode root) {
        if (root == null) {
            return;
        }
        //左右子树依次从上到下调整
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        Mirror(root.left);
        Mirror(root.right);
    }
}

顺时针打印矩阵

标签：【数组】

题目描述

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

代码

import java.util.ArrayList;
/**
*	没啥技巧，考虑周全即可
**/
public class Solution {
    public ArrayList<Integer> printMatrix(int[][] matrix) {
        if (matrix == null) {
            return null;
        }
        int totalrows = matrix.length;
        int totalcols = matrix[0].length;
        int count = 0;
        int startrow = 0;
        int startcol = 0;
        ArrayList<Integer> res = new ArrayList<>();
        while (count < matrix.length * matrix[0].length) {
            count = count + (2 * totalcols + 2 * (totalrows - 2));
            if (totalcols == 1) {
                for (int i = 0; i < totalrows; i++) {
                    res.add(matrix[startrow++][startcol]);
                }
            } else if (totalrows == 1) {
                for (int i = 0; i < totalcols; i++) {
                    res.add(matrix[startrow][startcol++]);
                }
            } else {
                print(matrix, startrow++, startcol++, totalrows, totalcols, res);
            }

            totalrows -= 2;
            totalcols -= 2;
        }
        return res;
    }

    private void print(int[][] matrix, int row, int col, int totalrows, int totalcols, ArrayList<Integer> res) {
        //打印上面的行
        for (int i = 0; i < totalcols; i++) {
            res.add(matrix[row][col++]);
        }
        col--;
        //打印右边的列
        for (int i = 0; i < totalrows - 1; i++) {
            res.add(matrix[++row][col]);
        }
        //打印下面的行
        for (int i = 0; i < totalcols - 1; i++) {
            res.add(matrix[row][--col]);
        }
        //打印左边的列
        for (int i = 0; i < totalrows - 2; i++) {
            res.add(matrix[--row][col]);
        }
    }
}

包含min函数的栈

标签：【栈】

题目描述

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

注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

代码

import java.util.PriorityQueue;
import java.util.Stack;
import java.util.Queue;

public class Solution {
    //PriorityQueue太实用了
    Stack<Integer> stack = new Stack<Integer>();
    Queue<Integer> queue = new PriorityQueue<Integer>();

    public void push(int node) {
        stack.push(node);
        queue.add(node);
    }

    public void pop() {
        stack.pop();
        queue.remove();
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return queue.peek();
    }
}

栈的压入、弹出序列

标签：【栈】

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

代码

import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        if (pushA == null || popA == null || pushA.length != popA.length) {
            return false;
        }
        //辅助栈
        Stack<Integer> stack = new Stack<Integer>();
        int i = 0;
        int j = 0;
        while (j < popA.length) {
            //辅助栈包含要出栈的元素，比较实际出栈元素和期望出栈元素是否一致
            if (stack.contains(popA[j])) {
                if (stack.pop() != popA[j]) {
                    return false;
                }
                j++;
            } 
            //辅助栈不包含则要入栈
            else if (i < pushA.length) {
                stack.push(pushA[i]);
                i++;
            } 
            //所有元素都一如栈，期望元素不在辅助栈中，说明期望的是一个不存在的数，返回false
            else {
                return false;
            }
        }
        return true;
    }
}

从上往下打印二叉树

标签：【队列】【树】

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

代码

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * public class TreeNode {
 * int val = 0;
 * TreeNode left = null;
 * TreeNode right = null;
 * <p>
 * public TreeNode(int val) {
 * this.val = val;
 * <p>
 * }
 * <p>
 * }
 */
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        res.add(root.val);
        //用一个队列保存结点信息
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        print(res, queue);
        return res;
    }

    private void print(ArrayList<Integer> res, LinkedList<TreeNode> queue) {
        while (queue.size() != 0) {
            TreeNode root = queue.remove();
            if (root.left != null) {
                queue.add(root.left);
                res.add(root.left.val);
            }
            if (root.right != null) {
                queue.add(root.right);
                res.add(root.right.val);
            }
        }
    }
}

二叉搜索树的后序遍历序列

标签：【栈】【树】

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

代码

public class Solution {
    public boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        return verify(sequence, 0, sequence.length - 1);

    }

    //一棵 BST ：左孩子 < 根结点 < 右孩子;一棵 BST 的左子树或者右子树都是 BST;左子树区间的所有结点值     //< 根结点值 < 右子树区间所有结点值.
    private boolean verify(int[] sequence, int start, int end) {
        if (start >= end) {
            return true;
        }
        //寻找右子树的开始结点
        int index = start;
        for (int i = index; i < end && sequence[i] < sequence[end]; i++) {
            index++;
        }
        //右子树进行判断 
        for (int i = index; i < end; i++) {
            if (sequence[i] <= sequence[end]) {
                return false;
            }
        }
        //递归
        return verify(sequence, start, index - 1) && verify(sequence, index, end - 1);
    }
}

二叉树中和为某一值的路径

标签：【树】【回溯法】

题目描述

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

代码

import java.util.ArrayList;
import java.util.Stack;

/**
 * public class TreeNode {
 * int val = 0;
 * TreeNode left = null;
 * TreeNode right = null;
 * <p>
 * public TreeNode(int val) {
 * this.val = val;
 * <p>
 * }
 * <p>
 * }
 */
public class Solution {
    Stack<Integer> path = new Stack<Integer>();
    ArrayList<ArrayList<Integer>> paths = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if (root == null) {
            return paths;
        }
        if (root != null && root.val == target) {
            path.push(root.val);
            //注意下ArrayList的这种构造方法
            paths.add(new ArrayList<Integer>(path));
            return paths;
        }
        find(root, target);
        return paths;
    }

    private void find(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        //回溯法
        path.push(root.val);
        //叶子结点
        if (root.val == target && root.left == null && root.right == null) {
            paths.add(new ArrayList<Integer>(path));
            //出栈
            path.pop();
            return;
        }
        find(root.left, target - root.val);
        find(root.right, target - root.val);
        //回溯
        path.pop();
    }
}

复杂链表的复制

标签：【链表】

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

代码

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/

import java.util.HashMap;

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }
        //map保存新老结点之间的映射关系
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode curr = pHead;
        RandomListNode after = pHead;
        while (curr != null) {
            map.put(curr, new RandomListNode(curr.label));
            curr = curr.next;
        }

        while (after.next != null) {
            map.get(after).next = map.get(after.next);
            map.get(after).random = map.get(after.random);
            after = after.next;
        }
        map.get(after).next = null;
        map.get(after).random = null;
        return map.get(pHead);
    }
}

二叉搜索树与双向链表

标签：【链表】【二叉搜索树】

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

代码

/**
 * public class TreeNode {
 * int val = 0;
 * TreeNode left = null;
 * TreeNode right = null;
 * <p>
 * public TreeNode(int val) {
 * this.val = val;
 * <p>
 * }
 * <p>
 * }
 */
public class Solution {
    //前驱结点
    TreeNode pre = null;
    //链表头
    TreeNode firstLeft = null;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return pRootOfTree;
        }
        //中序遍历二叉搜索树即得到一个递增的序列
        Convert(pRootOfTree.left);
        pRootOfTree.left = pre;
        firstLeft = firstLeft == null ? pRootOfTree : firstLeft;
        if (pre != null) {
            pre.right = pRootOfTree;
        }
        pre = pRootOfTree;
        Convert(pRootOfTree.right);
        return firstLeft;
    }
}

字符串的排序

标签：【字符串】【动态规划】【递归】

题目描述

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

输入描述：
1
2
> 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
>

代码

import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeSet;

public class Solution {
    public ArrayList<String> Permutation(String str) {
        if (str == null || str.length() == 0) {
            return new ArrayList<String>();
        }
        //保证字典序且去重
        TreeSet<String> res = new TreeSet<>();
        StringBuffer sb = new StringBuffer();
        back(str, sb, res);
        ArrayList<String> result = new ArrayList<>();
        for (String item : res) {
            result.add(item);
        }
        return result;

    }

    public void back(String str, StringBuffer sb, TreeSet<String> res) {
        if (str.length() == 1) {
            sb.append(str);
            res.add(sb.toString());
            sb.deleteCharAt(sb.length() - 1);
            return;
        }
        for (int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            StringBuffer stringBuffer = new StringBuffer(str);
            //灵活使用StringBuffer的方法
            back(stringBuffer.deleteCharAt(i).toString(), sb, res);
            //回溯
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

数组中出现次数超过一半的数字

标签：【数组】

题目描述

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

代码

public class Solution {
    public int MoreThanHalfNum_Solution(int[] array) {
        //候选法
        int target = 0;
        int count = 0;
        if (array == null || array.length == 0) {
            return target;
        }
        for (int i = 0; i < array.length; i++) {
            //战场无人，我方+1
            if (count == 0) {
                target = array[i];
                count++;
            } else {
                //战场有人且是敌方的人，我方-1
                if (target != array[i]) {
                    count--;
                } else {
                    //战场有人且是我方的人，我方+1
                    count++;
                }
            }
        }
        count = 0;
        //清理战场，确认我方人数超过一半，防止有一个人猫着在最后等两败俱伤才出来
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                count++;
            }
        }
            if (count > array.length / 2) {
                return target;
            } else {
                target = 0;
            }
        return target;
    }

}

最小的K个数

标签：【数组】【高级算法】

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

代码

import java.util.PriorityQueue;
import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (input == null || input.length == 0 || k > input.length) {
            return res;
        }
        //优先级队列的应用，底层默认使用的是小顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
        for (int i = 0; i < input.length; i++) {
            queue.add(input[i]);
        }
        for (int i = 0; i < k; i++) {
            //小顶堆堆顶元素永远是最小的元素
            res.add(queue.remove());
        }
        return res;
    }
}

连续子数组的最大和

标签：【数组】

题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

代码

/**
*   (类似股票买卖问题)
*	对下标为i的元素array[i]，先试探的加上array[i], 如果和为负数，显然，以i结尾的元素对整个结果不作贡	*	献。
*	具体过程：
*	初始化：维护一个变量temp = 0
*	如果temp+array[i] < 0, 说明以i结尾的不作贡献，重新赋值temp = 0
*	否则更新temp = temp + array[i]
*	最后判断temp是否等于0， 如果等于0， 说明数组都是负数，选取一个最大值为答案。
**/
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int temp = 0;
        int res = 0;
        for (int i = 0; i < array.length; i++) {
            if (temp + array[i] < 0) {
                temp = 0;
            } else {
                temp = temp + array[i];
                res = Math.max(res, temp);
            }

        }
        if (temp == 0) {
            int max = array[0];
            for (int i = 0; i < array.length; i++) {
                if (array[i] > max) {
                    max = array[i];
                }
            }
            res = max;
        }
        return res;
    }
}

整数中1出现的次数（从1到n整数中1出现的次数）

标签：【查找】【数学】

题目描述

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

代码

/*
设N = abcde ,其中abcde分别为十进制中各位上的数字。
如果要计算百位上1出现的次数，它要受到3方面的影响：百位上的数字，百位以下（低位）的数字，百位以上（高位）的数字。
① 如果百位上数字为0，百位上可能出现1的次数由更高位决定。比如：12013，则可以知道百位出现1的情况可能是：100~199，1100~1199,2100~2199，，...，11100~11199，一共1200个。可以看出是由更高位数字（12）决定，并且等于更高位数字（12）乘以 当前位数（100）。
② 如果百位上数字为1，百位上可能出现1的次数不仅受更高位影响还受低位影响。比如：12113，则可以知道百位受高位影响出现的情况是：100~199，1100~1199,2100~2199，，....，11100~11199，一共1200个。和上面情况一样，并且等于更高位数字（12）乘以 当前位数（100）。但同时它还受低位影响，百位出现1的情况是：12100~12113,一共114个，等于低位数字（113）+1。
③ 如果百位上数字大于1（2~9），则百位上出现1的情况仅由更高位决定，比如12213，则百位出现1的情况是：100~199,1100~1199，2100~2199，...，11100~11199,12100~12199,一共有1300个，并且等于更高位数字+1（12+1）乘以当前位数（100）。
*/
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        //1的个数
        int count = 0;
        //当前位
        int i = 1;
        int current = 0, after = 0, before = 0;
        while ((n / i) != 0) {
            //当前位数字
            current = (n / i) % 10; 
            //高位数字
            before = n / (i * 10); 
            //低位数字
            after = n - (n / i) * i; 
            //如果为0,出现1的次数由高位决定,等于高位数字 * 当前位数
            if (current == 0){
                count += before * i;
            }
            //如果为1,出现1的次数由高位和低位决定,高位*当前位+低位+1    
            else if (current == 1){
                count += before * i + after + 1;
            }
            //如果大于1,出现1的次数由高位决定,//（高位数字+1）* 当前位数    
            else {
                count += (before + 1) * i;
            }
            //前移一位
            i = i * 10;
        }
        return count;
    }
}

把数组排成最小的数

标签：【数组】

题目描述

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

代码

import java.util.ArrayList;

public class Solution {
    public String PrintMinNumber(int [] numbers) {
    //实现一个类似于冒泡排序的算法，一个贪心的过程,每次找出使高位最小的那个数，比如，3,32组合332比323       //大，所以332口口口口口口也会比323口口口口口口要大，，然后将排完序的数字输出即可。
        if(numbers==null || numbers.length==0){
            return "";
        }
        for(int i=0;i<numbers.length;i++){
            for(int j=i+1;j<numbers.length;j++){
                if(Integer.parseInt(numbers[i]+""+numbers[j])>
                   Integer.parseInt(numbers[j]+""+numbers[i])){
                    int temp=numbers[j];
                    numbers[j]=numbers[i];
                    numbers[i]=temp;
                }
            }
        }
        String res="";
        for(int i=0;i<numbers.length;i++){
            res=res+numbers[i];
        }
        return res;
    }
}

丑数

标签：【穷举】

题目描述

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

代码

//维持三个指针来记录当前乘以2、乘以3、乘以5的最小值，相当于从3个维度来决定数组的下一个数字，落后的指针有
//后发优势即可以乘上数组中在该指针后面位置存在的数字，然后当其被选为新的最小值后，要把相应的指针+1；因为
//这个指针会逐渐遍历整个数组，因此最终数组中的每一个值都会被乘以2、乘以3、乘以5
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index<=0){
            return 0;
        }
        int[] res=new int[index];
        res[0]=1;
        //初始化指针指向最小丑数位置
        int p2=0;
        int p3=0;
        int p5=0;
        for(int i=1;i<index;i++){
            res[i]=Math.min(2*res[p2],Math.min(3*res[p3],5*res[p5]));
            //为了防止重复需要三个if都能够走到
            if(res[i]==2*res[p2]){
                p2++;
            }
            //为了防止重复需要三个if都能够走到
            if(res[i]==3*res[p3]){
                p3++;
            }
            //为了防止重复需要三个if都能够走到
            if(res[i]==5*res[p5]){
                p5++;
            }
        }
        return res[index-1];
    }
}

第一个只出现一次的字符

标签：【字符串】

题目描述

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

代码

import java.util.LinkedHashMap;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if(str==null ||str.length()==0){
            return -1;
        }
        if(str.length()==1){
            return 0;
        }
        //LinkedHashMap维护插入顺序，记录以字符为key的元素出现次数以及位置
        LinkedHashMap<Character,Integer> map=new LinkedHashMap<Character,Integer>();
        for(int i=0;i<str.length();i++){
            if(map.get(str.charAt(i))==null){
                map.put(str.charAt(i),i);
            }
            else{
                map.put(str.charAt(i),-1);
            }
        }
        //遍历key，找到那个第一个只出现一次的字符
        for(Character c:map.keySet()){
            if(map.get(c)!=-1){
                return map.get(c);
            }
        }
        return -1;
    }
}

数组中的逆序对

标签：【数组】

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007

输入描述：
1
2
> 题目保证输入的数组中没有的相同的数字数据范围：	对于%50的数据,size<=10^4	对于%75的数据,size<=10^5	对于%100的数据,size<=2*10^5
>

示例：

输入
1
2
> 1,2,3,4,5,6,7,0
>

输出
1
2
> 7
>

代码

public class Solution {
    int count = 0;

    public int InversePairs(int[] array) {
        if (array == null || array.length == 0) {
            return count;
        }
        patition(array, 0, array.length - 1);
        return count;
    }

    private void patition(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = (start + end) / 2;
        //划分子区间
        patition(array, start, mid);
        patition(array, mid + 1, end);
        merge(array, start, mid, end);
    }

    //归并排序
    private void merge(int[] array, int start, int mid, int end) {
        int i = start;
        int j = mid + 1;
        int t = 0;
        int[] temp = new int[end - start + 1];
        while (i <= mid && j <= end) {
            if (array[i] <= array[j]) {
                temp[t++] = array[i++];
            } else {
                temp[t++] = array[j++];
                //计数，减少计算
                count = count + mid - i + 1;
                count = count % 1000000007;
            }
        }
        while (i <= mid) {
            temp[t++] = array[i++];
        }
        while (j <= end) {
            temp[t++] = array[j++];
        }
        //排序结果写入原数组
        for (int k = 0; k < temp.length; k++) {
            array[start + k] = temp[k];
        }
    }
}

两个链表的第一个公共结点

标签：【链表】

题目描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

代码

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
/*
双指针法。创建两个指针p1和p2,分别指向两个链表的头结点，然后依次往后遍历。如果某个指针到达末尾，则将该指针指向另一个链表的头结点；如果两个指针所指的节点相同，则循环结束，返回当前指针指向的节点。比如两个链表分别为：1->3->4->5->6和2->7->8->9->5->6。短链表的指针p1会先到达尾部，然后重新指向长链表头部，当长链表的指针p2到达尾部时，重新指向短链表头部，此时p1在长链表中已经多走了k步(k为两个链表的长度差值)，p1和p2位于同一起跑线，往后遍历找到相同节点即可到达第一个公共结点。其实该方法主要就是用链表循环的方式替代了长链表指针先走k步这一步骤。
*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while (p1 != p2) {
            p1 = p1== null ? pHead2 : p1.next;
            p2 = p2== null ? pHead1 : p2.next;
        }
        return p1;
    }
}

数字在排序数组中出现的次数

标签：【数组】

题目描述

统计一个数字在排序数组中出现的次数。

代码

import java.util.Arrays;
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array==null ||array.length==0){
            return 0;
        }
        //用Arrays.binarySearch二分查找出目标数字在有序数组的索引下标
        int index=Arrays.binarySearch(array,k);
        //不存在则返回应该插入的位置，如{2,4,6}，查找0返回-1，查找3返回-2，查找7返回-4，即返回
        //-（实际应插入数组位置+1）
        if(index<=-1){
            return 0;
        }
        int count=1;
        //统计右边相同的数字
        for(int i=index+1;i<array.length &&array[i]==k;i++){
            count++;
        }
        //统计左边相同的数字
        for(int i=index-1;i>=0 &&array[i]==k;i--){
            count++;
        }
        return count;
    }
}

二叉树的深度

标签：【树】

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

代码

/**
 * public class TreeNode {
 * int val = 0;
 * TreeNode left = null;
 * TreeNode right = null;
 * <p>
 * public TreeNode(int val) {
 * this.val = val;
 * <p>
 * }
 * <p>
 * }
 */

import java.util.LinkedList;

public class Solution {
/*
	//深度优先递归
    public int TreeDepth(TreeNode root) {
        if (null == root) {
            return 0;
        }
        int left = 0;
        int right = 0;
        if (root.left != null) {
            left = TreeDepth(root.left);
        }
        if (root.right != null) {
            right = TreeDepth(root.right);
        }
        return 1 + (left >= right ? left : right);
    }
*/

    //层次遍历
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        LinkedList<TreeNode> list = new LinkedList<TreeNode>();
        list.add(root);
        int count = 0;
        while (list.size() != 0) {
            count++;
            int size = list.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = list.remove();
                if (curr.left != null) {
                    list.add(curr.left);
                }
                if (curr.right != null) {
                    list.add(curr.right);
                }
            }
        }
        return count;
    }
}

平衡二叉树

标签：【树】

题目描述

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

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

代码

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return deepth(root)!=-1;
    }
    private int deepth(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=deepth(root.left);
        //剪枝
        if(left==-1){
            return -1;
        }
        int right=deepth(root.right);
        //剪枝
        if(right==-1){
            return -1;
        }
        //不平衡
        if(Math.abs(left-right)>1){
            return -1;
        }
        return (left>right?left:right)+1;
    }
}

数组中只出现一次的数字

标签：【数组】

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

代码

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
/*
  首先：位运算中异或的性质：两个相同数字异或=0，一个数和0异或还是它本身。当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。依照这个思路，我们来看两个数（我们假设是AB）出现一次的数组。我们首先还是先异或，剩下的数字肯定是A、B异或的结果，这个结果的二进制中的1，表现的是A和B的不同的位。我们就取第一个1所在的位数，假设是第3位，接着把原数组分成两组，分组标准是第3位是否为1。如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。
*/
public class Solution {
    public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
        int res = 0;
        for (int i = 0; i < array.length; i++) {
            res = res ^ array[i];
        }
        //此时res为这两个只出现一次的数异或的结果
        int temp = 1;
        //从低位到高位开始寻找这两个数不同的位，即res中为1的位
        while ((temp & res) == 0) {
            temp = temp << 1;
        }
        int one = 0;
        int two = 0;
        for (int i = 0; i < array.length; i++) {
            //根据这个指定位的不同，分成两类
            if ((array[i] & temp) == 0) {
                one = one ^ array[i];
            }
            //根据这个指定位的不同，分成两类
            else {
                two = two ^ array[i];
            }
        }
        num1[0] = one;
        num2[0] = two;
    }
}

和为S的连续正数序列

标签：【穷举】

题目描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输出描述：
1
2
> 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
>

代码

import java.util.ArrayList;

/**
 *  滑动窗口法解连续区间和问题
 *  
 * 1.什么是滑动窗口？顾名思义，首先是一个窗口，既然是一个窗口，就需要用窗口的左边界i和右边界j来唯一表示一    个窗口，其次，滑动代表，窗口始终从左往右移动，这也表明左边界i和右边界j始终会往后移动，而不会往左移动。
 * 2.滑动窗口的操作
 * 扩大窗口，j += 1
 * 缩小窗口，i += 1
 * 算法步骤：
 * （1）初始化，i=1,j=1, 表示窗口大小为0
 * （2）如果窗口中值的和小于目标值sum， 表示需要扩大窗口，j += 1
 * （3）否则，如果狂口值和大于目标值sum，表示需要缩小窗口，i += 1
 * （4）否则，等于目标值，存结果，缩小窗口，继续进行步骤2,3,4
 * 这里需要注意2个问题：
 * （1）什么时候窗口终止呢，这里窗口左边界走到sum的一半即可终止，因为题目要求至少包含2个数
 * （2）什么时候需要扩大窗口和缩小窗口？解释可看上述算法步骤。
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        int left = 1;
        int right = 2;
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        while (left <= sum / 2 && right <= sum) {
            int count = 0;
            for (int i = left; i <= right; i++) {
                count += i;
            }
            //right加1，向右扩张
            if (count < sum) {
                right++;
            } 
            //left加1，向右收缩
            else if (count > sum) {
                left++;
            } else {
                ArrayList<Integer> list = new ArrayList<Integer>();
                for (int i = left; i <= right; i++) {
                    list.add(i);
                }
                res.add(list);
                left++;
            }
        }
        return res;
    }
}

和为S的两个数字

标签：【数学】【数组】【双指针】

题目描述

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

输出描述：
1
2
> 对应每个测试案例，输出两个数，小的先输出。
>

代码

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (array == null || array.length == 0) {
            return res;
        }
        //双指针
        int left = 0;
        int right = array.length - 1;
        //乘积
        int product = Integer.MAX_VALUE;
        //前后两个指针相遇就停止
        while (left < right) {
            if (array[left] + array[right] == sum) {
                if (array[left] * array[right] < product) {
                    product = array[left] * array[right];
                    res.add(0, array[left]);
                    res.add(1, array[right]);
                }
                left++;
            } else if (array[left] + array[right] > sum) {
                right--;
            } else {
                left++;
            }
        }
        return res;
    }
}

左旋转字符串

标签：【字符串】

题目描述

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

代码

import java.util.LinkedList;

public class Solution {
    public String LeftRotateString(String str, int n) {
        LinkedList<Character> list1 = new LinkedList<Character>();
        LinkedList<Character> list2 = new LinkedList<Character>();
        for (int i = 0; i < str.length(); i++) {
            if (i < n % str.length()) {
                list1.add(str.charAt(i));
            } else {
                list2.add(str.charAt(i));
            }
        }
        StringBuffer sb = new StringBuffer();
        while (list2.size() != 0) {
            sb.append(list2.remove());
        }
        while (list1.size() != 0) {
            sb.append(list1.remove());
        }
        return sb.toString();
    }
}

翻转单词顺序序列

标签：【字符串】

题目描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

代码

public class Solution {
    public String ReverseSentence(String str) {
        if(str==null ||str.length()==0){
            return "";
        }
        //String.trim()方法去除字符串前后的空格
        if(str.trim().equals(""))
        {
            return str;
        }
        //以空格分割字符串
        String[] input=str.split("\\s");
        StringBuffer sb=new StringBuffer();
        for(int i=input.length-1;i>=0;i--){
            sb.append(input[i]).append(" ");
        }
        String res=sb.toString();
        //输出字符串，去除最后一个空格
        return res.substring(0,res.length()-1);
    }
}

扑克牌顺子

标签：【字符串】

题目描述

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何，如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

代码

/**
*简单来说就是要是5个数字，最大和最小差值在5以内，并且没有重复数值。用一个set来填充数据，0不要放进去。set的*大小加上0的个数必须为5个。此外set中数值差值在5以内。
*/
import java.util.TreeSet;

public class Solution {
    public boolean isContinuous(int[] numbers) {
        if (numbers.length < 5 || numbers.length > 5) {
            return false;
        }
        TreeSet<Integer> set = new TreeSet<Integer>();
        int num = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == 0) {
                num++;
            } else {
                set.add(numbers[i]);
            }
        }
        if (num + set.size() != 5) {
            return false;
        }
        if (set.last() - set.first() < 5) {
            return true;
        }
        return false;
    }
}

孩子们的游戏（圆圈中最后剩下的数）

标签：【链表】【数学】

题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

代码

import java.util.LinkedList;

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n<=0){
            return -1;
        }
        LinkedList<Integer> list =new LinkedList<Integer>();
        for(int i=0;i<n;i++){
            list.add(i);
        }
        //被提出的小朋友
        int out=0;
        while(list.size()>1){
            //防止超出列表长度
            out=(out+m-1)%list.size();
            //移除
            list.remove(out);
        }
        //剩余的最后一个小朋友
        return list.get(0);
    }
}

求1+2+3+…+n

标签：【进制转化】【数学】

题目描述

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

代码

public class Solution {
    public int Sum_Solution(int n) {
        int sum = n;
        //逻辑且的短路原理，当n=0时，不再往下递归
        boolean temp = (n != 0) && ((sum = sum + Sum_Solution(n - 1)) != 0);
        return sum;
    }
}

不用加减乘除做加法

标签：【进制转化】【数学】

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

代码

/**
*  执行加法  x ^ y
*  进位操作 ( x & y ) << 1
*/
public class Solution {
    public int Add(int num1,int num2) {
        while(num2!=0){
            //保存进位信息
            int temp=(num1&num2)<<1;
            //二进制加
            num1=num1^num2;
            //进位赋予num2，循环执行相加，直到无进位为止
            num2=temp;
        }
        return num1;
    }
}

把字符串转换成整数

标签：【字符串】【数学】【字符串】

题目描述

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0

输入描述：
1
2
> 输入一个字符串,包括数字字母符号,可以为空
>

输出描述：

1 2	> 如果是合法的数值表达则返回该数字，否则返回0 >

示例1

输入
1
2
3
> +2147483647
> 1a33
>

输出

1
2
3

> 2147483647
> 0
>

代码

public class Solution {
    public int StrToInt(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        //第一个字符
        char first = str.charAt(0);
        //整数转化开始下标
        int start = 0;
        //符号标记，正数为0，负数为1
        int flag = 0;
        if (first == '+') {
            start = 1;
        } else if (first == '-') {
            start = 1;
            flag = 1;
        } else if (first < '0' || first > '9') {
            return 0;
        }
        long res = 0;
        for (int i = start; i < str.length(); i++) {
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                res = res * 10 + str.charAt(i) - '0';
            } else {
                return 0;
            }

        }
        if (flag == 0) {
            //正整数溢出
            if (res > Integer.MAX_VALUE) {
                return 0;
            }
        }
        if (flag == 1) {
            //负整数溢出
            if ((-1) * res < Integer.MIN_VALUE) {
                return 0;
            }
            res = (int) (-1 * res);
        }
        return (int) res;
    }
}

数组中重复的数字

标签：【数组】

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

代码

import java.util.HashMap;

public class Solution {
    public boolean duplicate(int numbers[], int length, int[] duplication) {
        if (numbers == null || length <= 1) {
            return false;
        }
        HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        for (int i = 0; i < length; i++) {
            if (map.get(numbers[i]) == null) {
                map.put(numbers[i], true);
            } else if (map.get(numbers[i])) {
                //第一个重复的数放到duplication[0]返回
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }
}

构建乘积数组

标签：【数组】

题目描述

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…A[i-1]A[i+1]…A[n-1]。不能使用除法。（注意：规定B[0] = A[1] A[2] … A[n-1]，B[n-1] = A[0] A[1] … A[n-2];）

对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。

代码

import java.util.ArrayList;
/**
*	暴力计算就完了
*/
public class Solution {
    public int[] multiply(int[] A) {
     int B[]=new int[A.length];
     int shunxu[] =new int[A.length];
     int nixu[] =new int[A.length];
     int temp_shun=1;
     int temp_ni=1;
     for(int i =0;i<A.length;i++){
         temp_shun*=A[i];
         shunxu[i]=temp_shun;
     }
     for(int j=A.length-1;j>=0;j--){
         temp_ni*=A[j];
         nixu[j]=temp_ni;
     }
     B[0]=nixu[1];
     for(int k=1;k<A.length-1;k++){
         B[k]=shunxu[k-1]*nixu[k+1];
     }
     B[A.length-1]=shunxu[A.length-2];
     return B;
    }
}

正则表达式匹配

标签：【字符串】

题目描述

请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配

代码

public class Solution {
    public boolean matchStr(char[] str, int i, char[] pattern, int j) {
        // 边界
        if (i == str.length && j == pattern.length) { 
            // 字符串和模式串都为空
            return true;
        } else if (j == pattern.length) { 
            // 模式串为空
            return false;
        }
        boolean flag = false;
        boolean next = (j + 1 < pattern.length && pattern[j + 1] == '*'); 
        // 模式串下一个字符是'*'
        if (next) {
            if (i < str.length && (pattern[j] == '.' || str[i] == pattern[j])) {
     /*
      * 要保证i<str.length，否则越界。
      * 出现了'*'，而且i和j指向的相等（这里的相等可以是真正的相等，也可以是'.'标记的相等）。
      * 比如abcd和ab*cf，其中i和j都指向了b。此时应该i+1和j+2。比如abbcd和ab*cf，其中i和j都指向了b。
      * 由于b出现了多次，应该不着急移动j，所以此时i+1即可。
      * 比如"cba","cb*a*a"，我也可以认为，j指向的第1个a没出现过，即使你相等。因此此时可以i不动，j+2。
      */
            return matchStr(str, i, pattern, j + 2) || matchStr(str, i + 1, pattern, j);
            } else {
                return matchStr(str, i, pattern, j + 2);
            }
        } else {
            if (i < str.length && (pattern[j] == '.' || str[i] == pattern[j])) {
                return matchStr(str, i + 1, pattern, j + 1);
            } else {
                return false;
            }
        }
    }

    public boolean match(char[] str, char[] pattern) {
        return matchStr(str, 0, pattern, 0);
    }
}

表示数值的字符串

标签：【字符串】

题目描述

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

代码

public class Solution {
    public boolean isNumeric(char[] str) {
    /*
        使用正则表达式
        [\\+\\-]?            -> 正或负符号出现与否
        \\d*                 -> 整数部分是否出现，如-.34 或 +3.34均符合
        (\\.\\d+)?           -> 如果出现小数点，那么小数点后面必须有数字；
                                否则一起不出现
        ([eE][\\+\\-]?\\d+)? -> 如果存在指数部分，那么e或E肯定出现，+或-可以不出现，
                            紧接着必须跟着整数；或者整个部分都不出现
    */
        String string = String.valueOf(str);
        return string.matches("[\\+\\-]?\\d*(\\.\\d+)?([eE][\\+\\-]?\\d+)?");
    }
}

字符流中第一个不重复的字符

标签：【字符串】

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

输出描述：
1
2
> 如果当前字符流没有存在出现一次的字符，返回#字符。
>

代码

public class Solution {
    //Insert one char from stringstream
    String input = "";
    char[] count = new char[256];

    public void Insert(char ch) {
        input += ch;
        //char型的数可以看成一个整数，计算机里保存char也是保存数值的
        count[ch]++;
    }

    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce() {
        for (int i = 0; i < input.length(); i++) {
            if (count[input.charAt(i)] == 1) {
                return input.charAt(i);
            }
        }
        return '#';
    }
}

链表中环的入口结点

标签：【链表】

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

代码

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
/**
*快慢指针法：step1.快指针每次走两步，慢指针每次走一步，直到两指针相遇；
*		   step2.快指针从链表头开始以一步的步长移动，慢指针从相遇点开始以一步的步长移动，等再次相遇的时
*                候，相遇点即链表环的入口。
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        if (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            while (fast != slow && fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            if (fast != null && fast.next != null) {
                fast = pHead;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            } else {
                return null;
            }
        }
        return null;
    }
}

删除链表中重复的结点

标签：【链表】

题目描述

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

代码

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null) {
            return pHead;
        }
        //哨兵结点，主要是为了返回调整后的链表头结点方便
        ListNode head = new ListNode(0);
        //保留当前调整结点的前驱结点信息，前驱结点的后继指针可能要调整
        ListNode pre = head;
        //正在处理的结点
        ListNode curr = pHead;
        head.next = pHead;
        while (curr != null) {
            if (curr.next != null && curr.val == curr.next.val) {
                curr = curr.next;
                while (curr.next != null && curr.val == curr.next.val) {
                    curr = curr.next;
                }
                curr = curr.next;
                pre.next = curr;
            } else {
                pre = curr;
                curr = curr.next;
            }
        }
        return head.next;
    }
}

二叉树的下一个结点

标签：【树】

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

代码

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    //父结点
    TreeLinkNode next = null;
    
    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) {
            return null;
        }
        //以pNode为开始结点的树有右子树的话，中序遍历的下一个结点是右子树的最左孩子结点
        if (pNode.right != null) {
            pNode = pNode.right;
            while (pNode.left != null) {
                pNode = pNode.left;
            }
            return pNode;
        }
        //pNode有父结点的情况
        while (pNode.next != null) {
            //当pNode是其父结点的左孩子时，父结点为中序遍历的下一个结点
            if (pNode.next.left == pNode) {
                return pNode.next;
            }
            //否则，将当前查询结点设为其父结点，继续进行查找
            pNode = pNode.next;
        }
        //pNode无父结点情况
        return null;
    }
}

对称的二叉树

标签：【树】

题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

代码

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        TreeNode copy = copyTree(pRoot);
        mirrorTree(pRoot);
        return compare(pRoot, copy);
    }

    //二叉树的深拷贝
    private TreeNode copyTree(TreeNode pRoot) {
        if (pRoot == null) {
            return null;
        }
        TreeNode root = new TreeNode(pRoot.val);
        root.left = copyTree(pRoot.left);
        root.right = copyTree(pRoot.right);
        return root;
    }

    //二叉树的镜像化
    private void mirrorTree(TreeNode pRoot) {
        if (pRoot == null) {
            return;
        }
        mirrorTree(pRoot.left);
        mirrorTree(pRoot.right);
        TreeNode temp;
        temp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = temp;

    }

    //比较原二叉树与镜像二叉树是否一致
    private boolean compare(TreeNode one, TreeNode two) {
        if (one == null && two == null) {
            return true;
        }
        if (one != null && two != null && one.val == two.val) {
            return compare(one.left, two.left) && compare(one.right, two.right);
        } else {
            return false;
        }
    }
}

按之字形顺序打印二叉树

标签：【栈】【树】

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

代码

import java.util.ArrayList;
import java.util.Stack;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        int count = 1;
        //奇数层栈
        Stack<TreeNode> stackodd = new Stack<TreeNode>();
        //偶数层栈
        Stack<TreeNode> stackeven = new Stack<TreeNode>();
        if (pRoot != null) {
            stackodd.add(pRoot);
        } else {
            return res;
        }

        while (!stackodd.isEmpty() || !stackeven.isEmpty()) {
            //奇数层处理
            if (count % 2 != 0) {
                ArrayList<Integer> temp = new ArrayList();
                //奇数层出栈
                while (!stackodd.isEmpty()) {
                    TreeNode root = stackodd.pop();
                    temp.add(root.val);
                    //左孩子入偶数层栈
                    if (root.left != null) {
                        stackeven.push(root.left);
                    }
                    //右孩子入偶数层栈
                    if (root.right != null) {
                        stackeven.push(root.right);
                    }
                }
                if (!temp.isEmpty()) {
                    res.add(temp);
                    count++;
                }
            } 
            //偶数层处理
            else {
                ArrayList<Integer> temp = new ArrayList();
                //偶数层出栈
                while (!stackeven.isEmpty()) {
                    TreeNode root = stackeven.pop();
                    temp.add(root.val);
                    //右孩子入奇数层栈
                    if (root.right != null) {
                        stackodd.push(root.right);
                    }
                    //左孩子入奇数层栈
                    if (root.left != null) {
                        stackodd.push(root.left);
                    }
                }
                if (!temp.isEmpty()) {
                    res.add(temp);
                    count++;
                }
            }
        }
        return res;
    }

}

把二叉树打印成多行

标签：【树】【bfs】

题目描述

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

代码

import java.util.ArrayList;
import java.util.LinkedList;

/*
public 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>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        if (pRoot != null) {
            queue.offer(pRoot);
            int deep = deepth(pRoot);
            int count = 0;
            while (!queue.isEmpty() && count <= (Math.pow(2, deep) - 1)) {
                count++;
                TreeNode temp = queue.poll();
                list.add(temp.val);
                if (temp.left != null) {
                    queue.offer(temp.left);
                } else {
                    temp.left = new TreeNode('#');
                    queue.offer(temp.left);
                }
                if (temp.right != null) {
                    queue.offer(temp.right);
                } else {
                    temp.right = new TreeNode('#');
                    queue.offer(temp.right);
                }

            }
            int sum = 0;
            for (int i = 0; i < deep; i++) {
                int persum = (int) Math.pow(2, i);
                ArrayList<Integer> temp = new ArrayList<Integer>();
                for (int j = 0; j < persum; j++) {
                    if (list.get(sum) != '#') {
                        temp.add(list.get(sum));
                    }
                    sum++;
                }
                res.add(temp);
            }

        }
        return res;
    }
	
    //树的深度
    private int deepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = deepth(root.left);
        int right = deepth(root.right);
        return 1 + (left >= right ? left : right);
    }

}

序列化二叉树

标签：【树】【序列化】

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#），以！表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，我们可以把一个只有根节点为1的二叉树序列化为”1,”，然后通过自己的函数来解析回这个二叉树

代码

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    int count = -1;
	//序列化
    String Serialize(TreeNode root) {
        if (root == null) {
            return "#";
        }
        //类似前序遍历的方式序列化
        return "" + root.val + "," + Serialize(root.left) + Serialize(root.right);
    }

    TreeNode Deserialize(String str) {
        String[] input = str.split(",");
        //前序方式遍历的位置
        count++;
        TreeNode node = null;
        if (input[count] != "#") {
            node = new TreeNode(Integer.parseInt(input[count]));
            node.left = Deserialize(str);
            node.right = Deserialize(str);
        }
        return node;
    }
}

二叉搜索树的第K个结点

标签：【树】

题目描述

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

代码

import java.util.PriorityQueue;
import java.util.HashMap;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    //优先级队列保存结点值，堆顶是最小值
    PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
    //保存值与结点之间的关联关系
    HashMap<Integer, TreeNode> map = new HashMap<Integer, TreeNode>();
	//二叉搜索树的第K个结点
    TreeNode KthNode(TreeNode pRoot, int k) {
        search(pRoot);
        if (k <= 0 || k > queue.size()) {
            return null;
        }
        for (int i = 1; i < k; i++) {
            queue.poll();
        }
        return map.get(queue.peek());
    }
	//中序遍历二叉搜索树得到一个排序的序列
    private void search(TreeNode pRoot) {
        if (pRoot == null) {
            return;
        }
        search(pRoot.left);
        queue.offer(pRoot.val);
        map.put(pRoot.val, pRoot);
        search(pRoot.right);
    }
}

数据流中的中位数

标签：【进制转化】【排序】【堆】

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

代码

import java.util.*;

public class Solution {
    int count = 0;
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {
        @Override
        //降序，实现大顶堆
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    public void Insert(Integer num) {
        if (count % 2 == 0) {//当数据总数为偶数时，新加入的元素，应当进入小根堆
            //（注意不是直接进入小根堆，而是经大根堆筛选后取大根堆中最大元素进入小根堆）
            //1.新加入的元素先入到大根堆，由大根堆筛选出堆中最大的元素
            maxHeap.offer(num);
            int filteredMaxNum = maxHeap.poll();
            //2.筛选后的【大根堆中的最大元素】进入小根堆
            minHeap.offer(filteredMaxNum);
        } else {//当数据总数为奇数时，新加入的元素，应当进入大根堆
            //（注意不是直接进入大根堆，而是经小根堆筛选后取小根堆中最大元素进入大根堆）
            //1.新加入的元素先入到小根堆，由小根堆筛选出堆中最小的元素
            minHeap.offer(num);
            int filteredMinNum = minHeap.poll();
            //2.筛选后的【小根堆中的最小元素】进入大根堆
            maxHeap.offer(filteredMinNum);
        }
        count++;
    }

    public Double GetMedian() {
        //从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值
        if (count % 2 == 0) {
            return new Double((minHeap.peek() + maxHeap.peek())) / 2;
        } 
        //从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值
        else {
            return new Double(minHeap.peek());
        }
    }
}

滑动窗口的最大值

标签：【堆】【双指针】

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下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]}。

窗口大于数组长度的时候，返回空

代码


import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Collections;

public class Solution {
    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (size > num.length || size <= 0) {
            return res;
        }
        //窗口下标
        int low = 0;
        //窗口上标
        int high = size - 1;
        //大顶堆
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>(Collections.reverseOrder());
        //初始化窗口，入堆
        for (int i = low; i <= high; i++) {
            heap.offer(num[i]);
        }
        //滑动窗口，获取每次窗口的最大值
        while (high < num.length - 1) {
            res.add(heap.peek());
            heap.remove(num[low]);
            low++;
            high++;
            heap.offer(num[high]);
        }
        //获取最后一个窗口的最大值
        res.add(heap.peek());
        return res;
    }
}

矩阵中的路径

标签：【dfs】【回溯】

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如:

a b c e

s f c s

a d e e

矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

代码

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        if (matrix == null || matrix.length == 0 || rows <= 0 || cols <= 0 || str == null || str.length == 0) {
            return false;
        }
        //矩阵
        char[][] m = new char[rows][cols];
        //访问标记
        int[][] visit = new int[rows][cols];
        //矩阵初始化
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                m[i][j] = matrix[i * cols + j];
            }
        }
        //从m[i][j]出发搜索
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int count = 0;
                if (find(m, rows, cols, str, i, j, count, visit)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean find(char[][] matrix, int rows, int cols, char[] str, int srow, int scol, int count, int[][] visit) {
        //已达到目标字符串的长度
        if (count >= str.length) {
            return true;
        }
        if (srow >= rows || scol >= cols || srow < 0 || scol < 0 || visit[srow][scol] == 1) {
            return false;
        }
        //置位访问标记
        visit[srow][scol] = 1;
        boolean flag = false;
        //当前位置的字符与目标字符一致，接着向上下左右四个方向继续搜索
        if (matrix[srow][scol] == str[count]) {
            flag = find(matrix, rows, cols, str, srow + 1, scol, count++, visit) ||
                   find(matrix, rows, cols, str, srow - 1, scol, count++, visit) ||
                   find(matrix, rows, cols, str, srow, scol + 1, count++, visit) ||
                   find(matrix, rows, cols, str, srow, scol - 1, count++, visit);
        }
        //取消访问标记
        visit[srow][scol] = 0;
        return flag;
    }
}

机器人的运动范围

标签：【数组】

题目描述

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

代码

public class Solution {
    //格子数统计
    int count = 0;
    public int movingCount(int threshold, int rows, int cols) {
        if (threshold < 0) {
            return 0;
        }
        //访问标记
        int[][] visit = new int[rows][cols];
        find(threshold, rows, cols, 0, 0, visit);
        return count;
    }
	//开始统计
    private void find(int threshold, int rows, int cols, int sr, int sc, int[][] visit) {
        if (sr >= rows || sr < 0 || sc >= cols || sc < 0 || visit[sr][sc] == 1) {
            return;
        }
        if (sum(sr, sc) > threshold) {
            return;
        }
        //访问标记置位
        visit[sr][sc] = 1;
        //格子数加一
        count++;
        find(threshold, rows, cols, sr + 1, sc, visit);
        find(threshold, rows, cols, sr - 1, sc, visit);
        find(threshold, rows, cols, sr, sc + 1, visit);
        find(threshold, rows, cols, sr, sc - 1, visit);
    }
	//计算数位之和
    private int sum(int row, int col) {
        int sumR = 0;
        int sumC = 0;
        while (row != 0) {
            sumR += row % 10;
            row /= 10;
        }
        while (col != 0) {
            sumC += col % 10;
            col /= 10;
        }
        return sumR + sumC;
    }
}

剪绳子

标签：【贪心】【数组】【数量关系】【高级算法】【组合数学】

题目描述

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],…,k[m]。请问k[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

输入描述：
1
2
> 输入一个数n，意义见题面。（2 <= n <= 60）
>

输出描述：
1
2
> 输出答案。
>

示例1

输入
1
2
> 8
>

输出
1
2
> 18
>

代码

public class Solution {
    public int cutRope(int target) {
        if (target == 2) {
            return 1;
        }
        if (target == 3) {
            return 2;
        }
        //记录表
        int[] record = new int[target + 1];
        //记录表初始化
        for (int i = 0; i < target + 1; i++) {
            record[i] = -1;
        }
        return solve(target, record);
    }

    private int solve(int target, int[] record) {
        //剩余的长度在4及以下直接返回，最佳解是不再分割
        if (target <= 4) {
            return target;
        }
        //记录表中有纪录，直接返回，避免重复计算
        if (record[target] != -1) {
            return record[target];
        }
        int max = 0;
        //自下而上，由子问题最优解得到问题的最优解
        for (int i = 1; i < target; i++) {
            max = Math.max(max, i * solve((target - i), record));
        }
        //子问题的最优解纪录到记录表中
        record[target] = max;
        return max;
    }
}