Huahua’s Tech Road

花花酱 LeetCode 1278. Palindrome Partitioning III

By zxi on December 2, 2019

You are given a string s containing lowercase letters and an integer k. You need to :

First, change some characters of s to other lowercase English letters.
Then divide s into k non-empty disjoint substrings such that each substring is palindrome.

Return the minimal number of characters that you need to change to divide the string.

Example 1:

Input: s = "abc", k = 2
Output: 1
Explanation: You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.

Example 2:

Input: s = "aabbc", k = 3
Output: 0
Explanation: You can split the string into "aa", "bb" and "c", all of them are palindrome.

Example 3:

Input: s = "leetcode", k = 8
Output: 0

Constraints:

1 <= k <= s.length <= 100.
s only contains lowercase English letters.

Solution: DP

dp[i][k] := min changes to make s[0~i] into k palindromes
dp[i][k] = min(dp[j][k – 1] + cost(j + 1, i)) 0 <= j < i

ans = dp[n-1][K]

Time complexity: O(n^2 * K) = O(n^3)
Space complexity: O(n*n + n*K) = O(n^2)

C++

// Author: Huahua, 8 ms, 9.1 MB

class Solution {

public:

int palindromePartition(string s, int K) {

const int n = s.length();

auto minChange = [&](int i, int j) {

int c = 0;

while (i < j)

if (s[i++] != s[j--]) ++c;

return c;

};

vector<vector<int>> cost(n, vector<int>(n));

for (int i = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j)

cost[i][j] = minChange(i, j);

// dp[i][j] := min changes to make s[0~i] into k palindromes

vector<vector<int>> dp(n, vector<int>(K + 1, INT_MAX / 2));

for (int i = 0; i < n; ++i) {

dp[i][1] = cost[0][i];

for (int k = 1; k <= K; ++k)

for (int j = 0; j < i; ++j)

dp[i][k] = min(dp[i][k], dp[j][k - 1] + cost[j + 1][i]);

}

return dp[n - 1][K];

}

};

C++/DP+DP

// Author: Huahua, 4 ms, 9.1MB

class Solution {

public:

int palindromePartition(string s, int K) {

const int n = s.length();

vector<vector<int>> cost(n, vector<int>(n));

for (int l = 2; l <= n; ++l)

for (int i = 0, j = l - 1; j < n; ++i, ++j)

cost[i][j] = (s[i] != s[j]) + cost[i + 1][j - 1];

vector<vector<int>> dp(n, vector<int>(K + 1, INT_MAX / 2));

for (int i = 0; i < n; ++i) {

dp[i][1] = cost[0][i];

for (int k = 2; k <= K; ++k)

for (int j = 0; j < i; ++j)

dp[i][k] = min(dp[i][k], dp[j][k - 1] + cost[j + 1][i]);

}

return dp[n - 1][K];

}

};

Python3

// Author: Huahua

import functools

class Solution:

def palindromePartition(self, s: str, K: int) -> int:

@functools.lru_cache(None)

def cost(i: int, j: int) -> int:

if i >= j: return 0

return cost(i + 1, j - 1) + (1 if s[i] != s[j] else 0)

@functools.lru_cache(None)

def dp(i: int, k: int) -> int:

if k == 1: return cost(0, i)

if k == i + 1: return 0

if k > i + 1: return 1**9

return min([dp(j, k - 1) + cost(j + 1, i) for j in range(i)])

return dp(len(s) - 1, K)

花花酱 LeetCode 1277. Count Square Submatrices with All Ones

By zxi on December 1, 2019

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

Constraints:

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1

Solution: DP

dp[i][j] := edge of largest square with bottom right corner at (i, j)
dp[i][j] = min(dp[i – 1][j], dp[i – 1][j – 1], dp[i][j – 1]) if m[i][j] == 1 else 0
ans = sum(dp)

Time complexity: O(n*m)
Space complexity: O(n*m)

C++

// Author: Huahua

class Solution {

public:

int countSquares(vector<vector<int>>& matrix) {

const int n = matrix.size();

const int m = matrix[0].size();

// dp[i][j] := edge of largest square with right bottom corner at (i, j)

vector<vector<int>> dp(n, vector<int>(m));

int ans = 0;

for (int i = 0; i < n; ++i)

for (int j = 0; j < m; ++j) {

dp[i][j] = matrix[i][j];

if (i && j && dp[i][j])

dp[i][j] = min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1;

ans += dp[i][j];

}

return ans;

}

};

花花酱 1276. Number of Burgers with No Waste of Ingredients

By zxi on December 1, 2019

Given two integers tomatoSlices and cheeseSlices. The ingredients of different burgers are as follows:

Jumbo Burger: 4 tomato slices and 1 cheese slice.
Small Burger: 2 Tomato slices and 1 cheese slice.

Return [total_jumbo, total_small] so that the number of remaining tomatoSlices equal to 0 and the number of remaining cheeseSlices equal to 0. If it is not possible to make the remaining tomatoSlices and cheeseSlices equal to 0 return [].

Example 1:

Input: tomatoSlices = 16, cheeseSlices = 7
Output: [1,6]
Explantion: To make one jumbo burger and 6 small burgers we need 4*1 + 2*6 = 16 tomato and 1 + 6 = 7 cheese. There will be no remaining ingredients.

Example 2:

Input: tomatoSlices = 17, cheeseSlices = 4
Output: []
Explantion: There will be no way to use all ingredients to make small and jumbo burgers.

Example 3:

Input: tomatoSlices = 4, cheeseSlices = 17
Output: []
Explantion: Making 1 jumbo burger there will be 16 cheese remaining and making 2 small burgers there will be 15 cheese remaining.

Example 4:

Input: tomatoSlices = 0, cheeseSlices = 0
Output: [0,0]

Example 5:

Input: tomatoSlices = 2, cheeseSlices = 1
Output: [0,1]

Constraints:

0 <= tomatoSlices <= 10^7
0 <= cheeseSlices <= 10^7

Solution: Math

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> numOfBurgers(int T, int C) {

// Jumbo = x, small = y

// 4x + 2y = T

// x + y = C

// x = (T - 2C) / 2

int x = T / 2 - C;

int y = C - x;

if (4 * x + 2 * y == T && x >= 0 && y >= 0) return {x, y};

return {};

}

};

花花酱 LeetCode 1275. Find Winner on a Tic Tac Toe Game

By zxi on December 1, 2019

Tic-tac-toe is played by two players A and B on a 3 x 3 grid.

Here are the rules of Tic-Tac-Toe:

Players take turns placing characters into empty squares (” “).
The first player A always places “X” characters, while the second player B always places “O” characters.
“X” and “O” characters are always placed into empty squares, never on filled ones.
The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.

Given an array moves where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which A and B play.

Return the winner of the game if it exists (A or B), in case the game ends in a draw return “Draw”, if there are still movements to play return “Pending”.

You can assume that moves is valid (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.

Example 1:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: "A" wins, he always plays first.
"X  "    "X  "    "X  "    "X  "    "X  "
"   " -> "   " -> " X " -> " X " -> " X "
"   "    "O  "    "O  "    "OO "    "OOX"

Example 2:

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: "B" wins.
"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

Example 3:

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.
"XXO"
"OOX"
"XOX"

Example 4:

Input: moves = [[0,0],[1,1]]
Output: "Pending"
Explanation: The game has not finished yet.
"X  "
" O "
"   "

Constraints:

1 <= moves.length <= 9
moves[i].length == 2
0 <= moves[i][j] <= 2
There are no repeated elements on moves.
moves follow the rules of tic tac toe.

Solution: Simulation

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string tictactoe(vector<vector<int>>& moves) {

vector<vector<string>> b(3, vector<string>(3, "#"));

bool A = true;

for (const auto& move : moves) {

b[move[0]][move[1]] = A ? "A" : "B";

A = !A;

}

for (int i = 0; i < 3; ++i) {

if (b[i][0] == b[i][1] && b[i][2] == b[i][1] && b[i][0] != "#")

return b[i][0];

if (b[0][i] == b[1][i] && b[2][i] == b[1][i] && b[0][i] != "#")

return b[0][i];

}

if (b[0][0] == b[1][1] && b[1][1] == b[2][2] && b[1][1] != "#")

return b[1][1];

if (b[2][0] == b[1][1] && b[1][1] == b[0][2] && b[1][1] != "#")

return b[1][1];

return moves.size() == 9 ? "Draw" : "Pending";

}

};

花花酱 LeetCode 1274. Number of Ships in a Rectangle

By zxi on December 1, 2019

(This problem is an interactive problem.)

On the sea represented by a cartesian plane, each ship is located at an integer point, and each integer point may contain at most 1 ship.

You have a function Sea.hasShips(topRight, bottomLeft) which takes two points as arguments and returns true if and only if there is at least one ship in the rectangle represented by the two points, including on the boundary.

Given two points, which are the top right and bottom left corners of a rectangle, return the number of ships present in that rectangle. It is guaranteed that there are at most 10 ships in that rectangle.

Submissions making more than 400 calls to hasShips will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example :

Input: 
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3
Explanation: From [0,0] to [4,4] we can count 3 ships within the range.

Constraints:

On the input ships is only given to initialize the map internally. You must solve this problem “blindfolded”. In other words, you must find the answer using the given hasShips API, without knowing the ships position.
0 <= bottomLeft[0] <= topRight[0] <= 1000
0 <= bottomLeft[1] <= topRight[1] <= 1000

Solution: Divide and Conquer

If the current rectangle contains ships, subdivide it into 4 smaller ones until
1) no ships contained
2) the current rectangle is a single point (e.g. topRight == bottomRight)

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

// Modify the interface to pass sea as a reference.

int countShips(Sea& sea, vector<int> topRight, vector<int> bottomLeft) {

int x1 = bottomLeft[0], y1 = bottomLeft[1];

int x2 = topRight[0], y2 = topRight[1];

if (x1 > x2 || y1 > y2 || !sea.hasShips(topRight, bottomLeft))

return 0;

if (x1 == x2 && y1 == y2)

return 1;

int xm = x1 + (x2 - x1) / 2;

int ym = y1 + (y2 - y1) / 2;

return countShips(sea, {xm, ym}, {x1, y1}) + countShips(sea, {xm, y2}, {x1, ym + 1})

+ countShips(sea, {x2, ym}, {xm + 1, y1}) + countShips(sea, {x2, y2}, {xm + 1, ym + 1});

}

};

Huahua's Tech Road

花花酱 LeetCode 1278. Palindrome Partitioning III

Solution: DP

C++

C++/DP+DP

Python3

花花酱 LeetCode 1277. Count Square Submatrices with All Ones

Solution: DP

C++

花花酱 1276. Number of Burgers with No Waste of Ingredients

Solution: Math

C++

花花酱 LeetCode 1275. Find Winner on a Tic Tac Toe Game

Solution: Simulation

C++

花花酱 LeetCode 1274. Number of Ships in a Rectangle

Solution: Divide and Conquer

C++