LeetCode 122. Best Time to Buy and Sell Stock II

Problem:

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:

Just when I thought this was a DP…….

public class Solution {
    int[] profit;
    
    public int maxProfit(int[] prices) {
        if (prices.length < 1) return 0;
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i-1]) max += prices[i] - prices[i-1];
        }
        return max;
    }
}

LeetCode 355. Design Twitter

Problem:

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:

  1. postTweet(userId, tweetId): Compose a new tweet.
  2. getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
  3. follow(followerId, followeeId): Follower follows a followee.
  4. unfollow(followerId, followeeId): Follower unfollows a followee.

Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);

// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.unfollow(1, 2);

// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);

Solution:

Fun one.

public class Twitter {
    ArrayList<Tweet> all;
    HashMap<Integer, User> users;
    
    public class Tweet {
        int id;
        int author;
        
        public Tweet(int author, int id) {
            this.author = author;
            this.id = id;
        }
    }
    
    public class User {
        int id;
        HashSet<Integer> following;
        ArrayList<Tweet> tweets;
        
        public User(int id) {
            this.id = id;
            this.following = new HashSet<Integer>();
            this.tweets = new ArrayList<Tweet>();
        }
        
        public void follow(int followeeId) {
            this.following.add(followeeId);
        }
        
        public void unfollow(int followeeId) {
            this.following.remove(followeeId);
        }
        
        public void postTweet(int tweetId) {
            Tweet t = new Tweet(this.id, tweetId);
            this.tweets.add(t);
            all.add(t);
        }
    }

    /** Initialize your data structure here. */
    public Twitter() {
        all = new ArrayList<Tweet>();
        users = new HashMap<Integer, User>();
    }
    
    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        User u = users.get(userId);
        if (u == null) {
            u = new User(userId);
            users.put(userId, u);
        }
        u.postTweet(tweetId);
    }
    
    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    public List<Integer> getNewsFeed(int userId) {
        User u = users.get(userId);
        if (u == null) return new ArrayList<Integer>();
        int count = 0;
        List<Integer> feed = new ArrayList<Integer>();
        for (int i = all.size() - 1; i >= 0; i--) {
            if (count >= 10) break;
            Tweet t = all.get(i);
            if (t.author == u.id || u.following.contains(t.author)) {
                count++;
                feed.add(t.id);
            }
        }
        return feed;
    }
    
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        User u = users.get(followerId);
        if (u == null) {
            u = new User(followerId);
            users.put(followerId, u);
        }
        u.follow(followeeId);
    }
    
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        User u = users.get(followerId);
        if (u == null) {
            u = new User(followerId);
            users.put(followerId, u);
        }
        u.unfollow(followeeId);
    }
}

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter obj = new Twitter();
 * obj.postTweet(userId,tweetId);
 * List<Integer> param_2 = obj.getNewsFeed(userId);
 * obj.follow(followerId,followeeId);
 * obj.unfollow(followerId,followeeId);
 */

Day 4 Week 6 on JFLAP

Today I did even more refactoring. I extracted methods from the long long code of parsing functions and moved the common ones to a file ParseHelper.js. The file contains a ParseHelper class, whose objects are able to hold many grammar-related variables. This will make my life much easier. Functions that do not need so many variables or are not only relavent to parsing are moved to GrammarTools.js. Other than this, I also moved each parsing function to its own controller file. The controllers also act as classes. Object oriented af!

Oh yes, before all these I moved the exercise feature to ExerciseController.js. FATester and FAFixer are now configured to use this class.

Day 3 Week 6 on JFLAP

Today I continued the refactoring process. FAEditor is fully functional now, with all of its buttons clickable. I moved saveFAState and relavent functions to FA.js. Dragging to add edges functions are still in there because my patience can only afford so much of refactoring! Other visualizations html files are moved to ui folder, css files in ui/css folder. For the next step, I plan to extract parsing methods to different js controller files in grammar folder.

LeetCode 224. Basic Calculator

Problem:

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

Solution:

Stack. I’ve seen this on Java intro book. Yeah my code is bad…

public class Solution {
    Stack<Integer> elements = new Stack<Integer>();
    Stack<Character> operators = new Stack<Character>();
    ArrayList<Character> op = new ArrayList<Character>();
    
    public int calculate(String s) {
        op.add('+');
        op.add('-');
        op.add('(');
        op.add(')');
        String temp = "";
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (op.indexOf(c) > -1) {
                temp = temp.trim();
                if (!temp.equals("")) {
                    elements.push(Integer.parseInt(temp));
                    temp = "";
                }
                if (c == ')') {
                    char pk = operators.pop();
                    while (pk != '(') {
                        int v1 = elements.pop();
                        int v2 = elements.pop();
                        if (pk == '+') elements.push(v1+v2);
                        else if (pk == '-') elements.push(v2-v1);
                        pk = operators.pop();
                    }
                    continue;
                }
                char pk = operators.isEmpty() ? 'e' : operators.peek();
                if (pk != 'e' && op.indexOf(pk) < 2 && c != '(') { // + or -
                    operators.pop();
                    int v1 = elements.pop();
                    int v2 = elements.pop();
                    if (pk == '+') elements.push(v1+v2);
                    else elements.push(v2-v1);
                }
                operators.push(c);
            }
            else if (i == s.length() - 1) {
                temp += c;
                temp = temp.trim();
                if (!temp.equals("")) {
                    elements.push(Integer.parseInt(temp));
                }
                char pk = operators.isEmpty() ? 'e' : operators.peek();
                if (pk != 'e' && op.indexOf(pk) < 2) { // + or -
                    operators.pop();
                    int v1 = elements.pop();
                    int v2 = elements.pop();
                    if (pk == '+') elements.push(v1+v2);
                    else elements.push(v2-v1);
                }
            }
            else {
                temp += c;
            }
        }
        while (!operators.empty()) {
            char op = operators.pop();
            int v1 = elements.pop();
            int v2 = elements.pop();
            if (op == '+') elements.push(v1+v2);
            else elements.push(v2-v1);
        }
        return elements.pop();
    }
}

Day 2 Week 6 on JFLAP

Today I improved the layout of RE to FA Converter. Now new nodes are no longer added to the top left corner. JFLAP 7 uses AffineTransform class provided along with Java, which JavaScript does not have, so I searched online and found this paper.js library. The APIs are almost the same so the code translates naturally. A screenshot of this improvement is shown below. Nodes have not been moved by hand.

 

RE to FA layoutLayout of New Nodes

 

Then I spent most of the time refactoring the code. I moved FA-related html files to a new folderui/, css files to ui/css, and controller files to other folders. FAtoRE code was moved to a controller and acts as an object in order to transfer graph data conveniently. The design is that controllers are like classes and user interface js files are scripts, which use the objects created by the controllers. Displaying right click menu feature was finally moved to FA.js. Tomorrow I will also move undo/redo feature toFA.js since it is relevant more to FA than to editing FA. So for now, FA.js includes both the description for the FA model and the controllers for FA user interface. I think one file does not need to do only one job since including js files in html files is troublesome.

One problem of this refactoring is that earlier links in this blog do not work any more. I will definitely take some time to update these links.

LeetCode 241. Different Ways to Add Parentheses

Problem:

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +,- and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

Solution:

Very similar to the binary search tree one. Recursion on operators.

public class Solution {
    List<Integer> elements = new ArrayList<Integer>();
    List<Character> operators = new ArrayList<Character>();
    
    public List<Integer> diffWaysToCompute(String input) {
        String temp = "";
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '*' || c == '-' || c == '+') {
                elements.add(Integer.parseInt(temp));
                temp = "";
                operators.add(c);
            }
            else temp += c;
        }
        elements.add(Integer.parseInt(temp));
        return compute(0, operators.size() - 1);
    }
    
    private List<Integer> compute(int s, int e) {
        List<Integer> results = new ArrayList<Integer>();
        if (s > e) {
            results.add(elements.get(s));
            return results;
        }
        for (int i = s; i <= e; i++) {
            List<Integer> lefts = compute(s, i - 1);
            List<Integer> rights = compute(i + 1, e);
            char o = operators.get(i);
            for (int left: lefts) {
                for (int right: rights) {
                    if (o == '-') results.add(left - right);
                    else if (o == '+') results.add(left + right);
                    else if (o == '*') results.add(left * right);
                }
            }
        }
        return results;
    }
}

LeetCode 95. Unique Binary Search Trees II

Problem:

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution:

Recursion with start and end.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<TreeNode>();
        return generate(1, n);
    }
    
    private List<TreeNode> generate(int s, int e) {
        List<TreeNode> re = new ArrayList<TreeNode>();
        if (s > e) {
            re.add(null);
            return re;
        }
        for (int i = s; i <= e; i++) {
            List<TreeNode> lefts = generate(s, i - 1);
            List<TreeNode> rights = generate(i + 1, e);
            for (TreeNode left: lefts) {
                for (TreeNode right: rights) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    re.add(root);
                }
            }
        }
        return re;
    }
}

LeetCode 96. Unique Binary Search Trees

Problem:

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution:

Memoization

public class Solution {
    int[] data;
    public int numTrees(int n) {
        data = new int[n + 2];
        data[0] = 1; data[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                data[i] += data[j] * data[i-1-j];
            }
        }
        return data[n];
    }
}

LeetCode 332. Reconstruct Itinerary

Problem:

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

  1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
  2. All airports are represented by three capital letters (IATA code).
  3. You may assume all tickets form at least one valid itinerary.

Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

Solution:

DFS+backtracking. At first I did not realize all tickets have to be used. Reading the question thoroughly is very important.

public class Solution {
    Map<String, List<String>> g = new HashMap<String, List<String>>();
    List<String> sol = new ArrayList<String>();
    int size;
    
    public List<String> findItinerary(String[][] tickets) {
        for (int i = 0; i < tickets.length; i++) {
            String from = tickets[i][0];
            String to = tickets[i][1];
            if (!g.containsKey(from)) {
                List<String> opts = new ArrayList<String>();
                opts.add(to);
                g.put(from, opts);
            }
            else {
                List<String> opts = g.get(from);
                opts.add(to);
                g.put(from, opts);
            }
        }
        
        sol.add("JFK");
        size = tickets.length + 1;
        find(sol);
        return sol;
    }
    
    private boolean find(List<String> current) {
        if (current.size() == size) return true;
        String start = current.get(current.size() - 1);
        List<String> opts = g.get(start);
        if (opts == null || opts.size() == 0) {
            return false;
        }
        Collections.sort(opts);
        for (int i = 0; i < opts.size(); i++) {
            String opt = opts.get(i);
            current.add(opt);
            opts.remove(i);
            if (find(current)) return true;
            opts.add(i, opt);
            current.remove(current.size() - 1);
        }
        return false;
    }
}