Press "Enter" to skip to content

Posts tagged as “search”

花花酱 LeetCode 805. Split Array With Same Average

Problem

题目大意:问能否将一个数组分成两部分,每部分的平均值相同。

In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

Example :
Input: 
[1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.

Note:

  • The length of A will be in the range [1, 30].
  • A[i] will be in the range of [0, 10000].

Solution: Search

Time complexity: O(2^n)

Space complexity: O(n)

 

花花酱 LeetCode 803. Bricks Falling When Hit

Problem

题目大意:给你一堵砖墙,求每次击碎一块后掉落的砖头数量。

We have a grid of 1s and 0s; the 1s in a cell represent bricks.  A brick will not drop if and only if it is directly connected to the top of the grid, or at least one of its (4-way) adjacent bricks will not drop.

We will do some erasures sequentially. Each time we want to do the erasure at the location (i, j), the brick (if it exists) on that location will disappear, and then some other bricks may drop because of that erasure.

Return an array representing the number of bricks that will drop after each erasure in sequence.

Example 1:
Input: 
grid = [[1,0,0,0],[1,1,1,0]]
hits = [[1,0]]
Output: [2]
Explanation: 
If we erase the brick at (1, 0), the brick at (1, 1) and (1, 2) will drop. So we should return 2.
Example 2:
Input: 
grid = [[1,0,0,0],[1,1,0,0]]
hits = [[1,1],[1,0]]
Output: [0,0]
Explanation: 
When we erase the brick at (1, 0), the brick at (1, 1) has already disappeared due to the last move. So each erasure will cause no bricks dropping.  Note that the erased brick (1, 0) will not be counted as a dropped brick.

Idea

  1. For each day, hit and clear the specified brick.
  2. Find all connected components (CCs) using DFS.
  3. For each CC, if there is no brick that is on the first row that the entire cc will drop. Clear those CCs.

Solution: DFS

C++

Java

Related Problems

花花酱 LeetCode 17. Letter Combinations of a Phone Number

题目大意:给你一串电话号码,输出可以由这串电话号码打出的所有字符串。

Problem:

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution 1: DFS

C++

Java

Python3

Solution 2:  BFS

C++

Java

Python

 

花花酱 LeetCode 216. Combination Sum III

题目大意:输出所有用k个数的和为n的组合。可以使用的元素是1到9。

Problem:

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

Example 2:

Input: k = 3, n = 9

Output:

 



Idea:

DFS + backtracking

bit

Solution:

C++

 

C++ / binary

 

Python

 

 

Related problems:

花花酱 LeetCode 79. Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Idea:
Search, depth first search
Solution:

C++



Python