317. Shortest Distance from All Buildings(Google, LeetCode)
problem
You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:
Each 0 marks an empty land which you can pass by freely. Each 1 marks a building which you cannot pass through. Each 2 marks an obstacle which you cannot pass through. For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):
1 - 0 - 2 - 0 - 1 | | | | | 0 - 0 - 0 - 0 - 0 | | | | | 0 - 0 - 1 - 0 - 0 The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.
Note: There will be at least one building. If it is not possible to build such house according to the above rules, return -1.
how to solve
I use breadth-first Search. I can count the distance from the each building by using bfs. One of the difficult thing is which I have to notice the possibility of this problem. To do so, I calculate the Count of the number of which how many building can reach. If this number is as same as the number of buildings I can judge this count is according to the rules
BFS 320. Generalized Abbreviation (Google, LeetCode)
Problem
Write a function to generate the generalized abbreviations of a word.
Example: Given word = "word", return the following list (order does not matter): ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
How to solve
I use breath first search algorithm.
code
302. Smallest Rectangle Enclosing Black Pixels
problem
An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.
For example, given the following image:
[ "0010", "0110", "0100" ] and x = 0, y = 2, Return 6.
how to solve
I can sove this problem by blute force search. I have to memorize the minX, maxX , minY, maxY. Then the answer is (maxX - minX + 1) * (maxY - minY + 1).
code
200. Number of Islands(Leet Code, Google)
Problem
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110 11010 11000 00000 Answer: 1
Example 2:
11000 11000 00100 00011 Answer: 3
How to Solve
To solve this, I used bfs search. Firstly, I check the each coordinate. If I didn't visit that coordinate I starts to bfs search from it and I change the visited flag true. The number of this times if the answer.
Code
316. Remove Duplicate Letters (Leet Code, Google)
problem
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example: Given "bcabc" Return "abc"
Given "cbacdcbc" Return "acdb"
how to solve
code
340. Longest Substring with At Most K Distinct Characters (Leet Code, Google)
https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
problems
Given a string, find the length of the longest substring T that contains at most k distinct characters.
For example, Given s = “eceba” and k = 2,
T is "ece" which its length is 3.
note
I used "shakutoriho". Firstly, I check the 's' string from the head to the end with right iterator. I can save the information whether I found the character in hash map. When I found the new character, I increment the count of the distinct numbers. If I found the character which I already had found, I can proceed the left iterator and decrement the count of the distinct numbers. Through this manipulation, if the situation is max numbers of the distinct num > k, I can save the max difference between right iterator and left iterator. It means the max length substring I wanna get.
