剑指Offer

剑指Offer

1、二维数组中的查找(1)

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

解题思路:

首先是有序的数组,马上就能想到可能需要用到二分查找,因为二分查找的时间复杂度是O(logn).那么大概就是遍历每个一维数组,每个二维数组采用二分查找

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

//利用数组特点
public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array.length <= 0) return false;
        if(array[0].length <= 0) return false;
        //从右上角开始查找
        int row = 0;
        int col = array[0].length - 1;
        while(col >= 0 && row < array.length) {
            if(target < array[row][col]) {
                col--;
            } else if(target > array[row][col]) {
                row++;
            } else {
                return true;
            }
        }
        return false;
    }
}

2、替换空格(1)

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

解题思路:

首先,通过indexOf不断获取空格index,然后替换找到index的位置为%20, 直到所有的空格被找完为止,没有空格返回index为-1

public class Solution {
    public String replaceSpace(StringBuffer str) {
        int index = str.indexOf(" ");
        while(index != -1) {
            str.replace(index, index + 1, "%20");//替换指定index的字符为%20
            index = str.indexOf(" ");//继续往下找对应空格的index
        }
        return str.toString();
    }
}

3、从尾到头打印链表(1)

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

解题思路:

实际上就是转化为链表反转问题,最后再遍历翻转后的链表即可

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode){
        ArrayList<Integer> dataList = new ArrayList<Integer>();
        ListNode prev = null;//逆序链表的头指针
        ListNode current = listNode;
        ListNode next = listNode;
        while(current != null) {
            next = current.next;//先指向当前结点下一个结点,不然断开当前结点无法继续指向下一个结点
            current.next = prev;
            prev = current;
            current = next;
        }
        while(prev != null) {
            dataList.add(prev.val);
            prev = prev.next;
        }         
        return dataList;
    }
}

4、二分查找(1)

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示:

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

解题思路:

就是很直接的二分查找题目

//递归实现
class Solution {
    public int search(int[] nums, int target) {
        return binarySearchWithRecursion(nums, 0, nums.length - 1, target);
    }

    public int binarySearchWithRecursion(int[] nums, int low, int high, int target){
        if(low > high){
            return -1;
        }

        int mid = (low + high) >>> 1;
        if(target == nums[mid]) return mid;
        if(target > nums[mid]){
            return binarySearchWithRecursion(nums, mid + 1, high, target);
        }else{
            return binarySearchWithRecursion(nums, low, mid - 1, target);
        }
    }
}

//递推实现
class Solution {
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while(low <= high) {
            int mid = (low + high) >>> 1;
            if(target > nums[mid]) {
                low = mid + 1;
            } else if(target < nums[mid]) {
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

5、有效的完全平方数(1)

给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。

说明:不要使用任何内置的库函数,如 sqrt。

示例 1:

输入:16
输出:True
示例 2:

输入:14
输出:False

解题思路:

完全平方数有一个结论 一个非负数n平方根小于 n/2 + 1, 所以可转化成二分查找在0~n/2 + 1范围查找平方根的值。只需要将查找的值取平方值然后和目标数值比较,相等就说明找到了。但是需要注意int溢出,所以建议使用long.

class Solution {
    public boolean isPerfectSquare(int num) {
        long low = 0;
        long high = num / 2 + 1;//一个非负数n平方根小于 n/2 + 1
        while(low <= high) {
            long mid = (low + high) >>> 1;
            long sqrtResult = mid * mid;
            if(num > sqrtResult) {
                low = mid + 1;
            } else if(num < sqrtResult) {
                high = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

6、两数之和 II - 输入有序数组(1)

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。

说明:

返回的下标值(index1 和 index2)不是从零开始的。
你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。
示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

解题思路:

首先,可以看到是升序的有序数组,可能就需要想到二分查找;然后题目求两个数之和是否等于目标数,实际上可以转换成依次遍历原数组元素,然后在数组后面的元素中有序查找目标值与当前元素的差值,转换成查找问题。有序查找就是二分查找的问题。时间复杂度是(nlogn).

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for(int i = 0; i < numbers.length; i++) {
            int index = binarySearchIndex(numbers, i + 1, target - numbers[i]);
            if(index != -1) {
               return new int[]{i + 1, index + 1}; 
            }
        }
        return new int[]{};
    }
    public int binarySearchIndex(int[] numbers, int startIndex, int target) {
        int low = startIndex;
        int high = numbers.length - 1;
        while(low <= high) {
            int mid = (low + high) >>> 1;  
            if(target > numbers[mid]) {
                low = mid + 1;
            } else if(target < numbers[mid]) {
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;        
    }
}

7、x的平方根(1)

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数,小数部分将被舍去。

解题思路:

还是利用一个非负数n的平方根小于 n/2 + 1 结论,转换成二分查找。但是需要注意的一点就是如果low>high指针就是时候需要返回值,这是没找到的情况,注意下取整,所以取high,以为high肯定比low小,取low就是上取整;还需要注意溢出情况。

class Solution {
    public int mySqrt(int x) {
        long low = 0;
        long high = x / 2 + 1;
        while(low <= high) {
            long mid = (low + high) >>> 1;
            long result = mid * mid;
            if(x > result) {
                low = mid + 1;
            } else if(x < result) {
                high = mid - 1;
            } else {
                return (int)mid;
            }
        }
        return (int)high;
    }
}

8、搜索插入位置(1)

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1
示例 3:

输入: [1,3,5,6], 7
输出: 4
示例 4:

输入: [1,3,5,6], 0
输出: 0

解题思路:

有序数组还是转化到二分查找,但是如果没有找到的时候,此时的low > high, 看是否需要返回low还是high很明显是low,返回它按照顺序的插入的位置。而是位于当前目标数之后的位置。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            if(target > nums[mid]) {
                low = mid + 1;
            } else if(target < nums[mid]) {
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return low;
    }
}

9、山脉数组的峰顶索引(1)

我们把符合下列属性的数组 A 称作山脉:

A.length >= 3
存在 0 < i < A.length - 1 使得A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1]
给定一个确定为山脉的数组,返回任何满足 A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1] 的 i 的值。

示例 1:

输入:[0,1,0]
输出:1
示例 2:

输入:[0,2,1,0]
输出:1

提示:

3 <= A.length <= 10000
0 <= A[i] <= 10^6
A 是如上定义的山脉

解题思路:

首先,需要明白峰顶的概念,以峰顶为界,一边是顺序递增一边顺序递减,所以将它进行二分查找,但是需要注意的是峰顶的位置一定是low和high相遇的时候找到的。

然后,如果每次mid位置的数比mid+1数大,说明峰顶肯定在前半部分,并且mid+1这个位置mid+1肯定不是峰顶,但是mid有可能是峰顶。所以调整high指针,high = mid;

然后,如果每次mid位置的数比mid+1数小,说明峰顶的肯定在后半部分,并且mid+1有可能是峰顶,但是mid肯定不是峰顶,所以调整low指针,low=mid+1

最后,low和high相遇肯定就是峰顶了。

class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int low = 0;
        int high = A.length - 1;
        while(low < high) {
            int mid = (low + high) >>> 1;
            if(A[mid] > A[mid + 1]) {
                high = mid;
            }
            if(A[mid] < A[mid + 1]) {
                low = mid + 1;
            }
        }
        return low;
    }
}

10、两个数组的交集 II(1)

给定两个数组,编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明:

输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
进阶:

如果给定的数组已经排好序呢?你将如何优化你的算法?
如果 nums1 的大小比 nums2 小很多,哪种方法更优?
如果 nums2 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?

解题思路:

首先,先把两个集合升序排列,然后利用i,j双指针遍历数组的形式,如果num1[i] < num2[j], i++; 如果num1[i] > num2[j], j++; 否则就是num1[i] == num2[j] ,i++和j++.然后把当前元素加入到一个新集合中。最后得到的就是交集了。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if(nums1.length == 0 || nums2.length == 0) {
            return new int[]{};
        }
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> results = new ArrayList<Integer>();
        int i = 0, j = 0;
        while(i < nums1.length && j < nums2.length) {
            if(nums1[i] < nums2[j]) {
                i++;
            } else if(nums1[i] > nums2[j]){
                j++;
            } else {
                results.add(nums1[i]);
                i++;
                j++;
            }
        }

        //下面主要是将List<Integer>转化成int[]
        int[] resultsArray = new int[results.size()];
        int k = 0;
        while(k < results.size()) {
            resultsArray[k] = results.get(k);
            k++;
        }
        return resultsArray;
    }
}

11、两个数组的交集(1)

给定两个数组,编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]
说明:

输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

解题思路:

相比上面交集题目,唯一不同的一点就是每个元素是唯一的,就是不存在重复的元素,所以存取交集的集合应该为Set集合。然后其他的同理。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1.length == 0 || nums2.length == 0) {
            return new int[]{};
        }
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        Set<Integer> results = new HashSet<Integer>();
        int i = 0, j = 0;
        while(i < nums1.length && j < nums2.length) {
            if(nums1[i] < nums2[j]) {
                i++;
            } else if(nums1[i] > nums2[j]){
                j++;
            } else {
                results.add(nums1[i]);
                i++;
                j++;
            }
        }
        int[] resultsArray = new int[results.size()];
        int k = 0;
        for (Integer result : results) {
            resultsArray[k++] = result;
        }
        return resultsArray;
    }
}

12、猜数字大小(1)

我们正在玩一个猜数字游戏。 游戏规则如下:
我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。
每次你猜错了,我会告诉你这个数字是大了还是小了。
你调用一个预先定义好的接口 guess(int num),它会返回 3 个可能的结果(-1,1 或 0):

-1 : 我的数字比较小
1 : 我的数字比较大
0 : 恭喜!你猜对了!
示例 :

输入: n = 10, pick = 6
输出: 6

解题思路:

首先,需要理解题目意思,guess函数是外部提供好的,所以只需要传入一个num它会返回-1,1,0实际上就是判断目标数字是大了还是小了,以便于动态调整low,high指针,此外1~n隐藏着是升序的。还需要注意: “我的数字比较小”,意思是对应的是我们猜的那个数字大了,需要调整high = mid - 1; “我的数字比较大”,意思是我们猜的那个数字小了,需要调整low = mid + 1;

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int low = 1;
        int high = n;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            if(guess(mid) == -1) {//说明我们猜大了,调整high
               high = mid - 1;
            } else if(guess(mid) == 1) {//说明我们猜小了,调整low
               low = mid + 1;
            } else if(guess(mid) == 0) {//猜对了
               return mid;
            }
        }
        return -1;
    }
}

13、一个错误的版本(1)

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5,并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以,4 是第一个错误的版本。

解题思路:

其实这个题目有点类似于山峰那道题,第一个错误版本一定存在,而且一定是low和high相等的时候,需要分析下,如果当前mid不是错误版本,那么错误版本肯定不在前半部分,所以需要调整low,但是需要注意low=mid+1,因为mid+1可能就是第一错误版本,所以low = mid + 1;如果当前mid是错误版本,但是第一个错误的版本肯定不在后面,需要调整high, 由于当前mid可能是第一个错误版本,所以high = mid而不是mid - 1

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int low = 1;
        int high = n;
        while(low < high) {
            int mid = (low + high) >>> 1;
            if(isBadVersion(mid)){
                high = mid;//如果mid是错误版本,第一个错误的版本肯定不在mid后面,需要调整high, 由于当前mid可能是第一个错误版本,所以high = mid 
            } else {
                low = mid + 1;//如果当前mid不是错误版本,那么错误版本肯定不在前半部分,所以需要调整low,但是需要注意low=mid+1,因为mid+1可能就是第一错误版本
            }
        }
        return high;
    }
}

14、寻找比目标字母大的最小字母(1)

给定一个只包含小写字母的有序数组letters 和一个目标字母 target,寻找有序数组里面比目标字母大的最小字母。

数组里字母的顺序是循环的。举个例子,如果目标字母target = ‘z’ 并且有序数组为 letters = [‘a’, ‘b’],则答案返回 ‘a’。

示例:

输入:
letters = [“c”, “f”, “j”]
target = “a”
输出: “c”

输入:
letters = [“c”, “f”, “j”]
target = “c”
输出: “f”

输入:
letters = [“c”, “f”, “j”]
target = “d”
输出: “f”

输入:
letters = [“c”, “f”, “j”]
target = “g”
输出: “j”

输入:
letters = [“c”, “f”, “j”]
target = “j”
输出: “c”

输入:
letters = [“c”, “f”, “j”]
target = “k”
输出: “c”
注:

letters长度范围在[2, 10000]区间内。
letters 仅由小写字母组成,最少包含两个不同的字母。
目标字母target 是一个小写字母。

解题思路:

首先是有序的数组letters使用二分查找,但是注意这里不是查找目标字母,而是查找比目标字母大的最小字母,换句话说就是查找比目标字母大的升序字符数组中第一次出现的字母, 所以low和high相遇肯定是比目标字母大的最小字母

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int low = 0;
        int high = letters.length - 1;
        //目标字母比最小字母要小以及大于或等于最大字母都返回最小字母
        if(target < letters[low] || target >= letters[high]) {
            return letters[low];
        }
        //注意: 二分查找中,一定存在且找得到,肯定是low和high相等情况下,while条件就是low < high而不是low <= high
        while(low < high) {
            int mid = (low + high) >>> 1;
            if(target >= letters[mid]) {//如果target大于或等于mid对应字母,反过来就是mid对应字母比目标字母小,说明比目标字母大的最小字母在后半部分,所以需要调整low,此外mid+1可能是第一个比目标字母大的字母,符合比目标字母大的最小字母
                low = mid + 1;
            } else {//如果target小于mid对应字母,反过来就是mid对应字母比目标字母大,说明比目标字母大的最小字母在前半部分或当前,所以调整high,但是可能当前mid就是比目标字母大的最小字母,所以high=mid
                high = mid;
            }
        }
        return letters[low];
    }
}

15、排列硬币

你总共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须正好有 k 枚硬币。

给定一个数字 n,找出可形成完整阶梯行的总行数。

n 是一个非负整数,并且在32位有符号整型的范围内。

示例 1:

n = 5

硬币可排列成以下几行:
¤
¤ ¤
¤ ¤

因为第三行不完整,所以返回2.
示例 2:

n = 8

硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

因为第四行不完整,所以返回3.

解题思路:

此题由于对阶梯限制特殊第K行就有K枚硬币,所以第K行一共消耗的硬币数量由等差数列公式可以得到为k(k+1)/2,我们有n枚硬币构建阶梯所需硬币必须小于我们有的即:k(k+1)/2<=n =》k^2+k-2n<=0对于这个以k为自变量的函数,我们要求k能取得的最大值同时满足这个不等式,根据二次函数根k = (sqrt(1+8n) - 1)/2,所以只需要返回(sqrt(1+8n) - 1)/2即可

class Solution {
    fun arrangeCoins(n: Int): Int {
       return ((Math.sqrt(((n.toLong() * 8 + 1).toDouble())) - 1) / 2).toInt()
    }
}

16、删除链表节点

请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。

现有一个链表 – head = [4,5,1,9],它可以表示为:

示例 1:

输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
示例 2:

输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.

说明:

链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。

解题思路:

该题解题思路有点动脑,首先把当前节点的下一个节点node.next的值val赋值给当前节点node的val, 然后实际上就相当于把node.next赋值给node,然后再将node.next指向node.next.next,成功删除了node.next也就间接删除node

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

class Solution {
    public void deleteNode(ListNode node) {
        if(node == null || node.next == null) {
            return;
        }
        node.val = node.next.val;//把当前节点的下一个节点node.next的值val赋值给当前节点node的val
        node.next = node.next.next;//然后再将node.next指向node.next.next
    }
}

17、链表中环的入口节点

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

解题思路:

怎么找到环的入口结点?
首先说方法:两指针相遇后,让一个指针从头结点开始,另一个从相遇结点开始,并以相同速度向后指,再次相遇时就是环的入口结点。

证明:
1)假设存在环,fast以速度2运行,slow以速度1运行,在slow走到入口t时,如图(m1为在slow首次到t时fast的位置,a为h到t的距离,b为t到m1的距离,n为环的周长):

由图知fast走的距离为a+b+xn,slow走的距离为a,又v(fast) = 2*v(slow),所以x(fast) = 2*x(slow),即2a = a+b+xn,因此a = b+xn
m1逆时针到t的距离为n-b

2)在首次相遇时,如图(m2为相遇点):

由于m1逆时针到t的距离为n-b,即要达到相遇需要追赶n-b的距离,由于两者速度差为1,因此需要n-b的时间才能相遇,此时slow再次向后n-b距离,即到达m2位置与fast相遇,因为一周长度为n,因此到t的距离为 n-(n-b) = b

3)为何令slow重新从pHead以速度1开始走,令fast从m2以速度1走?要想在入口t相遇,则需要从m2处再走b+xn的距离,刚好pHead处符合(由1)可知),所以令slow从pHead开始走。在相遇后就是入口t的位置。

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null) return null;
        ListNode fast = pHead;
        ListNode slow = pHead;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;//每次走2步
            slow = slow.next;//每次走1步
            if(slow == fast) {//首次相遇了
                slow = pHead;//slow重新指向pHead,此时slow距离相遇点距离为a=b+xn, 而此时fast离相遇点也正好是b+xn,只需要调整为每次都走1步,两者肯定在相遇点相遇
                while(slow != fast) {
                    fast = fast.next;//fast调整为每次都走1步
                    slow = slow.next;//slow调整为每次都走1步
                }
                return fast;//相遇点就是fast或slow指向的当前结点
            }
        }
        return null;
    }
}

18、反转链表(1)

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解题思路:

链表反转问题

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        ListNode prev = null;
        ListNode current = head;
        ListNode next = head;
        while(current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }
}

19、链表的中间结点

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

示例 1:

输入:[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式:[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意,我们返回了一个 ListNode 类型的对象 ans,这样:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2:

输入:[1,2,3,4,5,6]
输出:此列表中的结点 4 (序列化形式:[4,5,6])
由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。

提示:

给定链表的结点数介于 1 和 100 之间。

解题思路:

很简单就是使用快慢指针追赶问题,fast和low同时从head开始出发,fast的速度是low的两倍,当fast走到终点(即next为null)时,此时的slow指针正好走到链表的一半,此时slow指向的节点就是中间节点。

class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

20、合并两个有序的链表(1)

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

解题思路:

这道题思路主要就是借助了递归的思想,先分析子问题,然后再推广到求全局问题。比较两个链表,假如分析两个链表各有一个节点情况l1和l2,如果l1.val <= l2.val,那么就是 newHead = l1; l1.next = l2即可;如果l1.val > l2.val,那么就是newHead = l2; l2.next = l1; 然后求解全局问题,newHead = l1; l1.next = mergeTwoLists(l1.next, l2); 或 l2.next = mergeTwoLists(l2.next, l1);

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //list1,list2都为null,说明合成也为null
        if(list1 == null && list2 == null) return null;
        //list2为null, 合成后返回就是list1
        if(list2 == null) return list1;
        //list1为null, 合成后返回就是list2
        if(list1 == null) return list2;
        ListNode newHead = null;//新链表的头节点
        if(list1.val <= list2.val) {
            newHead = list1;
            newHead.next = Merge(list1.next, list2);
        } else {
            newHead = list2;
            newHead.next = Merge(list1, list2.next);
        }
        return newHead;
    }
}

21、删除排序链表中的重复元素

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

解题思路:

实际上设置两个指针prev和current, prev指向head, current指向head.next, 然后将prev.val与current.val对比,如果相等,说明存在重复元素,需要略过它所以有: prev.next = current.next;并且移动current = current.next; 如果不相等,就说明不需要删除,只需要把prev移到current位置,然后current移动到下一个结点: current = current.next. 这样就能把重复元素删掉。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return null;
        ListNode prev = head;
        ListNode current = head.next;
        while(current != null) {
            if(prev.val == current.val){
                prev.next = current.next;//绕过当前相同的元素节点
            } else {
                prev = current;
            }
            current = current.next;
        }
        return head;
    }
}

22、移除链表中的元素

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

解题思路:

其实删除当前current结点,是不好操作的,其实有时候我们更希望通过current.next = current.next.next方式删除current.next的结点。所以针对这个道题可以先构造一个头结点ne’wHead。然后就可以通过current.next = current.next.next删除current结点,最后返回newHead.next即可。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) return null;
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        ListNode current = newHead;
        while(current != null) {
            if(current.next != null && val == current.next.val){
               current.next = current.next.next;
            } else {
               current = current.next;
            }
        }
        return newHead.next;
    }
}

23、相交链表

编写一个程序,找到两个单链表相交的起始节点。

如下面的两个链表:

在节点 c1 开始相交。

示例 1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:

输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
解释:这两个链表不相交,因此返回 null。

注意:

如果两个链表没有交点,返回 null.
在返回结果后,两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

解题思路:

这道题主要考虑三个方面,第一边界情况;第二没有相交情况返回null; 第三有相交节点情况,返回相交节点。

针对第二种情况特殊说明下:
如果两个链表没有相交部分,那么分别遍历完毕两个链表A,B直到最后一个节点,如果两个链表最后一个节点都不相等,说明没有相交部分。

针对第三种情况特殊说明下:

如果两个链表有相交部分,求交点部分,假设链表A相交前有m个结点,链表B相交前有n个结点,两链表相交至末尾有k个结点。

指针A链表从头开始向后至A的末尾,然后再指向B链表表头,向后到相交点,总共走了: m+k+n个结点。

同理: 指针B链表从头开始向后至B的末尾,然后再指向A链表表头,向后到相交点,总共走了: n+k+m个结点。

最后发现,这样路径A,B走了相同的路程,又以相同速度,所以必定会在相交点相遇。所以当它们相等时,也就是相遇了,此时指向的结点就是相交结点。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }
        ListNode currentA = headA;
        ListNode currentB = headB;
        while(currentA.next != null){
            currentA = currentA.next;
        }
        while(currentB.next != null){
            currentB = currentB.next;
        }
        if(currentA != currentB){//第二种情况,A,B遍历到最后一个节点,发现都不相等,说明肯定没有相遇。
            return null;
        }
        currentA = headA;
        currentB = headB;
        //直到走到currentA == currentB为止
        while(currentA != currentB){
            //如果currentA走完后就把currentA指向headB继续走
            currentA = currentA.next == null ? headB : currentA.next;
            //如果currentB走完后就把currentB指向headA继续走
            currentB = currentB.next == null ? headA : currentB.next;
        }

        return currentA;//最后返回currentA
    }
}

24、环形链表

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

进阶:

你能用 O(1)(即,常量)内存解决此问题吗?

解题思路:

快慢指针追赶,相遇肯定就有环了

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

25、回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

解题思路:

思路比较清晰,首先通过快慢指针原理找到中间节点middle,然后通过从中间节点开始反转链表后半部分,然后对比前半部分和后半部分是不是一一对应相等。如果是说明就是回文链表了

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        ListNode middleNode = findMiddleNode(head);
        ListNode reverseNode = reverseList(middleNode);
        while(reverseNode != null){
            if(head.val != reverseNode.val){
                return false;
            }
            //同时分别从头和从反转后的中间节点开始遍历,直到遍历后半部分结束,都没有不相等的,最后返回true
            head = head.next;
            reverseNode = reverseNode.next;
        }
        return true;
     }

    public ListNode findMiddleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        ListNode next = head;
        while(current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }
}

26、链表中倒数第k个节点(1)

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

解题思路:

首先,拿到链表的总长度l, 倒数第k个结点,那么顺序就是第 l - k 个结点。然后正序遍历到 l - k时,返回当前结点。

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null) return null;
        int len = 0;
        ListNode current = head;
        while(current != null){
            ++len;
            current = current.next;
        }
        if(k > len) return null;
        int result = len - k;
        current = head;
        while(current != null) {
            if(result == 0) return current;
            --result;
            current = current.next;
        }
        return null;
    }
}

27、复杂链表的复制

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

解题思路:

首先,需要明白题目的意思,完整复制一个新的链表和原来一样。如果只在原链表上操作的话,需要三个步骤:

第一,先复制基本节点,仅对val赋值,暂不对random复制。例如: A -> B -> C 那么就是变成了: A -> A’ -> B -> B’ -> C -> C‘

第二,然后再对第一步中的A’,B’,C’进行random节点复制。例如: A -> A’ -> B -> B’ -> C -> C‘就真正变成了:A -> A -> B -> B -> C -> C

第三,最后就是把A -> A -> B -> B -> C -> C 拆成 A -> B -> C和A -> B -> C

public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead == null) return null;
        cloneBaseNodes(pHead);//A -> B -> C => A -> A' -> B -> B' -> C -> C‘
        cloneRandomPointer(pHead);//A -> A' -> B -> B' -> C -> C‘ =>A -> A -> B -> B -> C -> C
        return splitNewNodes(pHead);//A -> A -> B -> B -> C -> C => A -> B -> C, A -> B -> C
    }
    public void cloneBaseNodes(RandomListNode pHead) {
        RandomListNode currentNode = pHead;
        RandomListNode copyNode = null;
        while(currentNode != null) {
            copyNode = new RandomListNode(currentNode.label);
            copyNode.next = currentNode.next;
            currentNode.next = copyNode;
            currentNode = currentNode.next.next;//表示复制完一对,进行下一对,所以是currentNode.next.next
        }
    }
    public void cloneRandomPointer(RandomListNode pHead) {
        RandomListNode currentNode = pHead;
        RandomListNode copyNode = pHead.next;
        while(currentNode != null) {
            if(currentNode.random != null){
                copyNode.random = currentNode.random.next;
            }
            currentNode = currentNode.next.next;//表示处理完一对,进行下一对
            if(copyNode != null && copyNode.next != null){
                copyNode = copyNode.next.next;
            }
        }
    }
    public RandomListNode splitNewNodes(RandomListNode pHead) {
        RandomListNode newHead = pHead.next;//拆开,复制后链表的头结点。
        RandomListNode currentNode = pHead;
        RandomListNode copyNode = newHead;
        while(currentNode != null) {
            currentNode.next = currentNode.next.next;
            currentNode = currentNode.next;
            if(copyNode != null && copyNode.next != null){
                copyNode.next = copyNode.next.next;
                copyNode = copyNode.next;
            }
        }
        if(copyNode != null){
            copyNode.next = null;
        }
        return newHead;
    }
}

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

输入两个链表,找出它们的第一个公共结点。

解题思路:

本题和相交链表是一个意思,第一个公共结点也就是两个链表相交的第一个节点,如果两个链表有公共结点,那么公共结点出现在两个链表的尾部。所以和相交链表的思路是一致。

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null) return null;
        ListNode current1 = pHead1;
        while(current1.next != null) {
            current1 = current1.next;
        }
        ListNode current2 = pHead2;
        while(current2.next != null) {
            current2 = current2.next;
        }
        if(current1 != current2){
            return null;
        }
        current1 = pHead1;
        current2 = pHead2;
        while(current1 != current2) {
            current1 = (current1.next == null) ? pHead2 : current1.next;
            current2 = (current2.next == null) ? pHead1 : current2.next;
        }
        return current2;
    }
}

29、数组中重复的数字

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

解题思路:

这道题有多种方法,这里先说一种最直观的方法就是采用哈希表,创建一个HashMap, 遍历整个数组,如果以数组值为key的对应元素不在HashMap中,那么就把这个数组值作为key, put到HashMap中,如果存在于HashMap中,说明就出现了重复的数字,直接把这个数赋值给duplication[0],并返回true

    public boolean duplicate(int numbers[], int length, int[] duplication) {
        if (length <= 0 || numbers == null) {
            return false;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if (map.get(numbers[i]) == null) {
                map.put(numbers[i], i);
            } else {
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }

30、用两个栈实现队列(1)

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

解题思路:

路比较简单,栈是具有后进先出的特性,而队列是先进先出的。可以把第一个栈用于存储队列数据,先把数据依次push到Stack1中,然后pop的时候,先把Stack1全部压入Stack2中,此时Stack2栈顶元素也就是队列中队头元素,只需要把Stack2栈顶元素pop即可,最后别忘了把Stack2中的元素全部push回到Stack1中,其实Stack2就是相当于一个中转临时栈作用。

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() {
        while(!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        int result = stack2.pop();
        while(!stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
        return result;
    }
}

31、包含min函数的栈(1)

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

解题思路:

本题主要关键是min函数,需要遍历原数据栈,找到栈中最小值;但是会遇到一个问题就是原数据栈数据如何临时存在,所以需要再借助一个临时栈,先把原始栈中数据遍历pop到临时栈中,比较找到最小值后,再把临时栈中的数据push回到原数据栈中。

import java.util.Stack;

public class Solution {
    Stack<Integer> mDataStack = new Stack<>();
    Stack<Integer> mMinStack = new Stack<>();
    public void push(int node) {
        mDataStack.push(node);
        //若当前min栈为空或者当前node值小于当前min栈栈顶元素的值,就把当前node压入min栈中,否则压入min栈栈顶元素
        if(mMinStack.isEmpty() || node < mMinStack.peek()) {
            mMinStack.push(node);
        } else {
            mMinStack.push(mMinStack.peek());
        }
    }

    public void pop() {
        if(!mDataStack.isEmpty() && !mMinStack.isEmpty()) {
            mDataStack.pop();
            mMinStack.pop();
        }
    }

    public int top() {
        return mDataStack.isEmpty() ? -1 : mDataStack.peek();
    }

    public int min() {
        return mMinStack.isEmpty() ? -1 : mMinStack.peek();
    }
}

32、栈的压入、弹出序列

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

解题思路:

首先,遍历pushA数组,依次将它们压入mStack栈中,遍历过程需要依次和popA数组中数比较,如果相等就把mStack栈中pop,并且移动j++,依次比较popA下一个值,如果j计数等于了popA长度说明此时mStack出栈顺序和popA顺序一致, 也就是push一次就马上对应pop一次,说明肯定是栈弹出序列。还有一种情况就是pushA全部压入完毕, popA中还有元素。只需要依次将mStack的数pop,如果正好等于了popA中元素的顺序,那么肯定是栈弹出序列,否则就不是。

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length <= 0 || popA.length <= 0) return false;
        Stack<Integer> mStack = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushA.length; i++) {
            mStack.push(pushA[i]);
            if(pushA[i] == popA[j]) {
                j++;
                mStack.pop();
                if(j == popA.length) {
                    return true;
                }
            }
        }

        while(!mStack.isEmpty()) {
            if(mStack.pop() != popA[j++]) {
                return false;
            }
        }
        return true;
    }
}

33、棒球比赛

你现在是棒球比赛记录员。
给定一个字符串列表,每个字符串可以是以下四种类型之一:
1.整数(一轮的得分):直接表示您在本轮中获得的积分数。

  1. “+”(一轮的得分):表示本轮获得的得分是前两轮有效 回合得分的总和。
  2. “D”(一轮的得分):表示本轮获得的得分是前一轮有效 回合得分的两倍。
  3. “C”(一个操作,这不是一个回合的分数):表示您获得的最后一个有效 回合的分数是无效的,应该被移除。

每一轮的操作都是永久性的,可能会对前一轮和后一轮产生影响。
你需要返回你在所有回合中得分的总和。

示例 1:

输入: [“5”,”2”,”C”,”D”,”+”]
输出: 30
解释:
第1轮:你可以得到5分。总和是:5。
第2轮:你可以得到2分。总和是:7。
操作1:第2轮的数据无效。总和是:5。
第3轮:你可以得到10分(第2轮的数据已被删除)。总数是:15。
第4轮:你可以得到5 + 10 = 15分。总数是:30。
示例 2:

输入: [“5”,”-2”,”4”,”C”,”D”,”9”,”+”,”+”]
输出: 27
解释:
第1轮:你可以得到5分。总和是:5。
第2轮:你可以得到-2分。总数是:3。
第3轮:你可以得到4分。总和是:7。
操作1:第3轮的数据无效。总数是:3。
第4轮:你可以得到-4分(第三轮的数据已被删除)。总和是:-1。
第5轮:你可以得到9分。总数是:8。
第6轮:你可以得到-4 + 9 = 5分。总数是13。
第7轮:你可以得到9 + 5 = 14分。总数是27。
注意:

输入列表的大小将介于1和1000之间。
列表中的每个整数都将介于-30000和30000之间。

解题思路:

本题难点就是需要将题目意思转化成栈问题,我们从题目意思可以得到每轮比赛的计分都是和前一轮或前两轮有关的,通过前一轮或前两轮计分需要进行特定的规则计算操作后得到本轮的分数,并且还需要保存本轮的计分。因为本轮的计分会影响下一轮的计分,最后栈中保留所有轮有效计分。首先,初始化一个空栈,遍历ops数组,遇到数字就push到栈中,并且累加值到result中,如果是+,获得分数是前两轮总和,并把此轮分数push到栈中,累加到result中,如果是D,获得分数是前一轮分数两倍,并把此轮分数push到栈中,累加到result中,如果是C,栈顶元素分数是无效的,此时需要pop栈顶元素,result必须递减栈顶元素的值。

import java.util.Stack;
class Solution {
    public int calPoints(String[] ops) {
        Stack<Integer> stack = new Stack<>();
        int result = 0;
        for(int i = 0; i < ops.length; i++) {
            String option = ops[i];
            if(option.equals("C")) {
              if(!stack.isEmpty()) {
                  result -= stack.pop();
              }
            } else if(option.equals("D")) {
               if(!stack.isEmpty()) {
                   int value = stack.peek() * 2;
                   stack.push(value);
                   result += value;
               }
            } else if(option.equals("+")) {
               if(!stack.isEmpty()) {
                   int popValue = stack.pop();
                   int peekValue = stack.peek();
                   int totalValue = popValue + peekValue;
                   stack.push(popValue);
                   stack.push(totalValue);
                   result += totalValue;
               }
            } else {
                int value = Integer.parseInt(option);
                stack.push(value);
                result += value;
            }
        }
        return result;
    }
}

33、有效的括号

给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”
输出: true
示例 2:

输入: “()[]{}”
输出: true
示例 3:

输入: “(]”
输出: false
示例 4:

输入: “([)]”
输出: false
示例 5:

输入: “{[]}”
输出: true

解题思路:

解题思路很简单,依然是栈问题,首先遇到左半边括号时压入栈中,如果遇到的是右半边括号,将其与栈顶元素对比,如果相等就将栈顶元素pop出, 不相等那么就把当前字符push到栈中,遍历所有的字符,如果栈为空说明是有效括号,栈中还有元素说明是无效的。

import java.util.Stack;
class Solution {
    public boolean isValid(String s) {
        char[] symbols = s.toCharArray();
        Stack<Character> stack = new Stack<>(); 
        for(int i = 0; i < symbols.length; i++) {
            char currentSymbol = symbols[i];
            if(currentSymbol == '(' || currentSymbol == '{' || currentSymbol == '[') { 
               stack.push(currentSymbol);
            } else if(!stack.isEmpty() && isMatch(currentSymbol, stack.peek())) {
                stack.pop();
            } else {、
                stack.push(currentSymbol);
            }
        }
        return stack.isEmpty();
    }
    public boolean isMatch(char c, char peekChar) {
        return (c == ')' && peekChar == '(') || (c == '}' && peekChar == '{') || (c == ']' && peekChar == '[');
    }
}

34、比较含退格的字符串

给定 S 和 T 两个字符串,当它们分别被输入到空白的文本编辑器后,判断二者是否相等,并返回结果。 # 代表退格字符。

示例 1:

输入:S = “ab#c”, T = “ad#c”
输出:true
解释:S 和 T 都会变成 “ac”。
示例 2:

输入:S = “ab##”, T = “c#d#”
输出:true
解释:S 和 T 都会变成 “”。
示例 3:

输入:S = “a##c”, T = “#a#c”
输出:true
解释:S 和 T 都会变成 “c”。
示例 4:

输入:S = “a#c”, T = “b”
输出:false
解释:S 会变成 “c”,但 T 仍然是 “b”。

解题思路:

分析题目,#表示退格,应该和栈联系起来,思路比较简单,首先设置两个字符栈,S和T,每个栈都分别进行如下判断,如果是非#字符push到栈中,如果是#且栈为非空pop栈顶,最后同时pop两个栈,一次对比栈中元素是否一一对应相等,如果是则返回true.

import java.util.Stack;
class Solution {
    public boolean backspaceCompare(String S, String T) {
        char[] sChars = S.toCharArray();
        char[] tChars = T.toCharArray(); 
        Stack<Character> sStack = handleBackspace(new Stack<Character>(), sChars);
        Stack<Character> tStack = handleBackspace(new Stack<Character>(), tChars);
        while(!sStack.isEmpty() && !tStack.isEmpty()) {
            if(sStack.pop() != tStack.pop()){
                return false;
            }
        }
        if(!sStack.isEmpty() || !tStack.isEmpty()){
            return false;
        }
        return true;
    }

    public Stack<Character> handleBackspace(Stack<Character> stack, char[] chars) {
        for(int i = 0; i < chars.length; i++) {
            char currentSymbol = chars[i];
            if(currentSymbol != '#') {
                stack.push(currentSymbol);
            } else {
                if(!stack.isEmpty()) {
                    stack.pop();
                }
            }
        }
        return stack;
    }
}

35、用队列实现栈

使用队列实现栈的下列操作:

push(x) – 元素 x 入栈
pop() – 移除栈顶元素
top() – 获取栈顶元素
empty() – 返回栈是否为空
注意:

你只能使用队列的基本操作– 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。

解题思路:

解题思路很简单,用一个集合模拟栈即可。

class MyStack {
    private ArrayList<Integer> mDataList;
    /** Initialize your data structure here. */
    public MyStack() {
        mDataList = new ArrayList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        mDataList.add(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        if(!mDataList.isEmpty()) {
            int value = mDataList.get(mDataList.size() - 1);
            mDataList.remove(mDataList.size() - 1);
            return value;
        }
        return -1;
    }

    /** Get the top element. */
    public int top() {
        if(!mDataList.isEmpty()) {
            return  mDataList.get(mDataList.size() - 1);
        }
        return -1;
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return mDataList.size() == 0;
    }
}

36、下一个更大的元素

给定两个没有重复元素的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在,对应位置输出-1。

示例 1:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于num1中的数字4,你无法在第二个数组中找到下一个更大的数字,因此输出 -1。
对于num1中的数字1,第二个数组中数字1右边的下一个较大数字是 3。
对于num1中的数字2,第二个数组中没有下一个更大的数字,因此输出 -1。
示例 2:

输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于num1中的数字2,第二个数组中的下一个较大数字是3。
对于num1中的数字4,第二个数组中没有下一个更大的数字,因此输出 -1。
注意:

nums1和nums2中所有元素是唯一的。
nums1和nums2 的数组大小都不超过1000。

解题思路:

1、首先需要明白一点就是nums1是nums2的子集,而且最终输出的数组长度等于nums1的长度。

2、先把nums2第一个元素push到栈中,如果当前元素元素比栈顶元素要大,说明可能是我们需要找的,分别以栈顶元素为key,当前元素为value存入到一个HashMap中,然后再把栈顶元素出栈,表示找到了一对可能的值,如果当前元素比如栈顶元素小,那么就把这个元素压入栈中。

3、最后一步就直接遍历nums1,并把当前值去HashMap中查找到对应value,找不到就返回-1.

import java.util.Stack;
import java.util.HashMap;
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] resultArray = new int[nums1.length];
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums2.length; i++) {
            while(!stack.isEmpty() && stack.peek() < nums2[i]) {
               map.put(stack.pop(), nums2[i]);
            }
            stack.push(nums2[i]); 
        }
        int index = 0;
        for(int i = 0; i < nums1.length; i++) {
            resultArray[index++] = map.getOrDefault(nums1[i], -1);
        }
        return resultArray;
    }
}

37、最近请求的次数

写一个 RecentCounter 类来计算最近的请求。

它只有一个方法:ping(int t),其中 t 代表以毫秒为单位的某个时间。

返回从 3000 毫秒前到现在的 ping 数。

任何处于 [t - 3000, t] 时间范围之内的 ping 都将会被计算在内,包括当前(指 t 时刻)的 ping。

保证每次对 ping 的调用都使用比之前更大的 t 值。

示例:

输入:inputs = [“RecentCounter”,”ping”,”ping”,”ping”,”ping”], inputs = [[],[1],[100],[3001],[3002]]
输出:[null,1,2,3,3]

提示:

每个测试用例最多调用 10000 次 ping。
每个测试用例会使用严格递增的 t 值来调用 ping。
每次调用 ping 都有 1 <= t <= 10^9。

解题思路:

这道题目有点难看懂,实际上就是表示返回从3000ms前到现在ping的数量,只需要把每次ping的时间t先入队列,然后随着时间流逝,每次取出队列队头元素和当前ping的时间做差,一旦超过3000ms,就把超过3000ms的出队列,之后队列中剩下就是最近3000ms,队列长度就是请求次数

import java.util.*;
class RecentCounter {
    private Queue<Integer> mQueue;
    public RecentCounter() {
        mQueue = new ArrayDeque<>();
    }

    public int ping(int t) {
        mQueue.offer(t);
        while(t - mQueue.peek() > 3000) {
            mQueue.poll();
        }
        return mQueue.size();
    }
}

38、删除最外层的括号

有效括号字符串为空 (“”)、”(“ + A + “)” 或 A + B,其中 A 和 B 都是有效的括号字符串,+ 代表字符串的连接。例如,””,”()”,”(())()” 和 “(()(()))” 都是有效的括号字符串。

如果有效字符串 S 非空,且不存在将其拆分为 S = A+B 的方法,我们称其为原语(primitive),其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 S,考虑将其进行原语化分解,使得:S = P_1 + P_2 + … + P_k,其中 P_i 是有效括号字符串原语。

对 S 进行原语化分解,删除分解中每个原语字符串的最外层括号,返回 S 。

示例 1:

输入:”(()())(())”
输出:”()()()”
解释:
输入字符串为 “(()())(())”,原语化分解得到 “(()())” + “(())”,
删除每个部分中的最外层括号后得到 “()()” + “()” = “()()()”。
示例 2:

输入:”(()())(())(()(()))”
输出:”()()()()(())”
解释:
输入字符串为 “(()())(())(()(()))”,原语化分解得到 “(()())” + “(())” + “(()(()))”,
删除每隔部分中的最外层括号后得到 “()()” + “()” + “()(())” = “()()()()(())”。
示例 3:

输入:”()()”
输出:””
解释:
输入字符串为 “()()”,原语化分解得到 “()” + “()”,
删除每个部分中的最外层括号后得到 “” + “” = “”。

解题思路:

该题的思路就是找到出现”原语“的位置index, 然后我们就能分割出对应位置的”原语“,如何找到原语的位置,如果是)且队列不为空就pop出栈,如果是(就push到栈中,如果栈为空表示出现了一个原语,此时遍历的index就是原语出现的位置。

import java.util.Stack;
class Solution {
    public String removeOuterParentheses(String S) {
        Stack<Character> stack = new Stack<>();
        char[] sChars = S.toCharArray();
        StringBuilder sb = new StringBuilder();
        int start = 0;
        for(int i = 0; i < sChars.length; i++) {
            if(!stack.isEmpty() && sChars[i] == ')') {
                stack.pop();
                if(stack.isEmpty()) {
                    sb.append(S.substring(start + 1, i));
                    start = i + 1;
                }
            } else {
                stack.push(sChars[i]);
            }
        }
        return sb.toString();
    }
}

39、删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。

在 S 上反复执行重复项删除操作,直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例:

输入:”abbaca”
输出:”ca”
解释:
例如,在 “abbaca” 中,我们可以删除 “bb” 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”,其中又只有 “aa” 可以执行重复项删除操作,所以最后的字符串为 “ca”。

提示:

1 <= S.length <= 20000
S 仅由小写英文字母组成。

解题思路:

相邻重复项实际上就是abba实际上就栈结构,遍历S的字符数组,如果当前字符与栈顶元素相等就把栈顶元素pop出来,否则就把当前push到栈中,最后遍历完数组后,栈内剩下元素就是逆序组成字符串就是删除后的,所以需要借助一个集合来收集正序的字符序列。

import java.util.Stack;
class Solution {
    public String removeDuplicates(String S) {
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        List<String> strList = new ArrayList<>();
        char[] sChars = S.toCharArray();
        for(int i = 0; i < sChars.length; i++) {
            char currentSymbol = sChars[i];
            if(!stack.isEmpty() && stack.peek() == currentSymbol) {
                stack.pop();
                if(!strList.isEmpty()) {
                   strList.remove(strList.size() - 1);                   
                }
            } else {
                stack.push(currentSymbol);
                strList.add(String.valueOf(currentSymbol));
            }
        }
        for(int i = 0; i < strList.size(); i++) {
            sb.append(strList.get(i));
        }
        return sb.toString();
    }
}

40、重建二叉树(1)

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

解题思路:

我们都只知道前序(根-左-右),根据前序根结点位置可把 中序(左-根-右) 序列划为左子树序列和右子树序列,然后左右子树序列以递归方式重复前序结点划分中序左子树和右子树序列,不断划分,最终直到左右子树序列划分完毕为止。

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre == null || pre.length == 0 || in == null || in.length == 0) return null;
        return createBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }
    public TreeNode createBinaryTree(int [] pre, int pStart, int pEnd, int [] in, int inStart, int inEnd) {
        //创建根结点
        TreeNode root = new TreeNode(pre[pStart]);
        int partPosition = 0;//关键需要找到划分中序序列的位置partPosition
        for(int i = inStart; i <= inEnd; i++) {
            if(in[i] == root.val) {
                partPosition = i;
                break;
            }
        }
        if(partPosition - inStart > 0 ) {//说明划分中序左半部分含有元素,存在左子树
            int inSize = partPosition - inStart;
            root.left = createBinaryTree(pre, pStart + 1, pStart + inSize, in, inStart, partPosition - 1);
        }
        if(inEnd - partPosition > 0 ) {//说明划分中序右半部分含有元素,存在右子树
            int inSize = partPosition - inStart;
            root.right = createBinaryTree(pre, pStart + inSize + 1, pEnd, in, partPosition + 1, inEnd);
        }
        return root;
    }
}

41、斐波那契数列(1)

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

n<=39

解题思路:

斐波那契数列考查的就是递归+公式

f(1) = 1; f(2) = 1; f(n) = f(n - 1) + f(n - 2);

public class Solution {
    public int Fibonacci(int n) {
           if(n == 0) return 0;
           if(n == 1 || n == 2) return 1;
           return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

public class Solution {
    //dp动态规划实现
    public int Fibonacci(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 1;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 1;
        for(int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

42、跳台阶(1)

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

解题思路:

总结归纳规律,可得到对于只有0级台阶,青蛙0种跳法,对于只有1级台阶,它只有1种跳法,对于2级台阶,有两种跳法,分别是先跳1级再跳1级和直接跳2级,对于3级台阶可以选择1级-1级-1级、1级-2级、2级-1级共3种,对于4级台阶就是:1级-1级-1级-1级、1级-1级-2级、1级-2级-1级、2级-2级、2级-1级-1级共5种。可发现它实际上就是得到 f(n) = f(n - 1) + f(n - 2) 实际上是一个斐波那契数列

public class Solution {
    public int JumpFloor(int target) {
         if(target == 0) return 0;
         if(target == 1) return 1;
         if(target == 2) return 2;
         if(target == 3) return 3;
         return JumpFloor(target - 1) + JumpFloor(target - 2);
    }
}

//递推实现
public class Solution {
    public int JumpFloor(int target) {
        if(target == 1) return 1;
        int[] dp = new int[target + 1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= target; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[target];
    }
}

43、变态跳台阶(1)

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

解题思路:

因为青蛙可以跳上任意级的台阶,所以以青蛙跳上一个 4 级的台阶为例进行分析,它可以在开始直接跳 4 级到 4 级台阶,也可以从 1 级台阶上往上跳 3 个台阶到 4 级,也可以从 2 级台阶往上跳 2 个台阶到 4 级,还可以从 3 级台阶上跳 3 级到 4 级。所以f(4) = f(4-1) + f(4-2) + f(4-3) + f(4-4)

f(0)=0,f(1)=1

f(n) = 2*f(n-1),(n>=2)

public class Solution {
    public int JumpFloorII(int target) {
        if(target == 0) return 0;
        if(target == 1) return 1;
        return 2*JumpFloorII(target - 1);
    }
}

public class Solution {
    //dp动态规划解法
    public int JumpFloorII(int target) {
        if(target == 1) return 1;
        int[] dp = new int[target + 1];
        dp[1] = 1;
        for(int i = 2; i <= target; i++) {
            dp[i] = 2 * dp[i - 1];
        }
        return dp[target];
    }
}

44、矩形覆盖(1)

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

解题思路:

这道题依然就是找规律,f(0) = 0; f(1) = 1; f(2) = 2; f(3) = f(2) + f(1); f(4) = f(2) + f(3)

所以: f(n) = f(n-1) + f(n-2)

public class Solution {
    //找规律,斐波拉契数列 F(n) = F(n - 1) + F(n - 2)
    public int RectCover(int target) {
        if(target == 0) return 0;
        if(target == 1) return 1;
        if(target == 2) return 2;
        return RectCover(n - 1) + RectCover(n - 2);
    }
}  

public class Solution {
    //dp动态规划的解法
    public int RectCover(int target) {
        if(target == 0) return 0;
        if(target == 1) return 1;
        if(target == 2) return 2;
        int[] dp = new int[target + 1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= target; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[target];
    }
}  

45、旋转数组最小数字(1)

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

解题思路:

本题关键在于明白旋转点的含义,实际上就是非递减数组中递减拐点,也就是数组一部分递增序列到另一个递增序列的拐点,比如3,4,5,1,2; 3,4,5就是递增序列,然后又从5到1,2所以1就是拐点。那么一个数组中可能存在多个拐点。所以思路就很简单首先遍历数组,找到所有拐点的值把它存在ArrayList集合中,然后再求ArrayList集合中的最小值。就是旋转数组最小数字。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array == null || array.length == 0) return 0;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < array.length; i++) {
            if(array[i] >= max) {
                max = array[i];
            } else {//拐点
                if(array[i] < min) {
                    min = array[i];
                }
                max = array[i];//注意,经过一个拐点后max需要重置更新
            }
        }
        return min;
    }
}

46、二进制中1的个数(1)

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

解题思路:

利用&运算的特性,把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1,就可以进行多少次这样的操作

public class Solution {
    //利用&运算的特性,把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1,就可以进行多少次这样的操作
    public int NumberOf1(int n) {
        int result = 0;
        while (n != 0) {
            n = n & (n - 1);//把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0
            result++;//累加
        }
        return result;
    }
}

47、数值的整数次方(1)

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

保证base和exponent不同时为0

解题思路:

整数次方核心点就是循环累乘,但是就是需要考虑exponent > 0 或 exponent < 0 或 exponent = 0等情况。

import java.lang.Math;
public class Solution {
    public double Power(double base, int exponent) {
        double result = 1.0;
        int temp = 0;
        if(exponent == 0) return result;
        for(int i = 0; i < Math.abs(exponent); i++) {
            result *= base;
        }
        if(exponent > 0) {
            return result;
        } else {
            return 1.0 / result;
        }
    }
}

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

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

解题思路:

因为需要保证奇数和偶数相对位置不变,所以这里采用冒泡排序

public class Solution {
    public void reOrderArray(int [] array) {
        for(int i = 0; i < array.length; i++) {
            for(int j = 0; j < array.length - i - 1; j++) {
                if(array[j] % 2 == 0 && array[j + 1] % 2 == 1) {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }
}

49、树的子结构(1)

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

解题思路:

主要分为三步判断B是否是A的子结构,第一步是这个根节点root1为起点判断是否包含root2; 如果第一步找不到,那么就第二步这个根节点root1.left左子树为起点判断是否包含root2; 如果第二步找不到,那么就第三步这个根节点root1.right右子树为起点判断是否包含root2; 如果这三步都找不到说明B不是A的子结构。

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1 == null || root2 == null) return false;
        boolean result = isSubtree(root1, root2);//第一步是这个根节点root1为起点判断是否包含root2;
        if(!result) {//遍历左子树,第二步这个根节点root1.left左子树为起点判断是否包含root2
            result = HasSubtree(root1.left, root2);
        }
        if(!result) {//遍历右子树,第三步这个根节点root1.right右子树为起点判断是否包含root2
            result = HasSubtree(root1.right, root2);
        }
        return result;
    }

    //isSubtree先判断是否是子树
    public boolean isSubtree(TreeNode rootA, TreeNode rootB) {
        if(rootB == null) return true;
        if(rootA == null || rootA.val != rootB.val) return false;
        return isSubtree(rootA.left, rootB.left) && isSubtree(rootA.right, rootB.right);
    }
}

50、二叉树镜像(翻转二叉树)(1)

题目描述

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

二叉树的镜像定义:源二叉树
8
/
6 10
/ \ /
5 7 9 11
镜像二叉树
8
/
10 6
/ \ /
11 9 7 5

解题思路:

递归交换左右孩子结点即可

public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null) return;
        TreeNode temp = null;
        //交换结点
        temp = root.left;
        root.left = root.right;
        root.right = temp;

        //递归左子树
        if(root.left != null) {
            Mirror(root.left);
        }

        //递归右子树
        if(root.right != null) {
            Mirror(root.right);
        }
    }
}

51、顺时针打印矩阵(1)

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下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) {
        ArrayList<Integer> list = new ArrayList<>();
        addValue(matrix, list, 0);
        return list;
    }

    public void addValue(int[][] matrix, ArrayList<Integer> list, int start) {
        if (matrix == null || matrix.length == 0) {
            return;
        }

        int row = matrix.length;
        int col = matrix[0].length;
        //递归结束
        if (col <= 2 * start || row <= 2 * start) {
            return;
        }
        int stopX = col - 1 - start;
        int stopY = row - 1 - start;

        //打印上方的一行
        for (int i = start; i <= stopX; i++) {
            list.add(matrix[start][i]);
        }
        //打印右方的一行
        if(start <= stopX){
           for (int j = start + 1; j <= stopY; j++) {
               list.add(matrix[j][stopX]);
           }   
        }
        //打印下方的一行
        if(start < stopX && start < stopY){
           for (int k = stopX - 1; k >= start; k--) {
               list.add(matrix[stopY][k]);
           }   
        }
        //打印左方的一行
        if(start < stopX && start < stopY - 1){
           for (int l = stopY - 1; l >= start + 1; l--) {
               list.add(matrix[l][start]);
           } 
        }
        //每执行一次addValue表示打印了矩阵的一圈
        addValue(matrix, list, start + 1);
    }
}

52、从上往下打印二叉树

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

解题思路:

这是典型的二叉树的层序遍历,需要借助队列数据结构,这里使用的LinkedList

public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        //二叉树的层序遍历,从上到下,从左到右,采用队列结构
        Queue<TreeNode> linkedQueue = new LinkedList<TreeNode>();
        ArrayList<Integer> resultList = new ArrayList<>();
        if(root == null) return resultList;
        linkedQueue.offer(root);
        //直到队列为空,那么二叉树就遍历完毕
        while(!linkedQueue.isEmpty()) {
            //获取此时队列长度
            int queueSize = linkedQueue.size();
            for(int i = 0; i < queueSize; i++) {
                //遍历同一层级队列,poll出每个元素
                TreeNode currentNode = linkedQueue.poll();
                resultList.add(currentNode.val);
                //再判断左子树是否为空,不为空将其入队
                if(currentNode.left != null) linkedQueue.offer(currentNode.left);
                 //再判断右子树是否为空,不为空将其入队
                if(currentNode.right != null) linkedQueue.offer(currentNode.right);
            }
        }
        return resultList;
    }
}

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

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

解题思路:

二叉搜索树的特点是,若子树非空,则左子树的节点值均小于根节点的值,右子树均大于根节点的值。且数组序列最后一个元素肯定是根节点。

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0) return false;
        if(sequence.length == 1) return true;//只有一个根节点
        return BST(sequence, 0, sequence.length - 1);
    }
    public boolean BST(int[] sequence, int start, int end) {
        if(start >= end){//如果符合条件遍历完后,都没有return false,那么就是符合后序条件
            return true;
        }
        int i = start;
        //遍历完左子树,因为二叉搜索树左子树节点值都小于根节点,找到数组中最后一个左子树中的节点的位置
        while(i < end && sequence[i] < sequence[end]){
            i++;
        }
        //遍历完后i的位置就是第一个右子树节点。从第一个右子树节点开始遍历右子树的值,只要找到一个不满足右子树所有值大于根节点的值,就不是一个后序遍历
        for(int j = i; j < end; j++) {
            if(sequence[end] > sequence[j]) {
                return false;
            }
        }
        return BST(sequence, start, i - 1) && BST(sequence, i, end - 1);
    }
}

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

输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前)

解题思路:

首先思考节点值的和为输入的整数,每条路径都一定是从根节点到叶子节点,在数据结构中从根节点到叶子节点的遍历称之为深度优先遍历DFS。因此整个过程可以采用先序遍历方式的DFS,即根节点》左子树》右子树。随后考虑一次遍历完成后的处理,当一次遍历完成后,如果输入整数值恰好等于节点值之和,则输出这条路径并且回退一个节点;如果不等于则直接回退一个节点,即回退到当前节点的父节点,如果该父节点有右孩子,则继续遍历,否则继续回退。考虑回退到根节点,此时如果它有右孩子,则继续遍历,否则整个DFS结束。

public class Solution {
    ArrayList<ArrayList<Integer>> pathList = new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null) return pathList;
        path.add(root.val);
        target -= root.val;
        //遍历到最后,target的值正好减少到0且是叶子结点时,说明产生一条符合条件的路径
        if(root.left == null && root.right == null && target == 0) {
            pathList.add(new ArrayList<Integer>(path));
        }
        if(root.left != null) {
            FindPath(root.left, target);
        }
        if(root.right != null) {
            FindPath(root.right, target);
        }
        path.remove(path.size() - 1);//回退到父节点
        return pathList;
    }
}

55、二叉搜索树与双向链表

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

解题思路:

在二叉搜索树中,每个结点都有两个分别指向其左、右子树的指针,左子树结点的值总是小于父结点的值,右子树结点的值总是大于父结点的值。在双向链表中,每个结点也有两个指针,它们分别指向前一个结点和后一个结点。所以这两种数据结构的结点是一致,二叉搜索树和双向链表,只是因为两个指针的指向不同而已,通过改变其指针的指向来实现是完全可能的。

为了减少指针的变换次数,并让操作更加简单,在转换成排序双向链表时,原先指向左子结点的指针调整为链表中指向前一个结点的指针,原先指向右子结点的指针调整为链表中指向下一个结点的指针。
由于要求链表是有序的,可以借助二叉树中序遍历,因为中序遍历算法的特点就是从小到大访问结点。当遍历访问到根结点时,假设根结点的左侧已经处理好,只需将根结点与上次访问的最近结点(左子树中最大值结点)的指针连接好即可。进而更新当前链表的最后一个结点指针。同时中序遍历过程正好是转换成链表的过程,可采用递归方法处理。

//1、将左子树构成双链表,并返回该链表的头节点(左子树最左边的节点)
//2、定位到左链表的最后一个节点(左子树最右边的节点)
//3、如果左子树链表不为空,则将当前root追加到左子树链表后
//4、将右子树构造成双向链表,并返回链表头结点(右子树最左边的节点)
//5、如果右子树链表不为空,将右子树链表追加到当前root后
//6,根据左子树链表是否为空返回的整体双向链表的头节点
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }
        //只有一个根节点
        if(pRootOfTree.left == null && pRootOfTree.right == null) {
            return pRootOfTree;
        } 
        //1、将左子树构成双链表,并返回该链表的头节点
        TreeNode left = Convert(pRootOfTree.left);
        //2、定位到左子树链表的最后一个节点(左子树最右边的节点)
        TreeNode currentNode = left;
        while(currentNode != null && currentNode.right != null) {
            currentNode = currentNode.right;
        }
        //最终currentNode定位到左子树链表表尾最后一个节点
        //3、如果左子树链表不为空,则将当前root追加到左子树链表后
        if(left != null) {
            currentNode.right = pRootOfTree;//左子树链表的最后一个节点p(左子树最右边节点)的右指针指向当前root节点
            pRootOfTree.left = currentNode;//当前root节点的左指针指向左子树链表的最后一个节点p(左子树最右边节点)
        }
        //4、将右子树构造成双向链表,并返回链表头结点(右子树最左边的节点)
        TreeNode right = Convert(pRootOfTree.right);
        if(right != null) {
            right.left = pRootOfTree;//右子树链表的头结点right的左指针指向当前root
            pRootOfTree.right = right;//当前root的右指针指向右子树链表的头结点right
        }
        return left != null ? left : pRootOfTree;
    }
}

56、字符串的排列

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

输入描述:

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

解题思路:

  1. 把整个字符串视为第一个字符和后来的字符的组合

  2. 每次确定一个元素,和后面的元素依次兑换)

import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> resultList = new ArrayList<>();
        if(str == null || str.length() == 0) return resultList;
        PermutationChar(str.toCharArray(), 0, resultList);
        Collections.sort(resultList);//字典序排序
        return resultList;
    }

    public void PermutationChar(char[] chars, int start, ArrayList<String> list) {
        if(start == chars.length - 1) {//表示交换结束,已经是最后的交换结果了,也就对应图中最后一层
            String result = String.valueOf(chars);//将chars中交换后结果输出字符串
            if(!list.contains(result)) {//防止重复添加
                list.add(result);
            }
        } else {
            for(int i = start; i < chars.length; i++) {
                swapChar(chars, start, i);
                PermutationChar(chars, start + 1, list);
                swapChar(chars, start, i);
            }
        }

    }
    //交换字符
    public void swapChar(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}

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

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

解题思路:

首先,题目说了只有可能存在一个数字出现次数超过数组的一半,所以只需要找到出现次数的最多的数,然后再看如果是次数超过数组一半,那么输出这个数,如果没有超出就输出0

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0) return 0;
        int time = 1;
        int result = array[0];
        //第一步,找到出现次数最多的数result
        for(int i = 1; i < array.length; i++) {
            if(time == 0) {
                time = 1;
                result = array[i];
            } else if(result == array[i]){
                time++;
                result = array[i];
            } else {
                time--;
            }
        }
        //第二步,遍历整个数组,统计这个数出现的次数,如果次数大于数组长度,那么就输出这个数
        time = 0;
        for(int j = 0; j < array.length; j++) {
            if(result == array[j]) {
                time++;
            }
        }
        return time > array.length / 2 ? result : 0;
    }
}

58、最小K个数

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

解题思路:

思路比较清晰,只需要把当前数组从小到大排序,然后排序的长度为k即可。

思路一: 冒泡排序,只需要进行K轮比较,算法复杂度是O(kn)

利用冒泡排序的思想,每一轮排序把剩余数组中最小的一个数字放到前面已排序的后面,只要进行K轮即可

思路二: 快速排序,算法复杂度是O(n)

利用快速排序划分的思想,每一次划分就会有一个数字位于以数组从小到达排列的的最终位置index;
位于index左边的数字都小于index对应的值,右边都大于index指向的值;
所以,当index > k-1时,表示k个最小数字一定在index的左边,此时,只需要对index的左边进行划分即可;
当index < k - 1时,说明index及index左边数字还没能满足k个数字,需要继续对k右边进行划分;
代码如下:

思路三: 利用容器TreeMap(底层基于红黑树,插入数据会自动升序排序),复杂度为O(nlogn)优点是可以处理海量数据,特别是N特别大情况,数据不可能一次性全部读入内存

import java.util.*;
public class Solution {
    //冒泡排序实现
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(input == null) return null;
        ArrayList<Integer> resultList = new ArrayList<>();
        if(k > input.length) return resultList;
        int temp = 0;
        for(int i = 0; i < k; i++) {
            for(int j = i + 1; j < input.length; j++) {
                if(input[i] > input[j]) {
                    temp = input[i];
                    input[i] = input[j];
                    input[j] = temp;
                }
            }
            resultList.add(input[i]);
        }
        return resultList;
    }
    //快速排序实现
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(input == null)
            return null;
        ArrayList<Integer> list = new ArrayList<Integer>(k);
        if(k > input.length)
            return list;
        int low = 0;
        int high = input.length - 1;
        int index = partition(input,low,high);
        while(index != k-1){
            if(index > k-1){
                high = index - 1;
            }else{
                low = index + 1;
            }
            index = partition(input,low,high);
        }
       for(int i = 0; i < k; i++){
           list.add(input[i]);
       }
        return list;
    }
    //划分操作
    public int partition(int[] array,int start,int end){
        int pivot = array[start];
        while(start < end){
            while(start < end && array[end] >= pivot) end--;
            array[start] = array[end];
            while(start < end && array[start] <= pivot) start++;
            array[end] = array[start];
        }
        array[start] = pivot; 
        return start;
    }
}
//TreeMap容器实现
    public ArrayList<Integer> GetLeastNumbers_Solution3(int [] input, int k) {
        if(input == null)
            return null;
        ArrayList<Integer> list = new ArrayList<Integer>(k);
        if(k > input.length)
            return list;
        TreeSet<Integer> tree = new TreeSet<Integer>();
        for(int i = 0 ; i < input.length; i++){
            tree.add(input[i]);
        }
        int i = 0;
        for(Integer elem : tree){
            if(i >= k)
                break;
            list.add(elem);
            i++;
        }
        return list;
    }

59、连续子数组的最大和

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

解题思路:

  • 最优方法,时间复杂度O(n)

  • 和最大的子序列的第一个元素肯定是正数

  • 因为元素有正有负,因此子序列的最大和一定大于0

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int maxSum = Integer.MIN_VALUE;
        int curSum = 0;
        for(int i=0; i<array.length; i++) {
            curSum += array[i];
            if(curSum > maxSum) {
                maxSum = curSum;
            }
            if(curSum < 0){
                curSum = 0;
            }
        }
        return maxSum;
    }
}

60、整数中1出现的次数(从1到n整数中1出现的次数)

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

解题思路:

第一种办法: 暴力循环解决

第二种办法: 数学规律,总结公式

public class Solution {
    //暴力解决    
    public int NumberOf1Between1AndN_Solution(int n) {
        int count = 0;
        for(int i = 0; i <= n; i++) {
            int temp = i;
            while(temp != 0) {
                if(temp % 10 == 1){
                    count++;
                }
                temp /= 10;
            }
        }
        return count;
    }
    //数学规律
    public int NumberOf1Between1AndN_Solution(int n) {
        int count = 0;
        for(int i = 1; i <= n; i *= 10) {
            int a = n / i;
            int b = n % i;
            count += (a + 8) / 10*i + ((a % 10 == 1) ? b+1 : 0);
        }
        return count;
    }
}

61、把数组排成最小的数

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

解题思路:

数组中所有的数拼接后有可能会超过整数的范围,因此本题必须要使用字符串来处理。
要对3,32 ,321 排序,不能直接比较32,3的大小,应该比较323,332的大小,即,3,32的大小应该有323,332的大小来确定。因此3比32大,3应该在32后面,32和321比较时,32321>32132,因此32>321,32在321后面,3,32,321由小到大排序为,321,32,3,组成的最小数为:321323

import java.util.*;

public class Solution {
    public String PrintMinNumber(int [] numbers) {
         if(numbers.length == 0 || numbers == null) {
             return "";
         }
        //装箱处理,不然下面的Arrays.sort无法重写
        Integer[] nums = new Integer[numbers.length];
        for(int i = 0;i < numbers.length; i++){
            nums[i]=numbers[i];
        }
        Arrays.sort(nums, new Comparator<Integer>(){
             //对数组numbers用自定义方法排序
            @Override
            public int compare(Integer num1, Integer num2) {
                 //重写compare方法来比较num1,num2的大小,当num1+""+num2和num2+""+num1
                //都是字符串,比较num1,num2的大小其实是比较两个子串的大小
                return ((num1+""+num2).compareTo(num2+""+num1));
            }
        });
        String result = "";
        for(int i = 0; i < nums.length; i++) {
            result += nums[i];
        }
        return result;
    }
}

62、二叉树的深度

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

解题思路:

二叉树的层序遍历,统计深度

import java.util.*;
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        int depth = 0;
        Queue<TreeNode> linkedQueue = new LinkedList<TreeNode>();
        linkedQueue.offer(root);
        while(!linkedQueue.isEmpty()) {
            int queueSize = linkedQueue.size();
            depth++;//表示遍历一层了
            for(int i = 0; i < queueSize; i++) {
                TreeNode currentNode = linkedQueue.poll();
                if(currentNode.left != null) {
                    linkedQueue.offer(currentNode.left);
                }
                if(currentNode.right != null) {
                    linkedQueue.offer(currentNode.right);
                }
            }
        }
        return depth;
    }
}

63、丑数

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

解题思路:

一一暴力遍历,使用遍历法求第k个丑数,从1开始遍历,如果是丑数则count++,直到count=k为止。那么如何判断丑数呢?根据丑数的定义,丑数只有2,3,5这三个因子,那么我们就拿数字除以这三个因子。具体算法如下:

Step1.如果一个数能够被2整除,那么让他继续除以2;

Step2.如果一个数能够被3整除,那么让他继续除以3;

Step3.如果一个数能够被5整除,那么让他继续除以5;

Step4.如果最后这个数变为1,那么这个数就是丑数,否则不是。

但是采用上述方法会超时,所以借助上面方法逆向思路考虑,质因子中都是2,3,5嘛。那么7,14这类数肯定就不会是的啦。接着我们就发现这样观察下来,丑数肯定是由丑数乘以2,3或者5再产生丑数的。这就是丑数不断产生的根本法则。我们会考虑,用一个数组把从小到大的丑数都装起来,然后你直接取第几个丑数就行了。

我们需要确保数组里面的丑数十排好序的。假设数组里已经有的最大丑数记为M。那怎么产生下一个丑数呢?该丑数肯定是前面某一个丑数乘以2,3,5的结果,所以我们首先考虑把已有的每个丑数乘以2。在乘以2的时候,能得到若干个小于或等于M的结果。由于是按顺序生成,小于或者等于M的数肯定已经在数组中了,我们不需要在此考虑;还会得到若干个大于M的结果,但我们只需要第一个大于M的结果。因为我们希望丑数是按顺序从小到大生成的,其它更大的结果以后再说。我们把得到的第一个乘以2后大于M的结果记为M2,同样地有M3,M5。那么下一个丑数应该就是M2,M3,M5的最小值。

前面分析的时候提到把已有的每一个丑数分别乘以2,3,5.事实上这不是必须的,因为已有的丑数是按照顺序存放在数组中的。对于乘以2而言,肯定存在一个丑数T2,排在它之前的每个丑数乘以2得到的结果都会小于已有的最大丑数,在它之后的每个丑数乘以2得到的结果都会太大。我们只需记下这个丑数的的位置,同时每次生成新的丑数的时候去更新这个T2即可,对于3和5而言也是如此。

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index <= 0) return 0;
        int[] uglyNumbers = new int[index];
        int nextIndex = 0, result2 = 1, result3 = 1, result5 = 1, index2 = 0, index3 = 0, index5 = 0;
        uglyNumbers[0] = 1;
        while(nextIndex < index - 1) {
            int tempResult = min(result2 * 2, result3 * 3, result5 * 5);
            uglyNumbers[++nextIndex] = tempResult;
            while(2 * result2 <= uglyNumbers[nextIndex]) {
                index2++;
                if(index2 >= index) {
                    break;
                }
                result2 = uglyNumbers[index2];
            }
            while(3 * result3 <= uglyNumbers[nextIndex]) {
                index3++;
                if(index3 >= index) {
                    break;
                }
                result3 = uglyNumbers[index3];
            }
            while(5* result5 <= uglyNumbers[nextIndex]) {
                index5++;
                if(index5 >= index) {
                    break;
                }
                result5 = uglyNumbers[index5];
            }
        }
        return uglyNumbers[index - 1];
    }
    public int min(int a, int b, int c) {
        int minNumber = a < b ? a : b;
        minNumber = minNumber < c ? minNumber : c;
        return minNumber;
    }
}

64、第一个只出现一次的字符

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

解题思路:

使用哈希表存储每个字符对应出现的次数(字符为key, 次数为value),最后遍历所有字符数组,查找到第一个字符对应value为1的字符,最后返回当前位置即可。

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

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

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

解题思路:

解法一: 暴力遍历-时间复杂度O(n)

解法二: 二分查找第一次出现目标数和最后一次出现目标数的位置,位置差+1就是出现的总次数-时间复杂度O(n)

public class Solution {

//二分查找,有序数组中重复数字的次数复杂度: O(logn)
    public int GetNumberOfK(int[] array, int k) {
        if (array == null || array.length == 0) return 0;
        int low = 0;
        int high = array.length - 1;
        int firstIndex = 0;
        boolean isFirstFound = false;
        //先找到出现目标数字的第一个位置firstIndex
        while (low <= high) {
            int mid = (low + high) >>> 1;
            if (k > array[mid]) {
                low = mid + 1;
            } else if (k < array[mid]) {
                high = mid - 1;
            } else {
                isFirstFound = true;
                //如果array[mid]的值k,一直往前找直到找到array[mid - 1]的值不等于k,那么当前mid就是出现目标数字的第一个位置
                if (mid - 1 >= 0 && k != array[mid - 1]) {
                    firstIndex = mid;
                    break;
                } else {
                    high = mid - 1;
                }
            }
        }

        //先找到出现目标数字的最后一个位置lastIndex
        int lastIndex = array.length - 1;
        low = 0;
        high = array.length - 1;
        boolean isLastFound = false;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            if (k > array[mid]) {
                low = mid + 1;
            } else if (k < array[mid]) {
                high = mid - 1;
            } else {
                isLastFound = true;
                //如果array[mid]的值k,一直往后找直到找到array[mid + 1]的值不等于k或者越界了,那么当前mid就是出现目标数字的最后一个位置,越界了说明就是最后一个位置
                if (mid + 1 <= array.length - 1 && k != array[mid + 1]) {
                    lastIndex = mid;
                    break;
                } else {
                    low = mid + 1;
                }
            }
        }
        //最后重复数字的个数就是:出现目标数字最后一个位置 - 出现目标数字第一个位置 + 1, 就得到了重复数的次数。
        if (isFirstFound || isLastFound) {
            return lastIndex - firstIndex + 1;
        } else {
            return 0;
        }
    }
}

66、数组中只出现一次的数字

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

解题思路:

解题思路有多种,这里说一种简单暴力的方法

由于题目中提到数组里除了两个数字之外,其他的数字都出现了两次,那么利用一个集合,如果数字是第一次出现就把它加到集合中,如果集合中已经存在这个数字那么就remove掉,那么出现两次的数字就被移除集合了,剩下来的就是只出现一次的数字了。

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
import java.util.*;
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < array.length; i++) {
            if(!list.contains(array[i])) {
                list.add(array[i]);
            } else {
                list.remove(new Integer(array[i]));
            }
        }
        if(list.size() > 1) {
            num1[0] = list.get(0);
            num2[0] = list.get(1);
        }
    }
}

67、数组中的逆序对

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

输入描述:

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

数据范围:

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

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

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

示例1

输入

1,2,3,4,5,6,7,0

输出

7

解题思路:

很容易想到的方法就是遍历每一个元素,让其与后面的元素对比,如果大于则count++,但是这样的时间复杂度是O(n2),因此,我们可以用归并排序思路。)

例如7,5,6,4可以划分为两段7,5和6,4两个子数组

  1. 在7,5中求出逆序对,因为7大于5所以有1对
  2. 在6,4中求出逆序对,因为6大于4所以逆序对再加1,为2
  3. 对7,5和6,4进行排序,结果为5,7,和4,6
  4. 设置两个指针分别指向两个子数组中的最大值,p1指向7,p2指向6
  5. 比较p1和p2指向的值,如果大于p2,因为p2指向的是最大值,所以第二个子数组中有几个元素就有几对逆序对(当前有两个元素,逆序对加2,2+2=4),7>6,比较完之后将p1指向的值放入辅助数组里,辅助数组里现在有一个数字7,然后将p1向前移动一位指向5
  6. 再次判断p1和p2指向的值,p1小于p2,因为p1指向的是第一个子数组中最大值,所以子数组中没有能和当前p2指向的6构成逆序对的数,将p2指向的值放入辅助数组,并向前移动一位指向4,此时辅助数组内为6,7
  7. 继续判断p1(指向5)和p2(指向4),5>4,第二个子数组中只有一个数字,逆序对加1,4+1=5,为5对,然后将5放入辅助数组,第一个子数组遍历完毕,只剩下第二个子数组,当前只有一个4,将4也放入辅助数组,函数结束。辅助数组此时为4,5,6,7.逆序对为5.
public class Solution {
    public int InversePairs(int [] array) {
        int len = array.length;
        if(array== null || len <= 0){
            return 0;
        }
        return mergeSort(array, 0, len-1);
    }
    public int mergeSort(int [] array, int start, int end){
        if(start == end)
            return 0;
        int mid = (start + end) / 2;
        int left_count = mergeSort(array, start, mid);
        int right_count = mergeSort(array, mid + 1, end);
        int i = mid, j = end;
        int [] copy = new int[end - start + 1];
        int copy_index = end - start;
        int count = 0;
        while(i >= start && j >= mid + 1){
            if(array[i] > array[j]){
                copy[copy_index--] = array[i--];
                count += j - mid;
                if(count > 1000000007){
                    count %= 1000000007;
                }
            }else{
                copy[copy_index--] = array[j--];
            }
        }
        while(i >= start){
            copy[copy_index--] = array[i--];
        }
        while(j >= mid + 1){
            copy[copy_index--] = array[j--];
        }
        i = 0;
        while(start <= end) {
            array[start++] = copy[i++];
        }
        return (left_count+right_count+count)%1000000007;
    }
}

68、平衡二叉树

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

解题思路:

首先,需要知道平衡二叉树的特点,左右子树高度差不超过1,运用递归思想,不平衡的条件有三种:左子树不平衡、右子树不平衡、左右子树高度差绝对值大于1

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return isBST(root).isBST;
    }
    //记录当前结点是否是平衡isBST以及当前的深度isBST
    private class ResultBST {
        boolean isBST;
        int depth;
        public ResultBST(boolean isBST, int depth) {
            this.isBST = isBST;
            this.depth = depth;
        }
    }
    public ResultBST isBST(TreeNode root) {
        if(root == null) return new ResultBST(true, 0);//空树也是平衡的
        ResultBST leftResultBST = isBST(root.left);
        ResultBST rightResultBST = isBST(root.right);
        //左子树不平衡、右子树不平衡
        if(!leftResultBST.isBST || !rightResultBST.isBST) {
            return new ResultBST(false, 0);
        }
        //左右子树高度差绝对值大于1
        if(Math.abs(leftResultBST.depth - rightResultBST.depth) > 1) {
            return new ResultBST(false, 0);
        }
        //平衡条件,树的深度等于左右子树深度最大值+1
        return new ResultBST(true, Math.max(leftResultBST.depth, rightResultBST.depth) + 1);
    }
}

69、二叉树的下一个结点

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

解题思路:

分析二叉树的下一个节点,一共有以下情况:

  1. 二叉树为空,则返回空;
  2. 节点是根节点,且节点右孩子存在,则指针从该节点的右孩子出发,一直沿着指向左子结点的指针找到的叶子节点即为下一个节点;
  3. 节点不是根节点。如果该节点是其父节点的左孩子,则返回父节点;否则继续向上遍历其父节点的父节点,重复之前的判断,返回结果。
public class Solution {
    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;
        }
        //该节点不是根节点,若该节点是其父节点的左孩子,则返回父节点;否则继续向上遍历其父节点的父节点,重复之前的判断,返回结果。
        while(pNode.next != null) {
            if (pNode.next.left == pNode)
                return pNode.next;
            pNode = pNode.next;
        }
        return null;
    }
}

70、对称的二叉树

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

解题思路:

首先,如果一个棵树是空树或是只有一个根结点的树那它也是一个对称二叉树。

如果这个棵树的左右子树是对称的,那么这棵树肯定也是对称二叉树,然后只需要对比左右子树。

若左右子树中都为null,说明肯定是对称的

若左右子树其中有一个为null,说明肯定不是对称的,

若左右子树中,左子树root的val不等于右子树root的val肯定不是对称的,如果相等就继续看左子树root.left和右子树root.right以及左子树root.right和右子树root.left是否对称。

public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        if(pRoot == null || (pRoot.left == null && pRoot.right == null)) return true;
        return isSymmetricalTree(pRoot.left, pRoot.right);
    }

    public boolean isSymmetricalTree(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) return true;
        if(root1 == null || root2 == null) return false;
        if(root1.val != root2.val) return false;
        return isSymmetricalTree(root1.left, root2.right) && isSymmetricalTree(root1.right, root2.left);
    }
}

71、二叉搜索树的第k个结点

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

解题思路:

二叉搜索树有个显著特点就是: 它的中序遍历就是从小到大排序,所以只需要中序遍历时候,把每个节点加入到集合中,然后取第K个结点即可。

import java.util.*;
public class Solution {
    private LinkedList<TreeNode> nodeList = new LinkedList<>();
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot == null || k == 0) return null;
        middle(pRoot);
        if(k > 0 && k <= nodeList.size()) {
            return nodeList.get(k-1);
        }
        return null;
    }
    public void middle(TreeNode pRoot) {
        if(pRoot == null) return;
        if(pRoot.left != null) {
            middle(pRoot.left);
        }
        nodeList.add(pRoot);
        if(pRoot.right != null) {
            middle(pRoot.right);
        }
    } 
}

72、求1+2+3+…+n

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

解题思路:

很简单,就是等差数列求和,求和公式是: n*(n+1) / 2;

public class Solution {
    public int Sum_Solution(int n) {
        return n*(n+1) / 2;
    }
}

73、不用加减乘除做加法

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

解题思路:

按照题目不能做加减乘除四则运算,剩下的也只有位运算了。比如如何得出5+17=22这个结果的,实际上,我们可以分三步进行:第一步只做各位相加不进位,此时相加的结果是12,第二步做进位,5+7中有进位,进位的值为10;第三步,把前面的两个结果加起来12+10的结果是22,刚好5+17=22

5的二进制是101,17的二进制是10001,还是试着把计算分成三步:第一步各位相加但不计进位,得到的结果是10100;第二步记下进位。在这个例子中只在最后一位相加时产生进位,结果是二进制的10,第三步把前两步的结果相加,得到的结果是10110,转换成十进制刚好是22,由此可见三步走的策略对二进制也是适用的

第一步不考虑进位对每一位相加。0+0,1+1的结果都是0,1+0的结果是1。0+1的结果是1,我们注意到这和异或的结果是一样的。对异或而言,0和0,1和1异或的结果是0,而0和1,1和0的异或结果是1,接着考虑第二步进位,对0+0,0+1,1+0而言,都不会产生进位,只有1+1时,会向前差生一个进位。此时我们可以想象成是两个数先做位与运算,然后再向前左移动一位。只有两个数都是1的时候,位与得到的结果是1,其余都是0。第三步相加的过程是重复前面的两步,直到不产生进位为止。

public class Solution {
    public int Add(int num1,int num2) {
        int sum, carry;
        do {
            sum = num1 ^ num2;
            carry = (num1 & num2) << 1;
            num1 = sum;
            num2 = carry;
        }while(num2 != 0);//直到不产生进位
        return num1;
    }
}

74、把字符串转换成整数

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

输入描述:

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

输出描述:

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

示例1

输入

+2147483647
1a33

输出

2147483647
0

解题思路:

首先,需要确定第一个字符,来决定这个数是正数还是负数,然后再去过滤是否含有非数字的字符(利用ASCII码),最后需要注意得到结果值是否超过了int数值的表示范围。

public class Solution {
    public int StrToInt(String str) {
        if(str == "" || str.length() == 0) return 0;
        long sum = 0;//需要注意溢出情况,先用long接收
        int symbol = 1;
        if(str.charAt(0) == '-') {//负数的处理
            symbol = -1;
            str = str.substring(1, str.length());
        } else if(str.charAt(0) == '+') {//正数的处理
            str = str.substring(1, str.length());
        }
        char[] chars = str.toCharArray();
        for(int i = 0; i < chars.length; i++) {
            //非数字的字符返回0,0对应的ascii码是48,9对应的ascii码是57
            if(chars[i] < 48 || chars[i] > 57) {
                return 0;
            }
            //算出sum值,比如字符串是373,
            //那么第一次遍历sum = 0 * 10 + 51 - 48 = 3,
            //第二次遍历 sum = 3 * 10 + 55 - 48 = 37, 
            //第三次遍历 sum = 37 * 10 + 51 - 48 = 373
            sum = sum * 10 + chars[i] - 48;
        }
        sum = sum * symbol;//最后处理下正负即可。
        //最后需要判断下,sum的数值范围不能超过int数值表示范围,如果超出了就返回0
        if(sum < Integer.MAX_VALUE + 1 || sum > Integer.MAX_VALUE){
            return 0;
        }
        return (int)sum;
    }
}

75、构建乘积数组

给定一个数组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]。不能使用除法。

解题思路:

例如:A[]={1,2,3}求B[]
B[0]=A[1]×A[2]=2×3=6
B[1]=A[0]×A[2]=1×3=3
B[2]=A[0]×A[1]=1×2=2

1.B[0]初始化为1,从下标i=1开始,先求出C[i]的值并放入B[i],即B[i]=C[i]=C[i-1]×A[i-1],所以B[1]=B[1-1]×A[1-1]=B[0]×A[0]=1×1=1,i++

2.B[2]=B[2-1]×A[2-1]=B[1]×A[1]=1×2=2,i++超出长度停止循环

3.C[i]计算完毕求D[i],设置一个临时变量temp初始化为1

4.从后往前变量数组,LengthA=3初始化i=LengthA-2=1,结束条件为i>=0

5.第一次循环,temp=temp×A[i+1]=1×A[2]=3,计算出A中最后一个元素的值放入temp,temp相当于D[i]的值

6.因为之前的B[i]=C[i],所以让B[i]×D[i]就是要保存的结果,即B[i]=B[1]=B[1]×temp=1×3=3,i–=0

7.计算B[i]=B[0],temp上一步中的值是A[2],在这次循环中temp=temp×A[0+1]=A[2]×A[1]=3×2=6

8.B[i]=B[0]=B0]×temp=1×6=6,i–<0循环结束

所以B数组为{6,3,2}

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
       if (A == null || A.length < 2) {
            return null;
        }

        int[] result = new int[A.length];

        // result[0]取1
        result[0] = 1;
        for (int i = 1; i < A.length; i++) {
            // 第一步每个result[i]都等于于data[0]*data[1]...data[i-1]
            // 当i=n-1时,此时result[n-1]的结果已经计算出来了【A】
            result[i] = result[i -1] * A[i - 1];
        }

        // tmp保存data[n-1]*data[n-2]...data[i+1]的结果
        int tmp = 1;
        // 第二步求data[n-1]*data[n-2]...data[i+1]
        // 【A】result[n-1]的结果已经计算出来,所以从data.length-2开始操作
        for (int i = A.length - 2; i >= 0; i--) {
            tmp *= A[i + 1];
            result[i] *= tmp;
        }

        return result;
    }
}

76、正则表达式匹配

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

解题思路:

当模式中的第二个字符不是“*”时:

1、如果字符串第一个字符和模式中的第一个字符相匹配,那么字符串和模式都后移一个字符,然后匹配剩余的。 2、如果
字符串第一个字符和模式中的第一个字符相不匹配,直接返回false。

而当模式中的第二个字符是“*”时:

如果字符串第一个字符跟模式第一个字符不匹配,则模式后移2个字符,继续匹配。如果字符串第一个字符跟模式第一个字符匹配,可以有3种匹配方式:
1、模式后移2字符,相当于x*被忽略;
2、字符串后移1字符,模式后移2字符;
3、字符串后移1字符,模式不变,即继续匹配字符下一位,因为*可以匹配多位;

public class Solution {
    public boolean match(char[] str, char[] pattern)
    {   if(str == null || pattern == null) return false;
        return matchCore(str, 0, pattern, 0);
    }
    public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
         //有效性检验:str到尾,pattern到尾,匹配成功
        if (strIndex == str.length && patternIndex == pattern.length) {
            return true;
        }
        //pattern先到尾,匹配失败
        if (strIndex != str.length && patternIndex == pattern.length) {
            return false;
        }
        //模式第2个是*,且字符串第1个跟模式第1个匹配,分3种匹配模式;如不匹配,模式后移2位
        if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
            if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) {
                return matchCore(str, strIndex, pattern, patternIndex + 2)//模式后移2,视为x*匹配0个字符
                        || matchCore(str, strIndex + 1, pattern, patternIndex + 2)//视为模式匹配1个字符
                        || matchCore(str, strIndex + 1, pattern, patternIndex);//*匹配1个,再匹配str中的下一个
            } else {
                return matchCore(str, strIndex, pattern, patternIndex + 2); // 当前字母无法匹配的情况,所以也视为匹配了0次
            }
        }
        //模式第2个不是*,且字符串第1个跟模式第1个匹配,则都后移1位,否则直接返回false
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) {
            return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
        }
        return false;
    }
}

77、表示数值的字符串

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

解题思路:

  • 对于“+/-”: 正常来看它们第一次出现的话应该出现在字符串的第一个位置,如果它第一次出现在不是字符串首位,而且它的前面也不是“e/E”,那就不符合规则;如果是第二次出现,那么它就应该出现在“e/E”的后面,如果“+/-”的前面不是“e/E”,那也不符合规则。
  • 对于“e/E”: 如果它的后面不接任何数字,就不符合规则;如果出现多个“e/E”也不符合规则。
  • 对于“.”: 出现多个“.”是不符合规则的。还有“e/E”的字符串出现“.”也是不符合规则的。 同时,要保证其他字符均为 0-9 之间的数字。
public class Solution {
    public boolean isNumeric(char[] str) {
        if(str == null || str.length == 0) return false;
        int len = str.length;
        boolean sign = false, decimal = false, hasE = false;
        for(int i = 0; i < len; i++){
            if(str[i] == '+' || str[i] == '-'){
                if(!sign && i > 0 && str[i-1] != 'e' && str[i-1] != 'E')
                    return false;
                if(sign && str[i-1] != 'e' && str[i-1] != 'E')
                    return false;
                sign = true;
            }else if(str[i] == 'e' || str[i] == 'E'){
                if(i == len - 1)
                    return false;
                if(hasE)
                    return false;
                hasE = true;
            }else if(str[i] == '.'){
                if(hasE || decimal)
                    return false;
                decimal = true;
            }else if(str[i] < '0' || str[i] > '9')
                return false;
        }
        return true;
    }
}

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

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

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

解题思路:

解题思路很像之前的数组中重复第一个数字,遍历整个字符数组,利用一个LinkedHashMap,以字符为key, 出现的次数为value存储;重复出现累加次数。最后再遍历一遍字符串数组,只要在LinkedHashMap中找到第一个次数为1的字符返回,否则就返回#

import java.util.*;
public class Solution {
    private ArrayList<Character> mCharList = new ArrayList<>();
    private Map<Character, Integer> mHashMap = new LinkedHashMap<>(); 
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        mCharList.add(ch);
        if(mHashMap.get(ch) == null){
            mHashMap.put(ch, 1);
        } else {
            mHashMap.put(ch, Integer.valueOf(mHashMap.get(ch)) + 1);
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
         for(int i = 0; i < mCharList.size(); i++) {
             char key = mCharList.get(i);
             if(mHashMap.get(key) == 1) {
                 return key;
             }
         }
        return '#';
    }
}

79、和为S的连续正数序列

题目描述

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

输出描述:

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

解题思路:

这题有多种方法,这里采用暴力双循环遍历的方法,就是遍历累加和正好等于S的序列。

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> resultList = new ArrayList<>();
        for(int i = 1; i < sum; i++) {
            int tempSum = 0;
            ArrayList<Integer> tempList = new ArrayList<>();
            for(int j = i; j < sum; j++) {
                if(tempSum >= sum) {//如果相加的和大于sum,说此次序列不满足,跳出循环
                    break;
                }
                tempSum += j;//小于sum说明有可能满足,继续累加j
                tempList.add(j);//并继续把j加入到临时数组中
                if(tempSum == sum) {//如果正好等于sum,说明找到了一个满足条件的序列,并把它加入到resultList中,跳出此次查找开始下一次的查找
                   resultList.add(tempList);
                   break;
                }
            }
        }
        return resultList;
    }
}

80、为S的两个数字

题目描述

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

输出描述:

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

解题思路:

首先是递增有序的数组,想到使用二分查找,利用二分查找到sum和当前值的差值,利用二分查找时间复杂度O(n*logn),利用二分查找sum与当前数组值的差值,是否在剩余数组中,如果存在那么当前值和查找到的值的和就会等于S;可能会存在多对,所以先把第一对加入集合中.

如果遇到多对,就拿当前找到这一对的乘积数值和集合中存在的一对乘积数值做比较,如果小于就更新集合中那对数,直到遍历完后,剩下的肯定是乘积最小的那一对。

import java.util.ArrayList;
public class Solution {
    //利用二分查找时间复杂度O(n*logn)
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        if(array == null || array.length == 0) return new ArrayList<Integer>();
        ArrayList<Integer> resultList = new ArrayList<>();
        for(int i = 0; i < array.length; i++) {
            //利用二分查找sum与当前数组值的差值,是否在剩余数组中,如果存在那么当前值和查找到的值的和就会等于S
            int foundResult = binarySearch(array, i + 1, sum - array[i]);
            if(foundResult != -1) {
                //可能会存在多对,所以先把第一对加入集合中
                if(resultList.size() == 0){
                    resultList.add(array[i]);
                    resultList.add(array[foundResult]);
                } else {
                    //如果遇到多对,就拿当前找到这一对的乘积数值和集合中存在的一对乘积数值做比较,如果小于就更新集合中那对数,直到遍历完后
                    //剩下的肯定是乘积最小的那一对。
                    if(array[i] * array[foundResult] < resultList.get(0) * resultList.get(1)) {
                        resultList.set(0, array[i]);
                        resultList.set(1, array[foundResult]);
                    }
                }
            }
        }
        return resultList;
    }

    //首先是递增有序的数组,想到使用二分查找,利用二分查找到sum和当前值的差值
    public int binarySearch(int[] array, int start, int target) {
        int low = start;
        int high = array.length - 1;
        while(low <= high) {
            int mid = (low + high) >>> 1;
            if(target > array[mid]) {
                low = mid + 1;
            } else if (target < array[mid]) {
                high = mid - 1;
            } else {
                return mid;
            }
        }

        return -1;
    }
}

81、左旋转字符串

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

解题思路:

左旋字符串实际上就是一个字符循环队列,每循环左移一次就相当于把队头元素插入到队尾元素,直到循环次数结束,此时队列中的字符组成的字符串就是移位后的结果。

import java.util.*;
public class Solution {
    public String LeftRotateString(String str,int n) {
        if(str == null || str.length() == 0) return "";
        if(n == 0) return str;
        char[] chars = str.toCharArray();
        Queue<Character> strQueue = new LinkedList<Character>();
        for(int i = 0; i < chars.length; i++) {
            strQueue.offer(chars[i]);
        }
        while(n > 0 && !strQueue.isEmpty()){
            strQueue.offer(strQueue.poll());
            n--;
        }
        StringBuilder sb = new StringBuilder();
        while(!strQueue.isEmpty()) {
            sb.append(String.valueOf(strQueue.poll()));
        }
        return sb.toString();
    }
}

82、翻转单词顺序列

牛客最近来了一个新员工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[] tempStrList = str.split(" ");
        if(tempStrList.length == 0) {//需要考虑拆分空格的情况,假如只有一个空格
            return str;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = tempStrList.length - 1; i >=0; i--) {
            sb.append(tempStrList[i]);
            if(i > 0){
                sb.append(" ");
            }
        }
        return sb.toString();
    }
}

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

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

解题思路:

可以和约瑟夫环的问题联系在一起,约瑟夫问题来解决。
如果只求最后一个报数胜利者的话,我们可以用数学归纳法解决该问题,为了讨 论方便,先把问题稍微改变一下,并不影响原意:
问题描述:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人 继续从0开始报数。求胜利者的编号。
我们知道第一个人(编号一定是m%n-1) 出列之后,剩下的n-1个人组成了一个新 的约瑟夫环(以编号为k=m%n的人开始):
k k+1 k+2 … n-2, n-1, 0, 1, 2, … k-2并且从k开始报0。
现在我们把他们的编号做一下转换:
k –> 0
k+1 –> 1
k+2 –> 2


k-2 –> n-3
k-1 –> n-2
变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解: 例如x是最终的胜利者,那么根据上面这个表把这个x变回去不刚好就是n个人情 况的解吗?!!变回去的公式很简单,相信大家都可以推出来:x’=(x+k)%n。
令f[i]表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然是f[n]。
递推公式
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
有了这个公式,我们要做的就是从1-n顺序算出f[i]的数值,最后结果是f[n]。 因为实际生活中编号总是从1开始,我们输出f[n]+1。

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n == 0) return -1;
        int sum = 0;
        for(int i = 2; i <= n; i++) {
            sum = (sum + m) % i;
        }
        return sum;
    }
}

84、扑克牌顺子

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。

解题思路:

根据癞子数量分类讨论

import java.util.*;

public class Solution {
    public boolean isContinuous(int[] numbers) {
        if (numbers == null || numbers.length < 5) return false;
        Arrays.sort(numbers);
        int count = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == 0) {
                count++;
            }
        }

        if (count == 4) {//4个癞子,必定能组成顺子
            return true;
        } else if (count == 3) {//3个癞子,剩下的两张牌可以是相邻,或者为顺子的最大值和最小值,相差在1~4之间
            return (numbers[4] - numbers[3]) >= 1 
                    && (numbers[4] - numbers[3]) <= 4;
        } else if (count == 2) {//2个癞子,剩下的3张牌中最大值和最小值之差在2~4之间,2个癞子可以填充在3张牌之外,也可以填充在3张牌之间,还有一点要注意的3张牌中不能有重复的
            return (numbers[4] - numbers[2]) >= 2 
                    && (numbers[4] - numbers[2]) <= 4 
                    && (numbers[4] != numbers[3]) 
                    && (numbers[3] != numbers[2]);
        } else if (count == 1) {//1个癞子,剩下的4张牌中最大值和最小值之差在3~4之间,不能有重复的牌
            return (numbers[4] - numbers[1]) >= 3 
                    && (numbers[4] - numbers[1]) <= 4 
                    && (numbers[4] != numbers[3]) 
                    && (numbers[3] != numbers[2]) 
                    && (numbers[2] != numbers[1]);
        } else {//0个癞子,max-min==4,且不能有重复的牌
            return (numbers[4] - numbers[0]) == 4 
                    && (numbers[4] != numbers[3]) 
                    && (numbers[3] != numbers[2]) 
                    && (numbers[2] != numbers[1]) 
                    && (numbers[1] != numbers[0]);
        }
    }
}

85、把二叉树打印成多行

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

解题思路:

实际上就是二叉树的层序遍历, 使用队列

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        Queue<TreeNode> linkedQueue = new LinkedList<TreeNode>();
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if(pRoot == null) return new ArrayList<>();
        linkedQueue.offer(pRoot);
        while(!linkedQueue.isEmpty()) {
            int queueSize = linkedQueue.size();
            ArrayList<Integer> tempResultList = new ArrayList<>();
            for(int i = 0; i < queueSize; i++) {
                TreeNode current = linkedQueue.poll();
                tempResultList.add(current.val);
                if(current.left != null) {
                    linkedQueue.offer(current.left);
                }
                if(current.right != null) {
                    linkedQueue.offer(current.right);
                }
            }
            result.add(tempResultList);
        }
        return result;
    }
}

86、按之字形顺序打印二叉树

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

解题思路:

其实还是二叉树的层序遍历,只是加入的结果的顺序有所不同,奇数层是从左到右,偶数层是从右到左,所以利用count来统计当前层数,然后判断如果是奇数层,那么正常顺序add,如果是偶数层需要逆序插入。

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        Queue<TreeNode> linkedQueue = new LinkedList<TreeNode>();
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if(pRoot == null) return new ArrayList<>();
        int count = 0;
        linkedQueue.offer(pRoot);
        while(!linkedQueue.isEmpty()) {
            count++;
            int queueSize = linkedQueue.size();
            ArrayList<Integer> tempResultList = new ArrayList<>();
            for(int i = 0; i < queueSize; i++) {
                TreeNode current = linkedQueue.poll();
                if(count % 2 == 1){
                    tempResultList.add(current.val);
                } else {
                    tempResultList.add(0, current.val);
                }

                if(current.left != null) {
                    linkedQueue.offer(current.left);
                }
                if(current.right != null) {
                    linkedQueue.offer(current.right);
                }
            }
            result.add(tempResultList);
        }
        return result;
    }
}

87、剪绳子

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

输入描述:

输入一个数n,意义见题面。(2 <= n <= 60)

输出描述:

输出答案。

示例1

输入

8

输出

18

解题思路:

可以采用贪婪算法得到最优解

public class Solution {
    public int cutRope(int target) {
        if(target < 2) {
            return 0;
        }
        if(target == 2) {
            return 1;
        }
        if(target == 3) {
            return 2;
        }

        int timeOfThree = target / 3;//啥也不管,先尽可能减去长度为3的段
        if(target - timeOfThree * 3 == 1) {//判断还剩下多少,再进行处理
            timeOfThree -= 1;
        }

        int timeOfTwo = (target - timeOfThree * 3) / 2;
        return (int)((Math.pow(3, timeOfThree))*(Math.pow(2, timeOfTwo)));
    }
}

88、序列化二叉树

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

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

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

解题思路:

题目意思很简单,实际上就是遍历二叉树得到一个遍历序列,然后又通过遍历序列重构建一个二叉树,这里采用层序遍历的方式来解决。

import java.util.*;
public class Solution {
    String Serialize(TreeNode root) {
        if(root == null) return null;
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> linkedQueue = new LinkedList<TreeNode>();
        linkedQueue.offer(root);
        while(!linkedQueue.isEmpty()) {
            int queueSize = linkedQueue.size();
            for(int i = 0; i < queueSize; i++) {
                TreeNode current = linkedQueue.poll();
                if(current != null) {
                    sb.append(current.val + "!");
                    linkedQueue.offer(current.left);
                    linkedQueue.offer(current.right);
                } else {
                    sb.append("#" + "!");
                }
            }
        }
        if(sb.length() != 0) {//删除最后多余的一个!
            sb.deleteCharAt(sb.length() - 1);
        }
        return sb.toString();
  }
    TreeNode Deserialize(String str) {
        TreeNode head = null;
        if(str == null || str.length() == 0) {
            return head;
        }
        String[] nodes = str.split("!");
        TreeNode[] treeNodes = new TreeNode[nodes.length];
        for(int i = 0; i < nodes.length; i++) {
            if(!nodes[i].equals("#")) {
                treeNodes[i] = new TreeNode(Integer.valueOf(nodes[i]));
            }
        }
        for(int i = 0, j = 1; j < treeNodes.length; i++) {
            if(treeNodes[i] != null) {
                treeNodes[i].left = treeNodes[j++];
                treeNodes[i].right = treeNodes[j++];
            }
        }
        return treeNodes[0];
  }
}

89、数据流中的中位数

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

解题思路:

我们可以将数据排序后分为两部分,左边部分的数据总是比右边的数据小。那么,我们就可以用最大堆和最小堆来装载这些数据:

  • 最大堆装左边的数据,取出堆顶(最大的数)的时间复杂度是O(1)
  • 最小堆装右边的数据,同样,取出堆顶(最小的数)的时间复杂度是O(1)

从数据流中拿到一个数后,先按顺序插入堆中:如果左边的最大堆是否为空或者该数小于等于最大堆顶的数,则把它插入最大堆,否则插入最小堆。然后,我们要保证左边的最大堆的size等于右边的最小堆的size或者最大堆的size比最小堆的size大1。
要获取中位数的话,直接判断最大堆和最小堆的size,如果相等,则分别取出两个堆的堆顶除以2得到中位数,不然,就是最大堆的size要比最小堆的size大,这时直接取出最大堆的堆顶就是我们要的中位数。

import java.util.*;
public class Solution {
    private PriorityQueue<Integer> mRightHeap = new PriorityQueue<>();
    private PriorityQueue<Integer> mLeftHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {
        public int compare(Integer num1, Integer num2) {
            return num2 - num1;
        }
    });

    public void Insert(Integer num) {
       if(mLeftHeap.isEmpty() || num <= mLeftHeap.peek()) {
           mLeftHeap.offer(num);
       } else {
           mRightHeap.offer(num);
       }

        if(mLeftHeap.size() < mRightHeap.size()) {
            mLeftHeap.offer(mRightHeap.peek());
            mRightHeap.poll();
        } else if(mLeftHeap.size() - mRightHeap.size() == 2) {
            mRightHeap.offer(mLeftHeap.peek());
            mLeftHeap.poll();
        }
    }

    public Double GetMedian() {
        if(mLeftHeap.size() > mRightHeap.size()) {
            return new Double(mLeftHeap.peek());
        } else {
            return new Double(mLeftHeap.peek() + mRightHeap.peek()) / 2;
        }
    }
}

90、滑动窗口的最大值

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{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]}。

解题思路:

deque是一个双端队列,用来保存有可能是滑动窗口最大值数字的下标;
在存入一个数字的下标之前,首先要判断队列里已有数字是否小于待存入的数字,如果小于则以此从队列的尾部删除;
如果队列头部的数字已经从窗口滑出,那么滑出的数字也需要从队列的头部删除。

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> list = new ArrayList<>();
        Deque<Integer> deque = new LinkedList<Integer>();
        if(num == null || num.length == 0 || size <= 0 || size > num.length) {
            return list;
        }
        for(int i = 0; i < num.length; i++) {
            while(!deque.isEmpty() && num[i] > num[deque.peekLast()]) {
                deque.removeLast();
            }
            if(!deque.isEmpty() && i - deque.peekFirst() >= size) {
                deque.removeFirst();
            }
            deque.offer(i);
            if(i >= size - 1){
                list.add(num[deque.peekFirst()]);
            }
        }
        return list;
    }
}

91、矩阵中的路径

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径,但是矩阵中不包含”abcb”路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

解题思路:

举例分析

例如在下面的 3*4 的矩阵中包含一条字符串“bcced”的路径。但矩阵中不包含字符串“abcb”的路径,因为字符串的第一个字符 b 占据了矩阵中的第一行第二格子之后,路径不能再次进入这个格子。

a b c e 
s f c s 
a d e e

解题思路

这是一个可以用回朔法解决的典型题。首先,在矩阵中任选一个格子作为路径的起点。假设矩阵中某个格子的字符为 ch,那么这个格子不可能处在路径上的第 i 个位置。如果路径上的第 i 个字符不是 ch,那么这个格子不可能处在路径上的第 i 个位置。如果路径上的第 i 个字符正好是 ch,那么往相邻的格子寻找路径上的第 i+1 个字符。除在矩阵边界上的格子之外,其他格子都有 4 个相邻的格子。重复这个过程知道路径上的所有字符都在矩阵中找到相应的位置。

由于回朔法的递归特性,路径可以被开成一个栈。当在矩阵中定位了路径中前 n 个字符的位置之后,在与第 n 个字符对应的格子的周围都没有找到第 n+1 个字符,这个时候只要在路径上回到第 n-1 个字符,重新定位第 n 个字符。

由于路径不能重复进入矩阵的格子,还需要定义和字符矩阵大小一样的布尔值矩阵,用来标识路径是否已经进入每个格子。

当矩阵中坐标为(row,col)的格子和路径字符串中下标为 pathLength 的字符一样时,从 4 个相邻的格子 (row,col-1),(row-1,col),(row,col+1) 以及 (row+1,col) 中去定位路径字符串中下标为 pathLength+1 的字符。

如果 4 个相邻的格子都没有匹配字符串中下标为 pathLength+1 的字符,表明当前路径字符串中下标为pathLength的字符在矩阵中的定位不正确,我们需要回到前一个字符 (pathLength-1),然后重新定位。

一直重复这个过程,直到路径字符串上所有字符都在矩阵中找到合适的位置

 public static boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        // 参数校验
        if (matrix == null || matrix.length != rows * cols || str == null || str.length < 1) {
            return false;
        }

        // 变量初始化
        boolean[] visited = new boolean[rows * cols];
        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }

        // 记录结果的数组,
        int[] pathLength = {0};
        // 以每一个点为起始进行搜索
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (hasPathCore(matrix, rows, cols, str, visited, i, j, pathLength)) {
                    return true;
                }
            }
        }

        return false;
    }

    /**
     * 回溯搜索算法
     *
     * @param matrix     输入矩阵
     * @param rows       矩阵行数
     * @param cols       矩阵列数
     * @param str        要搜索的字符串
     * @param visited    访问标记数组
     * @param row        当前处理的行号
     * @param col        当前处理的列号
     * @param pathLength 已经处理的str中字符个数
     * @return 是否找到 true是,false否
     */
    private static boolean hasPathCore(char[] matrix, int rows, int cols, char[] str, boolean[] visited,
                                       int row, int col, int[] pathLength) {

        if (pathLength[0] == str.length) {
            return true;
        }

        boolean hasPath = false;

        // 判断位置是否合法
        if (row >= 0 && row < rows
                && col >= 0 && col < cols
                && matrix[row * cols + col] == str[pathLength[0]]
                && !visited[row * cols + col]) {

            visited[row * cols + col] = true;
            pathLength[0]++;

            // 按左上右下进行回溯
            hasPath = hasPathCore(matrix, rows, cols, str, visited, row, col - 1, pathLength)
                    || hasPathCore(matrix, rows, cols, str, visited, row - 1, col, pathLength)
                    || hasPathCore(matrix, rows, cols, str, visited, row, col + 1, pathLength)
                    || hasPathCore(matrix, rows, cols, str, visited, row + 1, col, pathLength);

            if (!hasPath) {
                pathLength[0]--;
                visited[row * cols + col] = false;
            }

        }

        return hasPath;
    }

92、机器人的运动范围

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

解题思路:

例如,当 k 为 18 时,机器人能够进入方格(35,37),因为 3+5+3+7=18 但它不能进入方格(35,38),因为 3+5+3+8=19 请问该机器人能够达到多少格子?

解题思路

和前面的矩阵中的路径类似,这个方格也可以看出一个 m*n 的矩阵。同样在这个矩阵中,除边界上的格子之外其他格子都有四个相邻的格子。

机器人从坐标(0,0)开始移动。当它准备进入坐标为(i,j)的格子时,通过检查坐标的数位和来判断机器人是否能够进入。如果机器人能够进入坐标为(i,j)的格子,我们接着再判断它能否进入四个相邻的格子(i,j-1)、(i-1,j),(i,j+1) 和 (i+1,j)。

 public static int movingCount(int threshold, int rows, int cols) {
        // 参数校验
        if (threshold < 0 || rows < 1 || cols < 1) {
            return 0;
        }

        // 变量初始化
        boolean[] visited = new boolean[rows * cols];
        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }

        return movingCountCore(threshold, rows, cols, 0, 0, visited);
    }

    /**
     * 递归回溯方法
     *
     * @param threshold 约束值
     * @param rows      方格的行数
     * @param cols      方格的列数
     * @param row       当前处理的行号
     * @param col       当前处理的列号
     * @param visited   访问标记数组
     * @return 最多可走的方格
     */
    private static int movingCountCore(int threshold, int rows, int cols,
                                       int row, int col, boolean[] visited) {

        int count = 0;

        if (check(threshold, rows, cols, row, col, visited)) {
            visited[row * cols + col] = true;
            count = 1
                    + movingCountCore(threshold, rows, cols, row - 1, col, visited)
                    + movingCountCore(threshold, rows, cols, row, col - 1, visited)
                    + movingCountCore(threshold, rows, cols, row + 1, col, visited)
                    + movingCountCore(threshold, rows, cols, row, col + 1, visited);
        }

        return count;
    }

    /**
     * 断机器人能否进入坐标为(row, col)的方格
     *
     * @param threshold 约束值
     * @param rows      方格的行数
     * @param cols      方格的列数
     * @param row       当前处理的行号
     * @param col       当前处理的列号
     * @param visited   访问标记数组
     * @return 是否可以进入,true是,false否
     */
    private static boolean check(int threshold, int rows, int cols,
                                 int row, int col, boolean[] visited) {
        return col >= 0 && col < cols
                && row >= 0 && row < rows
                && !visited[row * cols + col]
                && (getDigitSum(col) + getDigitSum(row) <= threshold);
    }

    /**
     * 一个数字的数位之和
     *
     * @param number 数字
     * @return 数字的数位之和
     */
    private static int getDigitSum(int number) {
        int result = 0;
        while (number > 0) {
            result += (number % 10);
            number /= 10;
        }

        return result;
    }

93、N叉树层序遍历(树的层序遍历)

N叉树的层序遍历

解题思路:

使用第三方容器队列实现

  //N叉树的层序遍历(队列结构-queue.size-加入值顺序-遍历结点顺序)
    public ArrayList<Integer> levelOrder(TreeNode root) {
        ArrayList<Integer> resultList = new ArrayList<>();
        if(root == null) return resultList;
        LinkedList<TreeNode> mLinkedQueue = new LinkedList<>();
        while(!mLinkedQueue.isEmpty()) {
            int queueSize = mLinkedQueue.size();
            for(int i = 0; i < queueSize; i++) {
                TreeNode current = mLinkedQueue.poll();
                if(current != null) {
                    resultList.add(current.val);
                    mLinkedQueue.addAll(current.children);
                }
            }
        }
        return resultList;
    }

94、N叉树先序遍历(递归、迭代实现)

N叉树的先序遍历

解题思路:

使用递归和迭代两种方法实现

    //递归实现
     //N叉树的先序遍历-递归
    public ArrayList<Integer> prevOrderReverse(TreeNode root) {
        ArrayList<Integer> resultList = new ArrayList<>();
        prevReverseResult(root, resultList);
        return resultList;
    }
    public void prevReverseResult(TreeNode root, ArrayList<Integer> resultList) {
        if(root == null) return;
        resultList.add(root.val);
        for(int i = 0; i < root.children.size(); i++) {
            prevReverseResult(root.children.get(i), resultList);
        }
    }
    //N叉树的先序遍历-递推 (栈结构-children.size-加入值顺序-遍历结点逆序)
    public ArrayList<Integer> prevOrder(TreeNode root) {
        ArrayList<Integer> resultList = new ArrayList<>();
        LinkedList<TreeNode> linkedStack = new LinkedList<>();
        if(root == null) return resultList;
        linkedStack.push(root);
        while(!linkedStack.isEmpty()) {
            TreeNode current = linkedStack.pop();
            if(current != null) {
                resultList.add(current.val);
                //注意: 逆序
                for(int i = current.children.size() - 1; i >=0; i--) {
                    linkedStack.push(current.children.get(i));
                }
            }
        }
        return resultList;
    }

95、N叉树后序遍历(递归、迭代实现)

N叉树的后序遍历

解题思路:

使用递归和迭代两种方法实现,借助栈数据结构

    //N叉树的后序遍历-递归
    public ArrayList<Integer> postOrderReverse(TreeNode root) {
        ArrayList<Integer> resultList = new ArrayList<>();
        postReverseResult(root, resultList);
        return resultList;
    }

    public void postReverseResult(TreeNode root, ArrayList<Integer> resultList) {
        if(root == null) return;
        //先访问孩子结点
        for(int i = 0; i < root.children.size(); i++) {
             postReverseResult(root.children.get(i), resultList);
        }
        //再访问根结点
        resultList.add(root.val);
    }

    //N叉树的后序遍历-递推 (栈结构-children.size()-加入值逆序-遍历结点顺序)
    public ArrayList<Integer> postOrder(TreeNode root) {
        ArrayList<Integer> resultList = new ArrayList<>();
        LinkedList<TreeNode> linkedStack = new LinkedList<>();
        if(root == null) return resultList;
        linkedStack.push(root);
         while(!linkedStack.isEmpty()) {
            TreeNode current = linkedStack.pop();
            if(current != null) {
                resultList.add(0, current.val);
                for(int i = 0; i < current.children.size(); i++) {
                    linkedStack.push(current.children.get(i));
                }
            }
        }
        return resultList;
    }

96、二叉树层序遍历

     //二叉树层序遍历(队列结构-queue.size-加入值顺序-遍历结点顺序)
     public ArrayList<Integer> levelBinaryTree(TreeNode root) {
         ArrayList<Integer> resultList = new ArrayList<>();
         LinkedList<TreeNode> linkedQueue = new LinkedList<>();
         if(root == null) return resultList;
         linkedQueue.offer(root);
         while(!linkedQueue.isEmpty()) {
             int queueSize = linkedQueue.size();
             for(int i = 0; i < queueSize; i++) {
                 TreeNode current = linkedQueue.poll();
                 if(current != null) {
                     resultList.add(current.val);
                     if(current.left != null) {
                         linkedQueue.offer(current.left);
                     }
                     if(current.right != null) {
                         linkedQueue.offer(current.right);
                     }
                 }
             }
         }
         return resultList;
     }

97、二叉树先序遍历(递归、迭代实现)

     //二叉树先序遍历-递归
    public ArrayList<Integer> prevOrderBinaryTree(TreeNode root) {
        ArrayList<Integer> resultList = new ArrayList<>();
        if(root == null) return resultList;
        prevOrderBinaryTreeReverse(root, resultList);
        return resultList;
    }

    public void prevOrderBinaryTreeReverse(TreeNode root, ArrayList<Integer> resultList) {
        if(root == null) return;
        //先访问根结点
        resultList.add(root.val);
        //再访问左子树
        prevOrderBinaryTreeReverse(root.left, resultList);
        //再访问右子树
        prevOrderBinaryTreeReverse(root.right, resultList);
    }

   //二叉树先序遍历-递推(栈结构-加入值顺序-遍历左右结点逆序,先加右孩子再是左孩子)
    public ArrayList<Integer> prevOrderBinaryTree(TreeNode root) {
        ArrayList<Integer> resultList = new ArrayList<>();
        LinkedList<TreeNode> linkedStack = new LinkedList<>();
        if(root == null) return resultList;
        linkedStack.push(root);
        while(!linkedStack.isEmpty()) {
            TreeNode current = linkedStack.pop();
            if(current != null) {
                resultList.add(current.val);
                //先右孩子
                if(current.right != null) linkedStack.push(current.right);
                //再左孩子
                if(current.left != null) linkedStack.push(current.left);
            }
        }
        return resultList;
    }

98、二叉树中序遍历(递归、迭代实现)

    //二叉树的中序遍历-递归
     public ArrayList<Integer> midOrderBinaryTree(TreeNode root) {
        ArrayList<Integer> resultList = new ArrayList<>();
        if(root == null) return resultList;
        midOrderBinaryTreeReverse(root, resultList);
        return resultList;
    }

    public void midOrderBinaryTreeReverse(TreeNode root, ArrayList<Integer> resultList) {
        if(root == null) return;
        //先访问左子树
        midOrderBinaryTreeReverse(root.left, resultList);
        //再访问根结点
        resultList.add(root.val);
        //再访问右子树
        midOrderBinaryTreeReverse(root.right, resultList);
    }
    //二叉树的中序遍历-递推
    public ArrayList<Integer> midOrderBinaryTree(TreeNode root) {
        ArrayList<Integer> resultList = new ArrayList<>();
        LinkedList<Integer> linkedStack = new LinkedList<>();
        if(root == null) return resultList;
        TreeNode current = root;
        while(current != null || linkedStack.isEmpty()) {
            while(current != null) {
                linkedStack.push(current);
                current = current.left;
            }
            if(!linkedStack.isEmpty()) {//若currentNode=null 栈不为空,则说明已沿左子树访问完一条路径, 从栈中弹出栈顶结点,并访问其右孩子
                current = linkedStack.pop();
                if(current != null) {
                    //访问该结点
                     resultList.add(current.val);
                    //访问currentNode结点的右孩子
                     current = current.right;
                }
            }
        }
        return resultList;
    }

99、二叉树后序遍历(递归、迭代实现)

    //二叉树后序遍历-递归
    public ArrayList<Integer> postOrderBinaryTree(TreeNode root) {
        ArrayList<Integer> resultList = new ArrayList<>();
        if(root == null) return resultList;
        postOrderBinaryTreeReverse(root, resultList);
        return resultList;
    }

    public void postOrderBinaryTreeReverse(TreeNode root, ArrayList<Integer> resultList) {
        if(root == null) return;
        //先访问左子树
        postOrderBinaryTreeReverse(root.left, resultList);
        //再访问右子树
        postOrderBinaryTreeReverse(root.right, resultList);
        //再访问根结点
        resultList.add(root.val);
    }
    //二叉树后序遍历-递推(栈结构-加入值顺序-遍历左右结点顺序,先加左孩子再是右孩子)
    public ArrayList<Integer> postOrderBinaryTree(TreeNode root) {
        ArrayList<Integer> resultList = new ArrayList<>();
        LinkedList<TreeNode> linkedStack = new LinkedList<>();
        if(root == null) return resultList;
        linkedStack.push(root);
        while(!linkedStack.isEmpty()) {
            TreeNode current = linkedStack.pop();
            if(current != null) {
                resultList.add(current.val);
                //先左孩子
                if(current.left != null) linkedStack.push(current.left);
                //再右孩子
                if(current.right != null) linkedStack.push(current.right);
            }
        }
        return resultList;
    }

100、二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.

示例 1:

输入:
3
/
9 20
/
15 7
输出: [3, 14.5, 11]
解释:
第0层的平均值是 3, 第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].

import java.util.*;
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> resultList = new ArrayList<>();
        if(root == null) return resultList;
        Queue<TreeNode> linkedQueue = new LinkedList<>();
        linkedQueue.offer(root);
        while(!linkedQueue.isEmpty()) {
            int queueSize = linkedQueue.size();
            double sum = 0;
            for(int i = 0; i < queueSize; i++) {
                TreeNode current = linkedQueue.poll();
                if(current != null) {
                    sum += current.val;
                    if(current.left != null) linkedQueue.offer(current.left);
                    if(current.right != null) linkedQueue.offer(current.right);
                }
            }
            resultList.add(sum * 1.0 / queueSize * 1.0);
        }
        return resultList;
    }
}

101、二叉树的层次遍历 II

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

例如:
给定二叉树 [3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回其自底向上的层次遍历为:

[
[15,7],
[9,20],
[3]
]

import java.util.*;
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> resultList = new ArrayList<>();
        if(root == null) return resultList;
        Queue<TreeNode> linkedQueue = new LinkedList<>();
        linkedQueue.offer(root);
        while(!linkedQueue.isEmpty()) {
            List<Integer> tempList = new ArrayList<>();
            int queueSize = linkedQueue.size();
            for(int i = 0; i < queueSize; i++) {
                TreeNode current = linkedQueue.poll();
                if(current != null) {
                    tempList.add(current.val);
                    if(current.left != null) linkedQueue.offer(current.left);
                    if(current.right != null) linkedQueue.offer(current.right);
                }
            }
            resultList.add(0, tempList);//逆序插入
        }
        return resultList;
    }
}

102、二叉树的最大深度

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回它的最大深度 3 。

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

103、N叉树的最大深度

给定一个 N 叉树,找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

例如,给定一个 3叉树 :

我们应返回其最大深度,3。

说明:

树的深度不会超过 1000。
树的节点总不会超过 5000。

class Solution {
    public int maxDepth(Node root) {
        if(root == null) return 0;
        int max = 0;
        for(int i = 0; i < root.children.size(); i++) {
            int depth = maxDepth(root.children.get(i));
            if(depth > max) {
                max = depth;
            }
        }
        return max + 1;
    }
}

104、叶子相同的树

请考虑一颗二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

举个例子,如上图所示,给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两颗二叉树的叶值序列是相同,那么我们就认为它们是 叶相似 的。

如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的,则返回 true;否则返回 false 。

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) return true;
        if(root1 == null || root2 == null) return false;
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        findLeafValueList(root1, list1);//找出root1所有叶子结点组成的序列
        findLeafValueList(root2, list2);//找出root2所有叶子结点组成的序列
        //一一对比遍历两个序列是否完全一一对应,如果是那么就是叶子相似的树
        for(int i = 0; i < list1.size(); i++) {
            if(list1.get(i) != list2.get(i)) {
                return false;
            }
        }
        return true;
    }
    //找出一颗树中所有叶子结点的序列
    public void findLeafValueList(TreeNode root, List<Integer> list) {
        if(root == null) return;
        if(root.left == null && root.right == null) {
            list.add(root.val);
        }
        findLeafValueList(root.left, list);
        findLeafValueList(root.right, list);
    }
}

105、合并二叉树

的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
输出:
合并后的树:
3
/
4 5
/ \ \
5 4 7
注意: 合并必须从两个树的根节点开始。

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

106、二叉树的最小深度

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回它的最小深度 2.

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right != null) return minDepth(root.right) + 1;//左子树为null情况下,看右子树最小深度
        if(root.right == null && root.left != null) return minDepth(root.left) + 1;//右子树为null情况下,看左子树最小深度
        //左右子树都不为null情况下,取左右子树深度的最小值
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
     }
}

107、二叉树的所有路径

给定一个二叉树,返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

1
/
2 3

5

输出: [“1->2->5”, “1->3”]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> resultList = new ArrayList<String>();
        if(root == null) return resultList;
        getPath(root, new String(), resultList);
        return resultList;
    }

    public void getPath(TreeNode root, String sb, List<String> resultList) {
        if(root == null) return;
        if(root.left == null && root.right == null) {//到达叶子结点,产生一个条路径
            resultList.add(sb + root.val);
        } else {
            getPath(root.left, sb + root.val + "->", resultList);
            getPath(root.right, sb + root.val + "->", resultList);
        }
    }
}

108、二叉树的坡度

给定一个二叉树,计算整个树的坡度。

一个树的节点的坡度定义即为,该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。

整个树的坡度就是其所有节点的坡度之和。

示例:

输入:
1
/
2 3
输出: 1
解释:
结点的坡度 2 : 0
结点的坡度 3 : 0
结点的坡度 1 : |2-3| = 1
树的坡度 : 0 + 0 + 1 = 1
注意:

任何子树的结点的和不会超过32位整数的范围。
坡度的值不会超过32位整数的范围。

class Solution {
    public int findTilt(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) return 0;
        int leftTilt = getTreeTilt(root.left);
        int rightTilt = getTreeTilt(root.right);
        return Math.abs(leftTilt - rightTilt) + findTilt(root.left) + findTilt(root.right);
    }

    public int getTreeTilt(TreeNode root) {
        if(root == null) return 0;
        return root.val + getTreeTilt(root.left) + getTreeTilt(root.right);
    }
}

109、根据二叉树创建字符串

你需要采用前序遍历的方式,将一个二叉树转换成一个由括号和整数组成的字符串。

空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

示例 1:

输入: 二叉树: [1,2,3,4]
1
/
2 3
/
4

输出: “1(2(4))(3)”

解释: 原本将是“1(2(4)())(3())”,
在你省略所有不必要的空括号对之后,
它将是“1(2(4))(3)”。
示例 2:

输入: 二叉树: [1,2,3,null,4]
1
/
2 3
\
4

输出: “1(2()(4))(3)”

class Solution {
    private StringBuilder sb = new StringBuilder();
    public String tree2str(TreeNode t) {
        if(t == null) {
           return "";
        }
        sb.append(""+t.val);
        if(t.left != null) {
            sb.append("(");
            tree2str(t.left);
            sb.append(")");
        } else {
            if(t.right != null) {
                sb.append("()");
            }
        }
        if(t.right != null) {
            sb.append("(");
            tree2str(t.right);
            sb.append(")");
        }

        return sb.toString();
    }
}

110、相同的树

给定两个二叉树,编写一个函数来检验它们是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

输入: 1 1
/ \ /
2 3 2 3

    [1,2,3],   [1,2,3]

输出: true
示例 2:

输入: 1 1
/
2 2

    [1,2],     [1,null,2]

输出: false
示例 3:

输入: 1 1
/ \ /
2 1 1 2

    [1,2,1],   [1,1,2]

输出: false

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        if(p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

111、将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

  0
 / \

-3 9
/ /
-10 5

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null || nums.length == 0) return null;
        return buildTree(nums, 0, nums.length - 1);
    }
    public TreeNode buildTree(int[] nums, int low, int high) {
        if(low > high) return null;
        int mid = (low + high) >>> 1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildTree(nums, low, mid - 1);
        root.right = buildTree(nums, mid + 1, high);
        return root;
    }
}

112、把二叉搜索树转换为累加树

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如:

输入: 二叉搜索树:
5
/
2 13

输出: 转换为累加树:
18
/
20 13

class Solution {
    private int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root == null) return null;
        travel(root);
        return root;
    }
    public void travel(TreeNode root) {
        if(root == null) return;
        travel(root.right);
        sum += root.val;
        root.val = sum;
        travel(root.left);
    }
}

113、翻转二叉树

翻转一棵二叉树。

示例:

输入:

 4

/
2 7
/ \ /
1 3 6 9
输出:

 4

/
7 2
/ \ /
9 6 3 1

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

114、左叶子之和

计算给定二叉树的所有左叶子之和。

示例:

3

/
9 20
/
15 7

在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) return 0;
        return leftLeaves(root, root.left) + leftLeaves(root, root.right);
    }

    public int leftLeaves(TreeNode parent, TreeNode current) {
        if(current == null) return 0;
        if(current.left == null && current.right == null && parent.left == current) {
            return current.val;
        }
        return leftLeaves(current, current.left) + leftLeaves(current, current.right);
    }
}

115、路径之和

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树,以及目标和 sum = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        sum = sum - root.val;
        if(root.left == null && root.right == null) {
            return sum == 0;
        }
        return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    }
}

116、单值二叉树

如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时,才返回 true;否则返回 false。

示例 1:

输入:[1,1,1,1,1,null,1]
输出:true
示例 2:

输入:[2,2,2,5,2]
输出:false

class Solution {
    public boolean isUnivalTree(TreeNode root) {
        if(root == null) return true;
        if(root.left != null && root.left.val != root.val) {
            return false;
        }
        if(root.right != null && root.right.val != root.val) {
            return false;
        }
        return isUnivalTree(root.left) && isUnivalTree(root.right);
    }
}

117、二叉树的直径

给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 :
给定二叉树

      1
     / \
    2   3
   / \     
  4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意:两结点之间的路径长度是以它们之间边的数目表示。

class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return max;
    }

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

118、回文数(对称数)

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

示例 1:

输入: 121
输出: true
示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

import java.util.*;
class Solution {
    public boolean isPalindrome(int x) {
        if(x == 0) return true;
        if(x < 0)  return false;
        List<Integer> resultList = new ArrayList<>();
        while(x > 0) {
            resultList.add(x % 10);
            x /= 10;
        }
        int k = 0;
        int size = resultList.size();
        while(k < size / 2) {
            if(resultList.get(k) != resultList.get(size - k - 1)) {
                return false;
            }
            k++;
        }
        return true; 
    }
}

119、整数反转(注意int溢出)

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

示例 1:

输入: 123
输出: 321
示例 2:

输入: -123
输出: -321
示例 3:

输入: 120
输出: 21
注意:

假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

import java.util.*;
class Solution {
    public int reverse(int x) {
        int symbol = 1;
        if(x == 0) {
           return 0;
        } else if(x < 0) {
            symbol = -1;
            x = Math.abs(x);
        } else {
            symbol = 1;
        }

        List<Integer> resultList = new ArrayList<>();
        while(x > 0) {
            resultList.add(x % 10);
            x /= 10;
        }
        long sum = 0;
        int size = resultList.size();
        for(int i = 0; i < size; i++) {
            sum += resultList.get(i) * Math.pow(10, size - i - 1);
        }
        if(sum > Integer.MAX_VALUE) {
            return 0;
        }
        return symbol * (int)sum;
    }
}

120、合并两个有序数组

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p = m - 1;
        int q = n - 1;
        int size = m + n - 1;
        while(p >= 0 && q >= 0) {
            if(nums1[p] > nums2[q]) {
               nums1[size--] = nums1[p--];
            } else {
               nums1[size--] = nums2[q--]; 
            }
        }
        System.arraycopy(nums2, 0, nums1, 0, q + 1);
    }
}

121、排序之冒泡排序

    //BubbleSort O(n^2)
    public static int[] bubbleSort(int[] numbers) {
        if (numbers == null) {
            return new int[]{};
        }
        int len = numbers.length;
        //外层控制循环次数,对于长度为len长度的数,只需循环len - 1次
        for (int i = 0; i < len - 1; i++) {
            //内层控制循环次数,len - i,所以为了保证arr[j+1]不越界,j<len-i-1
            for (int j = 0; j < len - i - 1; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    int temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
        }
        return numbers;
    }

122、排序之选择排序

    //SelectSort O(n^2)
    public static int[] selectSort(int[] numbers) {
        if (numbers == null) return new int[]{};
        int len = numbers.length;
        for (int i = 0; i < len - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < len; j++) {
                if (numbers[minIndex] > numbers[j]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = numbers[minIndex];
                numbers[minIndex] = numbers[i];
                numbers[i] = temp;
            }
        }
        return numbers;
    }

123、排序之插入排序

    //InsertSort O(n^2)
    public static int[] insertSort(int[] numbers) {
        if (numbers == null) {
            return new int[]{};
        }
        int len = numbers.length;
        for (int i = 1; i < len; i++) {//i控制循环次数,因为已经默认第一个数的位置是正确的,所以i的起始值为1,i<len,循环len-1次
            int j = i;
            int target = numbers[j];//取出目标数
            while (j > 0 && target < numbers[j - 1]) {//如果目标数比前一个小,就不断向前比较
                numbers[j] = numbers[j - 1];//将numbers中j之前元素整体向后移动一位
                j--;
            }
            numbers[j] = target;//直到找到目标数比前一个数要大的时候,该j位置就是目标数要插入的位置
        }
        return numbers;
    }

124、排序之希尔排序

    //ShellSort O(n^2), 增量版的插入排序
    public static int[] shellSort(int[] numbers) {
        if (numbers == null) return new int[]{};
        int len = numbers.length;
        int k = len / 2;
        while (k > 0) {
            for (int i = k; i < len; i++) {
                int j = i;
                int target = numbers[j];
                while (j >= k && target < numbers[j - k]) {
                    numbers[j] = numbers[j - k];
                    j -= k;
                }
                numbers[j] = target;
            }
            k /= 2;
        }

        return numbers;
    }

125、排序之归并排序

    //MergeSort O(n*logn) 归并排序
    private static int[] mergeSort(int[] numbers, int left, int right) {
        int mid = (left + right) >>> 1;
        if (left < right) {
            mergeSort(numbers, left, mid - 1);
            mergeSort(numbers, mid + 1, right);
            mergeResult(numbers, left, mid, right);
        }
        return numbers;
    }

    private static void mergeResult(int[] numbers, int left, int mid, int right) {
        int[] tempArr = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            tempArr[k++] = numbers[i] <= numbers[j] ? numbers[i++] : numbers[j++];
        }

        while (i <= mid) {
            tempArr[k++] = numbers[i++];
        }

        while (j <= right) {
            tempArr[k++] = numbers[j++];
        }
        System.arraycopy(tempArr, 0, numbers, left, tempArr.length);
    }

126、排序之快速排序

    //QuickSort O(n*logn)快速排序
    private static int[] quickSort(int[] numbers, int left, int right) {
        if (left >= right) return new int[]{};
        int basic = numbers[left];
        int i = left;
        int j = right;
        while (i < j) {
            while (numbers[j] >= basic && i < j) {
                j--;
            }
            while (numbers[i] <= basic && i < j) {
                i++;
            }
            int temp = numbers[j];
            numbers[j] = numbers[i];
            numbers[i] = temp;
        }
        numbers[left] = numbers[i];
        numbers[i] = basic;
        quickSort(numbers, left,  j - 1);
        quickSort(numbers, j + 1, right);
        return numbers;
    }

127、排序之堆排序

//HeapSort O(n*logn)堆排序
public static int[] headSort(int[] numbers) {
        if (numbers == null) {
            return new int[]{};
        }
        int len = numbers.length;
        //初始化大顶堆(从最后一个非叶节点开始,从左到右,由下到上)
        for (int i = len / 2 - 1; i >= 0; i--) {
            adjustHeap(numbers, i, len);
        }
        //将顶节点和最后一个节点互换位置,再将剩下的堆进行调整
        for (int j = len - 1; j > 0; j--) {
            swap(numbers, 0, j);
            adjustHeap(numbers, 0, j);
        }

        return numbers;
    }


    /**
     * 整理树让其变成堆
     *
     * @param arr 待整理的数组
     * @param i   开始的结点
     * @param j   数组的长度
     */
    public static void adjustHeap(int[] arr, int i, int j) {
        int temp = arr[i];//定义一个变量保存开始的结点
        //k就是该结点的左子结点下标
        for (int k = 2 * i + 1; k < j; k = 2 * k + 1) {
            //比较左右两个子结点的大小,k始终记录两者中较大值的下标
            if (k + 1 < j && arr[k] < arr[k + 1]) {
                k++;
            }
            //经子结点中的较大值和当前的结点比较,比较结果的较大值放在当前结点位置
            if (arr[k] > temp) {
                arr[i] = arr[k];
                i = k;
            } else {//说明已经是大顶堆
                break;
            }
        }
        arr[i] = temp;
    }

    /**
     * 交换数据
     *
     * @param arr
     * @param num1
     * @param num2
     */
    public static void swap(int[] arr, int num1, int num2) {
        int temp = arr[num1];
        arr[num1] = arr[num2];
        arr[num2] = temp;
    }

   转载规则


《剑指Offer》 mikyou 采用 知识共享署名 4.0 国际许可协议 进行许可。
 本篇
剑指Offer 剑指Offer
剑指Offer1、二维数组中的查找(1) 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 解
下一篇 
Android中Retrofit2框架源码解析 Android中Retrofit2框架源码解析
Android中Retrofit2框架源码解析一、Retrofit简介1、阐述 Retrofit是一个基于Restful的HTTP网络请求框架(实际上内部真正网络请求是交由OkHttp去实现的),换句话说Retrofit实际上是一个负责网络
2020-02-03
  目录