How to use diff command in Linux? How to compare two files difference?

diff is a very useful command when you want to compare two files.

basic use of diff is:

diff fileA fileB

Say if fileA is:

Both are convinced
that a sudden surge of emotion bound them together.
Beautiful is such a certainty,
but uncertainty is more beautiful.

Because they didn’t know each other earlier, they suppose that
nothing was happening between them.
What of the streets, stairways and corridors

fileB is:

Both of us are convinced
that a sudden surge of emotion bound them together.
but uncertainty is more beautiful.

Because they didn’t know each other earlier, they suppose that
nothing was happening between them.
What of the streets, stairways and corridors
where they could have passed each other long ago?

The output of diff fileA fileB would be:

1c1

< Both are convinced

> Both of us are convinced

3d2

< Beautiful is such a certainty,

8a8

> where they could have passed each other long ago?

\ No newline at end of file

Let’s read the output.

If two files are identical output would be empty, otherwise it would be an instruction for modifying fileA to become fileB.

1c1 means change line 1 in fileA to match line 1 in fileB.

3d2 means delete line 3 in fileA to match line 2 in fileB.

8a8 means add a new line in line 8 in fileA to match line 8 in fileB.

So the first number is the line numbers in fileA, letter means action, c for change, d for delete, a for add and last number is for line numbers in fileB.

Line numbers could be multiple as well, like 2,5 means line 2 to line 5.

For more advanced comparison, checkout the manuals by running command

man diff

222 LeetCode Java: Count Complete Tree Nodes – Medium

Problem:

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Thoughts:

This problem is a little tricky.

Straight forward way is to count every single node, either a BFS, or a DFS.

I didn’t try it cause I think it should fail on running time, otherwise this problem will not make any sense.

Actually, it only costs h = logn time to calculate the height of the tree. ( n is the number of nodes.)

So the key point is to calculate what’s the offset of the last element which is in the last row.

I tried a binary search approach but didn’t succeed yet. I think BS would work here.

There is another working approach which is easier to understand.

Divide and conquer,

condition to test if a tree is complete tree it to test the depth of left-most node and the depth of right-most node. If they are the same, then it is a complete tree.

It’s always easy to calculate the number of nodes in a complete tree, 2^h – 1, where h is the height.

But if the two depth is not the same, then recursively solve the problem, which is divide, countNodes for the left subtree and the right subtree, sum up and plus 1.

Solutions:


/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
    public int countNodes(TreeNode root) {
        if(root==null)
            return 0;
        int left = leftDepth(root);
        int right = rightDepth(root);
        if(left == right)
            return (2<<(left-1))-1;
        else
            return countNodes(root.left) + countNodes(root.right)+1;
    }
    private int leftDepth(TreeNode node){
        int depth = 0;
        TreeNode it = node;
        while (it !=null){
            depth ++;
            it = it.left;
        }
        return depth;
    }
    private int rightDepth(TreeNode node){
        int depth = 0;
        TreeNode it = node;
        while (it !=null){
            depth ++;
            it = it.right;
        }
        return depth;
    }
}

221 LeetCode Java: Maximal Square – Medium

Problem:

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Thoughts:

This is a very obvious dynamic programming problem.

Define a corresponding array, max[i][j], represents the largest square ( only the edge, not the area) using (i, j) as the bottom right corner.

So to calculate max[i][j]

max[i][j] = 0 if matrix[i][j = 0// first row or first column

max[i][j] = 1 if i = 0 or j = 0 and matrix[i][j] = 1// first row or first column

if i != 0 and j != 0 and matrix[i][j] = 1 there are two cases here:

if max[i-1][j] and max[i][j-1] are not the same, then the new largest square is determined by the smaller of these two values,

max[i][j] = smaller + 1

if max[i-1][j] and max[i][j-1] are the same,

the number depends on if matrix[i – max[i-1][j]][j – max[i-1][j]] is 1

if it’s 1 then max[i][j] = max[i-1][j] + 1

if it’s 0 then max[i][j] = max[i-1][j]

Each step in the double loop, check the value of max[i][j], keep a max variable to keep the maximum value so that we could use it to return in the end.

When returning the value, remember to return the square of that because we store the edge length not the actual area in the array.

Solutions:


public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }
        int[][] max = new int[matrix.length][matrix[0].length];
        int maxSq = 0;
        for (int i = 0; i < matrix.length; i ++){
            for (int j = 0; j < matrix[0].length; j ++){
                if (matrix[i][j] == '1'){
                    if (i == 0 || j == 0){
                        max[i][j] = 1;
                    }
                    else{
                        if (max[i-1][j] == max[i][j-1]){
                            int val = max[i-1][j];
                            if (matrix[i- val][j - val] == '1')
                                max[i][j] = 1 + Math.min(max[i-1][j], max[i][j-1]);
                            else
                                max[i][j] = Math.min(max[i-1][j], max[i][j-1]);
                        }
                        else{
                            max[i][j] = 1 + Math.min(max[i-1][j], max[i][j-1]);
                        }
                    }//else i == 0 || j == 0
                }//if matrix[i][j] == '1'
                else{
                    max[i][j] = 0;
                }
                maxSq = Math.max(maxSq, max[i][j]);
            }//for j
        }//for i
        return maxSq * maxSq;
    }
}

220 LeetCode Java: Contains Duplicate III – Medium

Problem:

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] andnums[j] is at most t and the difference between i and j is at most k.

Thoughts:

This is a very difficult one if you don’t know there is a class called TreeSet.

With the help of TreeSet, it just becomes super easy.

A TreeSet is keeping all elements in k range based on current index.

Solutions:


public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (k < 1 || t < 0)
            return false;
        SortedSet<Long> set = new TreeSet<Long>();//keep all elements in k range
        for (int i = 0; i < nums.length; i++) {
            long left = (long) nums[i] - t;
            long right = (long) nums[i] + t + 1;
            SortedSet<Long> subSet = set.subSet(left, right);
            if (!subSet.isEmpty())
                return true;
            set.add((long) nums[j]);
            if (j>=k) {
                set.remove((long) nums[j - k]);
            }
        }
        return false;
    }
}

219 LeetCode Java: Contains Duplicate II – Medium

Problem:

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

Thoughts:

This is similar to version I. The difference is that instead of only test if there is duplicate, we need to tell the difference of two indices of the duplicate values.

And we care about the smallest difference.

Notice that you need to put value, index pair into the hashmap no matter if that element already appeared.

Solutions:


public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> left = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i ++){
            if (left.containsKey(nums[i])){
                if (i - left.get(nums[i])<= k){
                    return true;
                }
            }
            left.put(nums[i], i);
        }//for i
        return false;
    }
}

217 LeetCode Java: Contains Duplicate – Easy

Problem:

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Thoughts:

This is too straight forward and simple. I am curious if there is a solution that only takes O(1) space.

From running time perspective, we have to touch every element at lease once, so it needs to be O(n).

Solutions:


public class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i ++){
            if (set.contains(nums[i])){
                return true;
            }
            set.add(nums[i]);
        }    
        return false;
    }
}

216 LeetCode Java: Combination Sum III – Medium

Problem:

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

Thoughts:

This problem is modified based the Combination Sum II.

Difference is:

Candidates are numbers from 1 – 9 instead of given array.

Secondly, there is no constraints on number of elements in version II, but in III, the list of elements that adds up to given target value n has to have exact k elements.

Below is using an approach that’s modified based on the solution to Version II.

Solutions:


public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        int[] candidates = new int[9];
        for (int i = 0; i < 9; i ++){
            candidates[i] = i + 1;
        }
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(candidates == null || candidates.length == 0) 
            return result;
        ArrayList<Integer> current = new ArrayList<Integer>();
        Arrays.sort(candidates);
        combinationSum(k, candidates, n, 0, current, result);
        return result;
    }
    public void combinationSum(int k, int[] candidates, int target, int j, ArrayList<Integer> curr, List<List<Integer>> result){
        if(target == 0){
            if (curr.size() == k){
                ArrayList<Integer> temp = new ArrayList<Integer>(curr);
                result.add(temp);
            }
            return;
        }
        for(int i=j; i<candidates.length; i++){
            if (target < candidates[i]){
                return;
            }
            if (i == j || candidates[i] != candidates[i-1]){
                curr.add(candidates[i]);
                combinationSum(k, candidates, target - candidates[i], i + 1, curr, result);
                curr.remove(curr.size()-1);
            }
        }//for i
    }//combinationSum
}