<file_sep>
class MyString:
	def __init__(self, mStr):
		self.mStr = mStr
		self.mLen = len(mStr)

    ## abcab  5
    ## ab    2
	def lastoccurenceof(self,subStr):
		k = len(subStr)
		res = -1 
		for i in range(self.mLen - k+1):
			if self.mStr[i:i+k] == subStr:
				res = i
		return res 

def main():
	s = MyString("abcab")
	ans = s.lastoccurenceof("ab")

	print(ans)
main()<file_sep>def increasingList(N):
	def helper(lastElem, subres, index):
		if lastElem >= 5:
			print(subres[:])
			res.append(subres[:])
			return 

		i = 0
		while 2**i + lastElem <= N:
			subres.append(2**i + lastElem)
			helper(2**i + lastElem,subres, i+1) 
			subres.pop()
			i += 1 
	
	res = []
	subres = []

	helper(-1,[],0)

	return res

increasingList(5)<file_sep># 给一个矩阵，寻找Manhattan 距离最短的X和Y
# input：
# X O O O
# O O X Y
# O X O Y

# (p1, p2) = |p2.x – p1.x| + |p2.y – p1.y|.

def manhattanXYDist(grid):
	if not grid or not grid[0]:
		return 

	rows = len(grid)
	cols = len(grid[0])
	qX = []
	qY = [] 
	count = 0 
	deltaX = [0,0,-1,1]
	deltaY = [-1,1,0,0]
	for i in range(rows):
		for j in range(cols):
			if grid[i][j] == 'X':
				qX.append(i)
				qY.append(j)

	while qX and qY:
		tempX = qX 
		tempY = qY
		qX = []
		qY = []
		count += 1 
		while tempX and tempY:
			curX = tempX.pop(0)
			curY = tempY.pop(0)
			for i in range(4):
				nbX = curX + deltaX[i]
				nbY = curY + deltaY[i]

				if 0 <= nbX < rows and 0<=nbY < cols:
					if grid[nbX][nbY] == '0':
						grid[nbX][nbY] = count 
					if grid[nbX][nbY] == 'Y':
						return count 
					qX.append(nbX)
					qY.append(nbY)

	return -1 

grid = [['X','0','X','0'],	
		['0','0','0','0'],
		['0','0','0','Y']]

print(manhattanXYDist(grid))





<file_sep>##         1
##        2 3
##		 4 5 

class TreeNode:	
	def __init__(self,val):
		self.val = val 
		self.left, self.right = None, None 


def isCompleteBT(root):
	if not root:
		return True 

	q = [root]
	isNonFullNodeOccurs = False
	count =0

	while q:
		count +=1 
		node = q.pop(0)
		if node.left:
			if isNonFullNodeOccurs:
				return False 
			q.append(node.left)
		else:
			isNonFullNodeOccurs = True 


		if node.right:
			if isNonFullNodeOccurs:

				return False 
			q.append(node.right)
		else:
			isNonFullNodeOccurs = True 

	return True

def main():
	node1 = TreeNode(1)
	node2 = TreeNode(2)
	node3 = TreeNode(3)
	node4 = TreeNode(4)


	node1.left = node2
	node1.right = node3
	node2.right = node4

	print(isCompdleteBT(node1))

main()




<file_sep>## whaaaaaat => what

def deleteDuplicateLetter(word):
    if not word:
        return word
    lastElem = word[0]
    count =1 
    res = ''
    for ch in word[1:]:
        if lastElem == ch:
            count += 1 
        else:
            res = res + lastElem
            lastElem = ch 

    res = res + lastElem
    return res 

def main():
    nw = deleteDuplicateLetter("whaaaaaat")
    print(nw)

main()




<file_sep>class TreeNode():
	def __init__(self, val):
		self.val = val 
		self.children = []



def getMaxSpreadTime():
	def getMaxSpreadTimeHelper(node):
		if not node:
			return 0

		res = 0 
		for child in node.children:
			if child not in visited:
				tempSum = getMaxSpreadTimeHelper(child)
				if tempSum > res :
					res = tempSum
				visited.add(res)

		return res + node.val 		



	visited = set()

	root = TreeNode(0)
	node1 = TreeNode(1)
	node2 = TreeNode(2)
	node3 = TreeNode(3)
	node4 = TreeNode(4) 
	node5 = TreeNode(5)  
	node6 = TreeNode(6) 	

	root.children = [node1,node2, node3,node4]
	node2.children=[node5,node6]


	return getMaxSpreadTimeHelper(root)


print(getMaxSpreadTime())
<file_sep>import random

def matrix55():
	matrix = [[random.randint(0,100) for _ in range(5)] for _ in range(5)]
	print(matrix)


matrix55()<file_sep>## aaaabbbbbbc => 4xa6xb1xc
def encodeMultipleChar(input):
	if not input:
		return input

	lastElem = '#'
	count = 0
	res = []
	sub = ''
	for i, item in enumerate(input):
		if lastElem == '#':
			lastElem = item
			count = 1 
		else:
			if lastElem != item:
				sub = str(count) + 'x' + lastElem
				res.append(sub)
				count = 1 
				lastElem = item 
			else:
				count += 1 

	res.append(str(count) + 'x' + lastElem)

	return "".join(res)

# print(encodeMultipleChar("aaaabbbbbb"))

def decodeMultipleChar(input):
	if not input:
		return input 

	count = 0 
	alpha = '#'
	res = []
	for item in input:
		if item == 'x':
			continue 
		elif item.isdigit():
			count = int(item)
		elif item.isalpha():
			alpha = item
			res += [item]*count 

	return "".join(res)

print(decodeMultipleChar( encodeMultipleChar("a")))







<file_sep>import heapq 
import collections

def rearrangeString(words, k):
	if not words:
		return ""

	wlen = len(words)
	if k > wlen:
		return ""

	wordsCount = {}
	heap = []
	for w in words:
		wordsCount[w] = wordsCount.get(w, 0) + 1 

	for w,c in wordsCount.items():
		heapq.heappush(heap, (-c, w))
	res = ""
    
	while heap:

		count = min(k,wlen) ## wlen can be used to keep track of the remaining unasigned word
		used = []
		for i in range(count):
			if not heap:  ## if we didn't assign the k number then there is no word in heap. that means the min part number can't be accoimplished 
				break

			curCount, curWord = heapq.heappop(heap)
			res = res + curWord
			if -curCount >1:
				used.append((curCount + 1, curWord))
			wlen -= 1 
		for item in used:
			heapq.heappush(heap, item)
	return res 	 


# def rearrangeString2(words, k):
# 	_len = len(words)
# 	words_count = collections.Counter(words)
# 	que = []
# 	heapq.heapify(que)
# 	for w, v in words_count.items():
# 		heapq.heappush(que, (-v, w))
# 	res = ""
# 	while que:
# 		cnt = min(_len, k)
# 		used = []
# 		for i in range(cnt):
# 			if not que:
# 				return ""
# 			v, w = heapq.heappop(que)
# 			res += w
# 			if -v > 1:
# 				used.append((v + 1, w))
# 			_len -= 1
# 		for use in used:
# 			heapq.heappush(que, use)
# 	return res




print(rearrangeString("aaadbbcc",3))








<file_sep>import math
class ListNode:
	def __init__(self, val, next = None):
		self.val = val
		self.next = next

def reverseHalfLinkedList(head):
	if not head:
		return head 
	if not head.next:
		return head
	## get total number of node 
	cur = head 
	count = 0 
	while cur != None:
		cur = cur.next
		count += 1 
	## the cur will finally point to the None

	if count == 2:
		return head 

	dummy = left = ListNode(-1)
	dummy.next = head 
	## move to the half point 
	half = math.ceil(count/2) 
	for _ in range(half):
		left = left.next 
	## reverse 
	cur = left.next  
	prev = None 
	nxt = None 
	while cur != None:
		nxt = cur.next 
		cur.next = prev 
		prev = cur 
		cur = nxt
	left.next.next = cur
	left.next = prev

	return dummy.next 

def printLinkedList(head):
	while head != None:
		print(head.val)
		head = head.next 

def main():
	node5 = ListNode(5)
	node4 = ListNode(4,node5)
	node3 = ListNode(3,node4)
	node2 = ListNode(2,node3)
	# node2 = ListNode(2)
	node1 = ListNode(1,node2)

	# printLinkedList(node1)
	head = reverseHalfLinkedList(node1)
	printLinkedList(head)

main()


<file_sep>## 写一个函数把一个数组按第k个index的数进行排列，变成小于arr[k],等于arr[k],大于arr[k]的三部分。




def partitionArrayWithK(nums, k):
	if not nums:
		return []

	pivot = nums[k]
	l = 0
	r = len(nums)-1
	while l<= r :
		while l<=r and nums[l] < pivot:
			l += 1 
		while l<=r and nums[r] >= pivot:
			r -= 1 
		if l <= r :
			nums[l], nums[r] = nums[r], nums[l]
			l += 1 
			r -=1 

	r = len(nums) - 1 
	while l<= r :
		while l<=r and nums[l] == pivot:
			l += 1 
		while l<=r and nums[r] != pivot:
			r -= 1 
		if l <= r :
			nums[l], nums[r] = nums[r], nums[l]
			l += 1 
			r -=1 

	print(nums)
	return nums

nums1 = [6,7,8,1,3, 0,2,0,1,2,0,1,2,3,4,5,6]
partitionArrayWithK(nums1, 4)

