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