https://docs.google.com/document/d/1bJrzcsm7YjN_uD-qx9MOaHf6BHw8wnCZptxcwkF4pjU/edit
Thursday, August 18, 2016
Thursday, August 11, 2016
[LeetCode] Programming Bug Note
1. Delete Element In Unordered ArrayList, Vectors
a. Say delete 3 from 1 3 5 7 9, we replace 3 with 9 and erase 9, resulting in 1 9 5 79
But in the Leetcode problem Insert 380 381 Delete GetRandom O(1), when the index of the removed element, 1 in example 1, and 4 in example 2 is going to be used again in the future. Index 4 is actually out of bound in the second example.
In this case, operation sequence matters, it is infact two different types of operation sequence, while the result coincidents in some cases.
a. Say delete 3 from 1 3 5 7 9, we replace 3 with 9 and erase 9, resulting in 1 9 5 7
But in the Leetcode problem Insert 380 381 Delete GetRandom O(1), when the index of the removed element, 1 in example 1, and 4 in example 2 is going to be used again in the future. Index 4 is actually out of bound in the second example.
In this case, operation sequence matters, it is infact two different types of operation sequence, while the result coincidents in some cases.
Tuesday, August 9, 2016
[Test] Test Cases
关于TC的问题:
1. 分类 (classification)
unit test -> functional test -> integration test -> scenario test
越往右边TC的数目应该越少一些
2. 设计TC，还是要分类
1) positive TC - happy path
2) negative TC - 0, NULL, exception, overflow/underflow,
3) corner TC
3. 其他TC(基本就是靠嘴巴说)
1) Performance
2) Scalability
3) Load
4) Stress
5) Code coverage
6) Localization
7) Internationalization
8) Security
1. 分类 (classification)
unit test -> functional test -> integration test -> scenario test
越往右边TC的数目应该越少一些
2. 设计TC，还是要分类
1) positive TC - happy path
2) negative TC - 0, NULL, exception, overflow/underflow,
3) corner TC
3. 其他TC(基本就是靠嘴巴说)
1) Performance
2) Scalability
3) Load
4) Stress
5) Code coverage
6) Localization
7) Internationalization
8) Security
Monday, June 20, 2016
[LeetCode] 145. Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree
Given binary tree
{1,#,2,3}, 1
\
2
/
3
return
[3,2,1].My Code is too long...
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
/* Magically, I implemented the morris traversal post order traversal version
private void swap(List res, int i, int j){
if(i == j)
return;
res.set( i, res.get(i) ^ res.get(j) );
res.set( j, res.get(i) ^ res.get(j) );
res.set( i, res.get(i) ^ res.get(j) );
}
private void reverseArrayList(List res, int i, int j){
while(i < j){
swap(res, i++, j--);
}
}
public List postorderTraversal(TreeNode root) {
TreeNode d = new TreeNode(-1);
// Error: forgot to put root to d.left.....
d.left = root;
List res = new ArrayList();
TreeNode c = d;
while(null != c){
if(null == c.left){
c = c.right;
continue;
}else{
TreeNode n = c.left;
// Error: null != n && c != n
// We shouldn't traverse n to c, should be before c.
while(null != n.right && c != n.right){
n = n.right;
}
if(null == n.right){
n.right = c;
c = c.left;
}else{
// c == n.right
// add the last element of left.right subtree
//res.add(n.val);
// add the last element of left subtree
// Error: There are two cases of n, n could be a left child node and right child node.
//if(c.left != n)
// res.add(c.left.val);
// Error: the above ones are wrong
// When tree were returned from the rightmost child, it will print a series of root node. following the return of the subtrees.
n = c.left;
int count = 0;
//Error: while( c != n.right), this time it is
// In this case, last element in this list is not added in.
while(c != n.right){
//printPathReverse(root.left, pre);
//we need a way to print the path reversely to do that.
//One way is to reverse this path like we reverse linklist.
res.add(n.val);
n = n.right;
count++;
}
res.add(n.val);
count++;
if(count > 1)
reverseArrayList(res, res.size() - count, res.size()-1);
n.right = null;
c = c.right;
}
}
// we can not put d != c in while condition, because it is initial condition
// Error: we don't need to add this here,
// we need this loop when c = d to add c.left child into result.
// Since d has no right child, and d is not a children of anybody, it will never be printed out
//if(c == d)
// return res;
}
return res;
}
*/
/* The second implementation is based on one stack, which stores all elements on the path from root to current node,
all we need to judge is the current node c is the left or right child of the top element of the stack.
if it is left child, we go right. (note, if it has no right child, we keep pop stack, i.e. the same behavior as it is right child)
if it is right child, we keep pop stack
public List postorderTraversal(TreeNode root) {
List res = new ArrayList();
if(null == root)
return res;
Stack st = new Stack();
TreeNode c = root;
while(true){
// null == c is not going to work anymore, we don't know if null is left or right.
if(null == c.left && null == c.right){
st.push(c);
while(!st.empty()){
c = st.pop();
res.add(c.val);
// Error: st.empty() should resides here.
if(st.empty())
return res;
TreeNode r = st.peek();
// Note: The same operation always hold for
// 1. c is the left child of r, and r.right is null
// 2. c is the right chiild of r.
// In both case, we track back to the path towards root.
// Therefore, when c is left child of r, and r.right is not null
// we loop into r.right
if(c == r.left && null != r.right){
c = r.right;
break;
}
}
}else if(null == c.left){
st.push(c);
c = c.right;
}else{
st.push(c);
c = c.left;
}
}
}
*/
// The third implementation is based on a previous node recorder to keep track of the direction of traversal flow.
// We need loop enviroment to maintain a clean program
// Without loop enviroment, there might be many conditional statements.
// This is the version we seperate the top of stack and c, i.e. top of stack is always one layer above c.
public List postorderTraversal(TreeNode root) {
List res = new ArrayList();
if(null == root)
return res;
TreeNode c = root;
TreeNode pre = null;
Stack st = new Stack();
while(true){
//System.out.println("c.val = " + c.val);
//System.out.println("pre.val = " + (null == pre? -1 : pre.val) );
//System.out.println("size = " + st.size());
if(null == pre || pre.left == c || pre.right == c){
// Moving downward, in this case, we try to keep dig down
if(null != c.left){
st.push(c);
pre = c;
c = c.left;
}else if(null != c.right){
st.push(c);
pre = c;
c = c.right;
}else{
pre = c;
if(st.empty()){
System.out.println("empty");
res.add(c.val);
return res;
}else{
c = st.pop();
}
}
}else{
// Moving upward
res.add(pre.val);
if(pre == c.right || (pre == c.left && null == c.right) ){
//System.out.println("Up");
pre = c;
if(st.empty()){
System.out.println("empty2");
res.add(c.val);
return res;
}else{
c = st.pop();
}
}else{
// pre == c.left
pre = c;
st.push(c);
c = c.right;
}
}
}
}
}
Saturday, May 14, 2016
[Language] Playing with protocol buffer
- Install Protocal Buffer
- Please read the readmes. Running "make install" in the root directory installs the C++ libraries only. You need to install the Java and Python versions separately by following the instructions in the corresponding directories.
- https://groups.google.com/forum/#!topic/protobuf/60-OFrBXlAE
- How to start from protocol buffer
- Check example code from source code package.
- https://github.com/google/protobuf/tree/master/examples
- Including source for java, c++, and python
- Examples
- CPP
- protoc_middleman: addressbook.proto
- protoc --cpp_out=. --java_out=. --python_out=. addressbook.proto
- @touch protoc_middleman
- protoc_middleman_go: addressbook.proto
- mkdir tutorial # make directory for go package
- protoc --go_out=tutorial addressbook.proto
- @touch protoc_middleman_go
- add_person_cpp: add_person.cc protoc_middleman
- pkg-config --cflags protobuf # fails if protobuf is not installed
- c++ add_person.cc addressbook.pb.cc -o add_person_cpp `pkg-config --cflags --libs protobuf`
- pkg-config --cflags --libs protobuf
- pkg-config - Return metainformation about installed libraries
- The pkg-config program is used to retrieve information about installed libraries in
- the system. It is typically used to compile and link against one or more libraries.
- Here is a typical usage scenario in a Makefile:
- program: program.c
- cc program.c 'pkg-config --cflags --libs gnomeui'
- `pkg-config --cflags --libs protobuf ` returns
- -lprotobuf -lz -lpthread on centos
- -pthread -pthread -lprotobuf -lpthread on ubuntu 14.04
- "Package protobuf was not found in the pkg-config search path." if it is not installed
- Generated:
- add_person_cpp
- Run this file, saved it to an address book following prompt
- File looks like something like this
- list_people_cpp
- Run this file, returned with:
- Person ID: 1
- Name: Charles
- E-mail address: charles@gmail.com
- Home phone #: 541 346 1380
- Python
- Error： ImportError: No module named google.protobuf
- sudo pip install protobuf
- Java
- make Error: package com.google.protobuf does not exist
- need protobuf-java-*.jar
[Algorithm] Union Find Applications
- Kruskal Algorithm Minimal Spanning Tree
- Greedy Algorithm, sort all edges.
- Initialize each node as a set.
- Start from the smallest edge, union if they are not in the same set.
- Check Loop of Undirected Graph
- Check connection in undirected graph
- Tarjan's off-line lowest common ancestors algorithm
- Offline algorithm. All queries know in advance
- For tree with n node and m queries. We have O(n + m) running time.
- Request (u, v) is answered when u is visited, v is the current visiting node. or vice versa.
- https://gist.github.com/caot/696fb3d762af0d2340c1
- Code
- The basic idea is in infact DFS
- Recursive DFS travels from all the way from bottom to up, left to right.
- A node is marked as black if all its children are visited (marked as black)
- Black means, in query Ancester(u, v), if u is marked as black, the ancester pointer is pointed to the right place ( right place = exacted the common ancestor of v)
- The property of 3 is guaranteed by the nature of DFS.
- HDU-1213 How many tables
- Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers. One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table. For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class TarjanOfflineLCA {
void LCA(Node u) {
MakeSet(u);
Find(u).ancestor = u;
for (Node v : u.children()) {
LCA(v);
Union(u, v);
Find(u).ancestor = u;
}
u.colour = Node.black;
Node v;
for (Pair uv : P.pair()) {
u = uv.u();
v = uv.v();
if (v.colour == Node.black
&& u != null && v != null
&& Find(u) == Find(v) // required, but algorithm [3th Ed. p584] doesn't have it.
) {
System.out.println("Tarjan's Lowest Common Ancestor of {" + u.data
+ ", " + v.data + "}: " + Find(v).ancestor.data);
}
}
}
Wednesday, May 11, 2016
[Java] Parsing Char String Integer Double
char / Character
char c = '5';
To Integer
To Double
Double / double
double d = 1.0;
Double D = 1.0;
To Integer
int / Integer
To Char
Integer.toString(i).charAt(0)
Generate char according to it's index
(char)('A' + i)
(char)('a' + i)
'A' + i and 'a' + i in java are ascii integers, need (char) to convert back to char.
To String
Integer.toString(i);
String
String s1 = '500';
String s2 = "5.0".
To Integer
To Double
char c = '5';
To Integer
- Character.getNumericValue(c)
- int i = c - '0';
To Double
- double d = (double) (c - '0');
Character c = '5';
- Convert to char using c.charValue();
Double / double
double d = 1.0;
Double D = 1.0;
To Integer
- Integer i = D.intValue();
- int i = (int)d;
int / Integer
To Char
Integer.toString(i).charAt(0)
Generate char according to it's index
(char)('A' + i)
(char)('a' + i)
'A' + i and 'a' + i in java are ascii integers, need (char) to convert back to char.
To String
Integer.toString(i);
String
String s1 = '500';
String s2 = "5.0".
To Integer
- Integer.parseInt(s1);
To Double
- Double.praseDouble(s2);
Monday, May 9, 2016
[Deep Learning] Caffe Tutorial Illustrated
Caffe Tutorial Illustrated
1. Concepts
1.1 Blob
a. Caffe stores, communicates, and manipulates the information as blobs
b. The blob is the standard array and unified memory interface for the framework.
c. The layer comes next as the foundation of both model and computation.
d. The net follows as the collection and connection of layers.
e. The details of blob describe how information is stored and communicated in and across layers and nets.
Thursday, April 28, 2016
[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];
}
}
Wednesday, April 27, 2016
[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
return
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):
We get the following sequence (ie, for n = 3):
"123""132""213""231""312""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 =
You should return the following matrix:Given n =
3,[ [ 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 =
return
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
Given intervals
[1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given
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
return
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;
}
}
Tuesday, April 26, 2016
[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 =
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:
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
the contiguous subarray
1. DP, but we only need to store adjacent 2 numbers.[−2,1,−3,4,−1,2,1,−5,4],the contiguous subarray
[4,−1,2,1] has the largest sum = 6.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:
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,
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:
Return:
["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?
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;
}
}
Subscribe to:
Posts (Atom)