Thursday, March 13, 2014

Merge Two Sorted Lists

http://oj.leetcode.com/problems/merge-two-sorted-lists/
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

This problem is similar to Merge two sorted array,
but the recursive method is really good!!!!!!!!!!!!!!!!!!!!!!!!!!!1



Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m andn respectively.
Not a difficult problem to come up with an idea, but the order can affect complexity!!!!!!!

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

第一次面试就碰到这道题目,完完全全做错了,当时觉得两个指针移动,但是第一个指针移动的位置错了,而且一些basic case也没有cover
写的逻辑也十分有问题,总之蠢爆了!
下面的讲解来自leetcode详解:

Monday, February 10, 2014

CC Q1.3 given two strings, write a method to decide if one is a permutation of the other.

两种方法:都比较好想,但是有一些需要注意的地方
1 Check if the two strings have identical character counts.
这个方法中,只用一个标记数组来count,对第二个字符串判断时可以用--
false的条件可以有两种

2 sort the strings and compare : sort这里可以直接调用arrays的member function
package cc150;
/*
* Given two strings, write a method to decide if one is a permutation of the other.
* anagram
*/
/*My solution:
* method 1
* primary idea: len1== len2
* count of each char in s1 == count of same char in s2
*
* method 2: sort each string and compare
*/
public class ch13 {
// method 1: check if the two string have identical character counts
public static boolean permutation(String s1, String s2){
if(s1.length()!= s2.length()) return false; // no possibility if len1 != len2
boolean ispermutation = true;
int [] count = new int [256]; // count the number of each char in string
for(int i = 0; i < s1.length(); i++ ){
count[s1.charAt(i)]++; // count
}
//--------------should use only one array, so we can save space and no need compare if count1[] == count2[]
for(int j = 0; j< s2.length(); j++){
count[s2.charAt(j)]--;
}
// if s1 == s2 , all element in count[] should equal to 0
for(int k = 0; k < 256 ; k++){
if(count[k]!= 0) {
ispermutation = false;
break;
}
}
return ispermutation;
}
//------------------------------------better---------------------------------------
public static boolean permutation2(String s, String t) {
// the function is provide by the author https://github.com/gaylemcd/ctci
if (s.length() != t.length()) {
return false;
}
int[] letters = new int[256];
char[] s_array = s.toCharArray(); ///----------------change string to char---------------
for (char c : s_array) { // count number of each char in s.
letters[c]++;
}
for (int i = 0; i < t.length(); i++) {
int c = (int) t.charAt(i);
if (--letters[c] < 0) { // judge the value, decrease one loop
return false;
}
}
return true;
}
//---------------------------------------------------------------------------------
//-------------------------method 2 compare after sort-----------------------------
public static boolean permutationaftersort(String s1, String s2){
boolean ispermutation = true;
if (s1.length() != s2.length()) {
return false;
}
s1 = sort(s1);
s2 = sort(s2);
if(!s1.equals(s2)) ispermutation = false;
return ispermutation;
}
public static String sort(String s){
char[] schar = s.toCharArray();
////--------------------------!!!!!!!!!!!!!!!!!!!!!!!!!--------------------
//----this use the memeber function of Arrays------------------------
java.util.Arrays.sort(schar);
return new String(schar);
}
public static void main(String[] args){
String s1 = "abcdefg";
String s2 = "bcdgfea";
System.out.printf("string 1: %s\nstring 2: %s\n", s1,s2);
System.out.println("is permutation: "+ permutation(s1, s2));
System.out.println("is permutation using sort: "+ permutationaftersort(s1, s2));
}
}

CC150 Question1.2

not a difficult problem, but still something new for me
1:  the char at the end is null, we need to set back
2: operation with pointer
  while(str < ptrEnd) {
            temp = *str;
            *str++ = *ptrEnd; // this kind of write is good!
            *ptrEnd-- = temp;
        }
3 String is stored as char array in C
in C++,  many member functions is provided, but still based on char
Operation such as +, != , swap and so on.
http://www.cplusplus.com/reference/string/string/
I should do more practice with it
1234567891011121314151617181920212223242526272829303132333435363738394041
#include <iostream>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
/*
Implement a function void reverse(char* str) in C or C++
which reverses a null-terminated string.
created : Xiaojing liu
email: liu365@usc.edu
date:02/10/2014
*/
void reserve(char* str){
char *end = str;
if(str == NULL) return; // the string is empty
while(*(end+1) ){
//cout<<end<<endl;
end++; // point to the end
//cout<<"char:"<<*end<<endl;
}
char temp;
//swap the char at the start with the end
while(str < end){
temp = *str;
*str = *end;
str++;
*end = temp;
end--;
}
}
int main(int argc, char** argv) {
char str[] = "abcdefghijklmn";
cout<<str<<endl;
reserve(str);
cout<<"after reserve: "<<str<<endl;
system("pause");
return 0;
}

Sunday, February 9, 2014

RemoveDuplicatesfromSortedArrayII

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].
思路和Remove Duplicates from Sorted Array 一样, 不同的是相同时,如果是第一次相同,也要加在
数组中,用count计数
可以思考的: 如果数组没有排序,用hashmap来实现!(待补充)
1234567891011121314151617181920212223242526272829303132333435363738394041
package leetcode;
/*
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].
*/
public class RemoveDuplicatesfromSortedArray {
public static int removeDuplicates(int[] A) {// better
        int start = 0;
        //int length = A.length;
        if(A.length==0 || A.length==1) return A.length;
        for(int i = 1 ; i < A.length; i++){
         if(A[start] != A[i]){// find the first different element and append at the last
         start++;
         A[start] = A[i];
         }
        }
     
        return start+1;
    }
public static void main(String[] args){
int []Array = new int[]{1,1,2,2,3};
int len = removeDuplicates(Array);
for (int i = 0; i < Array.length; i++) {
System.out.printf("Array%d: %d \n", i, Array[i]);
}
System.out.printf("length:%d", len);
}
}

Remove Duplicates from Sorted Array

Leetcode 题目:
Two Pointers and Sliding Window
多指针 /滑动窗口法是面试题中最常见的题型之一,大多是利用多个指针对一个数组或链表 进行扫描,比如以不同 速度从头向尾扫描,或者分别从头和尾向中间扫描等等。使用多指针的目的是尽量减少循环 pass的次数以提高效率。需要注意的是扫描终止条件的判断。 
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].

My solution: 
public static int removeDuplicates( int[] A) { // better
        int start = 0;
        //int length = A.length;
        if (A.length ==0 || A. length==1) return A. length;
        for (int i = 1 ; i < A. length; i++){
               if (A[start] != A[i]){// find the first different element and append at the last
                     start++;
                     A[start] =  A[i];
                     
              }
        }
     
        return start+1;
    }
最初想要判断A[start] == A[i] 对数组进行处理,发现会需要每一次都将数组中元素向前移动,这样造成复杂度比较高,参考了leetcode详解中的方法,找到不等的元素,append在当前元素后面!

 public static void main(String[] args){
int []Array = new int[]{1,1,2,2,3};
int len = removeDuplicates(Array);
for (int i = 0; i < Array.length; i++) {
     System.out.printf("Array%d: %d \n", i, Array[i]);
   }
   System.out.printf("length:%d", len);
 
}
Output 如下:
Array0: 1 
Array1: 2 
Array2: 3 
Array3: 2 
Array4: 3
 length:3