classMinStack{ Stack<Integer> min; Stack<Integer> stack; publicMinStack(){ stack = new Stack<>(); min = new Stack<>(); } publicvoidpush(int val){ if (stack.isEmpty()) { stack.push(val); min.push(val); } else { stack.push(val); if (val < min.peek()) { min.push(val); } else { min.push(min.peek()); } } } publicvoidpop(){ if (stack.isEmpty()) {} stack.pop(); min.pop(); } publicinttop(){ return stack.peek(); } publicintgetMin(){ return min.peek(); } }
/** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */
如何求出最大公约数
求出两个正整数的最大公约数。
枚举
从较小整数的一半开始遍历到2,首次出现了两个正整数都整除的数,则该数就是两个正整数的最大公约数。
1 2 3 4 5 6 7 8 9 10 11 12 13
publicstaticintgetGreatestCommonDivisor(int a, int b){ int max = Math.max(a, b); int min = Math.min(a, b); if (max % min == 0) { return min; } for (int i = min / 2; i > 1; i--) { if (min % i == 0 && max % i == 0) { return i; } } return1; }
时间复杂度为O(min(a, b))
辗转相除法(欧几里得算法)
这个方法基于一个定理:
两个正整数a和b(a > b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
1 2 3 4 5 6 7 8
publicstaticintgetGreatestCommonDivisor(int a, int b){ int max = Math.max(a, b); int min = Math.min(a, b); if (max % min == 0) { return min; } return getGreatestCommonDivisor(max % min, min); }
publicstaticintgetGreatestCommonDivisor(int a, int b){ if (a == b) { return a; } int max = Math.max(a, b); int min = Math.min(a, b); return getGreatestCommonDivisor(max - min, min); }
避免了大数取模的计算,但是算法性能不稳定,最坏的时间复杂度为O(max(a, b))
更优算法
当a和b均为偶数时,gcd(a,b) = 2 * gcd(a / 2, b / 2) = 2 * gcd(a >> 1, b >> 1) = gcd(a >> 1, b >> 1) << 1;
当a为偶数,b为奇数时,gcd(a, b) = gcd(a / 2, b) = gcd(a >> 1, b);
当a为奇数,b为偶数时,gcd(a, b) = gcd(a, b / 2) = gcd(a, b >> 1);
当a和b均为奇数时,先利用更相减损术运算一次,gcd(a, b) = gcd(b, a - b),此时a - b必是偶数,然后进行上面情况的运算。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
publicstaticintgetGreatestCommonDivisor(int a, int b){ if (a == b) { return a; } if ((a & 1) == 0 && (b & 1) == 0) { return getGreatestCommonDivisor(a >> 1, b >> 1) << 1; } elseif ((a & 1) == 0 && (b & 1) != 0) { return getGreatestCommonDivisor(a >> 1, b); } elseif ((a & 1) != 0 && (b & 1) == 0) { return getGreatestCommonDivisor(a, b >> 1); } else { int max = Math.max(a, b); int min = Math.min(a, b); return getGreatestCommonDivisor(max - min, min); } }
进行简化之后为
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
publicstaticintgetGreatestCommonDivisor(int a, int b){ if (a == b) { return a; } if ((a & 1) == 0 && (b & 1) == 0) { return getGreatestCommonDivisor(a >> 1, b >> 1) << 1; } elseif ((a & 1) == 0) { return getGreatestCommonDivisor(a >> 1, b); } elseif ((b & 1) == 0) { return getGreatestCommonDivisor(a, b >> 1); } else { int max = Math.max(a, b); int min = Math.min(a, b); return getGreatestCommonDivisor(max - min, min); } }
publicstaticintgetMaxSortedDistance(int[] array){ Arrays.sort(array); int max = -1; for (int i = 1; i < array.length; i++) { int temp = array[i] - array[i - 1]; if (temp > max) { max = temp; } } return max; }
publicstaticintgetMaxSortedDistance(int[] array){ // 求出数组的最大值和最小值 int max = array[0]; int min = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; } if (array[i] < min) { min = array[i]; } } int d = max - min; // 最大值和最小值相等,证明数组的所有数相等 if (d == 0) { return0; } // 计数排序 int[] arr = newint[d + 1]; for (int i : array) { arr[i - min]++; } int maxDistance = 0; // 寻找最长连续的0 for (int i = 0; i < arr.length; i++) { if (arr[i] == 0) { int temp = i; while (arr[temp] == 0) { temp++; } if (temp - i > maxDistance) { maxDistance = temp - i; } } } return maxDistance + 1; }
publicstaticintgetMaxSortedDistance(int[] array){ // 求出数组的最大值和最小值 int max = array[0]; int min = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; } if (array[i] < min) { min = array[i]; } } int d = max - min; // 最大值和最小值相等,证明数组的所有数相等 if (d == 0) { return0; }
// 初始化桶 int bucketNum = array.length; Bucket[] buckets = new Bucket[bucketNum]; Arrays.fill(buckets,new Bucket());
// 遍历原始数组,确定每个桶的最大值和最小值 for (int i : array) { int index = ((i - min) * (bucketNum - 1) / d); if (buckets[index].min == null || buckets[index].min > i) { buckets[index].min = i; } if (buckets[index].max == null || buckets[index].max < i) { buckets[index].max = i; } }
// 遍历桶,找到最大差值 int leftMax = buckets[0].max; int maxDistance = 0; for (int i = 1; i < buckets.length; i++) { if (buckets[i].min == null) { continue; } if (buckets[i].min - leftMax > maxDistance) { maxDistance = buckets[i].min - leftMax; } leftMax = buckets[i].max; } return maxDistance; }
/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */
publicstaticintgetBestGoldMining(int[] arr){ Map<Integer, Integer> map = new HashMap<>(100); for (int i = 1; i <= 100; i++) { map.put(i,i); } for (int i : arr) { map.remove(i); } int res = 0; for (int key : map.keySet()) { res = key; } return res; }
先排序后寻找
将数组进行排序,然后逐个寻找。
1 2 3 4 5 6 7 8 9 10 11 12
publicstaticintgetBestGoldMining(int[] arr){ Arrays.sort(arr); if (arr[0] != 1) { return0; } for (int i = 0; i < arr.length - 1; i++) { if (arr[i] + 1 != arr[i + 1]) { return arr[i] + 1; } } return100; }
求和
计算出1~100的和,然后减去数组中元素的和,剩下的就是所缺少的整数了。
1 2 3 4 5 6 7
publicstaticintgetBestGoldMining(int[] arr){ int res = 5050; for (int i : arr) { res -= i; } return res; }