Posts tagged as “medium”

花花酱 LeetCode 794. Valid Tic-Tac-Toe State

By zxi on March 3, 2018

题目大意：判断一个井字棋的棋盘是否有效。

A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array, and consists of characters " ", "X", and "O". The ” ” character represents an empty square.

Here are the rules of Tic-Tac-Toe:

Players take turns placing characters into empty squares (” “).
The first player always places “X” characters, while the second player always places “O” characters.
“X” and “O” characters are always placed into empty squares, never 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.

Example 1:

Input: board = ["O ", " ", " "]

Output: false

Explanation: The first player always plays "X".

Example 2:

Input: board = ["XOX", " X ", " "]

Output: false

Explanation: Players take turns making moves.

Example 3:

Input: board = ["XXX", " ", "OOO"]

Output: false

Example 4:

Input: board = ["XOX", "O O", "XOX"]

Output: true

Note:

board is a length-3 array of strings, where each string board[i] has length 3.
Each board[i][j] is a character in the set {" ", "X", "O"}.

Idea: Verify all rules

C++

class Solution {

public:

bool validTicTacToe(vector<string>& board) {

int x = 0;

int o = 0;

int wins_x = getWins(board, 'X', x);

int wins_o = getWins(board, 'O', o);

return wins_x + wins_o <= 1 && x >= o + wins_x && x <= o + 1 - wins_o;

}

private:

int getWins(const vector<string>& board, char p, int& count) {

vector<string> rows(3);

string diag1, diag2;

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

diag1 += board[i][i];

diag2 += board[i][2 - i];

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

char c = board[i][j];

rows[j] += c;

count += c == p;

}

string win(3, p);

int wins = (diag1 == win) + (diag2 == win);

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

wins += rows[i] == win;

wins += board[i] == win;

}

return wins;

}

};

花花酱 LeetCode 468. Validate IP Address

By zxi on March 1, 2018

题目大意：给你一个字符串，让你判断是否是合法的ipv4或者ipv6地址，都不合法返回Neighter.

Write a function to check whether an input string is a valid IPv4 address or IPv6 address or neither.

IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots (“.”), e.g.,172.16.254.1;

Besides, leading zeros in the IPv4 is invalid. For example, the address 172.16.254.01 is invalid.

IPv6 addresses are represented as eight groups of four hexadecimal digits, each group representing 16 bits. The groups are separated by colons (“:”). For example, the address 2001:0db8:85a3:0000:0000:8a2e:0370:7334 is a valid one. Also, we could omit some leading zeros among four hexadecimal digits and some low-case characters in the address to upper-case ones, so 2001:db8:85a3:0:0:8A2E:0370:7334 is also a valid IPv6 address(Omit leading zeros and using upper cases).

However, we don’t replace a consecutive group of zero value with a single empty group using two consecutive colons (::) to pursue simplicity. For example, 2001:0db8:85a3::8A2E:0370:7334 is an invalid IPv6 address.

Besides, extra leading zeros in the IPv6 is also invalid. For example, the address 02001:0db8:85a3:0000:0000:8a2e:0370:7334 is invalid.

Note: You may assume there is no extra space or special characters in the input string.

Example 1:

Input: "172.16.254.1"

Output: "IPv4"

Explanation: This is a valid IPv4 address, return "IPv4".

Example 2:

Input: "2001:0db8:85a3:0:0:8A2E:0370:7334"

Output: "IPv6"

Explanation: This is a valid IPv6 address, return "IPv6".

Example 3:

Input: "256.256.256.256"

Output: "Neither"

Explanation: This is neither a IPv4 address nor a IPv6 address.

Solution 1: String / Brute force

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool isV4Num(string n) {

if (n.length() > 3 || n.empty()) return false;

std::reverse(n.begin(), n.end());

int a = 0;

int f = 1;

for (char c : n) {

if (!isdigit(c)) return false;

if (c == '0' && f > 1) return false;

a += (c - '0') * f;

f *= 10;

}

return a >= 0 && a <= 255;

}

bool isV6Num(string n) {

if (n.length() > 4 || n.empty()) return false;

std::reverse(n.begin(), n.end());

int a = 0;

int f = 1;

for (char c : n) {

if (isdigit(c))

a += (c - '0') * f;

else if (c >= 'a' && c <= 'f' || c >= 'A' && c <= 'Z')

a += (tolower(c) - 'a' + 10) * f;

else

return false;

f *= 16;

}

return a >= 0 && a < (1 << 16);

}

string validIPAddress(string IP) {

bool isIPv4 = true;

bool isIPv6 = true;

string cur;

int seg = 0;

for (char c: IP) {

if (c == '.') { ++seg; isIPv6 = false; isIPv4 &= isV4Num(cur); cur.clear(); }

else if (c == ':') { ++seg; isIPv4 = false; isIPv6 &= isV6Num(cur); cur.clear(); }

else cur += c;

}

isIPv4 &= isV4Num(cur) && seg == 3;

isIPv6 &= isV6Num(cur) && seg == 7;

return isIPv4 ? "IPv4" : (isIPv6 ? "IPv6" : "Neither");

}

};

花花酱 LeetCode 790. Domino and Tromino Tiling

By zxi on February 24, 2018

题目大意：有两种不同形状的骨牌(1×2长条形，L型）无限多块。给你一个2xN的板子，问一共有多少不同的方式可以完全覆盖。

We have two types of tiles: a 2×1 domino shape, and an “L” tromino shape. These shapes may be rotated.

XX <- domino

XX <- "L" tromino

Given N, how many ways are there to tile a 2 x N board? Return your answer modulo 10^9 + 7.

(In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.)

Example:

Input: 3

Output: 5

Explanation:

The five different ways are listed below, different letters indicates different tiles:

XYZ XXZ XYY XXY XYY

XYZ YYZ XZZ XYY XXY

Idea: DP

dp[i][0]: ways to cover i cols, both rows of i-th col are covered
dp[i][1]: ways to cover i cols, only top row of i-th col is covered
dp[i][2]: ways to cover i cols, only bottom row of i-th col is covered

Solution 1: DP

Time complexity: O(N)

Space complexity: O(N)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numTilings(int N) {

constexpr int kMod = 1000000007;

vector<vector<long>> dp(N + 1, vector<long>(3, 0));

dp[0][0] = dp[1][0] = 1;

for (int i = 2; i <= N; ++i) {

dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 1][1] + dp[i - 1][2]) % kMod;

dp[i][1] = (dp[i - 2][0] + dp[i - 1][2]) % kMod;

dp[i][2] = (dp[i - 2][0] + dp[i - 1][1]) % kMod;

}

return dp[N][0];

}

};

C++ V2

Since dp[i][1] always equals to dp[i][2], we can simplify a bit.

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numTilings(int N) {

constexpr int kMod = 1000000007;

vector<vector<long>> dp(N + 1, vector<long>(2, 0));

dp[0][0] = dp[1][0] = 1;

for (int i = 2; i <= N; ++i) {

dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + 2 * dp[i - 1][1]) % kMod;

dp[i][1] = (dp[i - 2][0] + dp[i - 1][1]) % kMod;

}

return dp[N][0];

}

};

Solution 2: DP

Another way to think about this problem

define: dp[i] ways to completely covert the i*2 board.

dp[0] = 1 # {}

dp[1] = 1 # {|}

dp[2] = 2 # {||, =}

dp[3] = 5 # {|||, |=, =|, ⌊⌉, ⌈⌋} = dp[2] ⊗ {|} + dp[1] ⊗ {=} + dp[0] ⊗ {⌊⌉, ⌈⌋}

dp[4] = 11 # dp[3] ⊗ {|} + dp[2] ⊗ {=} + dp[1] ⊗ {⌊⌉, ⌈⌋} + dp[0] ⊗ {⌊¯⌋,⌈_⌉}

dp[5] = 24 # dp[4] ⊗ {|} + dp[3] ⊗ {=} + 2*(dp[2] + dp[1] + dp[0])

...

dp[n] = dp[n-1] + dp[n-2] + 2*(dp[n-3] + ... + dp[0])

= dp[n-1] + dp[n-3] + [dp[n-2] + dp[n-3] + 2*(dp[n-4] + ... + dp[0])]

= dp[n-1] + dp[n-3] + dp[n-1]

= 2*dp[n-1] + dp[n-3]

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int numTilings(int N) {

constexpr int kMod = 1000000007;

vector<long> dp(N + 1, 1);

dp[2] = 2;

for (int i = 3; i <= N; ++i)

dp[i] = (dp[i - 3] + dp[i - 1] * 2) % kMod;

return dp[N];

}

};

花花酱 LeetCode 791. Custom Sort String

By zxi on February 24, 2018

题目大意：给你字符的顺序，让你排序一个字符串。

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.

S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.

Return any permutation of T (as a string) that satisfies this property.

Example :

Input:

S = "cba"

T = "abcd"

Output: "cbad"

Explanation:

"a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a".

Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs.

Note:

S has length at most 26, and no character is repeated in S.
T has length at most 200.
S and T consist of lowercase letters only.

Solution 1: HashTable + Sorting

Store the order of char in a hashtable
Sort the string based on the order

Time complexity: O(nlogn)

Space complexity: O(128)

// Author: Huahua

// Running time: 2 ms

class Solution {

public:

string customSortString(string S, string T) {

vector<int> order(128, INT_MAX);

int i = 0;

for (char c: S)

if (order[c] == INT_MAX) order[c] = ++i;

std::sort(T.begin(), T.end(), [&order](const char c1, const char c2){

return order[c1] < order[c2];

});

return T;

}

};

花花酱 LeetCode 789. Escape The Ghosts

By zxi on February 24, 2018

题目大意：给你目的地坐标以及幽灵的坐标，初始点在(0,0)，每次你和幽灵都可以移动一步。问你是否可以安全到达终点。

You are playing a simplified Pacman game. You start at the point (0, 0), and your destination is (target[0], target[1]). There are several ghosts on the map, the i-th ghost starts at (ghosts[i][0], ghosts[i][1]).

Each turn, you and all ghosts simultaneously *may* move in one of 4 cardinal directions: north, east, west, or south, going from the previous point to a new point 1 unit of distance away.

You escape if and only if you can reach the target before any ghost reaches you (for any given moves the ghosts may take.) If you reach any square (including the target) at the same time as a ghost, it doesn’t count as an escape.

Return True if and only if it is possible to escape.

Example 1:

Input:

ghosts = [[1, 0], [0, 3]]

target = [0, 1]

Output: true

Explanation:

You can directly reach the destination (0, 1) at time 1, while the ghosts located at (1, 0) or (0, 3) have no way to catch up with you.

Example 2:

Input:

ghosts = [[1, 0]]

target = [2, 0]

Output: false

Explanation:

You need to reach the destination (2, 0), but the ghost at (1, 0) lies between you and the destination.

Example 3:

Input:

ghosts = [[2, 0]]

target = [1, 0]

Output: false

Explanation:

The ghost can reach the target at the same time as you.

Note:

All points have coordinates with absolute value <= 10000.
The number of ghosts will not exceed 100.

Solution: Greedy / Math

You can escape if and only if no ghosts can reach target before you. Just need to compare the Manhattan distance.

如果所有的幽灵都无法在你之前到达target，那么你可以逃脱。只要比较曼哈顿距离即可。

C++

Time complexity: O(|ghost|)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {

const int steps = abs(target[0]) + abs(target[1]);

for (const auto& g: ghosts)

if (abs(g[0] - target[0]) + abs(g[1] - target[1]) <= steps)

return false;

return true;

}

};

Java

// Author: Huahua

// Running time: 4 ms

class Solution {

public boolean escapeGhosts(int[][] ghosts, int[] target) {

final int steps = Math.abs(target[0]) + Math.abs(target[1]);

for (int[] g : ghosts)

if (Math.abs(g[0] - target[0]) + Math.abs(g[1] - target[1]) <= steps)

return false;

return true;

}

Python3

"""

Author: Huahua

Running time: 40 ms

"""

class Solution:

def escapeGhosts(self, ghosts, target):

steps = abs(target[0]) + abs(target[1])

return not any(abs(x - target[0]) + abs(y - target[1]) <= steps for x, y in ghosts)