# 谷歌 onsite 题目 Number of Valid Strings google

Given an int `n` , output number of valid strings consisting of letters `A` , `B` and `C` . Any continuous three letters containing all three letters `A` , `B` , `C` make the whole string invalid. For example, `BACCA` is not a valid string because of the first three characters, but `CCCACCAABBB` is a valid string.

Example 1:

``````Input: n = 0
Output: 0
``````

Example 2:

``````Input: n = 1
Output: 3
Explanation: A, B, C
``````

Example 3:

``````Input: n = 2
Output: 9
Explanation: AA, AB, AC, BA, BB, BC, CA, CB, CC
``````

Example 4:

``````Input: n = 3
Output: 21
Explanation: 3^3 - 6 (ABC, ACB, BAC, BCA, CBA, CAB)
``````

Example 5:

``````Input: n = 4
Output: 51
``````

Given a list of doubly linked list nodes:

``````class ListNode {
int val;
ListNode prev;
ListNode next;
}
``````

Find the number of clusters (groups) in this list. A cluster is formed by nodes adjecent to each other.

Example 1:

Let’s say we have a doubly linked list like this (1) ⇔ (2) ⇔ (3) ⇔ (4) ⇔ (5)

Input: [(1), (3), (5)]
Output: 3
Explanation: Nodes (1), (3) and (5) are not adjacent to each other, forming 3 different clusters.
Example 2:

(1) ⇔ (2) ⇔ (3) ⇔ (4) ⇔ (5)

Input: [(1), (2), (3)]
Output: 1
Explanation: All nodes are adjacent to each other so there is only 1 cluster.
Example 3:

(1) ⇔ (2) ⇔ (3) ⇔ (4) ⇔ (5)

Input: [(1), (4), (2), (5)]
Output: 2
Explanation:
cluster 1: (1) (2)
cluster 2: (4) (5)
Example 4:

list 1: (1) ⇔ (2) ⇔ (3) ⇔ (4)
list 2: (5)

Input: [(4), (2), (1), (5)]
Output: 3
Explanation:
cluster 1: (1) (2)
cluster 2: (4)
cluster 3: (5)

Given a 2D grid of size r * c, where 1 is a wall (the cell is blocked) and 0 is empty (the cell to which you can travel). You have a hammer that you can use to break 1 wall. Is there a way to go from the upper left corner (0, 0) to the lower right corner (r - 1, c - 1)? If there is a way to go, find the length of the shortest path. You can move up, down, left or right at a time.

Example 1:

Input:
[[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 1, 0],
[1, 1, 1, 1, 0]]

Output: 7
Explanation: Change `1` at (0, 1) to `0`, the shortest path is as follows:
(0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (0, 4) -> (1, 4) -> (2, 4) -> (3, 4)
There are other options of length 7, not listed here.
Example 2:

Input:
[[0, 1, 1],
[1, 1, 0],
[1, 1, 0]]

Output: -1
Explanation: Regardless of which `1` is changed to `0`, there is no viable path.
You can assume (0, 0) and (r - 1, c - 1) are always empty.

Follow-up:
What if you can break k walls?

``````public class Main {
private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

public static void main(String[] args) {
int[][] grid = {
{0, 1, 0, 0, 0},
{0, 0, 0, 1, 0},
{1, 1, 0, 1, 0},
{1, 1, 1, 1, 0}};
System.out.println(minDist(grid, 1)); // 7

int[][] grid2 = {
{0, 1, 1},
{1, 1, 0},
{1, 1, 0}};
System.out.println(minDist(grid2, 1)); // -1
System.out.println(minDist(grid2, 2)); // 4
}

public static int minDist(int[][] grid, int k) {
int rows = grid.length;
int cols = grid.length;

Queue<Point> q = new ArrayDeque<>();
q.add(new Point(0, 0, 0));

boolean[][] visited = new boolean[rows][cols];
visited = true;

for (int dist = 0; !q.isEmpty(); dist++) {
for (int sz = q.size(); sz > 0; sz--) {
Point p = q.poll();
if (p.r == rows - 1 && p.c == cols - 1) return dist;

for (int[] dir : DIRS) {
int r = p.r + dir;
int c = p.c + dir;

if (isSafe(grid, r, c, visited)) {
int brokenWalls = p.walls + grid[r][c];
if (brokenWalls <= k) {
visited[r][c] = true;
q.add(new Point(r, c, brokenWalls));
}
}
}
}
}

return -1;
}

private static boolean isSafe(int[][] grid, int r, int c, boolean[][] visited) {
return r >= 0 && r < grid.length && c >= 0 && c < grid.length && !visited[r][c];
}

private static class Point {
int r;
int c;
int walls; // number of broken wall on the path

public Point(int r, int c, int walls) {
this.r = r;
this.c = c;
this.walls = walls;
}
}
}

``````

Time complexity: `O(r *c)` .
Space complexity: `O(r *c)` .