Press "Enter" to skip to content

Posts tagged as “permutation”

花花酱 LeetCode 357. Count Numbers with Unique Digits

Problem

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Solution: Math

f(0) = 1 (0)

f(1) = 10 (0 – 9)

f(2) = 9 * 9 (1-9 * (0 ~ 9 exclude the one from first digit))

f(3) = 9 * 9 * 8

f(4) = 9 * 9 * 8 * 7

f(x) = 0 if x >= 10

ans = sum(f[1] ~ f[n])

Time complexity: O(1)

Space complexity: O(1)

 

花花酱 LeetCode 384. Shuffle an Array

Shuffle a set of numbers without duplicates.

Example:

C++

 

花花酱 LeetCode 784. Letter Case Permutation

题目大意:给你一个字符串,每个字母可以变成大写也可以变成小写。让你输出所有可能字符串。

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string.  Return a list of all possible strings we could create.

Note:

  • S will be a string with length at most 12.
  • S will consist only of letters or digits.

 

Solution 1: DFS

Time complexity: O(n*2^l), l = # of letters in the string

Space complexity: O(n) + O(n*2^l)

C++

Java

Python 3

花花酱 LeetCode 769. Max Chunks To Make Sorted

题目大意:给你一个0 ~ n-1的排列,问你最多能分成几组,每组分别排序后能够组成0 ~ n-1。

Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of “chunks” (partitions), and individually sort each chunk.  After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Example 2:

Note:

  • arr will have length in range [1, 10].
  • arr[i] will be a permutation of [0, 1, ..., arr.length - 1].

Solution 1: Max so far / Set

Time complexity: O(nlogn)

Space complexity: O(n)

C++

 

Solution 2: Max so far

Time complexity: O(n)

Space complexity: O(1)

C++

Java

Python3

 

 

 

花花酱 LeetCode 39. Combination Sum

Problem:

Given a set of candidate numbers (C(without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

 

Idea:

DFS

Solution: C++

 

Python