junjiah

# 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 rightSideView(self, root):
    """

junjiah

// Runtime: 200ms. Typical DP.
class Solution {
public:
    int numSquares(int n) {
        vector<int> perfect_records(n + 1, 0);
        
        for (int i = 1; i <= n; ++i) {
            int min_to_perfect = INT_MAX;
            for (int j = 1; i - j * j >= 0; ++j) {
                if (perfect_records[i - j * j] < min_to_perfect) {

junjiah

// Rolling hash. Runtime: 92ms.
class Solution {
 public:
  vector<string> findRepeatedDnaSequences(string s) {
    // Parameter for rolling hash.
    const int ROLL_EXP = 5;
    // Step size in problem description.
    const int STEP = 10;
    // Most significant value for the rolling hash.
    const int MOST_SIGNIFICANT = pow(ROLL_EXP, STEP - 1);

junjiah

// Solved 'Bot saves princess' on hackerrank
// https://www.hackerrank.com/challenges/saveprincess
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

junjiah

#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

// DP, O(mn). Runtime: 1304 ms.
class Solution {
 public:
  bool isMatch(string s, string p) {

junjiah

#!/usr/bin/python

class DeepIterator(object):
    def __init__(self, ls):
        """ls: A list containing integers or list of same type."""
        self.ls = ls
        # An index stack indicating current index in each level.
        self.curr = [0]
    
    def __iter__(self):

junjiah

class Solution {
 public:
  // Use DFS to find cycles.
  bool canFinish(int numCourses, vector<pair<int, int>> &prerequisites) {
    // Init the graph.
    adjacency_list_ = vector<vector<int>>(numCourses);
    visited_ = vector<bool>(numCourses);
    visited_in_recursion_ = vector<bool>(numCourses);
    for (const auto &edge : prerequisites) {
      adjacency_list_[edge.second].push_back(edge.first);

junjiah

def get_connected_component_sizes(graph, node_num):
  """graph: Adjacency list for the graph.
     node_num: Number of nodes."""
  visited = [False] * node_num
  component_sizes = []
  
  for v in xrange(node_num):
    if not visited[v]:
      # DFS using stack.
      stack, sz = [v], 0

junjiah

from collections import namedtuple


# A reasonable large number to represent infinity.
INF = (1 << 31)
UNIT_LENGTH = 6
# Struct for edges.
Edge = namedtuple('Edge', ['src', 'dest'])

def calculate_shortest_distances(node_num, edges, src):

junjiah

def max_score(bricks):
    """bricks: A list of bricks."""
    sz = len(bricks)
    # DP algorithm. See the editorial.
    # https://www.hackerrank.com/challenges/play-game/editorial
    max_score_from = [0] * sz
    max_score_from[-1] = bricks[-1]
    max_score_from[-2] = max_score_from[-1] + bricks[-2]
    max_score_from[-3] = max_score_from[-2] + bricks[-3]