刷算法题的第1天

1、最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

题目链接：

https://leetcode-cn.com/problems/longest-increasing-subsequence/

这个题目有两种解法，第一种的时间复杂度是O(n^2)，第二种的时间复杂度是O(nlog(n))

1.1 LIS第一种解法

使用动态规划的方法去做

可以先定义一个dp数组，通过Arrays.fill()方法将dp数组中都初始化为1
动态规划中，状态转移方程可以这么来表示（假设当前的所有dp都已经知道了）

for(int j = 0; j < i; j++){
	if(nums[i] > nums[j]){
		dp[i] = Math.MAX(dp[i],dp[j] + 1);
	}
}

那么既然已经知道了一个，前面的那几个用数学归纳法一看就知道了，就是再遍历一次nums即可
最后的话，再从dp[]数组里面找到值最大的那个即可

动态规划的代码如下所示：

	public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int result = 0;
        for (int i = 0; i < dp.length; i++) {
            result = Math.max(result, dp[i]);
        }
        return result;
    }

1.2 LIS的第二种解法

联想到扑克牌的方法，再结合寻找最左侧二分查找的方法来，时间复杂度为O(nlogn)，相较于第一种方法的时间复杂度又提升了一级。

首先的话是定义扑克牌的堆数piles （最后返回的最长递增子序列的数也就是这个堆数piles）
把nums[]数组中的每一个元素取出来，通过寻找最左侧二分查找的代码把这个元素放入相应的堆当中
如果left的值和堆piles的值相等的话，那么piles应当执行piles++，说明此时要新建一个堆了
执行完成之后，需要把我们的poker(也就是每次取出来的那个进行比较的数字)放入到这个堆的最上面，也就是 top[left] = poker;

代码如下所示：

    public int lengthOfLIS(int[] nums) {
        int[] top = new int[nums.length];
        int piles = 0;
        for (int i = 0; i < nums.length; i++) {
            int poker = nums[i];
            int left = 0;
            int right = piles;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (top[mid] > poker) {
                    right = mid;
                } else if (top[mid] < poker) {
                    left = mid + 1;
                } else if (top[mid] == poker) {
                    right = mid;
                }
            }
            if (left == piles) {
                piles++;
            }
            top[left] = poker;
        }
        return piles;
    }

2.俄罗斯套娃信封问题

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。注意：不允许旋转信封。

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出：3 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

题目链接：

https://leetcode-cn.com/problems/russian-doll-envelopes/

分析：

首先对于这道题目来说，是一个二维数组，分析这道题目，其实就是上面第一小题的最长递增子序列的升级版，只不过上面那题是一维数组，现在的话变成了二维数组了。
解决的思路的话，先对二维数组进行排序，按照第一个数组从小到大排序，如果两个数都相同的话，就比较第二个数，将第二个数进行降序排序即可
排序的话，可以使用Arrays.sort()方法来进行排序，里面可以进行重写compare()方法，对于我们这道题目的规则来说，比较的代码就是return a[0]==b[0] ? b[1] - a[1] : a[0] - b[0]，代码就是这样，按照逆序的话，就是b[1]-a[1]，b[1]在前
排好序之后，其中的第二个数就可以看成是最长递增子序列了
然后再套用最长递增子序列的扑克牌方法即可，时间复杂度是O(nlog(n))

	public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
            }
        });
        int piles = 0;
        int[] top = new int[envelopes.length];
        for (int i = 0; i < envelopes.length; i++) {
            int poker = envelopes[i][1];
            int left = 0;
            int right = piles;
            while (left < right){
                int mid = left + (right - left) / 2;
                if (top[mid] > poker){
                    right = mid;
                }else if (top[mid] < poker){
                    left = mid + 1;
                }else if (top[mid] == poker){
                    right = mid;
                }
            }
            if (left == piles){
                piles++;
            }
            top[left] = poker;
        }
        return piles;
    }

3、判断子序列

题目描述：

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

题目链接：

https://leetcode-cn.com/problems/is-subsequence/submissions/

分析：

这道题目的话，用双指针就可以解决
一个指针指向的是字符串s,另外一个指针指向的是字符串t
通过charAt()方法不断的将s中的每个数字和t中的每个数字进行对比，如果两个数字相同的话，两个指针就都加1，否则的话，就只加指向t的指针即可
while循环退出的条件就是i < s.length() && j < t.length()

具体代码如下：

public boolean isSubsequence(String s, String t){
        int i = 0;
        int j = 0;
        while (i < s.length() && j < t.length()){
            if (s.charAt(i) == t.charAt(j)){
                i++;
                j++;
            }else {
                j++;
            }
        }
        return i == s.length();
    }

4、阶乘后的零

题目描述：给定一个整数 n ，返回 n! 结果中尾随零的数量。提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

输入：n = 3 输出：0 解释：3! = 6 ，不含尾随 0

题目链接：

https://leetcode-cn.com/problems/factorial-trailing-zeroes/submissions/

分析：

首先我们肯定不能一个个的去把对应的那些阶乘算出来，毕竟这个很大
那么我们从题目的角度进行分析，题目中表明的是判断阶乘后的0有几个，那么我们举个栗子，10×10 = 100，末尾含有1个0再乘上末尾含有1个零，结果就是末尾含有2个零，加起来就行。
那么就只要考虑阶乘中有多少个0就可以，然后把这些0都加起来就是最终返回的结果了
构成0的基本要素主要是2和5，2的话，其它偶数中很容易找到，现在的话，就是要是有5的，比如10，15，20，25，其中，25（可以拆成5和5，算2个），再深入一些，比如现在给的数字n是25，那么现在可以拆成5，10，15，20，25，25（25中含有2个5相乘），同理可得125可以拆成3个5相乘，算3个
那么代码就很容易实现了，先定义一个divisor为5（可以设为long类型[-2的63次，+2的63次减1]，万一数字大溢出了就不好了），和一个result用于存放最后要进行返回的值，每次在while循环里面，让n / divisor,把结果再加到result上面，然后再让divisor *= 5，这一步主要是找有没有含有多个5的，代码如下：

public int trailingZeroes(int n){
	int result = 0;
	long disivor = 5;
	while(n >= disivor){
		result += n / disivor;
		disivor *= 5; 
	}
	return result;
}

5、阶乘函数后K个零

题目描述： f(x) 是 x! 末尾是 0 的数量。（回想一下 x! = 1 * 2 * 3 * ... * x，且 0! = 1 ）

例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。给定 K，找出多少个非负整数 x ，能满足 f(x) = K

题目链接：

https://leetcode-cn.com/problems/preimage-size-of-factorial-zeroes-function/

分析：

这道题目的话，是告诉我们具体有多少个0，命名是K，然后需要求出符合这些具体K的的数字一共有多少个
文字有点晦涩难懂，举个栗子，比如现在给的一个K是4，就是说有结尾有4个0存在，那么也肯定是有4个5存在的（5和2相乘后末尾才有可能是0），我们可以举出来，5，10，15，20，那么20的话，阶乘之后的末尾肯定是4个0的，那么21、22、23、24的阶乘的末尾也肯定是有4个0的，（19的话不是，因为19的话，最多只有3个5，最多也只能构成3个0）
既然第二步我们已经分析出来了，从20~24共5个元素符合末尾是4个0的，那么我们就套用一下第4小题的那个函数，用来求出某个数结尾含有多少个0
用了第三步骤的那个函数之后，我们可以想象出一个nums[]数组，数组里面存放的是含有多少个0的重复数字，比如[1,2,2,2,2,2,3,3,3],然后我们需要求出2的最左侧的位置下标和2的最右侧位置下标，把这两个下标相减再加一就是最终返回的数了
因为这个数组是有序的，所以我们可以用寻找最左侧和寻找最右侧的二分查找算法来进行运算
【注意】这里需要提醒的是，k的取值范围是[0,10^9]，这个k是很大的，并且通过知道某个值求末尾含有多少个0的这个trailingZeroes()函数来说，它的原始的那些数字更加大了，所以我们的最右侧接收的数据类型定为是long类型，因为二分查找需要知道它的搜索区间，目前只知道最小的下界是0，而最大的上界不知道，并且这个上界很大，所以我们将它这个无穷大定为是Long.MAX_VALUE,（如果是int类型的话，就定义为Integer.MAX_VALUE），具体的代码如下所示：

	public int preimageSizeFZF(int k) {
        return (int)(right_bound(k) - left_bound(k) + 1);
    }
    
    public long trailingZeroes(long n){
        long result = 0;
        long disivor = 5;
        while (n >= disivor){
            result += n / disivor;
            disivor *= 5;
        }
        return result;
    }

    public long left_bound(int k){
        long left = 0;
        long right = Long.MAX_VALUE;
        while (left < right){
            long mid = left + (right - left) / 2;
            if (trailingZeroes(mid) > k){
                right = mid;
            }else if (trailingZeroes(mid) < k){
                left = mid + 1;
            }else if (trailingZeroes(mid) == k){
                right = mid;
            }
        }
        return left;
    }

    public long right_bound(int k){
        long left = 0;
        long right = Long.MAX_VALUE;
        while (left < right){
            long mid = left + (right - left) / 2;
            if (trailingZeroes(mid) > k){
                right = mid;
            }else if (trailingZeroes(mid) < k){
                left = mid + 1;
            }else if(trailingZeroes(mid) == k){
                left = mid + 1;
            }
        }
        return left - 1;
    }