mirror of
https://github.com/dholerobin/Lecture_Notes.git
synced 2025-03-15 13:49:59 +00:00
2.3 KiB
2.3 KiB
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]
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
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 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, '')