原创
  • 2020-08-04
  • 浏览 (3)
  • 评论 (0)

剑指 Offer 题解

JZ1 . 二位数组中的查找

题目描述

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

解题思路

利用二维数组由上到下,由左到右递增的规律,
那么选取右上角的元素a[row][col]与target进行比较,
当target小于元素a[row][col]时,那么target必定在元素a所在行的左边,
即col--;
当target大于元素a[row][col]时,那么target必定在元素a所在列的下边,
即row++

public boolean Find(int target, int [][] array) {
    if(array == null)
        return false;
    int row = array.length-1;
    int col = array[0].length-1;
    int x = 0;
    int y = col;
    while(x <= row && y >= 0){
        if(target == array[x][y]){
            return true;
        }else if(target >array[x][y]){
            x++;
        }else{
            y--;
        }
    }
    return false;
}

JZ2 . 替换空格

题目描述

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

解题思路

是在原字符串基础上做替换,还是新开辟一个字符串做替换。基于这个问题,可以有两种解法。

1.在原字符串基础上做替换,那么肯定要扩大 2*空格数量 的字符容量,扩容之后需要将"%20"插入到原字符串之中。那么如何插入呢?一种简单的方法是从后往前,如果当前字符为空格,那么从后往前插入'0','2','%',否则插入对应的字符就行了。

2.在新开辟的字符串做替换,这种方法比较简单,依次遍历原字符串插入到新字符串中就行了。

/*在原字符串基础上做替换*/
public String replaceSpace(StringBuffer str) {
    int len = str.length();
    for(int i=0;i<len;i++){
        if(str.charAt(i) == ' '){
            str.append("  ");
        }
    }
    int p1 = len - 1;
    int p2 = str.length() - 1;
    while(p1 < p2){
        char c = str.charAt(p1--);
        if(c == ' '){
            str.setCharAt(p2--,'0');
            str.setCharAt(p2--,'2');
            str.setCharAt(p2--,'%');
        }else{
            str.setCharAt(p2--,c);
        }
    }
    return str.toString();
}

/*新开辟一个字符串替换*/
public String replaceSpace(StringBuffer str) {
    char[] chars = str.toString().toCharArray();
    StringBuffer reStr = new StringBuffer();
    int len = chars.length;
    for(int i=0;i<len;i++){
        if(chars[i] == ' '){
            reStr.append("%20");
        }else{
            reStr.append(chars[i]);
        }
    }

    return reStr.toString();
}

JZ3 . 从尾到头打印链表

题目描述

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

解题思路

从尾到头,很容易想到先反转链表,然后依次将元素放入到 ArrayList 中。还可以想到另外一种方法,就是使用递归的方法,递归的本质就是压栈,最先处理返回的元素一定是栈顶的元素(单链表的尾结点),所以可以递归遍历单链表,将元素压栈(递归就是压栈),就实现了从尾到头的顺序返回。

/*反转链表的方法*/
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> list = new ArrayList();
    ListNode pre = null, next = null;
    while(listNode != null){
        next = listNode.next;
        listNode.next = pre;
        pre = listNode;
        listNode = next;
    }
    while(pre != null){
        list.add(pre.val);
        pre = pre.next;
    }
    return list;
}

/*使用递归的方法*/
ArrayList<Integer> list = new ArrayList();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    if(listNode != null){
        //递归,压栈操作
        printListFromTailToHead(listNode.next);
        list.add(listNode.val);
    }
    return list;
}

JZ4 . 重建二叉树

题目描述

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

解题思路

public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    return dfs(pre,0,pre.length-1,in,0,in.length-1);
}

public TreeNode dfs(int [] pre,int preS,int preE,int [] in,int inS,int inE){
    if(preS > preE || inS > inE)
        return null;
    TreeNode root = new TreeNode(pre[preS]);
    for(int i=inS;i<=inE;i++){
        if(pre[preS] == in[i]){
            root.left = dfs(pre,preS+1,preS+i-inS,in,inS,i-1);
            root.right = dfs(pre,preS+i-inS+1,preE,in,i+1,inE);
            break;
        }
    }
    return root;
}

JZ5 . 用两个栈实现队列

题目描述

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

解题思路

栈是先进后出的结构,而队列是先进先出的结构。元素出栈的序列和元素出队的序列刚好是相反的。那么元素如果是入栈->出栈->入栈->出栈,负负得正。那么通过两个栈,就完全可以实现一个先进先出的队列。

Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
    stack1.push(node);
}

public int pop() {
    if(stack1.isEmpty() && stack2.isEmpty())
        return -1;
    if(stack2.isEmpty()){
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
    }
    return stack2.pop();
}

JZ6 . 旋转数组的最小数字

题目描述

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

解题思路

public int minNumberInRotateArray(int [] array) {
    if(array == null || array.length == 0)
        return 0;
    int left = 0;
    int right = array.length - 1;

    while(left <= right) {
            int mid = left + (right-left)/2;
        if(array[mid] > array[right]) {
            left = mid + 1;
        }else if(array[mid] < array[right]) {
            right = mid;
        }else {
            right = right - 1;
        }
    }

    return array[left];
}

JZ7 . 斐波那契数列

题目描述

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项是1)。
n<=39

解题思路

斐波那契数列:s(n) = s(n-1) + s(n-2)。很容易想到用递归的方法求第 n 项的值。因为我们已经知道了第 0 项和第 1 项的值,根据递推公式,就可以求得任意一项的值。因为递归是一个压栈的过程,使用递归会存在重复计算,还可以考虑用动态规划的方法求解,动态规划不会出现重复计算,只需要记录 n-1 项的值和 n-2 项的值就可以得到第 n 项的值。

//递归解法
public int Fibonacci(int n) {
    if(n == 0 || n == 1)
        return n;
    return Fibonacci(n-1) + Fibonacci(n-2);
}

//动态规划解法
public int Fibonacci(int n) {
    if(n == 0 || n == 1)
        return n;
    int[] dp = new int[2];
    dp[0] = 0;
    dp[1] = 1;
    int res = 0;
    for(int i=2;i<=n;i++){
        res = dp[0]+dp[1];
        dp[0] = dp[1];
        dp[1] = res;
    }
    return res;
}

JZ8 . 跳台阶

题目描述

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

解题思路

例举几个数分析你会发现一个规律,跳台阶和斐波那契数列满足同样的公式:s(n) = s(n-1) + s(n-2)。

//递归解法
public int JumpFloor(int target) {
    if(target <= 3)
        return target;
    return JumpFloor(target-1)+JumpFloor(target-2);
}

//动态规划解法
public int JumpFloor(int target) {
    if(target <= 3)
        return target;
    int[] dp = new int[2];
    dp[0] = 2;
    dp[1] = 3;
    int res = 0;
    for(int i=4;i<=target;i++){
        res = dp[0]+dp[1];
        dp[0] = dp[1];
        dp[1] = res;
    }
    return res;
}

JZ9 . 变态跳台阶

题目描述

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

解题思路

public int JumpFloorII(int target) {
    return 1 << --target;
}

JZ10 . 矩形覆盖

题目描述

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

*解题思路

public int RectCover(int target) {
    if(target <= 3){
        return target;
    }
    int[] dp = new int[2];
    dp[0] = 2;
    dp[1] = 3;
    int res = 0;
    for(int i=4;i<=target;i++){
        res = dp[0]+dp[1];
        dp[0] = dp[1];
        dp[1] = res;
    }
    return res;
}

JZ11 . 二进制中1的个数

题目描述

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

解题思路

考察位运算

public int NumberOf1(int n) {
    int count = 0;
    while(n != 0){
        count++;
        n = n & (n-1);
    }
    return count;
}

JZ12 . 数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0。

解题思路

//暴力
public double Power(double base, int exponent) {
    if(base == 0)
        return 0;
    if(exponent == 0){
        return 1;
    }
    double res = 1.0;
    if(exponent < 0){
        base = 1/base;
        exponent = -exponent;
    }
    while(--exponent >= 0){
        res *= base;
    }
    return res;
}

//递归,快速幂
public double Power(double base, int exponent) {
    if(base == 0)
        return 0;
    if(exponent == 0){
        return 1;
    }
    double res = 1.0;
    if(exponent < 0){
        base = 1/base;
        exponent = -exponent;
    }
    return dfs(base,exponent);
}

public double dfs(double base,int exponent){
    if(exponent == 0)
        return 1.0;
    double res = dfs(base,exponent/2);
    if(exponent%2 == 1){
        return res*res*base;
    }else{
        return res*res;
    }
}

//非递归,快速幂
public double Power(double base, int exponent) {
    if(base == 0)
        return 0;
    if(exponent == 0){
        return 1;
    }
    if(exponent < 0){
        base = 1/base;
        exponent = -exponent;
    }
    double res = 1.0;
    while(exponent != 0){
        if(exponent%2 == 1){
            res *= base;
        }
        exponent >>= 1;
        base *= base;
    }
    return res;
}

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

题目描述

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

解题思路

看到这题很容易联想到荷兰国旗问题,使用划分的方法,将奇数和偶数调整到两边。但仔细一想又不对,荷兰国旗问题有一个划分的基本点,而这题却没有。想来想去,只能回到最简单的思维。该题如果对空间复杂度没有太大的要求,那么完全可以使用一个辅助数组来存储最后的结果。遍历原始数组两次,第一次遍历将奇数放入到辅助数组,第二次遍历将偶数放入到辅助数组,最后将辅助数组中的值拷贝到原始数组中就行了。那如果数据量很大,对空间有限制怎么办?既然不能使用辅助空间,那么相应的代价可能就是时间。使用原地(in-place)算法,不需要辅助空间,也可以解决这道问题,但是对应的时间复杂度提高到了 O(n^2)。

// 使用辅助数组,时间复杂度 O(n)
public void reOrderArray(int [] array) {
    int len = array.length;
    int[] res = new int[len];
    int index = 0;
    for(int i=0;i<len;i++){
        if((array[i] & 1) == 1){
            res[index++] = array[i];
        }
    }
    for(int i=0;i<len;i++){
        if((array[i] & 1) == 0){
            res[index++] = array[i];
        }
    }
    System.arraycopy(res, 0, array, 0, len);
}

// in-place 算法,时间复杂度 O(n^2)
public void reOrderArray(int [] array) {
    int len = array.length;
    int next = 0;
    for(int i=0;i<len;i++){
        if((array[i] & 1) == 1){//如果是奇数
            int temp = array[i];
            for(int k=i-1;k>=next;k--){//[next,i-1] 范围上的数整体后移
                array[k+1] = array[k];//后一个数等于前一个数
            }
            array[next++] = temp;
        }
    }
}

JZ14 . 链表中倒数第 K 个结点

题目描述

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

解题思路

因为遍历链表只能从头结点开始,要求倒数第 K 个结点,可以转化为求正数第多少个,这是最简单的解决思维。所以可以遍历一遍链表,求出结点的个数 count ,那么倒数第 K 个节点,就是头结点往后移动 count - k 个步数。 还有另外一种方法,利用快慢指针,快指针先走 K 个步数,然后快慢指针一起走,快指针指向空结点后停止,这时候慢指针肯定比快指针少走 K 步,也就是说慢指针就是链表中倒数第 K 个结点。

// 普通解法,时间复杂度 O(2*n),空间复杂度 O(1)
public ListNode FindKthToTail(ListNode head,int k) {
    int count = 0;
    ListNode p1 = head;
    while(p1 != null){
        p1 = p1.next;
        count++;
    }
    if(head == null || k<=0 || k > count)
        return null;
    int step = count - k;
    while(step > 0){
        head = head.next;
        step--;
    }
    return head;
}

// 快慢指针方法,时间复杂度 O(n),空间复杂度 O(1)
public ListNode FindKthToTail(ListNode head,int k) {
    ListNode fast = head;
    ListNode slow = head;
    while(fast != null){
        if(k > 0){
            k--;
        }else{
            slow = slow.next;
        }
        fast = fast.next;
    }
    return k > 0 ? null : slow;
}

JZ15 . 反转链表

题目描述

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

解题思路

反转链表,就是将每个结点 next 指针指向它的前一个结点。这里 pre 指针记录当前结点的前一个结点,next 记录当前结点的 后一个结点。

public ListNode ReverseList(ListNode head) {
    ListNode pre = null,next = null;
    while(head != null){
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

JZ16 . 合并两个排序的链表

题目描述

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

解题思路

相信写过归并排序的看到这题,就一定会想到分治法,因为两个链表的结点都是单调递增的,如果用归并的排序的思维来写这题,那就再简单不过了,只不过结构转换了成了链表。只需要额外开辟两个指针的空间,来记录当前遍历到的结点和需要返回的头结点,即可得到结果。

// 分治法,时间复杂度 O(n),空间复杂度 O(1)
public ListNode Merge(ListNode list1,ListNode list2) {
    ListNode head,p;
    head = p = new ListNode(0);
    for(;list1 != null && list2 != null;p = p.next){
        if(list1.val < list2.val){
            p.next = list1;
            list1 = list1.next;
        }else{
            p.next = list2;
            list2 = list2.next;
        }
    }
    if(list1 != null)
        p.next = list1;
    if(list2 != null)
        p.next = list2;
    return head.next;
}

JZ17 . 树的子结构

题目描述

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

子结构定义:树A和树B的根结点相等,并且树A的左子树和树B的左子树相等,树A的右子树和树B的右子树相等

解题思路

如何判断一棵树是另外一棵树的子结构?很显然,这是一个递归的过程。暂时忘记递归这个过程,如果给你两棵完全一样的树,并且只有根左右3个结点,如何判断他们是一样的呢?这个谁都会,不用觉得递归难,递归其实也是 DFS,对于这道题,关键在于给出当前判断两棵树是否一样的代码,至于下一步如何做,和当前的策略是一样的,用递归就行了。

public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    if(root1 == null || root2 == null)
        return false;
    else{
        return doesTreeSame(root1,root2) || HasSubtree(root1.left,root2) ||
            HasSubtree(root1.right,root2);
    }
}

public boolean doesTreeSame(TreeNode root1,TreeNode root2){// 判断两棵树是否一样
    if(root2 == null)// 子结构遍历完了,说明一样
        return true;
    if(root1 == null)// 子结构没遍历完,父结构却遍历结束了,肯定不存在
        return false;
    if(root1.val == root2.val){// 根节点相等,比较左右子结点
        return doesTreeSame(root1.left,root2.left) &&
        doesTreeSame(root1.right,root2.right);
    }else{// 根节点不等,肯定不存在
        return false;
    }
}

JZ18 . 二叉树的镜像

题目描述

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

解题思路

本质是互换根节点左右子树的位置。给出当前如何交换根节点左右子树位置的一般解法,至于下一步如何做,和当前的解法是一样的,所以这题就非常的简单,简单理解递归,不用想太复杂。

public void Mirror(TreeNode root) {
    if(root != null){
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        Mirror(root.left);
        Mirror(root.right);
    }
}

JZ19 . 顺时针打印矩阵

题目描述

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下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.

解题思路

顺时针打印,就是从外圈到内圈一层层打印。矩阵的左上角和右下角坐标可以确定一个矩阵的打印范围。打印方法自然是从左到右、从上到下、从右到左、从下到上,这就是完整的一圈。需要注意的是,当这个矩阵只有一行或一列时,从右到左、从下到上就不用打印了。因为从左到右、从上到下已经打印完了。

public static ArrayList<Integer> printMatrix(int [][] matrix) {
    ArrayList<Integer> list = new ArrayList<>();
    int x1,y1,x2,y2;
    x1 = y1= 0;
    x2 = matrix.length-1;
    y2 = matrix[0].length-1;
    while(x1 <= x2 && y1 <= y2) {
        // left to right
        for(int i=y1;i<=y2;i++) {
            list.add(matrix[x1][i]);
        }
        // top to bottom
        for(int i=x1+1;i<=x2;i++) {
            list.add(matrix[i][y2]);
        }
        // right to left
        if(y1 != y2 && x1 != x2) // only one col
            for(int i=y2-1;i>=y1;i--) {
                list.add(matrix[x2][i]);
            }
        // bottom to top
        if(x1 != x2 && y1 != y2) {// only one row
            for(int i=x2-1;i>x1;i--) {
                list.add(matrix[i][y1]);
            }
        }
        x1++;y1++;x2--;y2--;
    }
    return list;
}

JZ20 . 包含 min 函数的栈

题目描述

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

解题思路

常规思路,如果要求一组元素中的最小值,至少要遍历一次才能得到结果,此时的时间复杂度是 O(n),显然不满足 O(1) 的要求。如果要实现 O(1),那么只能用空间换取时间。开辟两个栈的空间,一个是元素正常入栈出栈的空间,称为 normal。一个是存储当前栈中最小元素的空间,称为 min。当 min 栈为空的时候,元素正常进入 min 栈,如果 min 栈不为空且进栈的元素要大于 min 栈栈顶元素,此时栈内最小的元素就是 min 栈顶元素,min 栈顶元素入栈。其他情况下正常进栈即可。

Stack<Integer> normal = new Stack<Integer>(),min = new Stack<Integer>();
public void push(int node) {
    normal.push(node);
    if(!min.isEmpty() && min.peek() < node) {// min 栈不为空且新入栈的元素比栈顶元素小
        min.push(min.peek());
    }else {
        min.push(node);
    }
}

public void pop() {// normal 栈和 min 栈同时弹出
    normal.pop();
    min.pop();
}

public int top() {// 返回 normal 的栈顶元素
    return normal.peek();
}

public int min() {// 返回整个栈的最小元素
    return min.peek();
}

JZ21 . 栈的压入、弹出序列

题目描述

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

解题思路

入栈之后的元素可以立即出栈,也可以不出栈继续让后面的元素入栈,可以用一个栈来模拟这个过程。当一个元素入栈以后,比较它和弹出序列第一个元素的大小,如果相等,说明这个元素入栈后立即出栈了,将此元素弹出,重复这个过程,比较下一个元素。如果不相等,后面的元素继续依次入栈,再进行上面的处理即可。当整个入栈序列遍历完之后,辅助栈是空的,就说明这个弹出序列是可以存在的。

public boolean IsPopOrder(int [] pushA,int [] popA) {
  Stack<Integer> stack = new Stack<Integer>();
      int index = 0;
      for(int i=0;i<pushA.length;i++) {
          stack.push(pushA[i]);
          while(!stack.isEmpty() && popA[index] == stack.peek()) {
              index++;
              stack.pop();
          }
      }
      return stack.isEmpty();
}

JZ22 . 从上往下打印二叉树

题目描述

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

解题思路

从上往下,从左到右,其实就是层次遍历二叉树。层次遍历不同于二叉树的前序、中序、后序遍历,前序、中序、后续是多个相同的子过程叠加得到的结果,而层次遍历是很常规的遍历方式,符合人们的常规思维,先遍历哪个元素就打印哪一个元素,在打印顺序上和队列先进先出的特点非常相似,所以我们可以利用一个队列的辅助空间来层次遍历一颗二叉树。
对于这个队列,如果元素不为空,每次遍历弹出队首打印,如果队首结点有左结点那么左结点先入队,有右结点,右结点后入队,一直重复这个过程直到队列为空的时候,这棵二叉树就层次遍历结束了。

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    ArrayList<Integer> list = new ArrayList<Integer>();
    if(root != null) {
        queue.offer(root);
        while(!queue.isEmpty()) {
            root = queue.poll();
            if(root.left != null) {
                queue.offer(root.left);
            }
            if(root.right != null) {
                queue.offer(root.right);
            }
            list.add(root.val);
        }
    }
    return list;
}

JZ23 . 二叉搜索树的后续遍历序列

题目描述

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

解题思路

后续遍历二叉树的根节点一定在序列末尾,根据二叉搜索树的性质(任意节点的左子树上的值都比该节点值小,右子树的值都比该节点大),可以根据根节点将此序列分为两部分,第一部分所有的值都小于该根节点,第二部分除根节点外所有的值都大于该根节点。根据这两个条件遍历两次,若发现第二部分有节点值小于根节点,返回 false 说明该序列一定不是二叉搜索树的后序遍历结果。上面的策略是一个完美的递归模型。

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

public boolean dfs(int[] sequence,int first,int last) {
    if(last - first < 1) // 序列遍历完了,first 与 last 重合
        return true;

    int index = first;
    int lastVal = sequence[last];
    // 遍历第一部分
    for(;index < last && sequence[index]<lastVal;index++);
    // 遍历第二部分
    for(int i=index;i < last;i++) {
        if(sequence[i]<lastVal) {
            return false;
        }
    }
    // 递归执行子过程
    return dfs(sequence, first, index-1) && dfs(sequence, index, last-1);

}

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

题目描述

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

解题思路

本题的意思是找出所有从根节点到某个叶子结点路径和等于给定整数的路径。既然是从根节点出发到叶子结点,那么有多少个叶子结点就有多少条路径,那么如何从根节点走过所有的路径呢?答案当然是二叉树的前序遍历,每次遍历到一个结点,我们就让target减去当前结点的值,如果target==0并且当前结点是叶子结点(左右结点都为null),说明我们找到了一条路径。

ArrayList<ArrayList<Integer>> pList = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
    if(root == null) {
        return pList;
    }
    target -= root.val;
    list.add(root.val);
    if(target == 0 && root.left == null && root.right == null) {// 找到一条路径
        pList.add(new ArrayList<Integer>(list));
    }
    FindPath(root.left, target, sum, list, pList);
    FindPath(root.right, target, sum, list, pList);
    list.remove(list.size()-1);
    return pList;
}

JZ25 . 复杂链表的复制

题目描述

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

解题思路

public RandomListNode Clone(RandomListNode pHead){
    if(pHead == null)
        return null;
    RandomListNode cur = pHead;

    // 在原链表的每个结点后面加入一个新节点,即复制所有结点过程
    while(cur != null){
        RandomListNode clone = new RandomListNode(cur.label);
        clone.next = cur.next;
        cur.next = clone;
        cur = clone.next;
    }

    // 为复制的所有结点的 random 赋值
    cur = pHead;
    while(cur != null){
        RandomListNode clone = cur.next;
        if(cur.random != null){
            clone.random = cur.random.next;
        }
        cur = clone.next;
    }

    // 将复制的链表拆分出来
    cur = pHead;
    RandomListNode resHeadNode = pHead.next;
    while(cur.next != null){
        RandomListNode next = cur.next;
        cur.next = next.next;
        cur = next;
    }
    return resHeadNode;
}

JZ26 . 二叉搜索树与双向链表

题目描述

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

解题思路

TreeNode pre = null;
public TreeNode Convert(TreeNode pRootOfTree) {
    if(pRootOfTree == null)
        return null;
    Convert(pRootOfTree.right);
    if(pre != null){
        pRootOfTree.right = pre;
        pre.left = pRootOfTree;
    }
    pre = pRootOfTree;
    Convert(pRootOfTree.left);
    return pre;
}

JZ27 . 字符串的排列

题目描述

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

输入描述

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

解题思路

ArrayList<String> res = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
public ArrayList<String> Permutation(String str) {
       if(str == null || str.length() == 0)
           return res;
       char[] cArr = str.toCharArray();
       Arrays.sort(cArr);
       int[] flag = new int[cArr.length];
       dfs(cArr,flag,0);
       return res;
}

public void dfs(char[] cArr, int[] flag, int step) {
    if(step == cArr.length && !res.contains(sb.toString())) {
        res.add(sb.toString());
        return ;
    }
    for(int i=0;i<cArr.length;i++) {
        if(flag[i] == 0) {
            sb.append(cArr[i]);
            flag[i] = 1;
            dfs(cArr, flag, step+1);
            flag[i] = 0;
            sb.deleteCharAt(step);
        }
    }
}

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

题目描述

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

解题思路

public int MoreThanHalfNum_Solution(int [] array) {
    HashMap<Integer,Integer> hashMap = new HashMap<Integer, Integer>();
    int len = array.length;
    for(int i=0;i<len;i++) {
        if(hashMap.containsKey(array[i]))
            hashMap.put(array[i], hashMap.get(array[i])+1);
        else
            hashMap.put(array[i], 1);
    }
    for(int i=0;i<len;i++) {
        if(hashMap.get(array[i]) > len / 2)
            return array[i];
    }
    return 0;
}

JZ29 . 最小的 K 个数

题目描述

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

解题思路

本题很容易想到先对元素排序然后取前 K 个数就可以得到答案,用不同的排序算法,时间复杂度也不同。然而这题我并不打算用这种方法,相信出题者的本意也并不是让我们使用排序后得到结果。下面我利用堆这种结构解决了这个问题,维护一个大小为 K 的大根堆,将不在堆中的元素与堆顶点元素比较大小,如果待入队元素比堆顶点元素小,两数交换。对剩余元素继续与堆顶点元素比较,遍历结束之后,整个大根堆就是要找的最小的 K 个数。

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    ArrayList<Integer> res = new ArrayList<>();
    if(input == null || input.length == 0 || k > input.length || k == 0){
        return res;
    }
    int[] maxHeap = new int[k];
    for(int i=0;i<k;i++){
        maxHeap[i] = input[i];
    }
    // 调整为大根堆
    for(int i=1;i<k;i++){
        heapInsert(maxHeap,i);
    }

    for(int i=k;i<input.length;i++){
        if(input[i] < maxHeap[0]){
            maxHeap[0] = input[i];
            // 元素交换后要重新调整为大根堆
            heapfiy(maxHeap,0,k);
        }
    }
    for(int i=0;i<k;i++){
        res.add(maxHeap[i]);
    }
    return res;
}

public void heapfiy(int[] arr,int index,int size){
    while((2*index+1) < size){
        int left = 2*index+1;
        int right = left+1;
        int max = right > size && arr[right] < arr[left] ?  right : left;
        if(arr[max] < arr[index]){
            break;
        }
        swap(arr,max,index);
        index = max;
    }
}

public void heapInsert(int[] arr,int i){
    while(arr[i] > arr[(i-1)/2] && i > 0){
        swap(arr,i,(i-1)/2);
        i = (i-1)/2;
    }
}

public void swap(int[] arr,int i,int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

JZ30 . 连续子数组的最大和

题目描述

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

解题思路

public int FindGreatestSumOfSubArray(int[] array) {
    if(array == null || array.length == 0)
        return 0;
    int len = array.length;
    int[] dp = new int[len];    //记录以每个数字结尾的子数组最大和
    int res = dp[0] = array[0];
    for(int i=1;i<len;i++) {
        dp[i] = Math.max(array[i], dp[i-1]+array[i]);
        res = Math.max(res, dp[i]);
    }
    return res;
}

JZ31 . 整数中1出现的次数(从1到n整数中1出现的次数)

题目描述

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

解题思路

这道题其实属于一道数学归纳和找规律的问题。详细的解析可以参考
从1到n整数中1出现的次数

public int NumberOf1Between1AndN_Solution(int n) {
    int cnt = 0;
    int times = 1,cur = n % 10,low = 0,high = n / 10;
    while(high != 0 || cur != 0) {
        if(cur == 0) {
            cnt += high * times;
        }else if(cur == 1) {
            cnt += high * times + low + 1;
        }else {
            cnt += (high+1)*times;
        }
        low += cur * times;
        cur = high % 10;
        high /= 10;
        times *= 10;
    }
    return cnt;
}

JZ32 . 把数组排成最小的数

题目描述

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

解题思路

贪心问题,这里的贪心策略是:两个数拼接起来比较拼接之后数的大小,每个数可以在左边,也可以在右边。取拼接之后更小的那个数,那么这两个数的相对顺序与拼接之后更小数的顺序一致。

public String PrintMinNumber(int [] numbers) {
    if(numbers == null || numbers.length == 0){
        return "";
    }
    String[] nums = new String[numbers.length];
    for(int i=0;i<numbers.length;i++){
        nums[i] = numbers[i] + "";
    }
    Arrays.sort(nums,new Comparator<String>(){
        public int compare(String o1,String o2){
            return (o1+o2).compareTo(o2+o1);
        }
    });
    String ret = "";
    for(int i=0;i<nums.length;i++){
        ret += nums[i];
    }
    return ret;
}

JZ33 . 丑数

题目描述

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

解题思路

public int GetUglyNumber_Solution(int index) {
    if(index <= 6)
        return index;

    int i2=0,i3 = 0,i5=0;
    int[] dp = new int[index];
    dp[0] = 1;

    for(int i=1;i<index;i++) {
        dp[i] = Math.min(dp[i2]*2, Math.min(dp[i3]*3, dp[i5]*5));
        if(dp[i] == dp[i2]*2)
            i2++;
        if(dp[i] == dp[i3]*3)
            i3++;
        if(dp[i] == dp[i5]*5)
            i5++;
    }

    return dp[index-1];
}

JZ34 . 第一个只出现一次的字符位置

题目描述

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

解题思路

public static int FirstNotRepeatingChar(String str) {
    if(str == null || str.length() ==0)
        return -1;
    char[] cs = str.toCharArray();
    BitSet bsOne = new BitSet();
    BitSet bsTwo = new BitSet();
    for(int i=0;i<cs.length;i++) {
        if(!bsOne.get(cs[i])) {
            bsOne.set(cs[i]);
        }else {
            bsTwo.set(cs[i]);
        }
    }
    for(int i=0;i<cs.length;i++) {
        if(bsOne.get(cs[i]) && !bsTwo.get(cs[i]))
            return i;
    }
    return -1;
}

JZ35 . 数组中的逆序对

题目描述

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

输入描述

题目保证输入的数组中没有的相同的数字

数据范围:

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2*10^5

解题思路

public int InversePairs(int [] array) {
    int kMod = 1000000007;
    int[] help;
    int ret = 0;
    public int InversePairs(int [] array) {
        if(array == null || array.length == 0)
            return 0;
            help = new int[array.length];
        mergeSort(array,help,0,array.length-1);
        return ret;
    }

    public void mergeSort(int[] arr,int[] help,int left,int right){
        if(left < right){
            int mid = left + ((right-left)>>1);
            mergeSort(arr,help,left,mid);
            mergeSort(arr,help,mid+1,right);
            merge(arr,help,left,mid,right);
        }
    }

    public void merge(int[] arr,int[] help,int left,int mid,int right){
        int p1,p2,index;
        index = p1 = left;
        p2 = mid+1;
        while(p1 <= mid && p2 <= right){
            if(arr[p1] > arr[p2]){
                help[index++] = arr[p2++];
                ret += (mid-p1+1);
                ret %= kMod;
            }else{
                help[index++] = arr[p1++];
            }
        }
        while(p1 <= mid){
            help[index++] = arr[p1++];
        }
        while(p2 <= right){
            help[index++] = arr[p2++];
        }
        for(int i=left;i<=right;i++){
            arr[i] = help[i];
        }
    }
}

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

题目描述

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

解题思路

题目抽象:给定两个单链表A,B,假设一定含有公共结点,返回第一个公共结点的指针。

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    ListNode p1,p2;
    p1 = pHead1;
    p2 = pHead2;
    while(p1 != p2){
        p1 = p1 == null ? pHead2 : p1.next;
        p2 = p2 == null ? pHead1 : p2.next;
    }
    return p1;
}

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

题目描述

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

解题思路

public int GetNumberOfK(int [] array , int k) {
   int len = array.length;
   int l=0,r=len;
   int lBound,rBound;

   // 左边界 <= k
   while(l < r) {
       int mid = l + ((r-l) >> 1);
       if(array[mid] >= k) {
           r = mid;
       }else {
           l = mid + 1;
       }
   }
   lBound = l;
   // 右边界 > k
   l=0;r=len;
   while(l < r) {
       int mid = l + ((r-l) >> 1);
       if(array[mid] > k) {
           r = mid;
       }else {
           l = mid + 1;
       }
   }
   rBound = r;
   return rBound - lBound;
}

JZ38 . 二叉树的深度

题目描述

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

解题思路

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

JZ39 . 平衡二叉树

题目描述

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

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

解题思路

判断一个数是否为平衡二叉树。平衡二叉树是左子树的高度与右子树的高度差的绝对值小于等于1,同样左子树是平衡二叉树,右子树为平衡二叉树。根据定义,如果我们能够求出以每个结点为根的树的高度,然后再根据左右子树高度差绝对值小于等于1,,就可以判断以每个结点为根的树是否满足定义

boolean isBalanced = true;

public boolean IsBalanced_Solution(TreeNode root) {
    height(root);
    return isBalanced;
}

private int height(TreeNode root) {
    if(root == null)
        return 0;
    int left = height(root.left);
    int right = height(root.right);
    if(Math.abs(left-right)>1)
        isBalanced = false;
    return 1 + Math.max(left, right);
}

JZ40 . 数组中只出现一次的数字

题目描述

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

解题思路

// BitSet 解法
int num = 0;
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
    BitSet bsOne = new BitSet();
    BitSet bsTwo = new BitSet();
    for(int i=0;i<array.length;i++){
        if(!bsOne.get(array[i])){
            bsOne.set(array[i]);
        }else{
            bsTwo.set(array[i]);
        }
    }
    for(int i=0;i<array.length;i++){
        if(bsOne.get(array[i]) && !bsTwo.get(array[i])){
            if(num == 0){
                num1[0] = array[i];
                num++;
            }else{
                num2[0] = array[i];
            }
        }
    }
}

// 位运算, 异或运算解法
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
    int num = 0;
    for(int i:array) {//所有数字异或
        num ^= i;
    }

    //找到第一个为1的标志位
    int index = 0;
    for(;;index++)
        if((num&(1<<index)) != 0)
            break;

    for(int i:array) {
        if((i&(1<<index)) == 0)//标志位为0的组
            num1[0] ^= i;
        else    //标志位为1的组
            num2[0] ^= i;
    }
}

JZ41 . 和为S的连续正数序列

题目描述

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

输出描述

输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序

解题思路

滑动窗口

public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
   //存放结果
    ArrayList<ArrayList<Integer> > result = new ArrayList<>();
    //两个起点,相当于动态窗口的两边,根据其窗口内的值的和来确定窗口的位置和大小
    int plow = 1,phigh = 2;
    int cur = plow + phigh;
    while(phigh > plow){
        //相等,那么就将窗口范围的所有数添加进结果集
        if(cur == sum){
            ArrayList<Integer> list = new ArrayList<>();
            for(int i=plow;i<=phigh;i++){
                list.add(i);
            }
            result.add(list);
            cur -= (plow++);
        //如果当前窗口内的值之和小于sum,那么右边窗口右移一下
        }else if(cur < sum){
            cur += (++phigh);
        }else{
        //如果当前窗口内的值之和大于sum,那么左边窗口右移一下
            cur -= (plow++);
        }
    }
    return result;
}

JZ42 . 和为S的两个数字

题目描述

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

输出描述

对应每个测试案例,输出两个数,小的先输出。

解题思路

双指针

public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
    ArrayList<Integer> list = new ArrayList<>();
    if(array == null || array.length <= 1){
        return list;
    }
    int l = 0,r = array.length-1;
    int cur = 0;
    while(l < r){
        cur = array[l] + array[r];
        if(cur == sum){
            list.add(array[l]);
            list.add(array[r]);
            break;
        }else if(cur > sum){
            r--;
        }else{
            l++;
        }
    }
    return list;
}

JZ43 . 左旋转字符串

题目描述

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

解题思路

// 使用库函数,字符串截取
public String LeftRotateString(String str,int n) {
    if(str == null || n <= 0 || n > str.length())
        return str;
    String str1 = str.substring(n);
    String str2 = str.substring(0,n);
    return str1 + str2;
}

// 自己实现一个类似的库函数
public String LeftRotateString(String str,int n) {
    if(str == null || n <= 0 || n > str.length())
        return str;
    int len = str.length();
    char[] origin = str.toCharArray();
    char[] dist = new char[len];
    int i = n,j = 0;
    for (; i<len; i++,j++)
        dist[j] = origin[i];
    for (i=0; i<n; i++,j++)
        dist[j] = origin[i];
    return String.valueOf(dist);
}

JZ44 . 翻转单词顺序列

题目描述

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

解题思路

public String ReverseSentence(String str) {
    if(str == null || str.length() <= 1)
        return str;
    String[] words = str.split(" ");
    int len = words.length;
    int l = 0,r = len-1;
    while(l < r) {
        swap(words,l++,r--);
    }
    String ret = "";
    for(int i=0; i<len;i++) {
        ret += i == len - 1 ? words[i] : words[i] + " ";
    }
    return ret.isEmpty() ? str : ret;
}

public void swap(String[] arr,int l,int r) {
    String word = arr[l];
    arr[l] = arr[r];
    arr[r] = word;
}

JZ45 . 扑克牌顺子

题目描述

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(排除空vector),包含0-13的数组,判断公差是否为1.

public boolean isContinuous(int [] numbers) {
    if(numbers == null || numbers.length == 0)
        return false;
    BitSet bs = new BitSet();
    int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    for(int i=0;i<numbers.length;i++) {
        if(numbers[i] > 0) {
            if(bs.get(numbers[i])) {
                return false;
            }else {
                bs.set(numbers[i]);
                max = Math.max(max, numbers[i]);
                min = Math.min(min, numbers[i]);
            }
        }
    }
    return max - min < 5;
}

JZ46 . 孩子们的游戏(圆圈中最后剩下的数)

题目描述

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

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


解题思路

链表

// 使用链表,模拟这个过程。时间复杂度 O(n^2),空间复杂度 O(n)
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.offer(i);
    }
    int index = 0;
    while(n > 1) {
        index = (index+m-1)%n;
        list.remove(index);
        n--;
    }
    return list.getFirst();
}

JZ47 . 求1+2+3+...+n

题目描述

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

解题思路

递归,位运算

public int Sum_Solution(int n) {
    boolean b =  (n > 1) && ((n += Sum_Solution(n-1)) > 0);
    return n;
}

JZ48 . 不用加减乘除做加法

题目描述

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

解题思路

位运算

public int Add(int num1,int num2) {
    int next, cur;
    do{
        // 进位
        next = (num1 & num2) << 1;
        // 按位和
        cur = num1 ^ num2;
        num1 = next;
        num2 = cur;
    }while(num1 != 0);
    return cur;
}

JZ49 . 把字符串转换成整数

题目描述

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

输入描述:

输入一个字符串,包括数字字母符号,可以为空

输出描述:

如果是合法的数值表达则返回该数字,否则返回0

解题思路


JZ50 . 数组中重复的数字

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中第一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
返回描述:
如果数组中有重复的数字,函数返回true,否则返回false。
如果数组中有重复的数字,把重复的数字放到参数duplication[0]中。(ps:duplication已经初始化,可以直接赋值使用。)

解题思路

去重类的题目,BitSet 非常好用。

public boolean duplicate(int numbers[],int length,int [] duplication) {
    if(numbers == null || length == 0)
        return false;
    BitSet bs = new BitSet();
    for(int i=0;i<length;i++) {
        if(!bs.get(numbers[i])) {
            bs.set(numbers[i]);
        }else {
            duplication[0] = numbers[i];
            return true;
        }
    }
    return false;
}

JZ51 . 构建乘积数组

题目描述

给定一个数组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无意义,故而无法构建,因此该情况不会存在。

解题思路

public int[] multiply(int[] A) {
    int n = A.length;
    int[] B = new int[n];

    for(int i=0,product=1;i<n;product *= A[i],i++) {//从左往右累乘
        B[i] = product;
    }

    for(int i=n-1,product=1;i>=0;product *= A[i],i--) {//从右往左累乘
        B[i] *= product;
    }

    return B;
}

JZ52 . 正则表达式匹配

题目描述

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

解题思路


JZ53 . 表示数值的字符串

题目描述

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

解题思路

参考《剑指 Offer》 题解。这里不使用有限状态自动机,实现太过复杂。

int index;
int size;
public boolean isNumeric(char[] str) {
    if(str == null || str.length == 0)
        return false;
    size = str.length;
    if(str[0] == ' ')
        index++;
    boolean numeric = scanUnsignedInteger(str);    // 扫描整数
    if(index < size && str[index] == '.') {    // 扫描小数
        index++;
        numeric = scanInteger(str) || numeric;
    }
    if(index < size && (str[index] == 'E' || str[index] == 'e')) {    // 扫描指数
        index++;
        numeric = scanUnsignedInteger(str) && numeric;
    }
    if(index < size && str[index] == ' ')
        index++;
    return numeric && (index == size);
}

private boolean scanUnsignedInteger(char[] str) {
    if(index < size && (str[index] == '+' || str[index] == '-'))
        index++;
    return scanInteger(str);
}

private boolean scanInteger(char[] str) {
    int pre = index;
    while(index < size && str[index] >= '0' && str[index] <= '9')
        index++;
    return pre < index;
}

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

题目描述

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

解题思路

题目抽象:每个字符依次进入队列,保证这个队列里面没有重复的字符,返回队首。

返回值描述

如果当前字符流没有存在出现一次的字符,返回#字符。

LinkedList<Character> queue = new LinkedList<Character>();

public void Insert(Character ch){
    if(queue.contains(ch)) {
        queue.remove(ch);
    }else {
        queue.offer(ch);
    }
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce(){
    return queue.isEmpty() ? '#' : queue.peek();
}

JZ55 . 链表中环的入口结点

题目描述

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

解题思路

链表有环,说明有两个结点的 next 指针指向同一个结点,用 HashSet 找到这个结点就可以了。

public ListNode EntryNodeOfLoop(ListNode pHead){
    HashSet<ListNode> hs = new HashSet();
    while(pHead != null){
        if(hs.contains(pHead))
            return pHead;
        hs.add(pHead);
        pHead = pHead.next;
    }
    return pHead;
}

JZ56 . 删除链表中重复的结点

题目描述

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

解题思路

public ListNode deleteDuplication(ListNode pHead){
    ListNode vHead, pre, cur;
    vHead = new ListNode(-1);
    vHead.next = cur = pHead;
    pre = vHead;
    while(cur != null){
        if(cur.next != null && cur.val == cur.next.val){
            cur = cur.next;
            while(cur.next != null && cur.val == cur.next.val){
                cur = cur.next;
            }
            cur = cur.next;
            pre.next = cur;
        }else{
            pre = cur;
            cur = cur.next;
        }
    }
    return vHead.next;
}

JZ57 . 二叉树的下一个结点

题目描述

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

解题思路

因为是中序遍历,所以遍历序列遵循左根右的规律。

public TreeLinkNode GetNext(TreeLinkNode pNode){
    if(pNode == null){
        return null;
    }

    if(pNode.right != null){
        pNode = pNode.right;
        while(pNode.left != null){
            pNode = pNode.left;
        }
        return pNode;
    }else{
        TreeLinkNode parent = pNode.next;
        while(parent != null && parent.left != pNode){
            pNode = parent;
            parent = pNode.next;
        }
        return parent;
    }
}

JZ58 . 对称的二叉树

题目描述

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

解题思路

boolean isSymmetrical(TreeNode pRoot) {
    if (pRoot == null)
        return true;
    return isSymmetrical(pRoot.left, pRoot.right);
}

boolean isSymmetrical(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null)
        return true;
    if (t1 == null || t2 == null)
        return false;
    if (t1.val != t2.val)
        return false;
    return isSymmetrical(t1.left, t2.right) && isSymmetrical(t1.right, t2.left);
}

JZ59 . 按之字形顺序打印二叉树

题目描述

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

解题思路


JZ60 . 把二叉树打印成多行

题目描述

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

解题思路


JZ61 . 序列化二叉树

题目描述

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

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

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

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

解题思路

下面代码采用前序遍历的方式去序列化一颗二叉树,还是递归的方式。只要掌握了二叉树的三种遍历方式,那么序列化便是一种很简单的事情。至于反序列化其实和序列化的方式是一样的。如何序列化的,那么如何反序列就行了。上面借助一个队列存储了这颗二叉树的前序遍历序列。反序列化的时候按照前序遍历的方式一个个结点递归重构就行了。除了前序的方式,还可以用中序、后序的方式。方法都是类似的。

import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    String Serialize(TreeNode root) {
        String res = "";
        if(root == null)
            return res += "#,";
        res += root.val+",";
        res += Serialize(root.left);
        res += Serialize(root.right);
        return res;
  }
    TreeNode Deserialize(String str) {
       String[] values = str.split(",");
        Queue<String> queue = new LinkedList<String>();

        for(int i = 0;i<values.length;i++) {
            queue.offer(values[i]);
        }

        return reconBypreString(queue);
  }
    TreeNode reconBypreString(Queue<String> queue) {
        String val = queue.poll();
        if(val.equals("#"))
            return null;
        TreeNode head = new TreeNode(Integer.valueOf(val));
        head.left = reconBypreString(queue);
        head.right = reconBypreString(queue);
        return head;
    }
}

JZ62 . 二叉搜索树的第k个结点

题目描述

给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
解题思路

我们知道,二叉搜索树的中序遍历结果是递增的。所以很容易想到通过中序遍历来找到第 K 小的结点。上面的代码使用递归的方式实现中序遍历,一旦 cnt == k 这个条件成立,这个结点就是我们要的结点。

public class Solution {
    private int cnt = 0;
    private TreeNode res;
    TreeNode KthNode(TreeNode pRoot, int k)
    {
       inOrder(pRoot, k);
       return res;
    }

    public void inOrder(TreeNode pRoot, int k){
        if(pRoot == null){
            return ;
        }
        inOrder(pRoot.left, k);
        if(++cnt == k)
            res = pRoot;
        inOrder(pRoot.right, k);
    }
}
正文到此结束
本文目录