org.json.JSONException: Value <feed of type java.lang.String cannot be converted to JSONArray

This error is reported by android studio. It is caused by wrong format of data, which means that the link don't provide Json or the Json format is incorrect or you parse the correct Json in wrong way!




solution:
1. check if your link links to Json page, just paste your link to the browser to see if the Json appears to be downloded or on the wed page
2. check the Json is correct or not, correct means syntax correct, you can check it in Json formatter online
3. realize the difference between Json object and Json array, Json array use [ ] , while Json object use {}

leetcode-17 Letter Combinations of a Phone Number

題意: 給定一電話面板,上面每個數字會對應到特定幾個英文字,求一串數字所能對應到所有的字串


解題思路:其實這題算法很簡單,難的是動手實踐,舉例來說23, 2對應到a,b,c ; 3對應到d,e,f; 所以所有可能就是:
ad         
ae
af
bd
be
bf
cd
ce
cf
可發現會循環,所以就是將觀察到的規則寫出來,即所求
c++ code: 如下

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        string arr[8]={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        int len=digits.length();
        vector<string> ans;
        
        if(len==0)
            return ans;
        int total=1;
       
        for(int i=0;i<len;i++)
        {
            if(digits[i]=='0'||digits[i]=='1')
                return ans;
            else if(digits[i]=='7'||digits[i]=='9')
                total=total*4;
            else
                total=total*3;
        }
        int rep=total;
        for(int i=0;i<total;i++)
            ans.push_back("");
        for(int i=0;i<len;i++)
        {
            if(digits[i]=='7'||digits[i]=='9')
            {
                int cnt=total/rep;
                rep=rep/4;
                for(int j=0;j<cnt;j++)
                {
                    for(int k=0;k<4;k++)
                    {
                        for(int n=0;n<rep;n++)
                            ans[j*rep*4+k*rep+n]+=arr[digits[i]-50][k];
                    }
                }
            }
            else
            {
                int cnt=total/rep;
                rep=rep/3;
                for(int j=0;j<cnt;j++)
                {
                    for(int k=0;k<3;k++)
                    {
                        for(int n=0;n<rep;n++)
                            ans[j*rep*3+k*rep+n]+=arr[digits[i]-50][k];
                    }
                }
            }
                
            
        }
        
        return ans;
    }
};

leetcode-16 3Sum Closest

題意:給定一數組和目標數,找出最接近目標數的三數和


解題思路:這題解法跟3Sum 類似,只是判定移動start或end的標準改為三數和與target的差值


c++ code如下:

 
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int len=nums.size();
        int ans=nums[0]+nums[1]+nums[2];
        for(int i=0;i<len-2;i++)
        {
            if(nums[i-1]==nums[i]&&i)
                continue;
            int start=i+1; 
            int end=len-1;
            while(start!=end)
            {
                if(nums[i]+nums[start]+nums[end]-target==0)
                    return target;
                else if(nums[i]+nums[start]+nums[end]-target>0)
                {
                    if(abs(ans-target)>nums[i]+nums[start]+nums[end]-target)
                        ans=nums[start]+nums[end]+nums[i];
                    end--;
                }
                else
                {
                    if(abs(ans-target)>abs(nums[i]+nums[start]+nums[end]-target))
                        ans=nums[start]+nums[end]+nums[i];
                    start++; 
                }
            }
        }
        return ans;
    }
    
    int abs(int k)
    {
        if(k<0)
            return -k;
        else
            return k;
    }
};

leetcode-15 3Sum

題意: 給定一串數列,求出是否存在三數相加為零,若存在,輸出三數,注意每組三數不可重複


解題思路:這題是鼎鼎有名的3 sum problem, 在計算幾何學常用,其算法為對數列進行排序,針對每個數字做考慮,舉例來說,有一數列:
-7,-5,-3,-1,4,6,8,10
第一輪先考慮-7,使用兩個指標,start 跟 end, start指向-5,end 指向 10, 因為-7-5+10=-2, 故表示-5不可能和-7同時出現在一組內,因為10已經是目前最大,都還不足以將其變成大於零,故將start右移,依此類推,即可遍歷所有情況,然而此題還有一難點,就是如何去除重複答案,我是用map來達成任務,複雜度主要由指標移動貢獻,由於掃過n個數,每個數兩個指標移動為1~n-3,故複雜度為O(1+2+...+n-3)=
$O(n^2)$


p.s. 此題有更快算法,但非常複雜,請見連結
https://arxiv.org/abs/1404.0799


c++ code如下:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int len=nums.size();
        map<vector<int>,int> ans;
        for(int i=0;i<len-2;i++)
        {
            if(nums[i]==nums[i-1]&&i)
                continue;
            int start=i+1;
            int end=len-1;
            while(start!=end)
            {
                if(nums[start]+nums[end]+nums[i]==0)
                {
                    vector<int>temp;
                    temp.push_back(nums[i]);
                    temp.push_back(nums[start]);
                    temp.push_back(nums[end]);
                    if(!ans.count(temp))
                        ans.insert(make_pair(temp,0));
                    start++;
                }
                else if(nums[start]+nums[end]+nums[i]<0)
                    start++;
                else
                    end--;
            }
        }
        vector<vector<int>> ans1;
        map<vector<int>,int>::iterator it;
        for(it=ans.begin();it!=ans.end();it++)
        {
            ans1.push_back(it->first);
        }
        return ans1;
    }
};

leetcode-14 Longest Common Prefix

題意: 求出一串字串的最大公共前綴字串(longest common prefix)
解題思路: 其實這題蠻簡單的,就一個一個字串做比對,即所求


c++ code:

class Solution { public: string longestCommonPrefix(vector<string>& strs) { int len=strs.size(); if(len==0) return ""; string ans=strs[0]; string temp; for(int i=1;i<len;i++) { int com=min(ans.size(),strs[i].size()); temp=""; for(int j=0;j<com;j++) { if(strs[i][j]==ans[j]) { temp=temp+strs[i][j]; } else break; } ans=temp; } return ans; } };

leetcode-13 Roman to integer

題意: 將羅馬表示法轉為一般十進位表示


解題思路:待補

leetcode-12 Integer to Roman

題意:將整數轉為羅馬表示法

解題思路: 須先了解羅馬表示法規則,可參閱Roman numerals ,接著照規則寫,即所求,複雜度O(1)

C++ code如下:

class Solution {
public:
    string intToRoman(int num) {
        string ans="";
        for(int i=1;i<=num/1000;i++)
            ans=ans+'M';
        num=num%1000;
        if(num/100>=5)
        {
            if(num/100==9)
                ans=ans+"CM";
            else
            {
                ans=ans+'D';
                for(int i=1;i<=num/100-5;i++)
                    ans=ans+'C';
            }
        }
        else
        {
            if(num/100==4)
                ans=ans+"CD";
            else
            {
                for(int i=1;i<=num/100;i++)
                    ans=ans+'C';
            }
        }
        num=num%100;
        if(num/10>=5)
        {
            if(num/10==9)
                ans=ans+"XC";
            else
            {
                ans=ans+'L';
                for(int i=1;i<=num/10-5;i++)
                    ans=ans+'X';
            }
        }
        else
        {
            if(num/10==4)
                ans=ans+"XL";
            else
            {
                for(int i=1;i<=num/10;i++)
                    ans=ans+'X';
            }
        }
        num=num%10;
        if(num>=5)
        {
            if(num==9)
                ans=ans+"IX";
            else
            {
                ans=ans+'V';
                for(int i=1;i<=num-5;i++)
                    ans=ans+'I';
            }
        }
        else
        {
            if(num==4)
                ans=ans+"IV";
            else
            {
                for(int i=1;i<=num;i++)
                    ans=ans+'I';
            }
        }
        return ans;
    }
};

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;
        }
        
    }
};

leetcode-6 ZigZag Conversion

題意: 給定一呈現Zigzag形狀的字串,將其一列一列讀,給出結果


解題思路: 算是我寫到現在最水的一題,把zigzag的圖畫一次,就會發現排在第幾列和mod有關,因此能得知元素在第幾列,逐一加進答案字串,即所求,複雜度O(n),其中n為字串長度


C++ code 如下:

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows==1)
            return s;
        else
        {
            string ans="";
            int len=s.size();
            for(int i=0;i<numRows;i++)
            {
                for(int j=0;j*2*(numRows-1)+i<len;j++)
                {
                    if(i&&i!=(numRows-1))
                    {
                        ans+=s[j*2*(numRows-1)+i];
                        if((j+1)*2*(numRows-1)-i<len)
                            ans+=s[(j+1)*2*(numRows-1)-i];
                    }
                    else
                        ans+=s[j*2*(numRows-1)+i];
                }
            }
            return ans;
        }
    }
};

leetcode-5 Longest Palindromic Substring

題意: 求出最長回文子字串


解題思路:這題有許多解法,比如說動態規劃,不過在這裡筆者採用較為直觀的方法,也就是選定中心點,向兩端擴展,因為從字串內的每個字符考慮的話,其複雜度為$O(n^2)$,和動態規劃一樣,在這裡有個小技巧,可插入無關的元素,來簡化題目,這樣就不需考慮奇偶長度的回文串了,通通視為奇數長度處理


p.s 這題有O(n)算法,稱為Manacher's Algorithm,有需要可自行google


C++ code 如下:

class Solution {
public:
    string longestPalindrome(string s) {
        int len=s.size();
        string ns="";
        int maxl=0;
        
        int left;
        int right;
        for(int i=0;i<len;i++)
        {
            ns=ns+s[i];
            ns=ns+'*';
        }
        int len1=2*len;
        for(int i=0;i<len1;i++)
        {
            int rep=0;
            int j;
            if(ns[i]!='*')
                rep=1;
            for(j=1;(i-j>=0)&&(i+j<len1-1);j++)
            {
                if(ns[i-j]==ns[i+j])
                {
                    if(ns[i-j]!='*')
                        rep+=2;
                }
                else
                    break;
            }
            if(rep>maxl)
            {
                if(ns[i]=='*')
                {
                    left=i/2-rep/2+1;
                    right=i/2+rep/2;
                }
                else
                {
                    left=i/2-(rep-1)/2;
                    right=i/2+(rep-1)/2;
                }
                maxl=rep;
            }
        }
        string ans="";
        for(int i=left;i<=right;i++)
            ans=ans+s[i];
    
        return ans;   
    }
};

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 官方文件