https://leetcode.com/problems/jewels-and-stones/description/
You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.
This is the only
The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A"
Input: J = "aA", S = "aAAbbbb"
Output: 3Input: J = "z", S = "ZZ"
Output: 0
In [12]:
class Solution:
def numJewelsInStones(self, J=[], S=[]):
"""
:type J: str
:type S: str
:rtype: int
>>> numJewelsInStones(J="aA",S="aAAbbbb")
3
"""
jewels_set = set(J)
jewels_in_stones = [s for s in S if s in jewels_set]
return len(jewels_in_stones)
Solution().numJewelsInStones(J="aA", S="aAAbbbb")
if __name__ == "__main__":
import doctest
doctest.testmod()
https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/description/
In [70]:
'''
>>> Solution().countPrimeSetBits(842,888)
23
'''
class Solution:
# def set_bits(self, num):
# count=0
# while num > 0 :
# count += (num & 1)
# num = num >> 1
# return count
def countPrimeSetBits(self, L, R):
"""
:type L: int
:type R: int
:rtype: int
"""
primes = {2, 3, 5, 7, 11, 13, 17, 19}
return sum( [1 for x in range(L, R+1) if bin(x).count('1') in primes ] )
# return sum(bin(x).count('1') in primes for x in range(L, R+1))
Solution().countPrimeSetBits(842,100000)
if __name__=="__main__": import doctest; doctest.testmod()
In [103]:
class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
# 1.23 µs ± 46.6 ns
# return bin(n).count('1')
count=0
# 23.5 µs ± 1.38 µs
while n :
count += (n & 1)
n = n>>1
# 9.47 µs ± 81.8 ns
# while n:
# n = n&(n-1)
# count += 1
return count
n=1000000000000000000000000000000000100000000
print(bin(n)[2:])
print(Solution().hammingWeight(n))
%timeit Solution().hammingWeight(n)
https://leetcode.com/problems/toeplitz-matrix/description/
A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.
Now given an M x N matrix, return True if and only if the matrix is Toeplitz.
Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: True
Explanation:
1234
5123
9512In the above grid, the diagonals are "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", and in each diagonal all elements are the same, so the answer is True.
Input: matrix = [[1,2],[2,2]]
Output: False
Explanation:
The diagonal "[1, 2]" has different elements.matrix will be a 2D array of integers.
matrix will have a number of rows and columns in range [1, 20].
matrix[i][j] will be integers in range [0, 99].Spent 2h!
In [149]:
m=[
[3, 4, 5, 6],
[2, 3, 4, 5],
[1, 2, 3, 4]
]
def is_toeplitz(m):
def is_diag(i0,j0,n_rows,n_cols):
M=min(n_rows-i0,n_cols-j0)
return all( [m[i0][j0]==m[i0+k][j0+k] for k in range(1,M)] )
n_rows=len( m )
n_cols=len( m[0])
first_row = [is_diag(0,j,n_rows,n_cols) for j in range(0,n_cols)]
first_col = [is_diag(i,0,n_rows,n_cols) for i in range(1,n_rows)]
return (all(first_row) and all(first_col))
# Left-Top neibour
def is_toeplitz2(m):
n_rows=len( m )
n_cols=len( m[0])
return all(i==0 or j==0 or m[i][j]==m[i-1][j-1]
for j in range(0,n_cols)
for i in range(0,n_rows))
def is_toeplitz3(m):
n_rows=len( m )
if n_rows < 2:
return True
n_cols=len( m[0])
if n_cols < 2:
return True
return all(m[i][j]==m[i-1][j-1]
for j in range(1,n_cols)
for i in range(1,n_rows))
def isToeplitzMatrix(matrix):
return all(r == 0 or c == 0 or matrix[r-1][c-1] == val
for r, row in enumerate(matrix)
for c, val in enumerate(row))
print(is_toeplitz(m))
print(is_toeplitz3(m))
%timeit is_toeplitz(m)
%timeit is_toeplitz3(m)
mm=[[(i,j) for j in range(0,4)] for i in range(0,3)]
print(mm)
# flatten
flat_list = [v for row in m for v in row]
print(flat_list)
# which means:
flat_list =[]
for row in m:
for v in row:
flat_list.append(v)
print(flat_list)
https://leetcode.com/problems/largest-number-at-least-twice-of-others/description/
In a given integer array nums, there is always exactly one largest element.
Find whether the largest element in the array is at least twice as much as every other number in the array.
If it is, return the index of the largest element, otherwise return -1.
Input: nums = [3, 6, 1, 0]
Output: 1
Explanation: 6 is the largest integer, and for every other number in the array x,
6 is more than twice as big as x. The index of value 6 is 1, so we return 1.Input: nums = [1, 2, 3, 4]
Output: -1
Explanation: 4 isn't at least as big as twice the value of 3, so we return -1.nums will have a length in the range [1, 50].
Every nums[i] will be an integer in the range [0, 99].
In [180]:
a=[1,2,4,5,3]
def find_largest(a):
m = max(a)
i = a.index(m)
del a[i]
m2 = max(a)
return i if m==0 or m/m2>=2 else -1
find_largest(a)
Out[180]:
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
In [ ]:
class Node:
def __init__(self, val=None, nex=None):
self.val = val
self.next = nex
def __str__(self):
s = ''
nn = self
while True:
s = s+str(nn.val)+' -> '
nn = nn.next
if nn is None:
break
return s
carry = 0
def add(n1, n2):
global carry
v1 = int(n1.val) if n1 else 0
v2 = int(n2.val) if n2 else 0
summ = carry + v1 + v2
v = summ % 10
carry = summ // 10
return Node(v)
def next_nodes(n1, n2):
n1 = n1.next if n1 else None
n2 = n2.next if n2 else None
return n1, n2
def add_nodes(h1, h2):
if h1 is None:
return h2
elif h2 is None:
return h1
else:
n1, n2 = h1, h2
head = add(n1, n2)
n = head
while True:
n1, n2 = next_nodes(n1, n2)
n.next = add(n1, n2)
n = n.next
if n1 == None and n2 == None:
break
return head
head1 = Node(2, Node(4, Node(3, Node(5, Node(1)))))
head2 = Node(5, Node(6, Node(4)))
h12 = add_nodes(head1, head2)
print(head1)
print(head2)
print(h12)