leetcode-4 Median of Two Sorted Arrays

題意: 有兩個已經排序好的陣列,求其中位數,複雜度要求為O(log(n+m)),其中n,m為陣列長度


解題思路:這題非常難,網路上解法有二分搜索和遞迴兩種


C++ code:待補

leetcode-3 Longest Substring Without Repeating Characters

題意: 給定一串字串,求出不含有重覆字符的最常連續子字串的長度


解題思路: 利用尺取法,逐次推進,當遇到重覆字符時,重置累積的長度,須考慮兩種狀況,第一種狀況,前一個重覆的字符位置,ex. "bbcabcdef",當遇到第二個c時,須將長度從舊的c的下一個起算;第二種情況,若有其他組重複字符,其前一個重覆元素在目前指到元素的前一個重覆元素之後的話,則須從這種情況開始計算,ex. "cabbcdef", 當遇到第二個時,並不是從前一個c開始計算,而是從前一組重覆字符,也就是b起算,complexity為O(n),其中n為字串長度


c++程式碼如下:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int eng[600][2];
        memset(eng,0,sizeof(eng));
        int len=s.length();
        int count=0;
        int ans=0;
        int temp=-1;
        for(int i=0;i<len;i++)
        {
            if(eng[s[i]][0])
            {
                
                if(ans<count)
                    ans=count;
                if(eng[s[i]][1]>temp)
                    temp=eng[s[i]][1];
                if(temp>eng[s[i]][1])
                    count=i-temp;
                else
                    count=i-eng[s[i]][1];
                eng[s[i]][1]=i;
                
                
            }
            else
            {
                eng[s[i]][0]=1;
                eng[s[i]][1]=i;
                count++;
            }
            //cout<<count<<endl;
        }
        if(count>ans)
            ans=count;
        return ans;
    }
};

leetcode-2 Add Two Numbers

題意:給定兩個linked list,將其中的數字相加,每個欄位只限個位數,所以如果進位的話,則需加至下一個欄位,意思就類似加法,只是反向操作


解題思路: 就是要對linked list 有一定熟悉啦


c++程式碼如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
   
    
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
        ListNode* ans=new ListNode(0);
        ListNode* first=ans;
        ans->val=(l1->val+l2->val)%10;
        int temp=(l1->val+l2->val)/10;
        while(l1->next!=NULL||l2->next!=NULL||temp)
        {
            ListNode* nextnode=new ListNode(0);
            int c=0;
            if(l1->next!=NULL)
            {
                 l1=l1->next;
                 c=c+l1->val;
            }
            if(l2->next!=NULL)
            {
                 l2=l2->next;
                 c=c+l2->val;
            }
           
            nextnode->val=(c+temp)%10;
            ans->next=nextnode;
            ans=ans->next;
            temp=(c+temp)/10;
            
           
        }
       
        return first;
    }
};

leetcode-1 two sum

題意:
在一個陣列裡面,求出相加為目標值得兩數,其分別的座標為何,題目保證只有一組解


解題思路
這題解題思路很簡單,就是要了解c++ STL map的使用,來把演算法的複雜度降到$O(nlog n)$,
p.s: 亦可使用hashmap,也就是C++中的unordered_map來實現,其複雜度最佳可到$O(n)$,但hash你知道的嗎XD,可能會讓複雜度變超大!


code如下:

class Solution {
public:
    map<int,int>p;
    vector<int> twoSum(vector<int>& nums, int target) {
        int len=nums.size();
        for(int i=0;i<len;i++)
        {
            if(p.find(nums[i])!=p.end())
            {
                vector<int>ans;
                ans.push_back(p.find(nums[i])->second);
                ans.push_back(i);
                return ans;
            }
            p.insert(make_pair(target-nums[i],i));
        }
    }
};

android XML: tool 用法

在寫android時,XML構成我們APP的頁面,但其中有一個麻煩的地方,就是測試時,如果更動XML code,還要再改回來,實在好麻煩,於是Android Studio提供了一個貼心的功能,就是tool 這個namespace,我們只要引進這個namespace,再點旁邊的preview,就能看到我們改XML的效果,而且更棒的是,藉由tool更改的設定,在runtime時不會被編譯,也就是我們可以盡量測啦!


使用時,在layout下加入這一句,xmlns:tools="http://schemas.android.com/tools",其中聰明的你一定發現xmlns就是XML namespace的縮寫,接下來就可以用tool的功能了,舉例來說
1.  tools:text="anything you want to type"   可以讓textview或元件顯示文字
2.  tools:locale="es"   可以讓程式的預設環境改為英文


其他還有許多功能,就不一一列出了


參考資料:
1. Udacity
2. android studio 官方文件

c++ const教學

想必很多人在研究C++語言時,常遇到const這個東東吧XD,表面上看似複雜,其實不難,以下就讓我來一一道來吧!


const就是constant的縮寫,在C++裡面代表用這個方式表示的資料無法用這個方式修改,聽起來很抽象,就讓我用實例來展示吧


1. 出現在常數時:


const int c=100;
其實和 #define c 100 功能一樣,一但做出如此宣告,若之後想要改變c的值,就會compile error


2. 出現在參照時:
int b=100;
const int &a=b;


如果這時候我們想用a去改變b,比如說 a=150,會compile error,因為我們已經固定參照了!
但如果我們直接改b,則是被允許的! 比如說b=200,編譯會過


3. 出現在指標時:
int b=100;
const int *a=&b;
和參照時一樣,我們不能透過這個指標去改變b的值,只能直接用b改


4. 出現在STL iterator 時:
vector <int> v;
v.push_back(1);
v.push_back(2);
vector<int> const_iterator p;
for(p=v.begin();p!=v.end();p++)
     cout<<*p;
此處一樣,我們不能透過iterator去修改vector元素的值


這次的整理就到這,是不是很簡單啊XD


參考資料:
1. edx
2. MSDN

gradient descent algorithm for multivariate linear regression

目標函數:
$h_w (x) = w_0 + w_1 x_1 + w_2 x_2 + \cdots +w_nx_n$

演算法:
$w_j \leftarrow w_j - \alpha \frac{1}{m} \sum\limits_{i=1}^{m} (h_w(x^{(i)}) - y^{(i)}) \cdot x_j^{(i)} \; \text{for j = 0...n}$
$do$ $this$ $until$ $convergence$

其中:
$x_j^{(i)} :\text{第j組資料的第i個特徵} $
$x^{(i)}:\text{由第i組資料的所有特徵組成的column vector}$
$m  : \text{餵的資料組數}$
$ n  :\text{特徵的數量}$


我想第一眼看到這個演算法應該頗傻眼吧,感覺很複雜,其實還好,這個演算法在machine learning中被稱為gradient descent algorithm,主要是用來從資料中學習的演算法
我想有學過線性代數的人都知道最小平方法,其重點是求出一條直線,使直線和其他點的平方誤差最小,這個演算法也是類似道理,希望從資料中得到誤差最小的直線,至於如何做呢,就如同上面提到的演算法一樣,利用逐次逼近來使目標函數誤差最小,其中選取$\alpha$是一門學問,選太小會使演算法收斂太慢,選太大可能會導致演算法無法收斂,因此實務上選取$\alpha$都是慢慢嘗試,這個演算法因為是採用嘗試的,且一旦到local minima就不會動了,因此可能找到的不會是全域最佳解(不過在linear regression的情況下並不會發生local manima的情況)! 這個想法非常好用,並不只限於線性回歸,以後會再出現歐XD

gradient descent 方法有一些優化的方法:
1. feature scaling
2. stochastic gradient descent
3. adagrad



資料來源:
1. coursera: machine learning by andrew ng
2. artificial intelligence a modern approach 3rd
3. 李宏毅教授youtube