517 Super Washing Machines

  • the least steps we need to eventually finish this process is determined by the peak of abs(cnt) (accumulative count of gain/lose array) and the max of “gain/lose” array. >For a single machine, necessary operations is to transfer dresses from one side to another until sum of both sides and itself reaches the average number. We can calculate (required dresses) - (contained dresses) of each side as L and R:

L > 0 && R > 0: both sides lacks dresses, and we can only export one dress from current machines at a time, so result is abs(L) + abs® L < 0 && R < 0: both sides contains too many dresses, and we can import dresses from both sides at the same time, so result is max(abs(L), abs®) L < 0 && R > 0 or L >0 && R < 0: the side with a larger absolute value will import/export its extra dresses from/to current machine or other side, so result is max(abs(L), abs®)

public class Solution {
public int findMinMoves(int[] machines) {
int total = 0;
for(int i: machines)
total += i;
if(total%machines.length != 0)
return -1;
int avg = total/machines.length, cnt = 0, max = 0;
for(int load: machines){
cnt += load-avg; //load-avg is "gain/lose"
max = Math.max(Math.max(max, Math.abs(cnt)), load-avg);
}
return max;
}
}
view raw 517_0906.java hosted with ❤ by GitHub

529 Minesweepe

  • think carefully B and E
    class Solution {
    // O(9^n) O(1)
    public char[][] updateBoard(char[][] board, int[] click) {
    int m = board.length;
    int n = board[0].length;
    if (click.length < 2) return board;
    int i = click[0];
    int j = click[1];
    if (board[i][j] == 'M') {
    board[i][j] = 'X';
    return board;
    }
    revealBoard(board, m, n, i, j);
    return board;
    }
    private void revealBoard(char[][] board, int m, int n, int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n) return;
    if (board[i][j] != 'E') return;
    int count = 0;
    for (int bi = -1; bi <= 1; bi++) {
    for (int bj = -1; bj <= 1; bj++) {
    if (bi == 0 && bj == 0) continue;
    count += countMines(board, m, n, i+bi, j+bj);
    }
    }
    if (count == 0) {
    board[i][j] = 'B';
    for (int bi = -1; bi <= 1; bi++) {
    for (int bj = -1; bj <= 1; bj++) {
    if (bi == 0 && bj == 0) continue;
    revealBoard(board, m, n, i+bi, j+bj);
    }
    }
    } else {
    board[i][j] = Character.forDigit(count, 10);
    }
    }
    private int countMines(char[][] board, int m, int n, int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n) return 0;
    if (board[i][j] == 'M') return 1;
    return 0;
    }
    }
    view raw 529_0906.java hosted with ❤ by GitHub

564. Find the Closest Palindrome

public class Solution {
public String mirroring(String s) {
String x = s.substring(0, (s.length()) / 2);
return x + (s.length() % 2 == 1 ? s.charAt(s.length() / 2) : "") + new StringBuilder(x).reverse().toString();
}
public String nearestPalindromic(String n) {
if (n.equals("1"))
return "0";
String a = mirroring(n);
long diff1 = Long.MAX_VALUE;
diff1 = Math.abs(Long.parseLong(n) - Long.parseLong(a));
if (diff1 == 0)
diff1 = Long.MAX_VALUE;
StringBuilder s = new StringBuilder(n);
int i = (s.length() - 1) / 2;
while (i >= 0 && s.charAt(i) == '0') {
s.replace(i, i + 1, "9");
i--;
}
if (i == 0 && s.charAt(i) == '1') {
s.delete(0, 1);
int mid = (s.length() - 1) / 2;
s.replace(mid, mid + 1, "9");
} else
s.replace(i, i + 1, "" + (char)(s.charAt(i) - 1));
String b = mirroring(s.toString());
long diff2 = Math.abs(Long.parseLong(n) - Long.parseLong(b));
s = new StringBuilder(n);
i = (s.length() - 1) / 2;
while (i >= 0 && s.charAt(i) == '9') {
s.replace(i, i + 1, "0");
i--;
}
if (i < 0) {
s.insert(0, "1");
} else
s.replace(i, i + 1, "" + (char)(s.charAt(i) + 1));
String c = mirroring(s.toString());
long diff3 = Math.abs(Long.parseLong(n) - Long.parseLong(c));
if (diff2 <= diff1 && diff2 <= diff3)
return b;
if (diff1 <= diff3 && diff1 <= diff2)
return a;
else
return c;
}
}
view raw 564_0906.java hosted with ❤ by GitHub

647. Palindromic Substrings

  • memo valid substring from i to j
    class Solution {
    // O(n^2) O(n^2)
    public int countSubstrings(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    int res = 0;
    for (int i = n - 1; i >= 0; i--) {
    dp[i][i] = 1;
    res++;
    for (int j = i+1; j < n; j++) {
    if (s.charAt(i) == s.charAt(j) && (i+1 == j || dp[i+1][j-1] == 1)) {
    dp[i][j] = 1;
    res++;
    }
    }
    }
    return res;
    }
    }
    view raw 647_0906.java hosted with ❤ by GitHub