leetcode-11 Container With Most Water

題意: 給定一個數組,假設值代表板子高度,index代表板子位子,求任選兩塊板子裝水(p.s兩塊版子中間的其他版子此時視為不存在),所能裝的最多水量


解題思路: 利用雙指針,其中一指針指向數組開頭,另一指針指向數組尾端,記錄此時面積,和原先記錄的答案比較;之後,將指向比較矮木板的指針往另外一塊木板方向移動,複雜度為O(n),其中n為數組元素個數


演算法實現不難,難的是理解為何演算法是正確的,我們可以來簡單證明一下,如果這種移動木塊的方法能夠涵蓋所有情況,則這個演算法會是正確的,我們可以想一下為何移動的是矮木板,因為如果移動的是指向高木板的指針,則所圍成的面積必定下降,因為不管下一塊被指向的木板的高度比較高或一樣,則新的面積為矮木板高度乘與較短的寬度;或較矮,則新的面積為新木板乘與較少寬度,所以矮木板移動時,即表示之前矮木板所能形成的最大面積已經被考慮了!!每次移動木板即表示被移動木板的所有情況已經被考慮,因為一開始從兩端開始移動,又最終兩塊木板重合,即表示所有情形皆被考慮,故此算法成立


C++ code 如下:

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l=0;
        int r=height.size()-1;
        int ans=min(height[l],height[r])*(r-l);
        while(l!=r)
        {
           
            if(height[l]<height[r])
                l++;
            else
                r--;
            if(ans<min(height[l],height[r])*(r-l))
                ans=min(height[l],height[r])*(r-l);
        }
        return ans;
    }
};

useful computer science open course

1. computer science theory:

(1) algorithm and data structure:

a. algorithm(from NCTU in Mandarin): cover the basic of algorithm, move in a reasonable pace,can be used as the first course in algortihm


b. Introduction to Algorithms(MIT): one of the lecturer is the author of the introduction to algortihm(CLRS), so you should use it with the algorithm bible(CLRS), and you will find it is really useful. However, the material is somewhat hard, maybe this should be your second OCW of data structure and algorithm


c. Computational Geometry(from edx in Mandarin): a good course on computatational geometry, use the beatiful picture to cover the core concept of the algorithm


d. Algorithms on Strings(coursera): week 3 is a good tutorial of the KMP algorithm

(2) linear algebra:

a. Linear Algebra(MIT): teach by the world-famous professor, Gilbert Strang, this course is fun and easy to understand, this course emphasize to build your math sence without too much proof, highly recommended

(3) discrete math:

a. Mathematics for Computer Science(MIT): a great course covers many aspect of computer science, even cover the Akra-Bazzi theorem

(4) computer architecure:

a. computer organization(from NTHU in Mandarin): this course covers the key concept of the subject bible,"computer organization and design",the professor keeps asking question to the student, also help the viewer to think about the logic behind computer design, highly recommended!

(5) operating system:

a. Operating Systems(from sharecourse in Mandarin): use the slide from the most popular OS book,"Operating system concepts", the professor almost cover all the material of the first 2/3 part of the book, highly recommended!

(6) artificial intelligence:

a. Intro to artificial intelligence(from Udacity): offered by Stanford, and one of the lecturer, Peter Norvig, is the author of the AI bible,"Artificial Intelligence:Modern approach", this course is base the book. Excellent course with easy-understanding teaching, highly recommended.

b. learning from data(from Caltech): offered by Caltech, a really good introduction to machine learning, highly recommended. If you got the companion textbook, "Learning from data, a short course", the learning process will be faster!! 

(7) database:

a. databases (Stanford): currently viewed as the best DB class on the internet, highly recommended.

2. programming language:

(1) c/c++:

a. C++ Programming (from edx in Madarin): very thorough course in C++, go from the basic to very deep concept, cover OOP, STL.

(2)Java:

a.Intro to Java programming(Udacity): a beginer course in Java, help you to build the OOP concept, highly recommened


b. Software Construction in Java(edx): not only cover the Java language, but also the concept of the software engineering, such as version control(git), unit test; really good course, highly recommedned for people who has former programming experience!

(3)HTML/CSS/Javascript:  

(4)android:

a. android basic: user interface(Udacity):  It's a great course, which teachs the XML, which constitute the layout of android

b. android basic:user input(Udacity): It's also a great course, which teachs you how to make interactive app;
p.s. I only recommend this two, because the learning curve is really deep in the sequel!

(5)version control

a. How to use git and github(Udacity): excellent course in git and github, practice git with the vedio, and after you complete the vedio, you will find that you know how to use git well!

leetcode-10 Regular Expression Matching

題意: 待完成

leetcode-9 palidrome number

題意:要求判定一數是否為回文數,不可使用額外空間


解題思路:這題題目有誤,因為不管你使用任何方法,一定會用到額外空間,至少O(1),就算只是對常數做除法,比如說x=x/10; 10這個常數也需要空間,所以此題無解


C++ code: 無

Java概念: mutable v.s. immutable

在學習Java語言時,常常聽到人家說mutable和immutable,到底是甚麼意思呢?如果從字面上的意思來說的話,mutable代表可改變的,immtable代表不可改變的,還是很抽象,對吧!,就讓我們用實例來說明吧!


有四個名詞要認識mutable value,immutable value,mutable reference,immutable reference,就讓我一一來說明吧!


1. mutable reference point to immutable values:
   舉例來說:
   String s1="a";
   這個宣告代表我們創建一個名叫s1的reference,它指向一個String type的物件,名為"a", 而reference指向可以改變,但物件的值不能改變
   所以以下code的輸出結果會是a,因為s2已經指向了"a"這個物件,而物件的值不能被改變
    String s1="a";
    String s2=s1;
    s1="b";
    System.out.println(s2);
 2. immutable reference point to mutable values
    final StringBuilder s= new StringBuilder("hello");
    final 在這裡的用法和C++ const(點擊可參考我之前文章)類似,意思就是指向不可變,也就是s永遠都要指向"hello"這個物件,但我們可以改變"hello" 這個 StringBuilder  類型物件的值


總結:
mutable value: 值可以改變
immutable value: 值不能改變
mutable reference: 可以指向其他地方
immutable reference: 不可以指向其他地方


參考資料:
1. edx course: MITx: 6.005.1x Software Construction in Java
2. https://docs.oracle.com/javase/7/docs/api/java/lang/String.html

leetcode-8 String to Integer(atoi)

題意:將字串轉為signed int,若不符合格式,返回0,若溢位,返回INT_MAX or INT_MIN


解題思路: 這題也算簡單,就依照題目要求,分類情況,答案就出來了!複雜度為O(n),其中n為字串長度


C++ code如下:

class Solution {
public:
    int myAtoi(string str) {
        int len=str.size();
        long long y=0;
        int ok=0;
        int sign=1;
        for(int i=0;i<len;i++)
        {
            if(str[i]>=58||str[i]<=47)
            {
                if(!ok)
                {
                    if(str[i]=='+')
                        ok=1;
                    else if(str[i]=='-')
                    {
                        ok=1;
                        sign=-1;
                    }
                    else if(str[i]!=' ')    
                        return 0;
                }
                else
                {
                    if(sign*y>INT_MAX)
                        return sign*INT_MAX;
                    else if(sign*y<INT_MIN)
                        return sign*INT_MIN;
                    else
                        return sign*y;
                }
            }
            else
            {
                ok=1;
                y=y*10+str[i]-'0';
                if(sign*y>INT_MAX)
                    return INT_MAX;
                else if(sign*y<INT_MIN)
                    return INT_MIN;
            }
        }
        if(sign*y>INT_MAX)
            return INT_MAX;
        else if(sign*y<INT_MIN)
            return INT_MIN;
        else
            return sign*y;
    }
};

leetcode-7 Reverse Integer

題意: 給定一32bit帶正負號整數,將其反轉後輸出,若反轉後產生溢位,則輸出0


解題思路: 首先要先知道32-bit signed integer的範圍是 -2147483648 ~ 2147483647,接下來就可進行反轉,反轉再進行溢位判定即大功告成,複雜度為O(n),其中n為輸入數字位數


C++ code 如下:

class Solution {
public:
    int reverse(int x) {
        if(x==-2147483648)
            return 0;
        long long y=0;
        int count=0;
        int c=x;
        if(x<0)
            c=-1*x;
            
        while(c)
        {
            y=y*10+(c%10);
            c/=10;
        }
        
        if(x>0)
        {
            if(y>2147483647 )
                return 0;
            else
                return(int)y;
        }
        else
        {
            if(y>2147483648 )
                return 0;
            else
                return-(int)y;
        }
        
    }
};