二分查找是在每次匹配后,將查找的空間一分為二的算法,二分查找應(yīng)該是有序的數(shù)組進行查找.
二分查找模板
1. 模板一
int binarySearch(int[] nums, int target){
if(nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while(left <= right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid - 1; }
}
// End Condition: left > right
return -1;
}
模板一,
初始條件 , left = 0, right = nums.length - 1
終止 left > right
向左查找：right = mid-1
向右查找：left = mid+1
不需要后序的處理,因為每一步都在, 進行遍歷會遍歷所有的可能,當(dāng)條件結(jié)束一定是不滿足條件
2. 模板二
int binarySearch(int[] nums, int target){
if(nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length;
while(left < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid; }
}
// Post-processing:
// End Condition: left == right
if(left != nums.length && nums[left] == target) return left;
return -1;
}
它用于查找需要訪問數(shù)組中當(dāng)前索引及其直接右鄰居索引的元素或條件。
模板二,
初始條件: left = 0, right = nums.length;
終止條件 left == right
向左查找：right = mid
向右查找：left = mid+1
需要最終判斷 ,left 沒有出界的情況下, left 是否是最終的答案
保證查找空間在每一步中至少有 2 個元素宛逗。
需要進行后處理薛躬。 當(dāng)你剩下 1 個元素時抛寝，循環(huán) / 遞歸結(jié)束。 需要評估剩余元素是否符合條件斧账。
3.模板三
int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while (left + 1 < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
// Post-processing:
// End Condition: left + 1 == right
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -1;
}
初始條件: left = 0, right = nums.length - 1;
終止條件: left + 1 == right
向左查找：right = mid
向右查找：left = mid
它用于搜索需要訪問當(dāng)前索引及其在數(shù)組中的直接左右鄰居索引的元素或條件出牧。
保證查找空間在每個步驟中至少有 3 個元素。
需要進行后處理搏恤。 當(dāng)剩下 2 個元素時违寿，循環(huán) / 遞歸結(jié)束。 需要評估其余元素是否符合條件熟空。
最后需要判斷最后的兩個元素,left 和 right 是否是最后的結(jié)果
模板四
不進行判斷,直接進行返回最終的迭代值
public int firstBadVersion(int n) {
int left = 1;
int right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
這種模板主要用于,首先邊界值不能超出,同時條件判斷需要兩個值同時判斷的問題
我們讓right 的更新包括mid,讓left 的更新 +1
最后留下的一個元素就是最終要的元素, right 的判斷就必須包括答案的最終條件
二分法左右邊界定位
// 重復(fù)或不存在時藤巢，返回左邊界
public int binarySearch(int[] nums,int target){
int left = 0,right = nums.length-1;
while(left<right){
int mid = left + (right - left)/2;
if (nums[mid] >= target){
high = mid;
}else{
low = mid + 1;
}
}
if(nums[low] == target){
return low;
}
return -1;
}
// 最后的一次出現(xiàn)右邊界的位置
public int binarySearch(int[] nums,int target){
int left = 0,right = nums.length-1;
while(left < right){
// 注意這里一定要加1 否則會出現(xiàn)死循環(huán)
int mid = left + (right - left + 1)/2;
if（nums[mid] <= target）{
low = mid;
}else{
high = mid -1;
}
}
if(nums[low] == target){
return low;
}
return -1;
}
upper 和 lower
// lower_bound 是找到第一個大于等于目標(biāo)值的數(shù)
private static int lower_bound(int[] nums, int key) {
int low = 1,hig = nums.length;
while (low < hig) {
int mid = low + ((hig - low) >> 1);
if (nums[mid] >= key) hig = mid;
else low = mid + 1;
}
return low;
}
// upper bound 是找到第一個 大于目標(biāo)值的數(shù)
private static int upper_bound(int[] nums,int key){
int low = 1,hig = nums.length-1;
while (low < hig) {
int mid = low + ((hig - low) >> 1);
if (nums[mid] <= key) low = mid + 1;
else hig = mid;
}
return low;
}
模板一
// 求 x 的開方值
public int mySqrt(int x) {
if (x < 2){
return x;
}
int left = 1, right = x/2 + 1;
while (left <= right){
int mid = left + (right - left)/2;
if (mid == x/mid){
return mid;
}else if (mid > x/mid){
right = mid - 1;
}else {
left = mid + 1;
}
}
// 模板一,退出循環(huán)一定是沒有查詢到等號要求的值
// 沒有查找到具體的相等的, 返回剛好小于的
return right;
}
// 在旋轉(zhuǎn)數(shù)組中進行查找
思路:
如果 中間值等于 目標(biāo)值直接返回
如果目標(biāo)值大于nums[0] (他會包括 正常沒旋轉(zhuǎn)的情況)
- 只有中間值大于等于nums[0], 中間值小于目標(biāo)值 left = mid + 1,其他情況都是減
如果目標(biāo)值小于nums[0], 說明數(shù)組一定旋轉(zhuǎn)了 - 只有中間值也小于nums[0], 中間值大于 目標(biāo)值 right = mid -1 ,其他都是加
在討論情況是要確定一個簡單的同時是一定的,那么剩下的就是相反的,只用確定一個條件即可
public int search(int[] nums, int target) {
int left = 0,right = nums.length -1;
while (left <= right){
int mid = left + (right - left)/2;
if (nums[mid] == target){
return mid;
}
if (target >= nums[0]){
if (nums[mid] >= nums[0] && nums[mid] < target){
left = mid + 1;
}else {
right = mid - 1;
}
}else {
if (nums[mid] < nums[0] && nums[mid] > target){
right = mid - 1;
}else {
left = mid + 1;
}
}
}
return -1;
}
模板二
我們不判斷是否等于,這里需要判斷連續(xù)的兩個值,可以轉(zhuǎn)換為兩個方向的夾逼
public int findPeakElement(int[] nums) {
int left = 0,right = nums.length;
while (left < right){
int mid = left + (right - left)/2;
// 這里 mid 和 mid + 1 是我們要判斷的數(shù)字,mid + 1 是不會越界的
// nums[-1] = nums[n] = -∞ 保證通過這種條件可以找到峰值
if (nums[mid] > nums[mid+1]){
right = mid;
}else {
left = mid + 1;
}
}
return left;
}
public int firstBadVersion(int n) {
int left = 1;
// right 一定不能變成 n + 1 因為可能會超出int的邊界值 // 而第二種最后的 超出邊界返回你
int right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if(isBadVersion(mid)){
right = mid;
}else{
left = mid + 1;
}
}
return left;
}
public int findMin(int[] nums) {
if (nums.length == 0){
return nums[0];
}
if (nums[0] < nums[nums.length-1]){
return nums[0];
}
int left = 0, right = nums.length-1;
while (left < right){
int mid = left + (right - left)/2;
if (nums[mid] < nums[0]){
right = mid;
}else {
left = mid + 1;
}
}
return nums[left];
}
// 查詢目標(biāo)值,返回數(shù)組中目標(biāo)值的起始值和最終值
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0){
return new int[]{-1,-1};
}
int start = 0;
int end = nums.length -1;
int left = 0,right = nums.length-1;
while (left <= right){
int mid = left + (right - left)/2;
if (nums[mid] == target){
int i = mid;
while (--i >= start){
if (nums[i] != nums[mid]){
break;
}
}
start = i+1;
i = mid;
while (++i <= end){
if (nums[i] != nums[mid]){
break;
}
}
end = i-1;
return new int[]{start,end};
}else if (nums[mid] > target){
right = mid -1;
}else {
left = mid + 1;
}
}
return new int[]{-1,-1};
}
// 找尋兩個排序數(shù)組中的中位數(shù)
將兩個數(shù)組進行合并, 然后將數(shù)組中的一半+1 放到新數(shù)組中,然后選出最終的結(jié)果
public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
if (m == 0){
if (n % 2 == 0){
return (nums2[n/2-1] + nums2[n/2])/2.0;
}else {
return nums2[n/2];
}
}
if (n == 0){
if (m % 2 == 0){
return (nums1[m/2-1] + nums1[m/2])/2.0;
}else {
return nums1[m/2];
}
}
int i =0,j=0;
int index = 0;
int max = (m+n)/2+1;
int[] num = new int[max];
while (index < max){
if (i >= m){
num[index++] = nums2[j++];
}else if (j >= n){
num[index++] = nums1[i++];
}else if (nums1[i] <= nums2[j]){
num[index++] = nums1[i++];
}else {
num[index++] = nums2[j++];
}
}
if ((m + n) %2 == 0){
return (num[(m+n)/2-1] + num[((m+n)/2)])/2.0;
}else {
return num[(m+n)/2];
}
}
// 使用兩個變量保存到中間值即可
// 使用兩個變量保存最后兩個數(shù),遍歷到 len/2
public double findMedianSortedArrays3(int[] A, int[] B) {
int m = A.length;
int n = B.length;
int len = m + n;
int left = -1,right = -1;
int aStart = 0,bStart = 0;
for (int i=0;i<=len/2;i++){
left = right;
if (aStart<m && (bStart>=n || A[aStart] < B[bStart])){
right = A[aStart++];
}else {
right = B[bStart++];
}
}
if ((len & 1) == 0){
return (left + right)/2.0;
}else {
return right;
}
}
// 使用遞歸的方式查詢第k小方式
思路:
首先求出中間位的位數(shù), 偶數(shù)有兩個,奇數(shù)一個
然后迭代求第k大,
迭代:
首先每次保證 A 小于 B
如果 A的長度等于0 ,直接返回B 的第k個數(shù)字
如果 k 已經(jīng)遞減到1 直接返回 A 和 B的首數(shù)字最小值
思路就是每次 K 遞減 1/2 ,然后再刪除 k/2 個數(shù)字
如果 A[i] 大于 B[j] 說明 A[i] 可能是第k大 , 刪除 B[j] 之前的數(shù)字
如果 B[j] 大于 A[i] 說明 B[j] 可能是第k大, 刪除 A[i] 之前的數(shù)字
public double findMedianSortedArrays4(int[] A, int[] B) {
int n = A.length;
int m = B.length;
// 求中位數(shù), +1, +2 求出的是初始從1 開始的中位數(shù),如果相等就是奇數(shù),否則偶數(shù)
int left = (n+m+1)/2;
int right = (n+m+2)/2;
// 將偶數(shù)和奇數(shù)合并
return (getKth(A,0,n-1,B,0,m-1,left)+ getKth(A,0,n-1,B,0,m-1,right))/2.0;
}
public int getKth(int[] A,int start1,int end1,int[] B,int start2,int end2,int k){
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
if (len1 > len2){
return getKth(B,start2,end2,A,start1,end1,k);
}
if (len1 == 0){
return B[start2+k-1];
}
if (k == 1){
return Math.min(A[start1],B[start2]);
}
int i = start1 + Math.min(len1,k/2)-1;
int j = start2 + Math.min(len2,k/2)-1;
// 找到第Kth 還要保證 左邊最大值小于右邊最小值
if (A[i]>B[j]){
return getKth(A,start1,end1,B,j+1,end2,k - (j-start2 + 1));
}else {
return getKth(A,i+1,end1,B,start2,end2,k-(i-start1+1));
}
}
/// 查詢兩個數(shù)組的中位數(shù)
迭代計算,
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m > n) { // to ensure m<=n
int[] temp = A; A = B; B = temp;
int tmp = m; m = n; n = tmp;
}
// halfLen 保證 在奇數(shù)比中位數(shù)多1 ,偶數(shù)是最后的中位數(shù)
// 以 iMin = 0, iMax = m,
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
// B[j-1] 代表的是 左部的數(shù), A[i] 代表右部的數(shù)
// 左大于右, iMin = i + 1
if (i < iMax && B[j-1] > A[i]){
iMin = i + 1; // i is too small
}
// 兩個都是判斷左大于右進行 移動
else if (i > iMin && A[i-1] > B[j]) {
iMax = i - 1; // i is too big
}
// 不存在左大于右,進行輸出,
else { // i is perfect
// i 等于0 說明 左最大在i-1 和 j-1 中, B中,如果奇數(shù)返回 maxLeft
int maxLeft = 0;
if (i == 0) { maxLeft = B[j-1]; }
else if (j == 0) { maxLeft = A[i-1]; }
else { maxLeft = Math.max(A[i-1], B[j-1]); }
if ( (m + n) % 2 == 1 ) { return maxLeft; }
// minRight 在 i 和 j 中產(chǎn)生
int minRight = 0;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = Math.min(B[j], A[i]); }
// 返回 (left + right) / 2.0
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
// 兩數(shù)相除
思路:
如果除數(shù)是0 ,直接返回-1
如果被除數(shù)是0,直接返回0
如果被除數(shù)是負(fù)數(shù)的最小值,同時除數(shù)是負(fù)數(shù)-1,那么直接返回最大值
判斷是不是負(fù)數(shù) 兩數(shù)進行異或 如果小于0 表明是負(fù)數(shù)
首先將數(shù)都轉(zhuǎn)換為long型的正數(shù), 用一個變量div_count保存每次加的值
被除數(shù) 減去 除數(shù) , 結(jié)果 + div_count
然后 除數(shù) 加倍 div_count 加倍
中間需要處理的情況,如果 被除數(shù) 小于 初始除數(shù) break
如果 被除數(shù) 減 當(dāng)前除數(shù) 剩余 小于當(dāng)前除數(shù),那么就不進行加倍,除數(shù)還原,div_count 還原
public int divide(int dividend, int divisor) {
if (divisor == 0){
return -1;
}
if (dividend == 0){
return 0;
}
if (dividend == Integer.MIN_VALUE && divisor == -1){
return Integer.MAX_VALUE;
}
boolean negetive = (dividend^divisor)<0;
int res = 0, div_count = 1;
long dividend_tmp = Math.abs((long)dividend);
long divisor_tmp = Math.abs((long)divisor);
while (dividend_tmp>=divisor_tmp){
dividend_tmp -= divisor_tmp;
res += div_count;
if (dividend_tmp < Math.abs((long)divisor)){
break;
}
if (dividend_tmp-divisor_tmp < divisor_tmp){
divisor_tmp = Math.abs((long)divisor);
div_count = 1;
continue;
}
divisor_tmp += divisor_tmp;
div_count += div_count;
}
return negetive?0-res:res;
}
// 使用移位進行兩數(shù)相減
思路:
先將 除數(shù)和被除數(shù)轉(zhuǎn)換為 long 型的正數(shù)
初始 移位 為 1, 同時備份 right
當(dāng) 被除數(shù) - 除數(shù) 向左進行移位的值 < 0 退出,否則移位的數(shù) ++, 算出可以進行移位的最大位數(shù)
被除數(shù) - 除數(shù), 向左移位的位數(shù)
結(jié)果 + 1 相左移動的位數(shù)
public int divide2(int dividend, int divisor) {
long right = Math.abs((long)dividend);
long left = Math.abs((long)divisor);
long ans = 0;
while (left<=right){
long k = right,cur = 1;
while (k-(left << cur) > 0) {
cur++;
}
right -= (left << (cur-1));
ans += (1<<(cur-1));
}
if ((dividend^divisor)<0) {
ans = -ans;
}
if(ans >= Integer.MAX_VALUE){
return Integer.MAX_VALUE;
}
if(ans <= Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
return (int)ans;
}
// 計算 x 的 n次冪
// 使用 快速冪計算 x 的 n次方
// 主要思路是, 冪次方每次除二,基數(shù)每次平方,又因為冪次方每次是奇數(shù)偶數(shù)交替, ans *= x
public double myPow(double x, int n) {
long m = Math.abs((long)n);
if ((n ^ 1) < 0){
x = 1.0/x;
}
double ans = 1.0;
while (m > 0){
if (m % 2 == 1){
ans *= x;
}
x *= x;
m /= 2;
}
return ans;
}
// 使用二分法在矩陣中查詢相應(yīng)的值
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
return false;
}
int m = matrix.length;
int n = matrix[0].length;
int left = 0; int right = m-1;
while (left<=right){
int mid = left + (right - left)/2;
if (matrix[mid][0] == target){
return true;
}else if (matrix[mid][0] < target){
left = mid + 1;
}else {
right = mid - 1;
}
}
int lineNum = left - 1 < 0 ? 0: left -1;
left = 0;right = n-1;
while (left<=right){
int mid = left + (right - left)/2;
if (matrix[lineNum][mid] == target){
return true;
}else if (matrix[lineNum][mid] < target){
left = mid + 1;
}else {
right = mid - 1;
}
}
return false;
}
// 相當(dāng)于進行了展平的操作
// 因為這些數(shù)據(jù)展平了是,順序的
public boolean searchMatrix2(int[][] matrix, int target) {
int m = matrix.length;
if (m == 0){
return false;
}
int n = matrix[0].length;
int left = 0; int right = m * n -1;
while (left <= right){
int mid = left + (right - left)/2;
if (matrix[mid/n][mid%n] == target){
return true;
}else if (matrix[mid/n][mid%n] > target){
right = mid -1;
}else {
left = mid + 1;
}
}
return false;
}
// 查詢帶有重復(fù)旋轉(zhuǎn)數(shù)組
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0){
return false;
}
int left = 0;int right = nums.length -1;
if (nums[0] == target){
return true;
}else {
while (left < nums.length-1 && nums[left] == nums[0]){
left ++;
}
while (right > 0 && nums[right] == nums[0]){
right --;
}
}
while (left <= right){
int mid = left + (right - left)/2;
if (nums[mid] == target){
return true;
}
if (target >= nums[0]){
if (nums[mid] >= nums[0] && nums[mid] < target){
left = mid + 1;
}else {
right = mid - 1;
}
}else {
if (nums[mid] < nums[0] && nums[mid] > target){
right = mid - 1;
}else {
left = mid + 1;
}
}
}
return false;
}
// 對帶有重復(fù)元素求解最小值
// 重復(fù)數(shù)組只要保證數(shù)組的前后元素不要一致就可以區(qū)分出是否進行了旋轉(zhuǎn)的操作
public int findMin2(int[] nums){
int left = 0,right = nums.length;
while (right - left != 1 && nums[left] == nums[right-1]){
right --;
}
if (nums[left] <= nums[right-1]){
return nums[left];
}
while (left < right){
int mid = left + (right - left)/2;
if (nums[mid] >= nums[0]){
left = mid + 1;
}else {
right = mid;
}
}
return nums[left];
}
// 實現(xiàn) 長度最小的子數(shù)組
// 使用雙指針實現(xiàn)滑動窗口的解析
先是 遞增的加，當(dāng) sum 大于期望值 s, 從 left 開始遞減息罗，同時更新 最小的長度值
public int minSubArrayLen2(int s, int[] nums)
{
int n = nums.length;
int ans = Integer.MAX_VALUE;
int left = 0;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
while (sum >= s) {
ans = Math.min(ans, i + 1 - left);
sum -= nums[left++];
}
}
return (ans != Integer.MAX_VALUE) ? ans : 0;
}
// 實現(xiàn)求最小的子數(shù)組的值
// 主要思想是 首先求出連續(xù)的遞增和
j ~ i 間的遞增和 可以表示為 nums[j] - nums[i] >= s
s + num[i] 可以找到我們想要的 nums[j]
那么就可以求出 j - i 的長度
實現(xiàn)二分搜著找到對應(yīng)的值掂咒，如果沒找到多返回一位
public int minSubArrayLen(int s, int[] nums) {
int min = nums.length;
if (min == 0) return 0;
min++;
int[] sums = new int[nums.length + 1];
sums[0] = 0;
for (int i = 1; i <= nums.length; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
for (int i = 1; i <= nums.length; i++) {
int toFind = s + sums[i - 1];
int bound = binarySearch(sums, toFind);
if (bound > 0) min = Math.min(min, bound - i + 1);
}
return min > nums.length ? 0 : min;
}
private int binarySearch(int[] arr, int key) {
int i = 0;
int j = arr.length - 1;
while (i < j - 1) {
int mid = i + (j - i)/2;
if (arr[mid] < key){
i = mid;
}else if (arr[mid] > key) {
j = mid;
}else {
return mid;
}
}
if (arr[j] >= key){
return j;
}
else{
return -1;
}
}
// 搜索二維矩陣2
從最上方，逆序的對每行進行檢測迈喉，然后進行二分搜索
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
return false;
}
int m = matrix.length;
int n = matrix[0].length;
for (int i = m-1;i>=0;i--){
if (target >= matrix[i][0] && target <= matrix[i][n-1]){
int index = Arrays.binarySearch(matrix[i], target);
if (index>=0){
return true;
}
}
}
return false;
}
// 搜索二位矩陣2 從左下開始
public boolean searchMatrix(int[][] matrix, int target) {
// 從左下開始俏扩， 實際相當(dāng)于從中間開始
int row = matrix.length-1;
int col = 0;
// 小于的行減，大于的列加
while (row >= 0 && col < matrix[0].length) {
if (matrix[row][col] > target) {
row--;
} else if (matrix[row][col] < target) {
col++;
} else { // found it
return true;
}
}
return false;
}
// h指數(shù)弊添，指的是， 最多n篇論文捌木，至少引用 n次
數(shù)組是排序的油坝， 只有保證
n - mid = x x 篇論文 ，至少引用 num[x] 次
n - mid <= num[x] 這是正確的答案刨裆， 否則我們求最大left = mid + 1;
最后求出的答案一定滿足澈圈， Math.min(n-left,citations[left]);
public int hIndex(int[] citations) {
if (citations == null || citations.length == 0){
return 0;
}
int n = citations.length;
int left = 0,right = citations.length-1;
while (left < right){
int mid = left + (right - left)/2;
if (n - mid <= citations[mid]){
right = mid;
}else {
left = mid + 1;
}
}
return Math.min(n-left,citations[left]);
}
// 最長的上升子序列
首先看訪問當(dāng)前位置的，是否大于等于0 說明當(dāng)前位置以及訪問過它的最長上升子序列的長度
返回帆啃，選或者不選當(dāng)前元素的最大長度
// 無序數(shù)組瞬女，找出最長的上升子序列，可以不連續(xù)
public int lengthOfLIS(int[] nums) {
int memo[][] = new int[nums.length+1][nums.length];
for (int[] l:memo){
Arrays.fill(l,-1);
}
return lengthOfLIS(nums,-1,0,memo);
}
public int lengthOfLIS(int[] nums, int previndex, int curpos, int[][] memo) {
if (curpos == nums.length) {
return 0;
}
if (memo[previndex + 1][curpos] >= 0) {
return memo[previndex + 1][curpos];
}
int taken = 0;
if (previndex < 0 || nums[curpos] > nums[previndex]) {
taken = 1 + lengthOfLIS(nums, curpos, curpos + 1, memo);
}
int nottaken = lengthOfLIS(nums, previndex, curpos + 1, memo);
memo[previndex + 1][curpos] = Math.max(taken, nottaken);
return memo[previndex + 1][curpos];
}
// 使用動態(tài)規(guī)劃解決 最長上升子序列
記錄數(shù)組的每一個位置的最長子序列數(shù)努潘， 添加新元素是遍歷前面找出在小于當(dāng)前值的情況下诽偷，最大的最長子序列數(shù)，
當(dāng)前的最長子序列數(shù)疯坤，就是前面的加1
public int lengthOfLIS3(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < dp.length; i++) {
int maxval = 0;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
maxval = Math.max(maxval, dp[j]);
}
}
dp[i] = maxval + 1;
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
// 使用二分法报慕，進行 最長上升子序列的測試
// 實際上 就是 找到當(dāng)前要插入的位置進行替換，如果插入位置在最后則压怠，長度+1進行插入
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int len = 0;
for (int num : nums) {
int i = Arrays.binarySearch(dp, 0, len, num);
if (i < 0) {
i = -(i + 1);
}
dp[i] = num;
if (i == len) {
len++;
}
}
return len;
}
在dp中查詢當(dāng)前數(shù)字應(yīng)該保存的位置眠冈，然后進行覆蓋，如果插入的位置等于len 就在后面插入 len ++菌瘫， 最后返回 len
// 使用二分查找 + 插入 計算右側(cè)小于當(dāng)前元素的個數(shù)
從倒數(shù)第二個元素開始進行插入蜗顽， 首先使用二分查找，查找小于當(dāng)前的元素的最后一個元素雨让， 并記錄下標(biāo)
記錄 nums[i] 的 數(shù)值雇盖， 從 i+1 復(fù)制到 i, posit - i , nums[posit] = pivot
public static List<Integer> binaryInsert(int[] nums) {
int n = nums.length;
if (n < 1) {
return new ArrayList<Integer>();
}
Integer[] res = new Integer[n];
res[n - 1] = 0;
for (int i = n - 2; i >= 0; i--) {
int posit = binarySearch(nums, i + 1, n - 1, nums[i]) - 1;
int pivot = nums[i];
System.arraycopy(nums, i + 1, nums, i, posit - i);
nums[posit] = pivot;
res[i] = posit - i;
}
return Arrays.asList(res);
}
// 這里查找的是，最后一個小于當(dāng)前元素的位置
private static int binarySearch(int[] nums, int low, int hig, int key) {
while (low <= hig) {
int mid = low + ((hig - low) >> 1);
if (nums[mid] < key) low = mid + 1;
else hig = mid - 1;
}
return low;
}
// 使用歸并排序進行計算右側(cè)小于當(dāng)前元素的個數(shù)
public static List<Integer> merge(int[] nums) {
int n = nums.length;
int[] idx = new int[n];
// 使用位置索引栖忠，原始位置不變
Integer[] res = new Integer[n];
// 初始化位置索引刊懈，還有結(jié)果數(shù)組
for (int i = 0; i < n; i++) {
idx[i] = i;
res[i] = 0;
}
// 直接使用拷貝这弧，節(jié)省拷貝時間
mergeSort(nums, 0, n - 1, idx, idx.clone(), res);
return Arrays.asList(res);
}
// 使用同一的輔助數(shù)組，避免頻繁創(chuàng)建虚汛、銷毀
private static void mergeSort(int[] nums, int low, int hig, int[] idx, int[] aux, Integer[] res) {
// 總長
int nRemaining = hig - low + 1;
if (nRemaining < 2) return;
int mid = low + ((hig - low) >> 1);
mergeSort(nums, low, mid, aux, idx, res);
mergeSort(nums, mid + 1, hig, aux, idx, res);
// 如果已經(jīng)有序匾浪，則無需歸并。
// 表示 兩個數(shù)組的左和右進行歸并
if (nums[aux[mid]] <= nums[aux[mid + 1]]) {
System.arraycopy(aux, low, idx, low, nRemaining);
return;
}
merge(nums, low, mid, hig, idx, aux, res);
}
private static void merge(int[] nums, int low, int mid, int hig, int[] idx, int[] aux, Integer[] res) {
int i = low, j = mid + 1;
for (int k = low; k <= hig; k++) {
if (i > mid) {
idx[k] = aux[j++];
} else if (j > hig) {
// 這里
res[aux[i]] += j - mid - 1;
idx[k] = aux[i++];
} else if (nums[aux[i]] > nums[aux[j]]) {
// 如果統(tǒng)計的是總交換次數(shù)卷哩，那么應(yīng)該在這里+mid-i+1
idx[k] = aux[j++];
} else {
// 這里
res[aux[i]] += j - mid - 1;
idx[k] = aux[i++];
}
}
}
// 使用模擬 + 二分查找 找尋右側(cè)小于當(dāng)前元素的個數(shù)
創(chuàng)建一個數(shù)組用于存儲要排序蛋辈， 創(chuàng)建結(jié)果數(shù)組 res
從后向前遍歷，在排序數(shù)組中查找要插入的位置将谊，（數(shù)組從小到大排序）
那么這個位置冷溶，就是其比右邊大的數(shù)據(jù)個數(shù)
同時我們將我們的數(shù)插入到對應(yīng)的位置
這里結(jié)果數(shù)組必須使用 Integer 因為，我們可能初始添加最后一個元素
// 使用新的 二分查找
public List<Integer> countSmaller(int[] nums) {
//排序數(shù)組
List<Integer> temp = new ArrayList<>();
//結(jié)果數(shù)組
Integer[] res = new Integer[nums.length];
//原數(shù)組從后向前遍歷尊浓，根據(jù)二分法升序插入到新數(shù)組
for(int i=nums.length-1;i>=0;i--){
int left = 0,right = temp.size();
while(left<right){
int mid =left+(right-left)/2;
if(temp.get(mid)>=nums[i]){
right = mid;
}else{
left = mid+1;
}
}
//新數(shù)組對應(yīng)位置的下標(biāo)即為原數(shù)組右側(cè)小于該數(shù)的個數(shù)
res[i] = left;
temp.add(left,nums[i]);
}
return Arrays.asList(res);
}
// 區(qū)間和的個數(shù)
這里一定要主要可能會出現(xiàn)區(qū)間和超過整數(shù)的范圍逞频，所以保存和一定用long類型
public int countRangeSum2(int[] nums,int lower,int upper){
int n = nums.length;
long presum = 0;
// 這里必須 n + 1 要保證 第一個和等于0
long[] S = new long[n+1];
int ret = 0;
for (int i=1;i<=n;i++){
presum += nums[i-1];
for (int j=1;j<=i;j++){
if (lower <= presum -S[j-1] && presum - S[j-1] <= upper){
ret ++;
}
}
S[i] = presum;
}
return ret;
}
// 使用歸并排序進行計算
int countRangeSum(vector<int>& nums, int lower, int upper) {
int n = nums.size();
vector<int64_t> S(n+1,0);
vector<int64_t> assist(n+1,0);
for(int i=1;i<=n;i++)S[i] = S[i-1] + nums[i-1];
return merge(S,assist,0,n,lower,upper);
}
int merge(vector<int64_t> &S,vector<int64_t> &assist,int L,int R,int low,int up){
if(L >= R) return 0;
int cnt = 0;
int M = L + (R-L)/2;
cnt += merge(S,assist,L,M,low,up);
cnt += merge(S,assist,M+1,R,low,up);
int Left = L;
int Upper = M+1,Lower = M+1;
while(Left <= M){
while(Lower <= R && S[Lower] - S[Left] < low)Lower++;
while(Upper <= R && S[Upper] - S[Left] <= up)Upper++;
cnt += Upper - Lower;
Left++;
}
//以下為歸并排序中歸并過程
Left = L;
int Right = M + 1;
int pos = L;
while(Left<= M || Right <= R){
if(Left > M)assist[pos] = S[Right++];
if(Right > R && Left <= M)assist[pos] = S[Left++];
if(Left <= M && Right <= R){
if(S[Left] <= S[Right])assist[pos] = S[Left++];
else assist[pos] = S[Right++];
}
pos++;
}
for(int i=L;i<=R;i++)S[i] = assist[i];
return cnt;
}
// 俄羅斯套娃
降維 + 最長遞增子序列
首先對一個序列進行排序，然后另一維數(shù)組就轉(zhuǎn)換為最長的遞增子序列的值
不排序栋齿，整體的二維數(shù)組是無序的
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < dp.length; i++) {
int maxval = 0;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
maxval = Math.max(maxval, dp[j]);
}
}
dp[i] = maxval + 1;
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
// 按寬度升序排列苗胀，如果寬度一樣，則按高度降序排列
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];
}
});
// 對高度數(shù)組尋找 LIS
int[] height = new int[n];
for (int i = 0; i < n; i++)
height[i] = envelopes[i][1];
return lengthOfLIS(height);
}
// 最大的矩陣和
在計算當(dāng)前位置的矩陣和的時候瓦堵，就是讓 上 面的矩陣和加上 左邊的矩陣和 - 左上角重疊矩陣和 基协，其次要算每一個矩陣 就是讓 sum[i][j] - sum[i][k] sum[i][j] - sum[k][j]
int maxSumSubmatrix(int[][] matrix, int k) {
if (matrix.length == 0 || matrix[0].length == 0) return 0;
int m = matrix.length, n = matrix[0].length, res = Integer.MIN_VALUE;
int[][] sum = new int[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int t = matrix[i][j];
if (i > 0) t += sum[i - 1][j];
if (j > 0) t += sum[i][j - 1];
if (i > 0 && j > 0) t -= sum[i - 1][j - 1];
sum[i][j] = t;
for (int r = 0; r <= i; ++r) {
for (int c = 0; c <= j; ++c) {
int d = sum[i][j];
if (r > 0) d -= sum[r - 1][j];
if (c > 0) d -= sum[i][c - 1];
if (r > 0 && c > 0) d += sum[r - 1][c - 1];
if (d <= k) res = Math.max(res, d);
}
}
}
}
return res;
}
// 使用二分法進行 矩陣中的第k小
// 可以確定左下角最小， 右上角最大
使用二分法進行判斷中間值菇用， 統(tǒng)計小于當(dāng)前數(shù)的數(shù)量澜驮，
統(tǒng)計時可以先判斷每行或每列的最后一位，如果大惋鸥，則整列都符合條件
不是找到滿足條件的就返回杂穷，而是繼續(xù)二分
public int kthSmallest(int[][] matrix, int k) {
int m = matrix.length;
int n = matrix[0].length;
int left = matrix[0][0];
int right = matrix[m-1][n-1];
while (left < right){
int mid = left + (right - left)/2;
int countLeMid = countLeMid(matrix, mid, m, n);
if (countLeMid < k){
left = mid + 1;
}else {
right = mid;
}
}
return left;
}
private int countLeMid(int[][] matrix, int mid, int m, int n) {
int res = 0;
int j = n - 1;
int i = 0;
while (i<m){
if (matrix[i][j] <= mid){
// j的最后坐標(biāo) j ，但是最后有 j + 1 個元素
res += (j + 1);
i++;
}else {
j--;
}
}
return res;
}
證明如下：
設(shè)min^{t}為第t輪二分的min卦绣，mid^{t}為第t輪二分的mid,max^{t}為第t輪二分的max,target是我們要查找的值亭畜。
因此min^{t}=min^{t-1}或者min^{t}=mid^{t-1}+1。如果min^{t}=mid^{t-1}+1,說明小于等于mid^{t-1}的矩陣中元素的個數(shù)小于k,說明mid^{t-1}<target,那么min^{t}=mid^{t-1}+1<target+1,即min^{t}<=target迎卤。因此拴鸵，只要其中有一次的min是由上一輪的mid轉(zhuǎn)化而來的，那么就可以保證min始終<=target蜗搔。如果min一直保持著初始狀態(tài)劲藐，從來沒有從上一輪mid轉(zhuǎn)化而來過，那么min^{t}=min{1}<=target樟凄。因此聘芜，min始終小于等于target。
同時缝龄，max^{t}=mid^{t-1}或者max^{t}=max^{t-1}汰现。如果max^{t}=mid^{t-1},說明小于等于mid^{t-1}的矩陣中的元素的個數(shù)>=k挂谍，說明mid^{t-1}>=target。因此瞎饲，只要其中有一次的max是由上一輪的mid轉(zhuǎn)化而來的口叙，那么就可以保證max始終>=target。如果max一直保持著初始狀態(tài)嗅战，從來沒有從上一輪mid轉(zhuǎn)化而來過妄田，那么max^{t}=max{1}>=target。因此驮捍，max始終大于等于target疟呐。
此外，由于min和max構(gòu)成的區(qū)間是在不斷縮小的东且，所以最終肯定可以達(dá)到min=max的狀態(tài)启具，從而退出循環(huán)。此時珊泳，由于min<=target,max>=target,而min=max鲁冯，所以min=max=target。
得證旨椒。
// 判斷一個字符串是不是另一個字符串的子序列
String 的 indexOf 可以獲取 單個字符在 String 中的位置 indexOf(c,i) 可以從i開始獲取之后字符的位置，如果
public boolean isSubsequence(String s, String t) {
int index = 0,i = 0;
while(index < s.length() && t.indexOf(s.charAt(index),i) >= i){
i = t.indexOf(s.charAt(index),i) + 1;
index++;
}
return index == s.length();
}
// 二分查詢 最右區(qū)間
使用 hashmap 保存 區(qū)間的具體位置堵漱，然后根據(jù)二分查找最小的可能值综慎，然后去map中找到具體的下標(biāo)
public int[] binary_search(int[][] intervals, int target, int start, int end) {
if (start >= end) {
if (intervals[start][0] >= target) {
return intervals[start];
}
return null;
}
int mid = (start + end) / 2;
if (intervals[mid][0] < target) {
return binary_search(intervals, target, mid + 1, end);
} else {
return binary_search(intervals, target, start, mid);
}
}
public int[] findRightInterval(int[][] intervals) {
int[] res = new int[intervals.length];
HashMap<int[], Integer> hash = new HashMap<>();
for (int i = 0; i < intervals.length; i++) {
hash.put(intervals[i], i);
}
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
for (int i = 0; i < intervals.length; i++) {
int[] interval = binary_search(intervals, intervals[i][1], 0, intervals.length - 1);
res[hash.get(intervals[i])] = interval == null ? -1 : hash.get(interval);
}
return res;
}
// 排列硬幣
根據(jù)數(shù)學(xué)公式，k(k+1) /2 = n勤庐，可以得到其正數(shù)解為：k = sqrt(2n+1/4) - 1/2示惊。然后求整即可。
唯一的問題是愉镰，這里2n+1/4有可能會超出sqrt函數(shù)的參數(shù)范圍米罚。
于是，我們可以變換一下丈探， k = sqrt(2) * sqrt(n+1/8) - 1/2录择，這樣求平方根就不會超限了。
于是碗降，我們就有了這么一行代碼
class Solution {
public int arrangeCoins(int n) {
return (int)(Math.sqrt(2) * Math.sqrt(n + 0.125) - 0.5);
}
}
// 使用二分法檢測排列硬幣的問題
public int arrangeCoins(int n) {
if (n == 0){
return 0;
}
int left = 1, right = n/2 + 1;
while (left < right){
int mid = left + (right - left+1)/2;
if (sumBeforeMid(mid) <= n){
left = mid;
}else {
right = mid - 1;
}
}
return right;
}
public long sumBeforeMid(long x){
if (x > 0){
if (x % 2 == 0){
return (x/2) *(x + 1);
}else {
return x * (x-1)/2 + x;
}
}
return 0;
}
// 查找 供暖器需要的半徑
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int j = 0;
int max = -1;
for(int i = 0;i < houses.length;i++){
if((j + 1 < heaters.length) && (Math.abs(houses[i] - heaters[j]) >= Math.abs(houses[i] - heaters[j + 1]))){
j++;
i--;
}else{
if(max < Math.abs(houses[i] - heaters[j])){
max = Math.abs(houses[i] - heaters[j]);
}
}
}
return max;
}
