LeetCode 226. Invert Binary Tree

Problem:

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

Solution:

The famous Google interview question for Max Howell ROFL.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

LeetCode 213. House Robber II

Problem:

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Solution:

public class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
    }
    
    private int rob(int[] nums, int low, int high) {
        int include = 0, exclude = 0;
        for (int i = low; i <= high; i++) {
            int tmp = include;
            include = exclude + nums[i];
            exclude = Math.max(exclude, tmp);
        }
        return Math.max(include, exclude);
    }
}

 

LeetCode 337. House Robber III

Problem:

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

     3
    / \
   2   3
    \   \ 
     3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

     3
    / \
   4   5
  / \   \ 
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution:

DP, at first I just did it recursively and it was AWFUL.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    HashMap<TreeNode, Integer> map = new HashMap<>();
    
    public int rob(TreeNode root) {
        if (root == null) return 0;
        if (map.containsKey(root)) return map.get(root);
        int rob0 = robNot(root);
        int rob1 = robYes(root);
        int max = Math.max(rob0, rob1);
        map.put(root, max);
        return max;
    }
    
    private int robYes(TreeNode root) {
        if (root == null) return 0;
        return root.val + robNot(root.left) + robNot(root.right);
    }
    
    private int robNot(TreeNode root) {
        if (root == null) return 0;
        return rob(root.left) + rob(root.right);
    }
}

LeetCode 238. Product of Array Except Self

Problem:

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements ofnums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Solution:

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] output = new int[nums.length];
        output[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            output[i] = output[i-1] * nums[i-1];
        }
        int right = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            output[i] *= right;
            right *= nums[i];
        }
        return output;
    }
}

LeetCode 279. Perfect Squares

Problem:

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Solution:

DP

public class Solution {
    
    public int numSquares(int n) {
        int[] least = new int[n+1];
        int root = 0;
        for (int i = 0; i <= n; i++) {
            if (i == root * root) {
                least[i] = 1;
                root++;
                continue;
            }
            int min = Integer.MAX_VALUE;
            for (int j = 1; j * j < i; j++)
                min = Math.min(least[j*j] + least[i-j*j], min);
            least[i] = min;
        }
        return least[n];
    }
}

LeetCode 382. Linked List Random Node

Problem:

Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

Solution:

Not using Reservoir Sampling, but I found this post that describes the process.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {

    int count;
    ListNode head;
    
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        count = 0;
        this.head = head;
        ListNode current = head;
        while (current != null) {
            current = current.next;
            count++;
        }
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        Random random = new Random();
        int rnd = random.nextInt(count);
        ListNode current = head;
        for (int i = 0; i < rnd; i++)
            current = current.next;
        return current.val;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

LeetCode 59. Spiral Matrix II

Problem:

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Solution:

Just like Spiral Matrix problem.

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        if (n == 0) return result;
        int x = n, y = n;
        int row = 0, col = -1;
        int num = 0;
        while (true) {
            for (int i = 0; i < x; i++)
                result[row][++col] = ++num;
            if (--y == 0) break;
            for (int i = 0; i < y; i++)
                result[++row][col] = ++num;
            if (--x == 0) break;
            for (int i = 0; i < x; i++)
                result[row][--col] = ++num;
            if (--y == 0) break;
            for (int i = 0; i < y; i++)
                result[--row][col] = ++num;
            if (--x == 0) break;
        }
        return result;
    }
}

Memo on C Language Programming

Starting yesterday I have been reading the official manual of C programming language from GNU. I have finished 17 chapters out of 20-something chapters of the whole manual. I realized that the best way to learn an open-source stuff is indeed to read the documentation/help manual.

Yesterday I covered basic knowledge of the programming language such as type, expression, function, and pointer. It didn’t take much time because I have read other materials on C before. I did spend some time understanding pointers since in Java there is no explicit definition of pointer.

Today’s new materials include IO, String operation and “making” a program with multiple C source code files. I’m going to write down here things new to me.

 

  1. File IO:
#include <stdio.h>
#include <stdlib.h>

int main() {
	FILE *stream;
	stream = fopen("shit.dat", "w");
	int my_array[2][2] =
	{
		{1,2},
		{3,4}
	};
	size_t object_size = sizeof(int);
	size_t object_count = 4;

	if (stream == NULL) {
		printf("shit.dat could not be created\n");
		exit(0);
	}
	printf("file opened for writing\n");
	fwrite(&my_array, object_size, object_count, stream);
	fclose(stream);
	
	stream = fopen("shit.dat", "r");
	if (stream == NULL) {
		printf("shit.dat could not be read\n");
		exit(0);
	}
	printf("file opened for reading\n");
	fread(&my_array, object_size, object_count, stream);
	fclose(stream);

	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			printf("%d ", my_array[i][j]);
		}
		printf("\n");
	}
	return 0;
}

Most important functions for input/output with files would be fopen, fclose, fread, fwrite, getline and fprintf. According to the manual, it is suggested to use fread, getline and fwrite since they are safer than the rest, some of which are already deprecated. It’s worth noting that the second and the third parameters of fwrite and fread are of type size_t. Other than this, this part is pretty easy.

 

2. Combination of getline and sscanf

getline is a safe method, if you pass in an uninitialized string pointer, the program will create a buffer of a proper size for you and populate the variable. However, if you use methods like scanf instead, you may encounter buffer overflow errors, which can be very common. getline returns a line of text before a linebreak from a stream, which can be either stdin or a file.

Then, sscanf is used to read stuff of a specific type or a format from the string. This combination, according to the manual, is much better than using scanf alone, since it avoids many errors.

Example code:

#include <stdlib.h>
#include <stdio.h>

int main()
{
	int args_assigned = 0;
	size_t nbytes = 2;
	char *my_string;
	int int1, int2, int3;

	while (args_assigned != 3)
	{
		puts("Please enter three integers separated by whitespace.");
		my_string = (char *) malloc(nbytes + 1);
		getline(&my_string, &nbytes, stdin);
		args_assigned = sscanf(my_string, "%d %d %d", &int1, &int2, &int3);
		if (args_assigned != 3)
		{
			puts("Invalid input!");
		}
		else
		{
			printf("Three integers: %d %d %d\n", int1, int2, int3);
		}
	}
	return 0;
}

It doesn’t matter that my_string is initialized with a very small size: getline will take care of that.

 

3. ARGP

ARGP is such a strong tool!! With this, it’s very easy to parse parameters passed to the program and provide the users with usage explanations and documentations interactively.

The boss function is argp_parse, which takes four parameters: 1. parameter options, in a struct type, 2. a function to handle the option and parameter fields, 3. a string describing the arguments format, 4. a string that documents the program.

There are so many options available for customization. Although it’s hard to remember all of the parameter types and requirements, in actual development process I can just copy the old example piece of code and continue happily from there.

Example code:

#include <stdio.h>
#include <argp.h>

const char *argp_program_version = "argex 1.0";
const char *argp_program_bug_address = "<han.yu@duke.edu>";

/* This structure is used by main to communicate with parse_opt. */
struct arguments
{
	char *args[2];
	int verbose;
	char *outfile;
	char *string1, *string2;
};

/*
 * 	OPTIONS. Field 1 in ARGP.
 * 	Order of fields: {NAME, KEY, ARG, FLAGS, DOC}.
*/
static struct argp_option options[] = 
{
	{"verbose", 'v', 0, 0, "Produce verbose output"},
	{"alpha", 'a', "STRING1", 0, "Do something with STRING1 related to the letter A"},
	{"bravo", 'b', "STRING2", 0, "Do something with STRING2 related to the letter B"},
	{"output", 'o', "OUTFILE", 0, "Output to OUTFILE instead of to standard output"},
	{0}
};

/*
 * PARSER. Field 2 in ARGP.
 * Order of parameters: KEY, ARG, STATE.
*/
static error_t parse_opt (int key, char *arg, struct argp_state *state)
{
	struct arguments *arguments = state->input;
	switch (key)
	{
		case 'v':
			arguments->verbose = 1;
			break;
		case 'a':
			arguments->string1 = arg;
			break;
		case 'b':
			arguments->string2 = arg;
			break;
		case 'o':
			arguments->outfile = arg;
			break;
		case ARGP_KEY_ARG:
			if (state->arg_num >= 2)
			{
				argp_usage(state);
			}
			arguments->args[state->arg_num] = arg;
			break;
		case ARGP_KEY_END:
			if (state->arg_num < 2)
			{
				argp_usage(state);
			}
			break;
		default:
			return ARGP_ERR_UNKNOWN;
	}
	return 0;
}

/*
 * ARGS_DOC. Field 3 in ARGP.
 * A description of the non-option command-line arguments that we accept.
*/
static char args_doc[] = "ARG1 ARG2";

/*
 * DOC. Field 4 in ARGP.
 * Program documentation.
*/
static char doc[] = 
"argex -- A program to demonstrate how to code command-line options and arguments.\vFrom the GNU C Tutorial.";

/*
 * The ARGP structure itself.
*/
static struct argp argp = {options, parse_opt, args_doc, doc};

/*
 * The main function.
 * Notic how now the only function call needed to process all command-line options and arguments nicely is argp_parse.
*/
int main (int argc, char **argv)
{
	struct arguments arguments;
	FILE *outstream;
	char waters[] = "Some long sentence";

	/* Set argument defaults */
	arguments.outfile = NULL;
	arguments.string1 = "";
	arguments.string2 = "";
	arguments.verbose = 0;

	/* Where the magic happens */
	argp_parse(&argp, argc, argv, 0, 0, &arguments);

	/* Where do we send output? */
	if (arguments.outfile)
			outstream = fopen(arguments.outfile, "w");
	else
		outstream = stdout;

	/* Print argument values */
	fprintf(outstream, "alpha = %s\nbravo = %s\n\n", arguments.string1, arguments.string2);
	fprintf(outstream, "ARG1 = %s\nARG2 = %s\n\n", arguments.args[0], arguments.args[1]);

	/* If in verbose mode, pring song stanza */
	if (arguments.verbose)
		fprintf(outstream, "%s", waters);

	return 0;
}

When it runs it really behaves like a “legit” GNU open source software!

 

I also read about makefiles: its rules, targets and variables that can simplify the code. I guess tomorrow I’ll read more about C. If I finish this manual I’ll take a look at the GNU Make manual.

Anyway, it’s cool that a book originally written 30 years ago is still not outdated at all.

 

LeetCode 172. Factorial Trailing Zeroes

Problem:

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Solution:

public class Solution {
    public int trailingZeroes(int n) {
        int deg = 5;
        int div = n/deg;
        int result = div;
        while(div > 1) {
            deg *= 5;
            div  = n/deg;
            result += div;
        }
        return result;
    }
}