Lintcode记录
- 作者:
- 淡白
- 创建时间：
- 2020-05-13 18:39:01
- lintcode
摘要：这篇文章包含了三个题目的代码和解题思路。首先是39-恢复旋转排序数组，这个题目要求将一个旋转排序数组恢复成原来的排序数组。代码中使用了寻找最小值的方法来确定旋转的起点，并将数组重新排列。接下来是2-尾部的零，这个题目要求给定一个整数n，计算n的阶乘末尾零的个数。代码中使用了分解因子的方法来计算零的个数。最后是44-最小子数组，这个题目要求找到一个数组中和最小的子数组。代码中使用了动态规划的方法来找到最小子数组。
39-恢复旋转排序数组
public static void recoverRotatedSortedArray(List nums) {
if(nums!=null&&nums.size()>1){
//长度2直接调换
if(nums.size()==2){
if(nums.get(0)>nums.get(1)){
nums.add(0,nums.get(0)+nums.get(1));
nums.add(1,nums.get(0)-nums.get(1));
nums.add(0,nums.get(0)-nums.get(1));
}
return;
}
int f=nums.get(0);
int l=nums.get(nums.size()-1);
int m=nums.get(nums.size()/2);
int min=nums.get(0);
int index=0;
int size=nums.size();
//判断循环起点
if(f>l){
if(f=0;i--){
if(nums.get(i)();
for (int i=index;i 2-尾部的零
//这题我原来是算出递归,却发现在遇到非常大的数时通过不了,后来看了解答,才知道可以通过分解因子来实现
//可以将每个数拆分成其素因子的乘积，可以发现，0是由2*5产生的，而5的数量一定小于2的数量，因此5的个数决定了结尾0的个数。
//只要计算n的阶乘中，5这个素因子出现多少次即可。
public static long trailingZeros(long n) {
long sum = 0;
while (n != 0) {
sum += n / 5;
n /= 5;
}
return sum;
}
44. 最小子数组
public static int minSubArray(final List nums) {
// 空判断
if (nums == null || nums.size() == 0) {
return 0;
}
// 初始值
int sum = nums.get(0);
int min = nums.get(0);
// 循环list
for (int i = 1; i < nums.size(); i++) {
// 为啥是大于0 因为本函数取值是最小连续数组以0为分界线
if (sum > 0) {
sum = nums.get(i);
} else {
sum += nums.get(i);
}
// 当前子数组和是否小于最小值
if (sum < min) {
min = sum;
}
}
return min;
}