Lintcode记录
摘要:Lintcode
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 }else {
if(l<m){
for (int i=nums.size()/2;i<nums.size();i++){
if(nums.get(i)<min){
min=nums.get(i);
index=i;
}
}
}else {
for (int i=nums.size()-1;i>=0;i--){
if(nums.get(i)<min){
min=nums.get(i);
index=i;
}
}
}
}
//从最小位置开始
List temp=new ArrayList<Integer>();
for (int i=index;i<size;i++){
temp.add(nums.get(i));
}
for (int i=0;i<index;i++){
temp.add(nums.get(i));
}
nums.clear();
nums.addAll(temp);
}
}
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<Integer> 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;
}