LeetCode

binary-search-tree-iterator.py

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class BSTIterator:
    # @param root, a binary search tree's root node
    def __init__(self, root):
        self._nodeStack = []
        self._traverseLeft(root)

    # @return a boolean, whether we have a next smallest number
    def hasNext(self):
        return len(self._nodeStack) > 0

    # @return an integer, the next smallest number
    def next(self):
        currentNode = self._nodeStack.pop()
        self._traverseLeft(currentNode.right)
        
        return currentNode.val
    
    def _traverseLeft(self, root):
        currentNode = root
        while currentNode:
            self._nodeStack.append(currentNode)
            currentNode = currentNode.left
        

# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())

department-highest-salary.sql

# Write your MySQL query statement below
SELECT Department.Name as Department, Employee.Name as Employee, Employee.Salary as Salary FROM Employee
    INNER JOIN Department
        ON Employee.DepartmentId = Department.Id
    LEFT JOIN (SELECT DepartmentId, max(Salary) as maxSalary FROM Employee GROUP BY DepartmentId) as MaxSalaryPerDepartment
        ON Employee.DepartmentId = MaxSalaryPerDepartment.DepartmentId
    WHERE Employee.Salary >= MaxSalaryPerDepartment.maxSalary;

rotate-list.py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @param k, an integer
    # @return a ListNode
    def rotateRight(self, head, k):
        
        # Find the length of the linked list,
        # and the last node of the list.
        len = 0
        currentNode = head
        oldEnd = None
        while currentNode:
            len += 1
            oldEnd = currentNode
            currentNode = currentNode.next
            
        # Determine the new starting node of the rotated list.
        cuttingK = 0 if len == 0 else (len - k) % len
        newHead = head
        newEnd = oldEnd
        while cuttingK > 0:
            cuttingK -= 1
            newEnd = newHead
            newHead = newHead.next
            
        # Connect the last node with the first node
        if oldEnd:
            oldEnd.next = head
        
        # Break the end of the rotated list
        if newEnd:
            newEnd.next = None
        
        return newHead
        
        

spiral-matrix.py

class Solution:
    # @param matrix, a list of lists of integers
    # @return a list of integers
    def spiralOrder(self, matrix):
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return []

        elif len(matrix) == 1:
            # 1 row
            return matrix[0]

        elif len(matrix[0]) == 1:
            # 1 column
            return [row[0] for row in matrix]

        else:
            # Top row
            shell = matrix[0]
    
            # Right column, exclude top & bottom
            middleRows = matrix[1:-1]
            shell += [row[-1] for row in middleRows]
    
            # Bottom row
            bottomRow = matrix[-1]
            bottomRow.reverse()
            shell += bottomRow
            
            # Left column, exclude top & bottom
            middleRows.reverse()
            shell += [row[0] for row in middleRows]

            return shell + self.spiralOrder( [ middleRow[1:-1] for middleRow in matrix[1:-1] ] )

subsets.py

class Solution:
    # @param S, a list of integer
    # @return a list of lists of integer
    def subsets(self, S):
        S.sort()
        self.S = S
        self.size = len(S)

        self.answerSets = []
        self._dfs(0, [])
        return self.answerSets
    
    def _dfs(self, i, subset):
        if i == self.size:
            self.answerSets.append(list(subset))
        else:
            self._dfs(i+1, subset)
            subset.append(self.S[i])
            self._dfs(i+1, subset)
            subset.pop()