Shortest Bridge

Shortest Bridge

In a given 2D binary array `A`, there are two islands. (An island is a 4-directionally connected group of `1`s not connected to any other 1s.)

Now, we may change `0`s to `1`s so as to connect the two islands together to form 1 island.

Return the smallest…

N-Queens

N-Queens

The n-queens puzzle is the problem of placing `n` queens on an `n x n` chessboard such that no two queens attack each other.

Given an integer `n`, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where `'Q'`

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

You may return the answer in any order.

Example 1:

`Input: n = 4, k = 2Output:[  [2,4],  [3,4],  [2,3],  [1,2],  [1,3],  [1,4],]`

Example 2:

`Input: n = 1…`

Permutations

Given an array `nums` of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

`Input: nums = [1,2,3]Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]`

Example 2:

`Input: nums = [0,1]Output: [[0,1],[1,0]]`

Example 3:

`Input: nums = [1]Output: [[1]]`

BackTracking

1. 修改当前值
2. 递归current node
3. 还原当前值
`def permute(self, nums): “”” :type nums: List[int] :rtype: List[List[int]] “””   def backTrack(nums, level):   if level == len(nums)-1:     self.ans.append(list(nums))   return  for i in range(level, len(nums)):     nums[level], nums[i] = nums[i], nums[level]     backTrack(nums, level+1)     nums[level], nums[i] = nums[i], nums[level] self.ans = [] backTrack(nums, 0) return self.ans`

Pacific Atlantic Water Flow

Given an `m x n` matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.

Water can only flow in four directions (up, down…

Number of Provinces

There are `n` cities. Some of them are connected, while some are not. If city `a` is connected directly with city `b`, and city `b` is connected directly with city `c`, then city `a` is connected indirectly with city `c`.

A province is a group of directly or indirectly connected…

Max Area of Island

Given a non-empty 2D array `grid` of 0's and 1's, an island is a group of `1`'s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. …

Median of Two Sorted Arrays

Given two sorted arrays `nums1` and `nums2` of size `m` and `n` respectively, return the median of the two sorted arrays.

Follow up: The overall run time complexity should be `O(log (m+ …`

Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single elemen …

Newbie Developer

Get the Medium app