apollomat/arrayproblems

arrayproblems's Issues

ways to make change

def change_ways(n, coins):
    arr = [1] + [0] * n
    for coin in coins:
        for i in range(coin, n + 1):
            arr[i] += arr[i - coin]
    return 0 if n == 0 else arr[n]

tic tac toe

public class TicTacToe {
private int[] columns;
private int[] rows;
private int diagonal;
private int antiDiagonal;
private int n;

/** Initialize your data structure here. */
public TicTacToe(int n) {
    columns = new int[n];
    rows = new int[n];
    diagonal = 0;
    antiDiagonal = 0;
    this.n = n;
}

/** Player {player} makes a move at ({row}, {col}).
    @param row The row of the board.
    @param col The column of the board.
    @param player The player, can be either 1 or 2.
    @return The current winning condition, can be either:
            0: No one wins.
            1: Player 1 wins.
            2: Player 2 wins. */
public int move(int row, int col, int player) {
    //Take player 1 and 2 as value of 1 and -1;
    int number = player == 1 ? 1 : -1;  // place the player, identify which player; player 1 as 1, player 2 as -1;
    rows[row] += number;   // save the value to row, col, diag, antiDiag
    columns[col] += number;
    if (row == col) {
        diagonal += number;
    }
    if (row == n - 1 - col) {
        antiDiagonal += number;
    }
    if (Math.abs(rows[row]) == n || Math.abs(columns[col]) == n ||  // winning condition
         Math.abs(diagonal) == n || Math.abs(antiDiagonal) == n)
        return player;
    return 0;    
}

}

2nd largest BST - IC

def find_largest(root_node):
    current = root_node
    while current:
        if not current.right:
            return current.value
        current = current.right


def find_second_largest(root_node):
    if (root_node is None or
            (root_node.left is None and root_node.right is None)):
        raise ValueError('Tree must have at least 2 nodes')

    current = root_node
    while current:
        # Case: current is largest and has a left subtree
        # 2nd largest is the largest in that subtree
        if current.left and not current.right:
            return find_largest(current.left)

        # Case: current is parent of largest, and largest has no children,
        # so current is 2nd largest
        if (current.right and
                not current.right.left and
                not current.right.right):
            return current.value

        current = current.right

654 - max Binary Tree given array

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

class Solution(object):
    def createBST(self,nums):
        if len(nums) == 0:
            return None
        
        
        index = 0
        max_num = 0
        for i in range(len(nums)):
            if nums[i] > max_num:
                max_num = nums[i]
                index = i
                
                
        root = TreeNode(max_num)
        root.left = self.createBST(nums[0:index])
        root.right = self.createBST(nums[index + 1:])
        return root
        
    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """

        
        return self.createBST(nums)

811 subdomain visit count

class Solution(object):
    def subdomainVisits(self, cpdomains):
        """
        :type cpdomains: List[str]
        :rtype: List[str]
        """



        dict_t = {}
        for i in cpdomains:
            amount, rest = i.split(' ')
            url = rest.split('.')
            site = ""
            for segment in reversed(url):
                site = segment + site
                if site not in dict_t:
                    dict_t[site] = 0
                dict_t[site] += int(amount)
                
                site = "." + site
        
        
        res = [str(dict_t[key]) + " " + key for key in dict_t]
        return res
                    

Longest substring with K characters

class Solution(object):

    def longest_substr(self, string, k):
        if string is None:
            raise TypeError('string cannot be None')
        if k is None:
            raise TypeError('k cannot be None')
        low_index = 0
        max_length = 0
        chars_to_index_map = {}
        for index, char in enumerate(string):
            chars_to_index_map[char] = index
            if len(chars_to_index_map) > k:
                low_index = min(chars_to_index_map.values())
                del chars_to_index_map[string[low_index]]
                low_index += 1
            max_length = max(max_length, index - low_index + 1)
        return max_length

814-prune-tree.cpp

    public TreeNode pruneTree(TreeNode root) {
        if ( root == null ) return null;
        
        root.left = pruneTree (root.left);
        root.right = pruneTree (root.right);
        
        if ( root.val == 0 && root.left == null && root.right == null ) return null;
        
        return root;
    }

459-repeated-substring.py

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        max_length = len(s)/2
        for i in range(max_length):
            curr_word = s[0:i + 1]
            multiple = len(s) / len(curr_word)
            if curr_word * multiple == s:
                return True
        return False
            

trim a bst 669

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

class Solution(object):
    def trimHelper(self, root, L, R):
        print "HERE\n"
        if root == None:
            return None
        print root.val


        if root.val < L:
            return self.trimHelper(root.right, L, R)
        if root.val > R:
            return self.trimHelper(root.left, L, R)
        

        newroot = TreeNode(root.val)
        newroot.left = self.trimHelper(root.left, L, R)
        newroot.right = self.trimHelper(root.right, L, R)
        return newroot

    def trimBST(self, root, L, R):
        """
        :type root: TreeNode
        :type L: int
        :type R: int
        :rtype: TreeNode
        """
        return self.trimHelper(root, L,R)

Knapsack

def max_duffel_bag_value(cake_tuples, weight_capacity):
# We make a list to hold the maximum possible value at every
# duffel bag weight capacity from 0 to weight_capacity
# starting each index with value 0
    max_values_at_capacities = [0] * (weight_capacity + 1)
    
    for current_capacity in xrange(weight_capacity + 1):
        # Set a variable to hold the max monetary value so far
        # for current_capacity
        current_max_value = 0
    
        for cake_weight, cake_value in cake_tuples:
            # If a cake weighs 0 and has a positive value the value of
            # our duffel bag is infinite!
            if cake_weight == 0 and cake_value != 0:
                return float('inf')
    
            # If the current cake weighs as much or less than the
            # current weight capacity it's possible taking the cake
            # would get a better value
            if cake_weight <= current_capacity:
    
                # So we check: should we use the cake or not?
                # If we use the cake, the most kilograms we can include in
                # addition to the cake we're adding is the current capacity
                # minus the cake's weight. We find the max value at that
                # integer capacity in our list max_values_at_capacities
                max_value_using_cake = (
                    cake_value
                    + max_values_at_capacities[current_capacity - cake_weight]
                )
    
                # Now we see if it's worth taking the cake. how does the
                # value with the cake compare to the current_max_value?
                current_max_value = max(max_value_using_cake,
                                        current_max_value)
    
        # Add each capacity's max value to our list so we can use them
        # when calculating all the remaining capacities
        max_values_at_capacities[current_capacity] = current_max_value
        
        
    print max_values_at_capacities
    return max_values_at_capacities[weight_capacity]
   
print max_duffel_bag_value([[1,100], [2,10]], 2)

shortest completing words

class Solution(object):
def shortestCompletingWord(self, licensePlate, words):
"""
:type licensePlate: str
:type words: List[str]
:rtype: str
"""
dict_t = {}
for i in licensePlate:
if i.isalpha():
char_t = i.lower()
if char_t not in dict_t:
dict_t[char_t] = 0
dict_t[char_t] += 1

    shortest_word = None
    
    
    for word in words:
        temp_dict = dict_t.copy()
        for char in word:
            char = char.lower()
            if char in temp_dict and temp_dict[char] > 0:
                temp_dict[char] -= 1

                
        values_left = [key for key, value in temp_dict.iteritems() if value > 0]
        
        if not values_left:
            if shortest_word == None or len(shortest_word) > len(word):
                shortest_word = word
            
            
    return shortest_word

806 number of lines for string

class Solution(object):
    def numberOfLines(self, widths, S):
        """
        :type widths: List[int]
        :type S: str
        :rtype: List[int]
        """
        
        curr_cap = 100
        num_lines = 1
        for i in range(len(S)):
            if curr_cap - widths[string.lowercase.index(S[i])] < 0:
                num_lines += 1
                curr_cap = 100 - widths[string.lowercase.index(S[i])]
            else:
                curr_cap -= widths[string.lowercase.index(S[i])] 
        return num_lines, 100 - curr_cap
                

513 findBottomLeft Value BT

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

class Solution(object):
    leftMost = 0
    max_level = 0
    def findLeft(self, root, is_left,level):
        if(root == None):
            return
        print root.val
        print "Level " + str(level)
        if level >= self.max_level:
            self.leftMost = root.val
            self.max_level = level
            
            
        self.findLeft(root.right, False, level + 1)

        self.findLeft(root.left, True, level + 1)
        
        
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.findLeft(root, True, 1)
        return self.leftMost

partition labels 763

class Solution(object):
    def partitionLabels(self, S):
        last = {c: i for i, c in enumerate(S)}
        j = anchor = 0
        ans = []
        for i, c in enumerate(S):
            j = max(j, last[c])
            if i == j:
                ans.append(i - anchor + 1)
                anchor = i + 1
            
        return ans

max profit all time, buy whenever 122

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        # 2 3 4 5
        """
        if len(prices) == 0:
            return 0
        min_p = prices[-1]
        sum = 0 
        for i in range(len(prices) - 2, -1, -1):
            if prices[i] < prices[i + 1]:
                sum += prices[i+1] - prices[i]
        return sum

80 remove duplicates from sorted array 2

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        good_index = 2
        if len(nums) <= 2:
            return len(nums)
        start = 2
        while start < len(nums):  
            if nums[start] == nums[good_index - 1] and nums[start] == nums[good_index - 2]:
                start += 1
            else:
                nums[good_index] = nums[start]
                good_index += 1
            
                start += 1
        
        return good_index 

gen paren

class Solution(object):
    
    def genPerms(self,n, res, curr, open_i, close_i):
        if(open_i + close_i == n):
            res.append(curr)
            return
        else:
            if open_i < n/2:
                self.genPerms(n, res, curr + '(', open_i + 1, close_i)
            if close_i < open_i:
                self.genPerms(n, res, curr + ')', open_i, close_i + 1)
        
        
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = []
        curr =""
        if(n == 0):
            return res
        
        self.genPerms(n*2, res, curr, 0, 0)
        return res

796 rotate string problem

class Solution(object):
    def rotateString(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: bool
        """
        if not len(A) == len(B):
            return False
        
        a_2 = A * 2
        
        if B in a_2:
            return True
        return False
        

coin change min

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        if(len(coins) == 0):
            return 0
        if(amount == 0):
            return 0
        dp = [2141700] * (amount + 1)
        dp[0] = 0
        
        for i in range(0, amount + 1):
            for k in coins:
                if(i >= k):
                    dp[i] = min(dp[i-k] + 1, dp[i])                    
        if dp[amount] == 2141700:
            return -1
        else:
            return dp[amount]

max contiguous subarray

def maxSum(arr):
  max_sum = -100
  dp = [0] * len(arr)
  dp[0] = arr[0]
  for i in range(len(arr))[1:]:
    dp[i] = max(arr[i] + dp[i-1], arr[i])
    max_sum = max(dp[i], max_sum)
  return max_sum

a = [1,2,3]
b = [-1,-2,-3]
c = [-20, 20, 30,40, -10, 500]
print maxSum(a)
print maxSum(b)
print maxSum(c)