[LeetCode] 70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Subscribe to see which companies asked this question

public class Solution {
    public int climbStairs(int n) {
        // 1d dp
        
        if(0 == n)
            return 0;
        if(1 == n)
            return 1;
        
        int[] dp = new int[3];
        
        dp[1] = 1;
        dp[2] = 2;
        
        for(int i = 3; i <= n; ++i){
            dp[i%3] = dp[(i-1)%3] + dp[(i-2)%3];
        }
        
        return dp[n%3];
    }
}

[LeetCode] 64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Subscribe to see which companies asked this question

public class Solution {
    public int minPathSum(int[][] grid) {
        
        int m = grid.length;
        if(0 == m)
            return 0;
        int n = grid[0].length;
        if(0 == n)
            return 0;
            
        int dp[] = new int[m];
        
        dp[0] = grid[0][0];
        for(int i = 1; i < m; ++i){
            dp[i] = dp[i-1] + grid[i][0];
        }
        
        for(int j = 1; j < n; ++j){
            for(int i = 0; i < m; ++i){
                if(0 == i){
                    dp[i] += grid[0][j];
                }
                else{
                    dp[i] = Math.min(dp[i-1], dp[i])+grid[i][j];
                }
            }
        }
        
        return dp[m-1];
        
    }
}

[LeetCode] 63. Unique Paths II

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
        int m = obstacleGrid.length;
        
        if(0 == m)
            return 0;
            
        int n = obstacleGrid[0].length;
        
        if(0 == n)
            return 0;
            
        int[] dp = new int[m];
        
        if( 1 == obstacleGrid[0][0])
            return 0;
        
        dp[0] = 1;
        
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                if(1 == obstacleGrid[j][i]){
                    dp[j] = 0;
                }else{
                    if(0 == j){
                        dp[j] = dp[j];
                    }else{
                        dp[j] += dp[j-1];
                    }
                }
            }
        }
        
        return dp[m-1];
    }
}

[LeetCode] 62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

public class Solution {
    public int uniquePaths(int m, int n) {
        if(0 == m || 0 == n)
            return 0;
            
        int[] dp = new int[m];
        
        for(int i = 0; i < m; ++i){
            dp[i] = 1;
        }
        
        for(int i = 1; i < n; ++i){
            for(int j = 1; j < m; ++j){
                dp[j] += dp[j-1];
            }
        }
        
        return dp[m-1];
    }
}

[LeetCode] 61. Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
    
        if(null == head)
            return null;
        
        if(0 == k)
            return head;
        
        int len = 1;
        
        ListNode tail = head;
        while(null != tail.next){
            tail = tail.next;
            ++len;
        }
        
        tail.next = head;
        
        ListNode c = tail;
        
        k %= len;
        k = len - k;
        
        while(k-- > 0){
            c = c.next;
        }
        
       ListNode ret = c.next;
        c.next = null;
        
        return ret;
        
    }
}

[LeetCode] 60. Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

public class Solution {
    public String getPermutation(int n, int k) {
        
        String ret = new String();
        
        if(0 == n)
            return ret;
            
        StringBuilder sb = new StringBuilder();
            
        ArrayList eArr = new ArrayList();
        
        for(int i = 1; i < n+1; ++i){
            eArr.add(i);
        }
        
        int[] pArr = new int[n+1];
        
        pArr[1] = 1;
        
        for(int i = 2; i < n+1; ++i){
            pArr[i] = pArr[i-1]*i;
        }
        
        // Error: i>=0. pArr[0] stored 0. division by 0 error.
        for(int i = n - 1 ; i>=1; --i){
            int pos = (k - 1) / pArr[i];
            sb.append(eArr.get(pos));
            eArr.remove(pos);
            k -= (pos) * pArr[i];
        }
        
        sb.append(eArr.get(0));
        
        return sb.toString();
        
    }
}

[LeetCode] 59. Spiral Matrix II

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 ]
]

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ret = new int[n][n];
        
        int i = 0;
        int j = 0;
        
        int c = 1;
        
        while(n > 1){
            for(int k = 0; k < n-1; ++k){
                ret[i][j++] = c++;
            }
            for(int k = 0; k < n-1; ++k){
                ret[i++][j] = c++;
            }
            for(int k = 0; k < n-1; ++k){
                ret[i][j--] = c++;
            }
            for(int k = 0; k < n-1; ++k){
                ret[i--][j] = c++;
            }
            i++;
            j++;
            n -= 2;
        }
        
        if(1 == n){
            ret[i][j] = c;
        }
        
        return ret;
        
    }
}

[LeetCode] 58. Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.

public class Solution {
    public int lengthOfLastWord(String s) {
        int len = s.length();
        if(0 == len)
            return 0;
            
        int l = 0;
        int r = 0;
        
        int retl = l;
        int retr = r;
        
        for(int i = 0; i < len; ++i){
            if(Character.isLetter(s.charAt(i))){
                r++;
            }else{
                if(l != r){
                    retl = l;
                    retr = r;
                }
                r++;
                l=r;
            }
        }
        
        // Error: You have to judge for the last time, if the sentence is ending with a word.
        if(l != r){
            retl = l;
            retr = r;
        }
        
        return retr-retl;
        
    }
}

[LeetCode] 57. Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List insert(List intervals, Interval newInterval) {
        
        List ret = new ArrayList();
        
        int len = intervals.size();
        
        for(int i = 0; i < len; ++i){
            Interval c = intervals.get(i);
            if(c.start > newInterval.end){
                ret.add(newInterval);
                ret.addAll(intervals.subList(i, len));
                return ret;
            }else if(c.end < newInterval.start){
                ret.add(c);
            }else{
                newInterval.start = Math.min(newInterval.start, c.start);
                newInterval.end = Math.max(newInterval.end, c.end);
            }
        }
        
        ret.add(newInterval);
        return ret;
    }
}

[LeetCode] 56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    
    class IntervalComparator implements Comparator{
        public int compare(Interval a, Interval b){
            return a.start - b.start;
        }
    }
    
    public List merge(List intervals) {
    
        List ret = new ArrayList();
    
        int len = intervals.size();
        
        if(0 == len)
            return ret;
    
        Collections.sort(intervals, new IntervalComparator());
        
        Interval m = intervals.get(0);
        
        for(int i = 1; i < len; ++i){
            Interval c = intervals.get(i);
            if(m.end >= c.start)
            {
                m.end = Math.max(m.end, c.end);
            }else{
                ret.add(m);
                m = c;
            }
        }
        
        ret.add(m);
        
        return ret;
        
    }
}

[LeetCode] 55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Subscribe to see which companies asked this question

public class Solution {
    public boolean canJump(int[] nums) {
        
        int len = nums.length;
        
        if(0 == len || 1 == len)
            return true;
        
        int r = nums[0];
        
        for(int i = 0; i < len; ++i){
            if(i >= r)
                return false;
            r = Math.max(r, i + nums[i] + 1);
            if(r >= len)
                return true;
        }
        
        return true;
        
    }
}

[LeetCode] 54. Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

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

You should return [1,2,3,6,9,8,7,4,5].

public class Solution {
    
    public List spiralOrder(int[][] matrix) {
        
        List res = new ArrayList();
        
        int m = matrix.length;
        if(0 == m)
            return res;
            
        int n = matrix[0].length;
        if(0 == n)
            return res;
            
        int i = 0; 
        int j = 0;
        
        while( m > 1 && n > 1){
            for(int k = 0; k < n -1; k++){
                res.add(matrix[i][j++]);
            }
            for(int k = 0; k < m -1; k++){
                res.add(matrix[i++][j]);
            }
            for(int k = 0; k < n -1; k++){
                res.add(matrix[i][j--]);
            }
            for(int k = 0; k < m -1; k++){
                res.add(matrix[i--][j]);
                
            }
            ++i; 
            ++j;
            m -= 2;
            n -= 2;
        }
        
        if(1 == n && 1 == m){
            res.add(matrix[i][j]);
        }
        
        if(m > 1 && 1 == n){
            for(int k = 0; k < m; ++k){
                res.add(matrix[i++][j]);
            }
        }
        if(n > 1 && 1 == m){
            for(int k = 0; k < n; ++k){
                res.add(matrix[i][j++]);
            }
        }
        return res;
            
    }
    
    
}

[LeetCode] 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

1. DP, but we only need to store adjacent 2 numbers.

public class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if(0 == len)
            return 0;
        
        int pre = nums[0];
        int max = nums[0];
        
        for(int i = 1; i < len; ++i){
            if(pre < 0)
                pre = nums[i];
            else
                pre = nums[i] + pre;
            max = Math.max(max, pre);
        }

        return max;
    }
}

[LeetCode] 52. N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Subscribe to see which companies asked this question

public class Solution {
    
    private boolean checkValid(int[][] board, int n, int x, int y){
        // check valid of a board placement.
        for(int i = 0; i < n; ++i){
            if(1 == board[i][y])
                return false;
            if(1 == board[x][i])
                return false;
            int off = y - i;
            if(x - off >= 0 && x - off < n && 1 == board[x - off][i])
                return false;
            if(x + off >= 0 && x + off < n && 1 == board[x + off][i])
                return false;
        }
        return true;
    }
    
    private void recordRes(int[][] board, int n, List> res){
        
        List sol = new ArrayList();
        for(int i = 0; i < n; ++i){
        StringBuilder sb = new StringBuilder();
            for(int j = 0; j < n; ++j){
                if(1 == board[i][j]){
                    sb.append('Q');
                }
                else{
                    sb.append('.');
                }
            }
        sol.add(sb.toString());
        }
        res.add(sol);
        return;
    }
    
    private void solveNQueensAux(int[][] board, int n, int col, List> res){
         for(int i = 0; i < n; ++i){
            if(checkValid(board, n, i, col)){
                /*
                board[i][col] = 1;
                if(col == n-1){
                    // record res
                    recordRes(board, n, res);
                    // Error: forgot to set the board back before return. Result in only one solution. 
                    board[i][col] = 0;
                    // there is only one solution for the last column.
                    return;
                }
                else{
                    solveNQueensAux(board, n, col+1, res);
                }
                board[i][col] = 0;
                */
                if(col == n-1){
                    board[i][col] = 1;
                    recordRes(board, n, res);
                    board[i][col] = 0;
                    return;
                }
                else{
                    // surrounding set and unset operation with recursive call is always a better idea.
                    board[i][col] = 1;
                    solveNQueensAux(board, n, col+1, res);
                    board[i][col] = 0;
                }
           
            }
         }
         
         return;
        
    }
    
    public int totalNQueens(int n) {
        List> res = new ArrayList>();
        if(0 == n)
            return 0;
        
        int[][] board = new int[n][n];
        
        solveNQueensAux(board, n, 0, res);
        
        return res.size();
       
    }
    
}

[LeetCode] 51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

public class Solution {
    
    private boolean checkValid(int[][] board, int n, int x, int y){
        // check valid of a board placement.
        for(int i = 0; i < n; ++i){
            if(1 == board[i][y])
                return false;
            if(1 == board[x][i])
                return false;
            int off = y - i;
            if(x - off >= 0 && x - off < n && 1 == board[x - off][i])
                return false;
            if(x + off >= 0 && x + off < n && 1 == board[x + off][i])
                return false;
        }
        return true;
    }
    
    private void recordRes(int[][] board, int n, List> res){
        
        List sol = new ArrayList();
        for(int i = 0; i < n; ++i){
        StringBuilder sb = new StringBuilder();
            for(int j = 0; j < n; ++j){
                if(1 == board[i][j]){
                    sb.append('Q');
                }
                else{
                    sb.append('.');
                }
            }
        sol.add(sb.toString());
        }
        res.add(sol);
        return;
    }
    
    private void solveNQueensAux(int[][] board, int n, int col, List> res){
         for(int i = 0; i < n; ++i){
            if(checkValid(board, n, i, col)){
                /*
                board[i][col] = 1;
                if(col == n-1){
                    // record res
                    recordRes(board, n, res);
                    // Error: forgot to set the board back before return. Result in only one solution. 
                    board[i][col] = 0;
                    // there is only one solution for the last column.
                    return;
                }
                else{
                    solveNQueensAux(board, n, col+1, res);
                }
                board[i][col] = 0;
                */
                if(col == n-1){
                    board[i][col] = 1;
                    recordRes(board, n, res);
                    board[i][col] = 0;
                    return;
                }
                else{
                    // surrounding set and unset operation with recursive call is always a better idea.
                    board[i][col] = 1;
                    solveNQueensAux(board, n, col+1, res);
                    board[i][col] = 0;
                }
           
            }
         }
         
         return;
        
    }
    
    public List> solveNQueens(int n) {
        List> res = new ArrayList>();
        if(0 == n)
            return res;
        
        int[][] board = new int[n][n];
        
        solveNQueensAux(board, n, 0, res);
        
        return res;
       
    }
}

[Java] 2D Array ND Array Related

1. Create a 2D array with known

Try the following:

int[][] multi = new int[5][10];

... which is a short hand for something like this:

int[][] multi = new int[5][];
multi[0] = new int[10];
multi[1] = new int[10];
multi[2] = new int[10];
multi[3] = new int[10];
multi[4] = new int[10];

[LeetCode ] 50. Pow(x, n)

Implement pow(x, n).

Subscribe to see which companies asked this question

public class Solution {
    public double myPow(double x, int n) {
        if(0 == n)
            return 1;
        if(0 == x)
            return 0;
        if(1 == x)
            return 1;
        if(1 == n)
            return x;
        
        if(n > 0)
            return myPow(x*x, n/2)*myPow(x, n%2);
        else{
            // Error: failed on negative number without this statement 
            return 1/(myPow(x*x, Math.abs(n)/2)*myPow(x, Math.abs(n)%2));
        }
    }
}

[Deep Learning] Notes for stanford_dl_ex

1. CNN

Solutions are from kloudkl/stanford_dl_ex-solutions,
https://github.com/kloudkl/stanford_dl_ex-solutions

1.1 cnnTrain.m

CNN training main,

function cnnTrain(options)
%% Convolution Neural Network Exercise

%  Instructions
%  ------------
%
%  This file contains code that helps you get started in building a single.
%  layer convolutional nerual network. In this exercise, you will only
%  need to modify cnnCost.m and cnnminFuncSGD.m. You will not need to
%  modify this file.

%%======================================================================
%% STEP 0: Initialize Parameters and Load Data
%  Here we initialize some parameters used for the exercise.

// Load default parameter if no parameter is passed???
if nargin < 1
    learning_rate_schedule = 'half_per_epoch';
end

USE_GPU = 0;
dataset = 'mnist';
dataset = 'svhn';

% Configuration
imageDim = 28;
numClasses = 10;  % Number of classes (MNIST images fall into 10 classes)
// what is filter size ???
filterDim = 9;    % Filter size for conv layer
// why do we need number of filters???
numFilters = 20;   % Number of filters for conv layer
// what is the definition of pooling dimension???
poolDim = 2;      % Pooling dimension, (should divide imageDim-filterDim+1)

%% Load images and labels
switch dataset
    case 'mnist'
        % Load MNIST Train
        addpath ../common/;
        images = loadMNISTImages('../common/train-images-idx3-ubyte');
        images = reshape(images,imageDim,imageDim,[]);
        labels = loadMNISTLabels('../common/train-labels-idx1-ubyte');
        labels(labels==0) = 10; % Remap 0 to 10
        
        % mean normalization
// for MNIST, image is 28*28*6000, data_mean is 28*28
        data_mean = mean(images, 3);
// for MNIST, data_std is 28 * 28
        data_std = std(images, 0, 3);
// preparing for bsxfun() ??? 
        data_std(data_std == 0) = 1;
// subtract image with data mean
        images = bsxfun(@minus, images, data_mean);
    case 'svhn'
        % Load SVHN Train
        load('../common/svhh_train_32_32_zeromean_mergeChannel');
        imageDim = 32;
end

% Sampling the data
numImages = size(images, 3);
% numImages = 60000;
% numImages = 10000;
// 1:min(numImages, end) index through smaller of numImages and end ???
images = images(:, :, 1:min(numImages, end));
labels = labels(1:min(numImages, end), :);

% Initialize Parameters
// init parameters for cnn
theta = cnnInitParams(imageDim,filterDim,numFilters,poolDim,numClasses);

% % Transfer to GPU
if USE_GPU
    device = gpuDevice(1);
    device.reset();
    images = gpuArray(images);
    labels = gpuArray(labels);
    theta = gpuArray(theta);
end

%%======================================================================
%% STEP 1: Implement convNet Objective
%  Implement the function cnnCost.m.

%%======================================================================
%% STEP 2: Gradient Check
%  Use the file computeNumericalGradient.m to check the gradient
%  calculation for your cnnCost.m function.  You may need to add the
%  appropriate path or copy the file to this directory.

DEBUG = false;  % set this to true to check gradient
% DEBUG = true;
if DEBUG
    % To speed up gradient checking, we will use a reduced network and
    % a debugging data set
    db_numFilters = 2;
    db_filterDim = 9;
    switch dataset
        case 'mnist'
            db_poolDim = 5;
        case 'svhn'
            db_poolDim = 6;
    end
    numDebugImages = 11; % better to be different from the numClasses
    db_images = images(:,:,1:numDebugImages);
    db_labels = labels(1:numDebugImages);
    db_theta = cnnInitParams(imageDim,db_filterDim,db_numFilters,...
        db_poolDim,numClasses);
    
    [cost grad] = cnnCost(db_theta,db_images,db_labels,numClasses,...
        db_filterDim,db_numFilters,db_poolDim);
    
    
    % Check gradients
    numGrad = computeNumericalGradient( @(x) cnnCost(x,db_images,...
        db_labels,numClasses,db_filterDim,...
        db_numFilters,db_poolDim), db_theta);
    
    % Use this to visually compare the gradients side by side
    num = numel(grad);
    for n = 1:num
        ratio = abs(grad(n) - numGrad(n)) / (abs(grad(n)) + 1e-6);
        if ratio > 1e-4
            fprintf('%d %10f %10f %10f\n', n, grad(n), numGrad(n), ratio);
        end
    end
    % Should be small. In our implementation, these values are usually
    % less than 1e-9.
    diff = norm(numGrad-grad)/norm(numGrad+grad)
    assert(diff < 1e-9,...
        'Difference too large. Check your gradient computation again');
    return;
end

%%======================================================================
%% STEP 4: Test
%  Test the performance of the trained model using the MNIST test set. Your
%  accuracy should be above 97% after 3 epochs of training

switch dataset
    case 'mnist'
        % Load mnist test
        testImages = loadMNISTImages('../common/t10k-images-idx3-ubyte');
        testImages = reshape(testImages,imageDim,imageDim,[]);
        testLabels = loadMNISTLabels('../common/t10k-labels-idx1-ubyte');
        testLabels(testLabels==0) = 10; % Remap 0 to 10
        
        testImages = bsxfun(@minus, testImages, data_mean);
    case 'svhn'
        % % Load SVHN test
        test = load('../common/svhh_test_32_32_zeromean_mergeChannel');
        testImages = test.images;
        testLabels = test.labels;
end

% % Transfer to GPU
if USE_GPU
    testImages = gpuArray(testImages);
    testLabels = gpuArray(testLabels);
end

%% STEP 3: Learn Parameters
%  Implement minFuncSGD.m, then train the model.

options.epochs = 3;
options.minibatch = 256;
options.alpha = 1e-1;
options.momentum = .95;

opttheta = minFuncSGD(@(x,y,z) cnnCost(x, y, z, numClasses, filterDim, ...
    numFilters, poolDim), theta, images, labels, options, testImages, ...
    testLabels, numClasses, filterDim, numFilters, poolDim);

%%======================================================================
%% STEP 4: Test

% [~, cost, preds]=cnnCost(opttheta, testImages, testLabels, numClasses, ...
%     filterDim, numFilters, poolDim, true);
% 
% acc = 100 * sum(preds==testLabels) / length(preds);
% 
% % Accuracy should be around 97.4% after 3 epochs
% fprintf('Accuracy is %f\n',acc);

2. cnnInitParams

function theta = cnnInitParams(imageDim,filterDim,numFilters,...
                                poolDim,numClasses)
% Initialize parameters for a single layer convolutional neural
% network followed by a softmax layer.
%                            
% Parameters:
%  imageDim   -  height/width of image
%  filterDim  -  dimension of convolutional filter                            
%  numFilters -  number of convolutional filters
%  poolDim    -  dimension of pooling area
%  numClasses -  number of classes to predict
%
%
% Returns:
%  theta      -  unrolled parameter vector with initialized weights

%% Initialize parameters randomly based on layer sizes.
assert(filterDim < imageDim,'filterDim must be less that imageDim');

// imageDim = 28, filterDim = 9, the outDim is the dimension of the filter square (map), in this case, 20 x 20 = 400 filters.
outDim = imageDim - filterDim + 1; % dimension of convolved image

% assume outDim is multiple of poolDim
// if this is asserted, it means this is no overlapping between pooling?
assert(mod(outDim, poolDim)==0,...
       'poolDim must divide imageDim - filterDim + 1');

// number of filters is the size of different filters that applied on a image. Each filter perform different filtering function.
Wc = 1e-1*randn(filterDim,filterDim,numFilters);

// from filter layer to pooling layer. 
outDim = outDim/poolDim;
hiddenSize = outDim^2*numFilters;

% we'll choose weights uniformly from the interval [-r, r]
r  = sqrt(6) / sqrt(numClasses+hiddenSize+1);
Wd = rand(numClasses, hiddenSize) * 2 * r - r;

bc = zeros(numFilters, 1);
bd = zeros(numClasses, 1);

% Convert weights and bias gradients to the vector form.
% This step will "unroll" (flatten and concatenate together) all 
% your parameters into a vector, which can then be used with minFunc. 
theta = [Wc(:) ; Wd(:) ; bc(:) ; bd(:)];

end

[LeetCode] 49. Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

public class Solution {
    public List> groupAnagrams(String[] strs) {
        
        List> ret = new ArrayList>();
        
        int len = strs.length;
        
        if(0 == len)
            return ret;
            
        Map> sMap = new HashMap>();
            
        //for(String s : strs){
        for(int i = 0; i < len; ++i){
            String s = strs[i];
            char[] sArr = s.toCharArray();
            Arrays.sort(sArr);
            String sSorted = new String(sArr);
            
            if(!sMap.containsKey(sSorted)){
                sMap.put(sSorted, new ArrayList());
            }
            sMap.get(sSorted).add(i);
        }
        
        for(String key : sMap.keySet()){
            List rEle = new ArrayList();
            List iList = sMap.get(key);
            for(Integer i : iList){
                rEle.add(strs[i]);
            }
            Collections.sort(rEle);
            ret.add(rEle);
        }
        
        return ret;
    }
}

[LeetCode] 48. Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

public class Solution {
    
    private void swap(int[][] matrix, int i, int j, int x, int y){
        
        // Error: A very silly mistake i != j || x != y
        if(i != x || j != y){
            // Error: Again, we have to judge identity if using bitwise method.
            matrix[i][j] = matrix[i][j] ^ matrix[x][y];
            matrix[x][y] = matrix[i][j] ^ matrix[x][y];
            matrix[i][j] = matrix[i][j] ^ matrix[x][y];
        }
    }
    
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        
        if(0 == n)
            return;
            
        for(int i = 0; i < (n+1)/2; ++i)
        // Error: Notice for n is odd, the rotation is not a square. 
        for(int j = 0; j < n/2; ++j){
            int si = j;
            int sj = n -1 -i;
            swap(matrix, i, j, si, sj);
            si = n - 1 - i;
            sj = n - 1 - j;
            swap(matrix, i, j, si, sj);
            si = n - 1 - j;
            sj = i;
            swap(matrix, i, j, si, sj);
        }
        return;
    }
}

[LeetCode] 46. Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

public class Solution {
    
    private void swap(Integer[] nums, int i, int j){
        
        // Error: Note, i mustn't = j, or it clear the integer with bitwise method.
        if(i == j)
            return;
        
        nums[i] = nums[i]^nums[j];
        nums[j] = nums[i]^nums[j];
        nums[i] = nums[i]^nums[j];
        return;
        
    }
    
    public void permuteAux(Integer[] nums, int index, List> ret){
        
        int len = nums.length;
        
        if(index == len){
            ArrayList t = new ArrayList(Arrays.asList(nums));
            ret.add(t);
            return;
        }
        

        
        for(int i = index; i < len; ++i){
            swap(nums, index, i);
            permuteAux(nums, index+1, ret);
            swap(nums, index, i);
        }
        
    }
    
    
    public List> permute(int[] nums) {
        
        
        List> ret = new ArrayList>();
        
        int len = nums.length;
        
        if(0 == len)
            return ret;
            
        Integer[] iNums = new Integer[nums.length];
        
        for(int i = 0; i < len; ++i){
            iNums[i] = nums[i];
        }
        
        permuteAux(iNums, 0, ret);
            
        return ret;
        
    }
}

[LeetCode] 43. Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note:

• The numbers can be arbitrarily large and are non-negative.
• Converting the input string to integer is NOT allowed.
• You should NOT use internal library such as BigInteger.

public class Solution {


    public String multiply(String num1, String num2) {
        
        String ret = new String();
        int len1 = num1.length();
        int len2 = num2.length();
        if(0 == len1 || 0 == len2)
            return ret;
        
        String rNum1 = new StringBuffer(num1).reverse().toString();
        String rNum2 = new StringBuffer(num2).reverse().toString();
        
        // At first, was trying to store everything in string operation as well. Quite complicated.
        int[] res = new int[len1 + len2 + 1];
        
        for(int i = 0; i != len2; ++i){
            
            int vi = rNum2.charAt(i) - '0';
            
            for(int j = 0; j != len1; ++j){
                
                res[i+j] += (rNum1.charAt(j) - '0') * vi;
                
            }
            
        }
        
        int carry = 0;
        
        for(int k = 0; k != len1 + len2 +1; ++k){
            
            res[k] += carry;
            carry = res[k] / 10;
            res[k] = res[k] % 10;

        }
        
        StringBuilder sb = new StringBuilder();
        
        int k = len1 + len2;
        
        while(k >=0){
            if(0 == res[k])
                --k;
            else
                break;
        }
        
        while(k >= 0){
            sb.append(res[k--]);
        }
        
        if(sb.toString().isEmpty()){
            return new String("0");
        }
        
        return sb.toString();
        
    }
}

[log] Brother 2270DW Reset Replace Toner Error [Reset Toner Sensor]

Please do the following steps to reset the toner sensor.

– Open the front cover and leave open while completing the following steps.
– Turn the printer off.
– Hold the ‘go’ button while turning the printer on. All lights should be on.
– Release the ‘go’ button (or “start’ button).
– Press the ‘go’ button (or “start’ button) 2 times.
– Pause. All panel lights should be on.
– Press the ‘go’ button (or “start’ button) 5 times.
The toner light should be off. (error may be flashing)
The paper light should be on or flashing.
– Close cover. The ready light should be the only light on.

[Log] Issue Installing Caffe on Ubuntu 14.04

Few issues.

1. Might need a reboot after installing the Cuda driver? CPU installation works fine. For GPU installation, make all, make test works fine, make testrun reports error. Might also because tried to install Cuda 6.5 in the process.

remember to add

export CUDA_HOME=/usr/local/cuda-7.5
export LD_LIBRARY_PATH=${CUDA_HOME}/lib64

PATH=${CUDA_HOME}/bin:${PATH}
export PATH

into .bashrc

2. Need the cudnn.h head file in /usr/include for CuDNN acceleration. Needed by cudnn.hpp.
Need the *.so file in lib64 to /lib64 folder

https://developer.nvidia.com/cudnn

3. CuDNN v5 is not working, few interface discrepancies were found. v4 works fine.

4. Test with all configurations works fine.

CPU Only

[----------] Global test environment tear-down

[==========] 1056 tests from 146 test cases ran. (39277 ms total)

[  PASSED  ] 1056 tests.

CuNN

[----------] Global test environment tear-down

[==========] 2003 tests from 269 test cases ran. (266570 ms total)

[  PASSED  ] 2003 tests.

GPU 

[----------] Global test environment tear-down

[==========] 1943 tests from 259 test cases ran. (244820 ms total)

[  PASSED  ] 1943 tests.

[Log] Issues Installing Ubuntu 14.04

0. Don't use UEFI for usb boot.

Won't recognize windows system.

1. Network. DHCP not working.

remove

auto eth0
iface eth0 inet dhcp

1.5 SSH auto start

sudo update-rc.d ssh defaults

2.  VNC Server

sudo apt-get update

This updates the package list for apt.

---

Then you'll need to install the Gnome components using Software Center:

Or Using Terminal:

sudo apt-get install gnome-core

---

To install VNC server using Software Center:

Or Using Terminal:

sudo apt-get install vnc4server

VNC view gray screen

edit ~/.vnc/xstartup

#!/bin/sh

def

export XKL_XMODMAP_DISABLE=1

unset SESSION_MANAGER

unset DBUS_SESSION_BUS_ADDRESS

gnome-panel &

gnome-settings-daemon &

metacity &

nautilus &

gnome-terminal &

3. Start VNC

vnc4server -geometry 1280x1024 -geometry 1024x768 -geometry 800x600

switch resolution

xrandr -s 0

4. Mount Windows Partitions.

fdisk -l

sudo mount -t ntfs -o nls=utf8,umask=0222 /dev/hdb1 /media/c

5. Internet Down for strange reason again.

Seems like it is a network manager bug

5.1. Purge network manager

Gnome:

sudo apt-get remove --purge network-manager-gnome network-manager

KDE:

sudo apt-get remove --purge knetworkmanager network-manager

reboot required. ifdown ifup won't initi the network.

5.2 Setup DHCP.  and name server
/etc/network/interfaces

auto lo
iface lo inet loopback

auto eth0
iface eth0 inet dhcp

5.3 Setup DNS nameserver
/etc/resolv.conf
nameserver 128.223.6.7
nameserver 8.8.8.8
nameserver 8.8.8.4

OR static

auto eth0
iface eth0 inet static
address 10.0.0.100
netmask 255.255.255.0
gateway 10.0.0.1

6. Command Not Working in 14.04

/etc/init.d/networking restart
sudo ifconfig eth0 down(up)

Use

sudo ifdown (ifup) eth0


7. Skip Login Screen.

source.
http://askubuntu.com/questions/148717/how-do-i-boot-into-the-console-and-then-launch-the-ubuntu-desktop-from-it

down voteaccepted

To return to the login screen Press Ctrl+Alt+F7 to return to the login screen. You can exit your terminal session on tty1 by typing exit before you do that. Doing startx -- :1 will start another X session under terminal tty1, logging you in directly (use :2, etc. for even more displays). Note that logging into multiple sessions as the same user is not recommended and could lead to system instability. To skip the login screen completely, boot into the console and then start the GUI, you must modify GRUB: sudo nano /etc/default/grub Change line GRUB_CMDLINE_LINUX_DEFAULT="quiet splash" to GRUB_CMDLINE_LINUX_DEFAULT="text" Ctrl-X, press Y and then Enter to save and exit. sudo update-grub Reboot and you should come up directly in tty1 -- no need to press Ctrl-Alt-F1. Login, and then startx to boot into the default desktop, or unity for Unity unity-2d-shell for Unity 2D gnome-shell for Gnome sudo service lightdm start to get the login screen (if you fix it :)

7. Ethernet problem

Might because of the intel network driver.
Last working setup
auto lo eth0
iface lo inet loopback
iface eth0 inet dhcp

Reboot doesn't work?
Must be shutdown at start?

OK. The answer is the intel ethernet driver. (It is strange sometimes it can work even without driver...)

From the logs it seems to me you have managed to update the driver from version 2.3.2-k to 3.2.4.2-NAPI.

I fixed my Intel NUC non working ethernet by:

• download the driver from https://downloadcenter.intel.com/download/15817, currently 3.2.4.2 (as shown in lshw -C above)
• make install in the src folder
• rmmod e1000e
• modprobe e1000e
• and to make the new driver survive a reboot update-initramfs -u

This I have to repeat at every kernel update, since kernel updates still (3.13.0-63) contain the old driver version 2.3.2-k, which does not work with my Intel NUC.

http://www.intel.com/content/www/us/en/support/network-and-i-o/ethernet-products/000005480.html?wapkw=(itanium)

8. How to prevent “Write Failed: broken pipe” on SSH connection?

needed to have rw for user only permissions on config. This fixed it.

chmod 600 ~/.ssh/config