Tuesday, August 7, 2012

3 different way Tree Traversal

=========================================================================
Node class for tree
class Node{
    int data;
    Node left;
    Node right;
}
=========================================================================
Case 1: pre-order 

Recursive
public static void preOrderRecursive(Node root){
    if(root == null)
        return;
		
    System.out.print(root.data + " ");		
    preOrderRecursive(root.left);
    preOrderRecursive(root.right);
}
NON-Recursive
public static void preOrderIterative(Node root){
    if(root == null)
        return;
		
    Stack<Node> unvisited = new Stack<Node>();
    unvisited.push(root);
	
    while(!unvisited.isEmpty()){
        Node node = unvisited.pop();
			
        System.out.print(node.data + " ");
        if(node.right != null)
            unvisited.push(node.right);
        if(node.left != null)
            unvisited.push(node.left);
    }	
}
=========================================================================
Case 2: in-order 

Recursive
public static void inOrderRecursive(Node root){
    if(root == null)
        return;	
	
    inOrderRecursive(root.left);
    System.out.print(root.data + " ");
    inOrderRecursive(root.right);
}
NON-Recursive
public static void inOrderIterative(Node root){
    if(root == null)
        return;
		
    Stack<Node> unvisited = new Stack<Node>();
		
    while(!unvisited.isEmpty() || root != null){
        if(root != null){
            unvisited.push(root);
            root = root.left;
        }else{
            root = unvisited.pop();
            System.out.print(root.data + " ");
            root = root.right;
        }
    }
}
========================================================================= 
Case 3: post-order 

Recursive
public static void postOrderRecursive(Node root){
    if(root == null)
        return;
		
    postOrderRecursive(root.left);
    postOrderRecursive(root.right);
    System.out.print(root.data + " ");		
}
NON-Recursive
public static void postOrderIterative(Node root){
    if(root == null)
        return;
		
    Stack<Node> finalStack = new Stack<Node>();
    Stack<Node> tempStack = new Stack<Node>();
	
    tempStack.push(root);
    while(!tempStack.isEmpty()){
        Node node = tempStack.pop();
        finalStack.push(node);
        if(node.left != null)
            tempStack.push(node.left);
				
        if(node.right != null)
            tempStack.push(node.right);
    }
	
    while(!finalStack.isEmpty()){
        Node node = finalStack.pop();
        System.out.print(node.data + " ");	
    }
}

Find a missing integer in an array of number

Find a missing integer in an array of number

Case 1: Sorted
Use two pointers to store previous and current value, and difference between two number should equal to 1.
public static int findMissing_Sorted(int[] input){
    if(input.length == 0)
        return 0;

    int prev = input[0];
    for(int i = 1 ; i < input.length ; i++){
        int curr = input[i];
        if((curr - prev) != 1)
            return (prev + 1);
        else
            prev = curr;
    }
    return 0;
}



Case 2: Unsorted
Get the sum of 1 to N, use formula sum = (N+1)*(N)/2
Minus the element in the array, and the remaining value is the missing number.
public static int findMissing_Unsorted(int[] input){
    if(input.length == 0)
        return 0;
   
    int N = 10;
    int max = (N + 1) * N / 2;
  
    for(int i = 0 ; i < input.length ; i++)
        max -= input[i];
   
    return max;
}

Monday, August 6, 2012

How to use *args and **kwargs in Python

from
http://www.saltycrane.com/blog/2008/01/how-to-use-args-and-kwargs-in-python/

http://docs.python.org/tutorial/controlflow.html#keyword-arguments


def test_var_args(farg, *args):
    print "formal arg:",farg
    for arg in args:
        print  "another arg:",arg
  


def test_var_kwargs(farg, **kwargs):
    print "formal arg:",farg
    for key in kwargs:
        print "another keyword arg: %s: %s" % (key, kwargs[key])

test_var_args(1, "two", 3, "four")
print '-'*40
test_var_kwargs(farg = 1, myarg2 = "two", myarg3 = 3, myarg4 = "four")


def test_var_args_call(arg1, arg2, arg3):
    print "arg1:", arg1
    print "arg2:", arg2
    print "arg3:", arg3

args = ("two", 3)
test_var_args_call(1, *args)


def test_var_args_call(arg1, arg2, arg3):
    print "arg1:", arg1
    print "arg2:", arg2
    print "arg3:", arg3

kwargs = {"arg3": 3, "arg2": "two"}
test_var_args_call(1, **kwargs)

Tuesday, July 31, 2012

Codeforce - 158A - Next Round

n, k = map(int, raw_input().strip().split() )
seq = map(int, raw_input().strip().split() )

score = seq[k - 1]

if score == 0:
    counter = 0
    for i in range(0, k):
        if seq[i] > score:
            counter += 1
    print counter
 
else:
    counter = k
    for i in range(k, n):
        if seq[i] >= score:
            counter += 1
        else:
            break
    print counter

ACM105 -- The Skyline Problem

#include <iostream>

using namespace std;

int main()
{
    int L,H,R;
    int counter = 0;
    int temp_pre,temp_curr;
    int min = 20000,max = 0;
    int building[10001] = {0};


    while(cin>>L>>H>>R)
    {
        if(min>L)
        min = L;

        if(max<R)
        max = R;

        for(int i = L ; i < R ; i++)
        {
            if(building[i] < H)
            building[i] = H;
        }
        counter++;
    }



    bool check = true;
    temp_pre = building[min];
    cout<<min<<" "<<temp_pre<<" ";

    for(int j = min+1 ; j <= max ; j++)
    {
        temp_curr = building[j];
        if(check) //check == true
        {
            if(temp_curr == 0)
            {
                check = false;
                cout<<j<<" "<<temp_curr;
            }else
            {
                if(temp_curr != temp_pre)
                {
                    cout<<j<<" "<<temp_curr<<" ";
                    temp_pre = temp_curr;
                }
            }
        }
        else
        {
            if(temp_curr == 0)
            {
                //do nothing
            }else
            {
                check = true;
                temp_pre = temp_curr;
                cout<<" "<<j<<" "<<temp_curr<<" ";
            }
        }
    }

    cout<<endl;
    return 0;
}

Codeforces -- 1A -- Theater Square

#include <iostream>
#include <math.h>

using namespace std;

int main(int argc, char* argv[]){
    long double n,m,a;

    cin>>n>>m>>a;

    long long res = (long long)(ceil(n/a) * ceil(m/a));

    cout<<res;
 return 0;
}

ACM 10035 -- Primary Arithmetic

#include <iostream>

using namespace std;


int main(int argc, char* argv[]){
    unsigned long long n1;
    unsigned long long n2;
    int carry = 0;
    int sum = 0;
    int count = 0;

    while(cin >> n1 >> n2) {
        if(n1 == 0 & n2 == 0)
            break;

        carry = 0;
        count = 0;
        sum = 0;

        while ((n1 > 0) || (n2 > 0)) {

            sum = carry + (n1 % 10) + (n2 % 10);

            if (sum >= 10) {
                count++;
            }

            carry = sum / 10;

            n1 /= 10;
            n2 /= 10;
        }

        if (count == 0) {
            cout << "No carry operation." << endl;
        } else if (count == 1) {
            cout << "1 carry operation." << endl;
        } else {
            cout << count << " carry operations." << endl;
        }
    }
 return 0;
}

ACM 494 -- Kindergarten Counting Game

#include <stdio.h>
#include <ctype.h>


int main()
{
    char temp;
    int counter = 0;
    int isWord = 0;
    while((temp = getchar()) != EOF){
        if(temp == '\n'){
            printf("%d\n", counter);
            counter = 0;
            isWord = 0;
        }else{
            if((temp >= 65 && temp <= 90)||(temp >= 97 && temp <= 122)){
                if(isWord == 0){
                    isWord = 1;
                    counter++;
                }
            }else{
                if(isWord == 1){
                    isWord = 0;
                }
            }
        }
    }
    return 0;
}

ACM 10038 -- Jolly Jumpers

#include <stdio.h>
#include <math.h>


int main(int argc, char* argv[])
{
    int counter;
    int num[3000];
    int flag[3000];

    while( scanf("%d", &counter) == 1 ){
        int i;
 for(i = 0 ; i < counter ; i++){
            scanf("%d", &num[i]);
            flag[i] = 0;
        }

        int res = 0;
        for(i = 1 ; i < counter ; i++){
            int diff;
            if(num[i] > num[i-1]){
                diff = num[i] - num[i-1];
            }else{
                diff = num[i-1] - num[i];
            }

            if(0 < diff && diff < counter){
                if(flag[diff] == 0){
                    flag[diff] = 1;
                }else{
                    res = 1;
                    break;
                }
            }else{
                res = 1;
                break;
            }

        }

        if( res == 1 ){
            printf("Not jolly\n");
        }
        else{
            printf("Jolly\n");
        }
    }
 return 0;
}

ACM 458 -- The Decoder

#include <stdio.h>
#include <ctype.h>


int main()
{
    char temp;
    while((temp=getchar())!=EOF)
    {
        (temp == '\n') ? putchar(temp) : putchar(temp-7);
    }
    return 0;
}

ACM 272 -- TEX Quotes

#include <stdio.h>
#include <ctype.h>


int main()
{
    char temp;
    int pair = 0;
    while((temp=getchar())!=EOF){
        if(temp == '"'){
            if(pair == 0){
                pair++;
                printf("``");
            }else{
                pair = 0;
                printf("''");
            }
        }else{
            putchar(temp);
        }
    }
    return 0;
}

ACM 10071 -- Back to High School Physics

#include<stdio.h>
#include<stdlib.h>

int main()
{
    int v, t;
    while (scanf("%d %d",&v, &t)!= EOF){
        printf("%d\n", 2*v*t);
    }
    return 0;
}

ACM 10055 -- Hashmat the Brave Warrior

#include <stdio.h>


int main()
{
    long long int hash, oppen;
    while (scanf("%lld %lld",&hash, &oppen)!= EOF){
        if(hash > oppen)
            printf("%lld\n", (hash - oppen));
        else
            printf("%lld\n", (oppen - hash));
    }
    return 0;
}


ACM 10110 -- Light, more light

#include <iostream>
#include <math.h>
#include <sstream>
#include <stdio.h>
#include <cstdio>

using namespace std;

bool willLight(double num){
    long long int test = (int) sqrt(num) ;

    if(test*test == num)
        return true;


    return false;
}


int main()
{
    double input;

    while(scanf("%lf", &input)){
        if(input == 0.0)
            break;

        if( willLight(input) )
            cout<<"yes"<<endl;
        else
            cout<<"no"<<endl;
    }

    return 0;
}

ACM 492 -- Pig-Latin

#include <stdio.h>
#include <ctype.h>
int test(char ch);

int main()
{
    int i;
    char ch;
    char root;
    int s;

    while(1){
        i = 0;
        while(1){
            ch = getchar();
            if(ch == EOF)
                return 0;
            if(isalpha(ch)){
                if(!i){
                    s = test(ch);

                    if(s)
                        printf("%c", ch);
                    else
                        root = ch;
                    i++;
    }else{
                    printf("%c", ch);
                }
            }else{
                if(!i){
                    printf("%c", ch);
                    break;
                }
                if(s){
                    printf("ay%c", ch);
                }else{
                    printf("%cay%c", root, ch);
                }
                break;
            }
        }
    }
    return 0;
}

int test(char ch){
 if(ch == 'A' || ch == 'a')
  return 1;
 if(ch == 'E' || ch == 'e')
  return 1;
 if(ch == 'I' || ch == 'i')
  return 1;
 if(ch == 'O' || ch == 'o')
  return 1;
 if(ch == 'U' || ch == 'u')
  return 1;

 return 0;
}


Sunday, June 17, 2012

Django -- redirect to outside link

in views.py
out_url = "http://www.google.com"
return render_to_response('short/redirect.html', {'out_url':out_url})
in short/redirect.html
<meta http-equiv="refresh" content="0; URL={{ out_url }}">

Tuesday, June 12, 2012

Django -- upload file

上傳資料,參考
http://oranlooney.com/django-file-uploads/
http://www.nitinh.com/2009/02/django-example-filefield-and-imagefield/
http://gibuloto.com/blog/models-dot-imagefield/ 

(1)設定上傳用的資料夾
Django 1.4 裡面有提供 MEDIA_URL 和 MEDIA_ROOT
這兩個部份的設定主要是讓使用者上傳資料和顯示

這邊就不從開新的app開始說,直接從settings.py和models.py設定開始

首先是settings.py的設定
cd //var/www/mutarock/mutarock
vim settings.py
MEDIA_ROOT = os.path.join(os.path.dirname(__file__), '..', 'multimedia').replace('\\','/')
MEDIA_URL = '/multimedia/'
設定完之後移到上一層去
cd ..
mkdir multimedia
接下來是apps裡面models.py的設定
class Picture(models.Model):
    image = models.ImageField(upload_to='pic')

上面的models開了一個欄位,讓使用者上傳圖片,在django裡面,系統不會真的把東西儲存在資料庫裡面
而是儲存資料在系統裡面的位置

MEDIA_ROOT 和 upload_to 的設定,有以下的關係

MEDIA_ROOT = ‘/home/myname/files/
upload_to=’videos’
file: abc.flv
results in: /home/myname/files/videos/abc.flv

MEDIA_ROOT = '/home/myname/files/'
upload_to='/videos'
and file : abc.flv
result will be saved in : '/videos/abc.flv' (i.e., root directory of filesystem)

upload_to也可以加進去上傳的日期和時間
upload_to='videos/%Y/%m/%d'
如果上傳時間是2012 Jun 12
檔案就會儲存到 /home/myname/files/videos/2012/06/12

(2)設定form.py
form的部分可以直接建立在html裡面,網路上的參考文章則是順便教了如何用django實做form
連到自己的apps裡面新增一個form.py
vim form.py
輸入下面的code
from django import forms
from PIL import Image
class PictureUploadForm(forms.Form):
    image = forms.ImageField()
    

    def clean_image(self):
        ' reject large images.'
        max_size = 10**7
        if len(self.cleaned_data['image'].read()) > max_size:
            raise forms.ValidationError('Image must be less then %d bytes.' % max_size)
        else:
            return self.cleaned_data['image']

上面的code會有一個可以欄位,讓使用者決定要上傳什麼圖檔
其中也自訂一個function,檢查上傳的檔案是否超過我們自定的大小

(3)設定views.py
import uuid #use for data name
from apps.picture.form import PictureUploadForm  #import your form

def picture_upload(request):

    picture = Picture()
    if request.method != 'POST':
        form = PictureUploadForm()
    else:
        form = PictureUploadForm(request.POST, request.FILES)
        if form.is_valid():

            # an UploadedFile object
            uploadedImage = form.cleaned_data['image']
            file_name = uuid.uuid4().hex
            file_extension = os.path.splitext(uploadedImage.name)[-1]
            full_file_name = file_name + file_extension

            # save picture object
            picture.image.save(
                full_file_name, 
                request.FILES['image'], 
                save = False
            )
            picture.save()
            return render_to_response(
                'example/result.html'
                {'result': "Upload success",},
                context_instance = RequestContext(request))


    return render_to_response(
        'example/picture_upload.html',
        {'form':form},
        context_instance = RequestContext(request))

簡單說明上面的code
如果request不是POST,就只回傳form
如果是POST,則把使用者選擇的圖片上傳到系統裡面
檔名的部分我是用uuid,這樣幾乎可以確保檔案名稱不會重複
file_extension是檔案的格式,例如 jpg 或是 png
最後就印出"Upload success"給使用者


picture_upload.html
<form enctype="multipart/form-data" method="post" action="example/picture_upload">
    {% csrf_token %}   
    <table>
        {{form.as_p}}
    </table>
    <input type="submit" value="Submit" id="Save"/>
</form>

result.html
<p> {{ result }} </p>


上傳檔案大概就是這樣,主要就是設定好
MEDIA_ROOT
upload_to
大概就沒問題了


MEDIA_URL的部分是要讓使用者可以讀取或是顯示出上傳的東西
我是設定成
MEDIA_URL = '/multimedia/'
然後再主要的urls.py加上
urlpatterns += patterns('',
    url(r'^multimedia/(?P.*)$', 'django.views.static.serve',
                 {'document_root': settings.MEDIA_ROOT}),
所以我輸入
http://localhost:8000/multimedia/pic/FileName
就可以顯示出我上傳的圖片了


Sunday, June 10, 2012

Django -- create a new app - part3

part 1和2已經記錄了如何開一個新的app和urls.py的設定
這一篇就把剩下的部分講完
這邊主要寫view.py和html的部分

首先先連到apps/polls/
cd //var/www/mutarock/apps/polls
vim views.py
首先先來新增一個index,這個可以印出資料庫最近新增的幾個投票
from django.template import Context, loader
from apps.polls.models import Poll
from django.http import HttpResponse

def index(request):
    latest_poll_list = Poll.objects.all().order_by('-pub_date')[:5]
    t = loader.get_template('polls/index.html')
    c = Context({
        'latest_poll_list': latest_poll_list,
    })
    return HttpResponse(t.render(c))
上面的code會抓出最近的5個投票,並且讀取polls/index.html這個templates
並且把投票資訊傳給他顯示

存檔之後執行熟悉的
python manage.py runserver
開啟瀏覽器 http://127.0.0.1:8000/polls 應該會跑出錯誤訊息
TemplateDoesNotExist at /polls/
polls/index.html
這是因為我們還沒有把templates建立起來,我們前面只是設定

移到前兩層,去建立我們的templates資料夾
cd //var/www/mutarock
mkdir templates
cd templates
mkdir polls
目前這個系統的資料夾應該會像
mutarock/
    manage.py
    mutarock/
    apps/    
        polls/
    templates/
        polls/
移到 templates/polls 資料夾去建立我們的index.html
{% if latest_poll_list %}
{% if latest_poll_list %}
    <ul>
    {% for poll in latest_poll_list %}
        <li><a href="/polls/{{ poll.id }}/">{{ poll.question }}</a></li>
    {% endfor %}
    </ul>
{% else %}
    <p>No polls are available.</p>
{% endif %}
這樣就可以順利顯示我們的polls資訊了
其他的細節我就不細講了,教學都還滿仔細的,我覺得自己講不太清楚,所以detail, vote, result直接看教學比較好
教學三,教學四


Thursday, June 7, 2012

Django -- create a new app - part2

part1是一些有關models建立以及如何和系統互動
這邊先來記錄一下如何顯示

首先先修改settings.py中的 TEMPLATE_DIRS
cd //var/www/mutarock/mutarock/
vim settings.py
TEMPLATE_DIRS = (
    # Put strings here, like "/home/html/django_templates" or "C:/www/django/templates".
    # Always use forward slashes, even on Windows.
    # Don't forget to use absolute paths, not relative paths.
    os.path.join(os.path.dirname(__file__), '..', 'templates').replace('\\','/'),
)
這個設定主要是告訴django你的模板放在哪裡,我這邊用的是相對路徑
方便將來移植,如果覺得完全不會動到就用絕對路徑也是可以的啦

回到前一層去新增templates資料夾
cd ..
mkdir templates
cd templates/
mkdir polls
我希望每個apps的模板放的地方不一樣,所以多新增一個子資料夾polls
到目前為止準備工作已經差不多了,接下來還有3個部分
  • 設定 urls.py
  • 編輯 /apps/polls/views.py
  • 編輯顯示用的 html

下面先來處理urls.py
這部分有很多不同的做法,你可以把全部的urls路徑都放到主資料夾下面的urls.py
也可以用導向的方式,在每個apps裡面都有自己的urls.py
教學上面的例子,下面兩個做法等價,挑自己喜歡的風格

例子一:
全都放在 //var/www/mutarock/mutarock/urls.py
from django.conf.urls import patterns, include, url

from django.contrib import admin
admin.autodiscover()

urlpatterns = patterns('',
    url(r'^polls/$', 'polls.views.index'),
    url(r'^polls/(?P\d+)/$', 'polls.views.detail'),
    url(r'^polls/(?P\d+)/results/$', 'polls.views.results'),
    url(r'^polls/(?P\d+)/vote/$', 'polls.views.vote'),
    url(r'^admin/', include(admin.site.urls)),
)


例子二
主資料夾負責導向
//var/www/mutarock/mutarock/urls.py
from django.conf.urls import patterns, include, url

from django.contrib import admin
admin.autodiscover()

urlpatterns = patterns('',
    url(r'^polls/', include('apps.polls.urls')),
    url(r'^admin/', include(admin.site.urls)),
)

apps的資料夾負責細節
//var/www/mutarock/apps/polls/urls.py (預設是沒有這個檔案,要自己新增)
from django.conf.urls import patterns, include, url

urlpatterns = patterns('apps.polls.views',
    url(r'^$', 'index'),
    url(r'^(?P\d+)/$', 'detail'),
    url(r'^(?P\d+)/results/$', 'results'),
    url(r'^(?P\d+)/vote/$', 'vote'),
)
之後再browser上面輸入 http://127.0.0.1/polls 系統就會知道要導向到polls的urls.py

  • 後面什麼都不接,會去找polls裡面view.py的index 
  • 後面接polls的id,找deatils
  • 以此類推


urls.py比較基本的概念就是這些,個人比較偏好第2種做法
主資料夾的urls.py看起來會比較整齊
不然開了幾十個apps不就可能會有幾百行在裡面


Django -- admin page

django的admin page相當的強大
可以顯示出來的東西非常多,不過還有很多細節需要去研究

首先先修改 settings.py
把 django.contrib.admin 的註解拿掉
INSTALLED_APPS = (
    'django.contrib.auth',
    'django.contrib.contenttypes',
    'django.contrib.sessions',
    'django.contrib.sites',
    'django.contrib.messages',
    'django.contrib.staticfiles',
    # Uncomment the next line to enable the admin:
    'django.contrib.admin',
    # Uncomment the next line to enable admin documentation:
    # 'django.contrib.admindocs',
    'apps.polls',
)


修改urls.py
from django.conf.urls import patterns, include, url

# Uncomment the next two lines to enable the admin:
from django.contrib import admin
import settings

admin.autodiscover()

urlpatterns = patterns('',
    # Examples:
    # url(r'^$', 'mutarock.views.home', name='home'),
    # url(r'^mutarock/', include('mutarock.foo.urls')),

    # Uncomment the admin/doc line below to enable admin documentation:
    # url(r'^admin/doc/', include('django.contrib.admindocs.urls')),

    # Uncomment the next line to enable the admin:
    url(r'^admin/', include(admin.site.urls)),
)
這邊的urlpattern是利用regular expression去表示
所以在domain後面接 admin 就會去開啟admin page
之後新增不同的app和服務之後就會實際了解如何作用

OK之後可以輸入
python manage.py runsever
打開瀏覽器進入你在domain下面的admin page
例如 http://127.0.0.1/admin
應該會看到














OK之後,下一步是把polls app也加進去admin page
這樣就可以方便管理了
先移到polls的資料夾下面並建立admin.py檔案
cd //var/www/mutarock/apps/polls/
vim admin.py
輸入
from polls.models import Poll
from django.contrib import admin

admin.site.register(Poll)

這樣就可以把這個apps註冊到admin page裡面
至於顯示的部分其實非常多樣化,可以依照apps的欄位顯示,或者顯示一些圖片或是縮圖
可以參考一下教學