mirror of
https://github.com/dholerobin/Lecture_Notes.git
synced 2025-03-15 21:59:56 +00:00
109 lines
2.3 KiB
Markdown
109 lines
2.3 KiB
Markdown
Number of Squareful Arrays
|
|
--------------------------
|
|
> Given A[N]
|
|
> array is squareful if for every pair of adjacent elements, their sum is a perfect square
|
|
> Find and return the number of permutations of A that are squareful
|
|
>
|
|
Example:
|
|
A = [2, 2, 2]
|
|
output: 1
|
|
A = [1, 17, 8]
|
|
output: 2
|
|
[1, 8, 17], [17, 8, 1]
|
|
|
|
|
|
```python
|
|
def check(a, b):
|
|
sq = int((a + b) ** 0.5)
|
|
return (sq * sq) == (a + b)
|
|
|
|
if len(A) == 1: # corner case
|
|
return int(check(A[0], 0))
|
|
|
|
count = 0
|
|
def permute_distinct(S, i):
|
|
global count
|
|
if i == len(S):
|
|
count += 1
|
|
|
|
for j in range(i, len(S)):
|
|
if S[j] in S[i:j]: # prevent duplicates
|
|
continue
|
|
|
|
if i > 0 and (not check(S[j], S[i-1])): # invalid solution - branch and bound
|
|
continue
|
|
|
|
S[i], S[j] = S[j], S[i]
|
|
permute_distinct(S, i+1)
|
|
|
|
S[i], S[j] = S[j], S[i] # backtrack
|
|
permute_distinct(A, 0)
|
|
return count
|
|
```
|
|
|
|
Gray Code
|
|
---------
|
|
|
|
> Given a non-negative integer N representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
|
|
|
|
> The gray code is a binary numeral system where two successive values differ in only one bit.
|
|
|
|
|
|
G(n+1) can be constructed as:
|
|
0 G(n)
|
|
1 R(n)
|
|
|
|
```
|
|
Example G(2) to G(3):
|
|
0 00
|
|
0 01
|
|
0 11
|
|
0 10
|
|
----
|
|
1 10
|
|
1 11
|
|
1 01
|
|
1 00
|
|
```
|
|
```python
|
|
def gray(self, n):
|
|
codes = [0, 1] # length 1
|
|
for i in range(1, n):
|
|
new_codes = [s | (1 << i) for s in reversed(codes)]
|
|
codes += new_codes
|
|
return codes
|
|
```
|
|
|
|
N Queens
|
|
--------
|
|
|
|
[NQueens - InterviewBit](https://www.interviewbit.com/problems/nqueens/)
|
|
Backtracking
|
|
- Place one queen per row
|
|
- backtrack if failed
|
|
|
|
Word Break II
|
|
-------------
|
|
> Given a string A and a dictionary of words B, add spaces in A to construct a sentence where each word is a valid dictionary word.
|
|
```
|
|
Input 1:
|
|
A = "catsanddog",
|
|
B = ["cat", "cats", "and", "sand", "dog"]
|
|
|
|
Output 1:
|
|
["cat sand dog", "cats and dog"]
|
|
```python
|
|
def wordBreak(A, B):
|
|
B = set(B)
|
|
sents = []
|
|
def foo(i, start, sent):
|
|
word = A[start:i+1]
|
|
if i == len(A):
|
|
if word in B:
|
|
sents.append((sent + ' ' + word).strip())
|
|
return
|
|
if word in B:
|
|
foo(i+1, i+1, sent + ' ' + word)
|
|
foo(i+1, start, sent)
|
|
foo(0, 0, '')
|
|
``` |