leonw007

// assume n>m

//case 1
for(int i=0; i< n ; i++) {
  someOperation(); // this line takes O(n) time 
}

//case 2     
for(int i=0; i< n ; i++) {
    if (i < (n/m) ) {

leonw007

package ch4;

public class PathSum {
	
	
	public static void main(String args[] ) {
		TreeNode n3 = new TreeNode(3, null, null);
		TreeNode n1 = new TreeNode(1, null, null);
		TreeNode n2 = new TreeNode(5, null, null);
		TreeNode n10 = new TreeNode(10, null, null);

leonw007

public class PathSum {
	
	public static void main(String args[] ) {
		TreeNode n3 = new TreeNode(3, null, null);
		TreeNode n1 = new TreeNode(1, null, null);
		TreeNode n2 = new TreeNode(5, null, null);
		TreeNode n10 = new TreeNode(10, null, null);
		TreeNode n4 = new TreeNode(4, n3, null);
		TreeNode n6 = new TreeNode(6, n4, n1);
		TreeNode n9 = new TreeNode(9, null, n10);

leonw007

package ch1;


/*
1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row
and column are set to 0.

* First, we at least need two loops, one for finding out the rows and columns containing 0,
* the other one to set 0. We cannot do it in one loop, because it will influence result.
* We set the row and column which contain 0, true.

leonw007

package ch1;

/*
1.6 Given an image represented by an NxN matrix, where each pixel in the image is
4 bytes, write a method to rotate the image by 90 degrees. Can you do this in
place?

* It would be easier to think if you can write down an example first.
* input: 
* 1  2  3  4 

leonw007

package ch1;
/*
1.5 Implement a method to perform basic string compression using the counts
of repeated characters. For example, the string aabcccccaaa would become
a2blc5a3. If the "compressed" string would not become smaller than the original
string, your method should return the original string.

* When we want to add something to a string constantly and without knowing the total length,
* StringBuilder is a good choice.
* We check whether the adjacent elements are same. if so, we increase count number; if not, we output the count number,

leonw007

package ch1;

/*
1.4 Write a method to replace all spaces in a string with'%20'. You may assume that
the string has sufficient space at the end of the string to hold the additional
characters, and that you are given the "true" length of the string. (Note: if implementing
in Java, please use a character array so that you can perform this operation
in place.)

* The core condition is that we have sufficient space at the end.

leonw007

package ch1;

/*
1.3 Given two strings, write a method to decide if one is a permutation of the other.

* The idea is quite similar to the first question
* We use the ASCII code to count how many times each character appears in the first string
* Then We reduce one in the count for each character appears in the second string
* if we get any count element less than 0, it means difference

leonw007

package ch1;

/*
1.2 Implement a function void reverse(char* str) in C or C++ which reverses a nullterminated string.

* We used a temp variable to exchange the i character with leng-1-i character
* One way to do this is our method
* char[] chars = str.toCharArray();
* String newStr = String.valueOf(chars);
* 

leonw007

package ch1;

/*
1.1 Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?
 
 *We assume that it is ASCII string. It means we can use at most 256 number to represent all characters
 *I set a int array for all possible characters. Initial value are all 0.
 *When we scan one character from the string, we add its value by 1.
 *When we detect a character is 1, it means it has appeared. Then we return false