給定一個(gè)有序數(shù)組arr提针，從左到右依次表示X軸上從左往右點(diǎn)的位置，給定一個(gè)正整數(shù)K曹傀，返回如果有一根長(zhǎng)度為K的繩子辐脖，最多能蓋住幾個(gè)點(diǎn)，繩子的邊緣點(diǎn)碰到X軸上的點(diǎn)皆愉，也算蓋住嗜价。
- 滑動(dòng)窗口，規(guī)定L,R判斷此時(shí)R -> L是否大于給定的長(zhǎng)度K 幕庐，一直增大R久锥，直到找到此時(shí)以L開(kāi)頭時(shí)的最大長(zhǎng)度記錄此時(shí)的值。然后向右移動(dòng)L繼續(xù)上面的步驟异剥。
/**
給定一個(gè)有序數(shù)組arr瑟由，從左到右依次表示X軸上從左往右點(diǎn)的位置，給定一個(gè)正整數(shù)K冤寿，
返回如果有一根長(zhǎng)度為K的繩子歹苦，最多能蓋住幾個(gè)點(diǎn)，繩子的邊緣點(diǎn)碰到X軸上的點(diǎn)疚沐，也算蓋住暂氯。
*/
public class CoverNum {
public static int coverNum(int[] arr,int k){
if(arr == null || arr.length == 0 || k < 0){
return 0;
}
int n = arr.length;
int L = 0;
int R = 0;
int max = 0;
// 枚舉所有開(kāi)頭
while (L < n){
while (R < n && (arr[R] - arr[L] <= k)){
R++;
}
max = Math.max(max,R - L);
L++;
}
return max;
}
}
括號(hào)有效配對(duì)是指：1）任何一個(gè)左括號(hào)都能找到和其正確配對(duì)的右括號(hào)，2）任何一個(gè)右括號(hào)都能找到和其正確配對(duì)的左括號(hào)有效的： (()) ()() (()()) 等無(wú)效的： (() )( 等亮蛔。
問(wèn)題一：怎么判斷一個(gè)括號(hào)字符串有效？
問(wèn)題二：如果一個(gè)括號(hào)字符串無(wú)效擎厢，返回至少填幾個(gè)字符能讓其整體有效
/**
* 括號(hào)有效配對(duì)是指：
* 1）任何一個(gè)左括號(hào)都能找到和其正確配對(duì)的右括號(hào)
* 2）任何一個(gè)右括號(hào)都能找到和其正確配對(duì)的左括號(hào)
* 有效的： (()) ()() (()()) 等
* 無(wú)效的： (() )( 等
* 問(wèn)題一：怎么判斷一個(gè)括號(hào)字符串有效究流？
* 問(wèn)題二：如果一個(gè)括號(hào)字符串無(wú)效，返回至少填幾個(gè)字符能讓其整體有效
*/
public class Parentheses {
public static boolean isValid(String str){
if(str == null || str.length() == 0){
// 規(guī)定空串無(wú)效
return false;
}
char[] c = str.toCharArray();
int n = c.length;
int count = 0;
for (int i = 0; i < n; i++) {
// 遇到左括號(hào)count++
if(c[i] == '('){
count ++;
}else {
count --;
}
// 遇到右括號(hào)count--
if(count < 0){
return false;
}
}
return count == 0;
}
public static int needParentheses(String str){
char[] c = str.toCharArray();
int n = c.length;
int count = 0;
int need = 0;
for (int i = 0; i < n; i++) {
if(c[i] == '('){
count ++;
}else {
count --;
}
if(count == -1){
// 需要一個(gè)左括號(hào)來(lái)配對(duì)
need++;
count = 0;
}
}
// 最后count>=0;
// 如果count為正數(shù)动遭，則是需要幾個(gè)右括號(hào)來(lái)配對(duì)芬探，加上需要幾個(gè)左括號(hào)need
return need + count;
}
public static int needParentheses2(String str){
char[] c = str.toCharArray();
int n = c.length;
int count = 0;
int need = 0;
for (int i = 0; i < n; i++) {
if(c[i] == '('){
count ++;
}else {
if(count == 0){
need++;
}else {
count --;
}
}
}
// 最后count>=0;
// 如果count為正數(shù)，則是需要幾個(gè)右括號(hào)來(lái)配對(duì)厘惦，加上需要幾個(gè)左括號(hào)need
return need + count;
}
}
括號(hào)有效配對(duì)是指：1）任何一個(gè)左括號(hào)都能找到和其正確配對(duì)的右括號(hào),2）任何一個(gè)右括號(hào)都能找到和其正確配對(duì)的左括號(hào),返回一個(gè)括號(hào)字符串中偷仿，最長(zhǎng)的括號(hào)有效子串的長(zhǎng)度。
- 動(dòng)態(tài)規(guī)劃宵蕉，生成一個(gè)記錄位置結(jié)尾的形成的最長(zhǎng)子串的數(shù)組酝静。假設(shè)我們現(xiàn)在求i位置的最長(zhǎng)有效子串的長(zhǎng)度，我們已經(jīng)知道i-1位置的最長(zhǎng)有效子串長(zhǎng)度為l羡玛，如果此時(shí)i位置時(shí)左括號(hào)别智，那么此時(shí)以i位置結(jié)尾不可能形成有效子串，則有效子串長(zhǎng)度為0稼稿，若是以右括號(hào)結(jié)尾的那么我們可以看此時(shí)從i位置向前推l的長(zhǎng)度的前一個(gè)位置是否是一個(gè)左括號(hào)薄榛，若不是則以i位置結(jié)尾的最長(zhǎng)子串長(zhǎng)度為0讳窟，若是那么我們可以確定以i位置結(jié)尾的最長(zhǎng)子串的最小長(zhǎng)度是l+2，還能不能更長(zhǎng)我們要看此時(shí)最少形成的子串的開(kāi)頭位置的前一個(gè)位置為結(jié)尾的子串的長(zhǎng)度相加敞恋。
/**
* 有效的最長(zhǎng)子串
*/
public class MaxParenthesesLen {
public static int maxParenthesesLen(String str){
if(str == null || str.length() == 0){
return 0;
}
char[] c = str.toCharArray();
int n = c.length;
int[] dp = new int[n];
dp[0] = 0;
int max = 0;
for (int i = 1; i < n; i++) {
if(c[i] == ')'){
/**
* 下面兩個(gè)if可以用這個(gè)替換
* int index = i - dp[i-1]-1;
* if(index >=0 && dp[index] =='('){
* dp[i] = dp[i-1]+2 +(index >0 ? dp[index-1] :0);
* }
*/
if(i-dp[i-1]-1 >= 0){
dp[i] = c[i-dp[i-1]-1] == '('? dp[i-1]+2:0;
}
if(i-dp[i-1]-2 >= 0){
dp[i] = dp[i] + dp[i-dp[i-1]-2];
}
}
max = Math.max(max,dp[i]);
}
return max;
}
// 求括號(hào)嵌套的深度,前提是括號(hào)字符串一定有效
// 一個(gè)變量count左括號(hào)加丽啡，右括號(hào)減，抓取遍歷過(guò)程中的最大值
public static int deep(String str){
char[] c = str.toCharArray();
int max = 0;
int count = 0;
for (int i = 0; i < c.length; i++) {
count = c[i] == '('?count+1 : count-1;
max = Math.max(max,count);
}
return max;
}
public static void main(String[] args) {
String str = "((()))((()))()";
System.out.println(maxParenthesesLen(str));
System.out.println(deep(str));
}
}
有一些排成一行的正方形硬猫。每個(gè)正方形已經(jīng)被染成紅色或者綠色÷瞪希現(xiàn)在可以選擇任意一個(gè)正方形然后用這兩種顏色的任意一種進(jìn)行染色,這個(gè)正方形的顏色將 會(huì)被覆蓋。目標(biāo)是在完成染色之后,每個(gè)紅色R都比每個(gè)綠色G距離最左側(cè)近浦徊。 返回最少需要涂染幾個(gè)正方形馏予。如樣例所示: s = RGRGR 我們涂染之后變成RRRGG滿足要求了,涂染的個(gè)數(shù)為2,沒(méi)有比這個(gè)更好的涂染方案瞧省。
- 題意就是要求紅色在左邊綠色在右邊召川。我們可以在內(nèi)個(gè)位置作一個(gè)分界線，計(jì)算滿足要求的最少的便函個(gè)數(shù)湃鹊，分割后會(huì)分成兩個(gè)部分冕香，左邊部分需要把綠色變成紅色蛹尝，右邊部分需要把紅色變成綠色，沒(méi)分一次統(tǒng)計(jì)此時(shí)的變換次數(shù)然后選出次數(shù)最少的悉尾。如果不優(yōu)化每一次都會(huì)重新計(jì)算左邊G的個(gè)數(shù)突那，右邊R的個(gè)數(shù)，我們可以用預(yù)處理技巧收集每個(gè)位置左邊個(gè)數(shù)构眯，右邊R的個(gè)數(shù)愕难。
/**
* 有一些排成一行的正方形。每個(gè)正方形已經(jīng)被染成紅色或者綠色”拱裕現(xiàn)在可以選擇任意一個(gè)正方形然后用這兩種顏
* 色的任意一種進(jìn)行染色,這個(gè)正方形的顏色將 會(huì)被覆蓋猫缭。目標(biāo)是在完成染色之后,每個(gè)紅色R都比每個(gè)綠色G距離最左側(cè)近。
* 返回最少需要涂染幾個(gè)正方形壹店。如樣例所示: s = RGRGR 我們涂染之后變成RRRGG滿足要求了
* ,涂染的個(gè)數(shù)為2,沒(méi)有比這個(gè)更好的涂染方案猜丹。
*/
public class GRNum {
public static int grNum(String str){
if(str == null || str.length() ==0){
return 0;
}
char[] c = str.toCharArray();
int n = c.length;
// 由于是從左向右遍歷我們可以用一個(gè)變量表示左邊遍歷過(guò)得G的數(shù)量，
int gNum = 0;
// 用另一個(gè)變量表示總共的R的數(shù)量
int rNum = 0;
for (int i = 0; i < n; i++) {
if(c[i] == 'R'){
rNum += 1;
}
}
int min = Integer.MAX_VALUE;
int res = 0;
// 遍歷到 表示此時(shí)左邊部分是 0~i-1,右邊部分i~n-1
// 有兩個(gè)邊界條件硅卢，全是G和全是R
for (int i = 0; i < n; i++) {
// res = 左邊部分的G的個(gè)數(shù)加上右邊部分R的個(gè)數(shù)
res = gNum + rNum;
if(c[i] == 'G'){
gNum += 1;
}else{
rNum -= 1;
}
min = Math.min(res,min);
}
// 全是R的時(shí)候
min = Math.min(min,gNum+rNum);
return min;
}
public static void main(String[] args) {
String str = "GGRRRR";
System.out.println(grNum(str));
}
}
給定一個(gè)N*N的矩陣matrix射窒，只有0和1兩種值，返回邊框全是1的最大正方形的邊長(zhǎng)長(zhǎng)度将塑。
例如:
01111
01001
01001
01111
01011
其中邊框全是1的最大正方形的大小為4*4脉顿，所以返回4。
- 邊長(zhǎng)為N的矩陣中長(zhǎng)方形的個(gè)數(shù)數(shù)量級(jí)是O(N^4)
- 正方形是O(N^3)
- 在矩陣中枚舉所有點(diǎn)抬旺，枚舉所有可能的邊長(zhǎng)讓后校驗(yàn)此邊長(zhǎng)下是否符合題意都是1弊予，可以完成，但是每次判斷是否都是1時(shí)需要重新計(jì)算復(fù)雜度高,用預(yù)處理技巧加速校驗(yàn)過(guò)程开财。
public class OneMatrix {
public static int oneMatrix(int[][] matrix){
if(matrix == null || matrix.length == 0){
return 0;
}
int rowN = matrix.length;
int colN = matrix[0].length;
// row[i][j] 表示i汉柒，j這個(gè)點(diǎn)開(kāi)始右邊連續(xù)1的長(zhǎng)度
int[][] row = new int[rowN][colN];
// col[i][j] 表示i,j位置開(kāi)始所有向下最長(zhǎng)的連續(xù)1的長(zhǎng)度
int[][] col = new int[rowN][colN];
generateRowArr(matrix,row,rowN - 1,colN - 1);
generateColArr(matrix,col,rowN - 1,colN - 1);
// 枚舉所有點(diǎn)和邊長(zhǎng)
int max = 0;
for (int i = 0; i < rowN; i++) {
for (int j = 0; j < colN; j++) {
for (int k = 1;k <= rowN;k++){
// 計(jì)算此時(shí)點(diǎn)是否符合
if(isV(row,col,i,j,k)){
max = Math.max(max,k);
}
}
}
}
return max;
}
private static boolean isV(int[][] r,int[][] c,int i ,int j,int k){
// 取出水平方向的長(zhǎng)度
int rowL = r[i][j];
// 豎直方向的長(zhǎng)度
int colL = c[i][j];
if(rowL >= k && colL >= k){
return true;
}
return false;
}
private static void generateRowArr(int[][] matrix,int[][] r,int row,int col){
for(int i = 0;i <= row ;i++){
r[i][col] = matrix[i][col] == 1 ? 1 : 0;
}
for (int i = 0; i <= row; i++) {
// 每一行從右向左填
for (int j = col - 1; j >= 0; j--) {
r[i][j] = matrix[i][j] == 1 ? 1 + r[i][j+1]:0;
}
}
}
private static void generateColArr(int[][] matrix,int[][] c,int row,int col){
for(int i = 0;i <= col ;i++){
c[row][i] = matrix[row][i] == 1 ? 1 : 0;
}
// 從下往上填
for (int i = row-1; i >= 0 ; i--) {
for (int j = 0; j <= col; j++) {
c[i][j] = matrix[i][j] == 1 ? 1 + c[i+1][j]:0;
}
}
}
public static void main(String[] args) {
int[][] arr = new int[][]{
{0,1,1,1,1},
{0,1,0,0,1},
{0,1,0,0,1},
{0,1,1,1,1},
{0,1,0,1,1}
};
System.out.println(oneMatrix(arr));
}
}
有n個(gè)打包機(jī)器從左到右一字排開(kāi)误褪，上方有一個(gè)自動(dòng)裝置會(huì)抓取一批放物品到每個(gè)打 包機(jī)上，放到每個(gè)機(jī)器上的這些物品數(shù)量有多有少碾褂，由于物品數(shù)量不相同兽间，需要工人 將每個(gè)機(jī)器上的物品進(jìn)行移動(dòng)從而到達(dá)物品數(shù)量相等才能打包。每個(gè)物品重量太大正塌、 每次只能搬一個(gè)物品進(jìn)行移動(dòng)嘀略，為了省力，只在相鄰的機(jī)器上移動(dòng)乓诽。請(qǐng)計(jì)算在搬動(dòng)最 小輪數(shù)的前提下帜羊，使每個(gè)機(jī)器上的物品數(shù)量相等。如果不能使每個(gè)機(jī)器上的物品相同鸠天， 返回-1讼育。 例如[1,0,5]表示有3個(gè)機(jī)器，每個(gè)機(jī)器上分別有1稠集、0奶段、5個(gè)物品，經(jīng)過(guò)這些輪后:
第一輪:1 0 <- 5 => 1 1 4第二輪:1 <- 1 <- 4 => 2 1 3第三輪:2 1 <- 3 => 2 2 2
移動(dòng)了3輪剥纷，每個(gè)機(jī)器上的物品相等痹籍，所以返回3
例如[2,2,3]表示有3個(gè)機(jī)器，每個(gè)機(jī)器上分別有2晦鞋、2蹲缠、3個(gè)物品， 這些物品不管怎么移動(dòng)鳖宾，都不能使三個(gè)機(jī)器上物品數(shù)量相等吼砂，返回-1枚舉每個(gè)位置,比如現(xiàn)在一共有sum個(gè)貨物，現(xiàn)在在i位置鼎文，i的左邊實(shí)際有貨物L(fēng) ，右邊實(shí)際有貨物R因俐，達(dá)標(biāo)情況下每個(gè)位置的貨物為x,i的左邊有機(jī)器n,右邊有機(jī)器m拇惋，則有如下情況。
1.如果左邊實(shí)際的貨物比nx大抹剩，右邊實(shí)際貨物比mx大撑帖，則取兩邊Max((L-nx),(R-mx));
2.如果L-（nx）>0,R-(mx)<0, 取絕對(duì)值大的。
3.如果L-（nx）<0,R-(mx)>0, 取絕對(duì)值大的澳眷。
4.如果L-（nx）<0,R-(mx)<0,絕對(duì)值相加胡嘿。
遍歷每個(gè)位置去最大值。
/**
* 有n個(gè)打包機(jī)器從左到右一字排開(kāi)钳踊，上方有一個(gè)自動(dòng)裝置會(huì)抓取一批放物品到每個(gè)打 包機(jī)上衷敌，放到每個(gè)機(jī)器上的這些物品數(shù)量有多有少勿侯，
* 由于物品數(shù)量不相同，需要工人 將每個(gè)機(jī)器上的物品進(jìn)行移動(dòng)從而到達(dá)物品數(shù)量相等才能打包缴罗。每個(gè)物品重量太大助琐、
* 每次只能搬一個(gè)物品進(jìn)行移動(dòng)，為了省力面氓，只在相鄰的機(jī)器上移動(dòng)兵钮。請(qǐng)計(jì)算在搬動(dòng)最 小輪數(shù)的前提下，使每個(gè)機(jī)器上的物品數(shù)量相等
* 舌界。如果不能使每個(gè)機(jī)器上的物品相同掘譬， 返回-1。 例如[1,0,5]表示有3個(gè)機(jī)器呻拌，每個(gè)機(jī)器上分別有1葱轩、0、5個(gè)物品柏锄，經(jīng)過(guò)這些輪后:
* 第一輪:1 0 <- 5 => 1 1 4第二輪:1 <- 1 <- 4 => 2 1 3第三輪:2 1 <- 3 => 2 2 2
* 移動(dòng)了3輪酿箭，每個(gè)機(jī)器上的物品相等，所以返回3
* 例如[2,2,3]表示有3個(gè)機(jī)器趾娃，每個(gè)機(jī)器上分別有2缭嫡、2、3個(gè)物品抬闷， 這些物品不管怎么移動(dòng)妇蛀，都不能使三個(gè)機(jī)器上物品數(shù)量相等，返回-1
*/
public class Machine {
public static int machine(int[] arr){
if(arr == null || arr.length == 0){
return -1;
}
// 求總數(shù)一個(gè)有幾件物品
int n = arr.length;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
// 不能被整除也不符合要求
if(sum % n != 0){
return -1;
}
// 左邊實(shí)際總數(shù)(右邊貨物的數(shù)量只需要總數(shù)減去左邊的和i位置的數(shù)量就可)
int left = 0;
// 平均每個(gè)位置應(yīng)該有的貨物數(shù)量
int average = sum / n;
int max = 0;
int temp = 0;
for (int i = 0; i < n; i++) {
if(((left - i * average) < 0) && ((sum - left-arr[i]) - ((n-i-1)*average))<0){
temp = Math.abs(left - i * average) + Math.abs((sum - left-arr[i])-((n-i-1)*average));
max = Math.max(max,temp);
}else{
temp = Math.max(Math.abs(left - i * average),Math.abs((sum - left-arr[i]) - ((n-i-1)*average)));
max = Math.max(max,temp);
}
left += arr[i];
}
return max;
}
public static void main(String[] args) {
int[] arr = {1,0,5};
System.out.println(machine(arr));
}
}
- 給定一個(gè)數(shù)組arr長(zhǎng)度為N笤成，你可以把任意長(zhǎng)度大于0且小于N的前綴作為左部分评架，剩下的 作為右部分。
但是每種劃分下都有左部分的最大值和右部分的最大值炕泳，請(qǐng)返回最大的纵诞， 左部分最大值減去右部分最大值的絕對(duì)值。 - 流程求數(shù)組中的最大值培遵，然后減去0位置和i-1位置較小的那個(gè)一數(shù)浙芙。
/**
* 給定一個(gè)數(shù)組arr長(zhǎng)度為N，你可以把任意長(zhǎng)度大于0且小于N的前綴作為左部分籽腕，剩下的 作為右部分嗡呼。
*
* 但是每種劃分下都有左部分的最大值和右部分的最大值，請(qǐng)返回最大的皇耗， 左部分最大值減去右部分最大值的絕對(duì)值南窗。
*/
public class ArrayOfMax {
public static int arrayOfMax(int[] arr){
// 假設(shè)輸入?yún)?shù)有效
int n = arr.length;
int max = arr[0];
for (int i = 1; i < n; i++) {
max = Math.max(arr[i],max);
}
int temp = arr[0] > arr[n-1] ? arr[n-1] : arr[0];
return max - temp;
}
}
- 給定一個(gè)數(shù)組arr，已知其中所有的值都是非負(fù)的，將這個(gè)數(shù)組看作一個(gè)容器万伤， 請(qǐng)返回容器能裝多少水比如窒悔，arr = {3，1壕翩，2蛉迹，5，2放妈，4}北救，根據(jù)值畫(huà)出的直方圖就是容器形狀，該容 器可以裝下5格水再比如芜抒，arr = {4珍策，5，1宅倒，3攘宙，2}，該容器可以裝下2格水拐迁。
- 雙指針蹭劈，數(shù)組的頭和尾不可能形成容器直接跳過(guò)，記錄一個(gè)左邊最大值线召，一個(gè)右邊最大值铺韧，如果左小于右先結(jié)算左邊水量，如果右小于左先結(jié)算右邊的水量缓淹，哪邊是瓶頸就先結(jié)算哪邊的水量哈打。
public class Water {
public static int water(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
int n = arr.length;
// 由于首尾都不能形成容器，多以不計(jì)算首位
// 一開(kāi)始的左邊最大就是0位置讯壶，右邊最大就是n-1位置
int leftMax = arr[0];
int rightMax = arr[n-1];
int L = 1;
int R = n - 2;
int water = 0;
// 哪邊的最大值是小先結(jié)算哪邊（小的一邊是瓶頸）
while (L <= R){
if(leftMax < rightMax){
// 結(jié)算左邊
water += Math.max(0,leftMax - arr[L]);
leftMax = Math.max(leftMax,arr[L++]);
}else {
// 結(jié)算右邊
water += Math.max(0,rightMax - arr[R]);
rightMax = Math.max(rightMax,arr[R--]);
}
}
return water;
}
public static void main(String[] args) {
int[] arr = {4,5,1,3,2};
System.out.println(water(arr));
}
}
- 如果給你一個(gè)二維數(shù)組料仗，每一個(gè)值表示這一塊地形的高度，
求整塊地形能裝下多少水伏蚊。 - 利用小根堆求解立轧。由于四個(gè)邊都不能形成裝水區(qū)域，首先把四個(gè)邊加入到小根堆中躏吊，在準(zhǔn)備一個(gè)布爾類型的二維數(shù)組肺孵，記錄所有進(jìn)過(guò)小根堆的位置，進(jìn)過(guò)一次后就不允許在進(jìn)入小根堆了颜阐。每次彈出一個(gè)元素然后收集他相鄰的上下左右四個(gè)位置的水位，然后把四個(gè)位置放入下根堆吓肋，重復(fù)上述過(guò)程直到小根堆變?yōu)榭铡?/li>
/**
* 如果給你一個(gè)二維數(shù)組凳怨，每一個(gè)值表示這一塊地形的高度，
* 求整塊地形能裝下多少水。
*/
public class HeapWater {
public static int heapWater(int[][] matrix){
if(matrix == null || matrix.length == 0){
return 0;
}
// 小根堆
PriorityQueue<Node> heap = new PriorityQueue<>(new MyComparator());
// 先把二維數(shù)組四個(gè)邊加入到堆中
int rowNum = matrix.length;
int colNum = matrix[0].length;
boolean[][] flag = new boolean[rowNum][colNum];
for (int i = 0;i < colNum;i++){
// 上下兩行
heap.offer(new Node(matrix[0][i],0,i));
heap.offer(new Node(matrix[rowNum-1][i],rowNum-1,i));
flag[0][i] = true;
flag[rowNum-1][i] = true;
}
for (int i = 1; i < rowNum-1; i++) {
// 左右兩列
heap.offer(new Node(matrix[i][0],i,0));
heap.offer(new Node(matrix[i][colNum-1],i,colNum-1));
flag[i][0] = true;
flag[i][colNum-1] = true;
}
int max = 0;
int water = 0;
while (!heap.isEmpty()){
// 彈出元素收集上下左右的水
Node poll = heap.poll();
max = Math.max(max,poll.value);
// 進(jìn)過(guò)小根堆的元素都是結(jié)算過(guò)得不要重復(fù)結(jié)算
if(poll.i-1>=0 &&!flag[poll.i-1][poll.j]){
water += Math.max(0,(max-matrix[poll.i-1][poll.j]));
heap.offer(new Node(matrix[poll.i-1][poll.j],poll.i-1,poll.j));
flag[poll.i-1][poll.j] = true;
}
if(poll.i+1 < rowNum && !flag[poll.i+1][poll.j]){
water += Math.max(0,(max-matrix[poll.i+1][poll.j]));
heap.offer(new Node(matrix[poll.i+1][poll.j],poll.i+1,poll.j));
flag[poll.i+1][poll.j] = true;
}
if(poll.j-1>=0 && !flag[poll.i][poll.j-1]){
water += Math.max(0,max-(matrix[poll.i][poll.j-1]));
heap.offer(new Node(matrix[poll.i][poll.j-1],poll.i,poll.j-1));
flag[poll.i][poll.j-1] = true;
}
if(poll.j+1<colNum && !flag[poll.i][poll.j+1]){
water += Math.max(0,(max-matrix[poll.i][poll.j+1]));
heap.offer(new Node(matrix[poll.i][poll.j+1],poll.i,poll.j+1));
flag[poll.i][poll.j+1] = true;
}
}
return water;
}
// 自定義比較器
static class MyComparator implements Comparator<Node>{
@Override
public int compare(Node o1, Node o2) {
return o1.value - o2.value;
}
}
public static void main(String[] args) {
int[][] martix = {
{4,4,4,4,4},
{4,1,4,1,4},
{4,2,4,3,4},
{4,4,4,4,4}
};
System.out.println(heapWater(martix));
}
}
public class Node {
// 橫坐標(biāo)
public int i;
// 縱坐標(biāo)
public int j;
int value;
public Node(int value,int i,int j){
this.value = value;
this.i = i;
this.j = j;
}
}
- 給定一個(gè)有序數(shù)組arr肤舞，給定一個(gè)正數(shù)aim
1）返回累加和為aim的紫新，所有不同二元組
2）返回累加和為aim的，所有不同三元組 - 雙指針求解李剖。定義雙指針L和R,應(yīng)為數(shù)組是有序的那么必然存在單調(diào)性芒率，規(guī)定arr[L]+arr[R]和為S，當(dāng)S>aim時(shí)向左移動(dòng)R篙顺，當(dāng)S小于aim時(shí)偶芍，向右移動(dòng)R，當(dāng)S等于aim時(shí)找到一個(gè)二元組德玫。注意只有在L不等于L-1或者R不等R+1的情況下才收集答案匪蟀，應(yīng)為這種情況下收集到的答案是第一次遇到的二元組。
/**
* 給定一個(gè)有序數(shù)組arr宰僧，給定一個(gè)正數(shù)aim
* 1）返回累加和為aim的材彪，所有不同二元組
* 2）返回累加和為aim的，所有不同三元組
*/
public class ErYaun {
// 返回二維數(shù)組每一行代表一個(gè)二元組琴儿，第一列代表二元組中第一個(gè)數(shù)
// 第二列代表二元組中第二個(gè)數(shù)
public static List<Yuan> erYuan(int[] arr, int aim){
if(arr == null || arr.length == 0){
return null;
}
int n = arr.length;
List<Yuan> res = new ArrayList<>();
// 定義雙指針
int L = 0;
int R = n - 1;
while (L < R){
if(arr[L]+arr[R] < aim){
// L向右移動(dòng)
L ++;
}else if(arr[L]+arr[R] > aim){
// R向左移動(dòng)
R --;
}else{
if(L == 0 || arr[L] != arr[L-1]){
res.add(new Yuan(arr[L++],arr[R]));
}else{
L++;
}
}
}
return res;
}
// 三元段化，從頭到尾遍歷元素，當(dāng)前位置i 用aim - arr[i] 看i+1開(kāi)始有多少二元組達(dá)標(biāo)aim-arr[i]
public static List<SanYuan> sanYuan(int[] arr,int aim){
if(arr == null || arr.length == 0){
return null;
}
int n = arr.length;
List<SanYuan> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
// 定義雙指針,每次開(kāi)頭都會(huì)變化
int L = i + 1;
int R = n - 1;
int temp = aim - arr[i];
while (L < R){
if(arr[L]+arr[R] < temp){
// L向右移動(dòng)
L ++;
}else if(arr[L]+arr[R] > temp){
// R向左移動(dòng)
R --;
}else{
if(L == 0 || arr[L] != arr[L-1]){
res.add(new SanYuan(arr[i],arr[L++],arr[R]));
}else{
L++;
}
}
}
}
return res;
}
}
- 長(zhǎng)度為N的數(shù)組arr造成，一定可以組成N^2個(gè)數(shù)值對(duì)显熏。
例如arr = [3,1,2]，
數(shù)值對(duì)有(3,3) (3,1) (3,2) (1,3) (1,1) (1,2) (2,3) (2,1) (2,2)谜疤，
也就是任意兩個(gè)數(shù)都有數(shù)值對(duì)佃延，而且自己和自己也算數(shù)值對(duì)。
數(shù)值對(duì)怎么排序夷磕？規(guī)定履肃，第一維數(shù)據(jù)從小到大，第一維數(shù)據(jù)一樣的坐桩，第二維數(shù)組也從小到大尺棋。所以上面的數(shù)值對(duì)排序的結(jié)果為：
(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3)
給定一個(gè)數(shù)組arr，和整數(shù)k绵跷，返回第k小的數(shù)值對(duì)膘螟。 - 假設(shè)數(shù)組有序，那么第K小的數(shù)值對(duì)的第一元素在原素組的下標(biāo)其實(shí)可以算出來(lái)是index = k-1/n,根據(jù)第一維下標(biāo)可以知道幫我們搞定了前面n(index)個(gè)碾局，還有幾個(gè)要搞定呢荆残？-> k-(n(index))個(gè)，第二個(gè)下標(biāo)就是求在大于等于index情況下找出（k-nindex）個(gè)的位置（k-nindex）/n
/**
* 長(zhǎng)度為N的數(shù)組arr净当，一定可以組成N^2個(gè)數(shù)值對(duì)内斯。
* 例如arr = [3,1,2]蕴潦，
* 數(shù)值對(duì)有(3,3) (3,1) (3,2) (1,3) (1,1) (1,2) (2,3) (2,1) (2,2)，
* 也就是任意兩個(gè)數(shù)都有數(shù)值對(duì)俘闯，而且自己和自己也算數(shù)值對(duì)潭苞。
* 數(shù)值對(duì)怎么排序？規(guī)定真朗，第一維數(shù)據(jù)從小到大此疹，第一維數(shù)據(jù)一樣的，第二維數(shù)組也從小到大遮婶。所以上面的數(shù)值對(duì)排序的結(jié)果為：
* (1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3)
*
* 給定一個(gè)數(shù)組arr蝗碎，和整數(shù)k，返回第k小的數(shù)值對(duì)蹭睡。
*/
public class KSmall {
public static int[] kSmall(int[] arr,int k){
if(arr == null || arr.length == 0){
return null;
}
int n = arr.length;
if(k > n*n){
return null;
}
// 定位第一個(gè)坐標(biāo)衍菱，如果數(shù)組長(zhǎng)度為n,那么我們知道第一元素會(huì)幫我搞定n個(gè)數(shù)值對(duì)
// 第二個(gè)會(huì)幫我搞定n個(gè)數(shù)值對(duì)，所以我們可以得知如果求第k小那么在有序數(shù)組中
// 第一維小標(biāo)一定在(k-1)/n的位置
int firstIndex = (k - 1) / n;
// 第二維元素求解肩豁，若我們已經(jīng)知道了第一維的下標(biāo)脊串，那么小于這個(gè)小標(biāo)的數(shù)的個(gè)數(shù)我們假設(shè)為a,等于這個(gè)下標(biāo)位置數(shù)的個(gè)數(shù)為b
// a可以幫我們搞定a*n個(gè)，那么還剩下k-a*n個(gè)沒(méi)搞定清钥，一定是用等于等于這個(gè)下標(biāo)的數(shù)字完成的有b個(gè)小標(biāo)為(k-a*n) - 1/b
// 小于數(shù)量
int small = 0;
// 等于數(shù)量
int eq = 0;
// 利用parttion過(guò)程求無(wú)數(shù)數(shù)組中第k小問(wèn)題
int r1 = process(arr,0,n-1,firstIndex);
for(int i = 0;i < n;i++){
if(arr[i] < r1){
small++;
}
if(arr[i] == r1) {
eq ++;
}
}
int r2 = process(arr,0,n-1,((k-small*n)-1)/eq);
return new int[]{r1,r2};
}
// 無(wú)序數(shù)組中求第k小的數(shù)琼锋，時(shí)間復(fù)雜度O(N)
private static int[] parttion(int[] arr,int L,int R,int aim){
// 小于區(qū)域
int less = L-1;
// 大于區(qū)域
int more = R+1;
int cur = L;
// 一次循環(huán)小于index位置數(shù)的進(jìn)小于區(qū)域，
// 大于index 位置數(shù)的進(jìn)大于區(qū)域
// 等于index位置數(shù)的不動(dòng)
while (cur < more){
if(arr[cur] < aim){
// 進(jìn)小于區(qū)域,跟小于區(qū)域下一個(gè)位置交換祟昭，小于區(qū)域向右擴(kuò)一個(gè)位置
// 當(dāng)前元素向前移動(dòng)一個(gè)位置
swap(arr,cur++,++less);
}else if(arr[cur] > aim){
// 進(jìn)大于區(qū)域缕坎，跟大于區(qū)域前一個(gè)交換，大于區(qū)域向左縮小一個(gè)位置
// 當(dāng)前位置不變
swap(arr,cur,--more);
}else {
cur++;
}
}
// 最后放回等于L~R必定都是等于k位置的數(shù)
return new int[]{less+1,more-1};
}
private static int process(int[] arr,int L,int R,int k){
while (L <= R){
// 只會(huì)進(jìn)一側(cè)
int aim = arr[L + (int)(Math.random()*(R - L+1))];
int[] parttion = parttion(arr, L, R,aim);
if(k >= parttion[0] && k<=parttion[1]){
return arr[parttion[0]];
}else if(k < parttion[0]){
R = parttion[0]-1;
}else {
L = parttion[1]+1;
}
}
// 這一句不會(huì)執(zhí)行
return 0;
}
private static void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
