Posts about Coding (old posts, page 1)

RSS feed

1000. Minimum Cost to Merge Stones

Comments

Problem Setting

There are N piles of stones arranged in a row. The i-th pile has stones[i] stones.

A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.

Find the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.

Variable Type Description
stones list an array of stones with the merging cost
K int the maximum number of consecutive piles

Interactive Python Execution

Pythontutor is an awesome website which allows us to execute the code and visualize the flow of the code and variables taking account into data structure and stored values.

In [1]:
from IPython.display import IFrame
IFrame("https://pythontutor.com/iframe-embed.html#code=class%20Solution%28object%29%3A%0A%20%20%20%20def%20mergeStones%28self,%20A,%20K%29%3A%0A%20%20%20%20%20%20%20%20N%20%3D%20len%28A%29%0A%20%20%20%20%20%20%20%20if%20%28N%20-%201%29%20%25%20%28K%20-%201%29%3A%20return%20-1%0A%20%20%20%20%20%20%20%20INF%20%3D%20float%28'inf'%29%0A%20%20%20%20%20%20%20%20memo%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20prefix%20%3D%20%5B0%5D%20%23%20prefix%20sum%0A%20%20%20%20%20%20%20%20for%20x%20in%20A%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20prefix.append%28prefix%5B-1%5D%20%2B%20x%29%0A%20%20%20%20%20%20%20%20def%20dp%28i,%20j,%20m%29%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20%28j%20-%20i%20%2B%201%20-%20m%29%20%25%20%28K%20-%201%29%3A%20return%20INF%20%20%23%20optimize%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20%28i,%20j,%20m%29%20in%20memo%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20memo%5Bi,%20j,%20m%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20i%20%3D%3D%20j%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%200%20if%20m%20%3D%3D%201%20else%20INF%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20m%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20dp%28i,%20j,%20K%29%20%2B%20prefix%5Bj%20%2B%201%5D%20-%20prefix%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20INF%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20mid%20in%20range%28i,%20j,%20K%20-%201%29%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res%20%3D%20min%28res,%20dp%28i,%20mid,%201%29%20%2B%20dp%28mid%20%2B%201,%20j,%20m%20-%201%29%29%0A%20%20%20%20%20%20%20%20%20%20%20%20memo%5Bi,%20j,%20m%5D%20%3D%20res%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20res%0A%20%20%20%20%20%20%20%20res%20%3D%20dp%280,%20N%20-%201,%201%29%0A%20%20%20%20%20%20%20%20return%20res%20if%20res%20%3C%20INF%20else%200%0A%20%20%20%20%20%20%20%20%0Astones%20%3D%20%5B3,5,1,2,6%5D%0AK%20%3D%203%0As%20%3D%20Solution%28%29%0As.mergeStones%28stones,%20K%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=nevernest&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false", width=1000, height=500)
Out[1]:

Read more…

1004. Max Consecutive Ones III

Comments

Problem Setting

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.

Variable Type Description
A list an array of 0s and 1s e.g., 111000
K int the maximum number of changes fliping from 0 to 1

Example 1

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2

Output: 6

Explanation: [1,1,1,0,0,1*,1,1,1,1,1*]

Numbers with * (astarisk) were flipped from 0 to 1. The longest subarray is indicated as a line of bold numers.

Read more…

617. Merge Two Binary Trees

Comments

Problem Setting

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1: 

Input: 
    Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
         3
        / \
       4   5
      / \   \ 
     5   4   7

Read more…

990 Satisfiability of Equality Equations

Comments

Problem Setting

Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: "a==b" or "a!=b". Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

Read more…

998 Smallest String Starting From Leaf

Comments

Problem Setting

The 2nd problem in Weekly Contest 122 is Smallest String Starting From Leaf

Given the root of a binary tree, each node has a value from 0 to 25 representing the letters 'a' to 'z': a value of 0 represents 'a', a value of 1 represents 'b', and so on.

Find the lexicographically smallest string that starts at a leaf of this tree and ends at the root.

(As a reminder, any shorter prefix of a string is lexicographically smaller: for example, "ab" is lexicographically smaller than "aba". A leaf of a node is a node that has no children.)

Read more…