leetcode-23 Merge k Sorted Lists

題意:合併k個已排序的linkedlist

解題思路:這題我是把全部的元素丟進c++ stl 的priority queue裡,能通過測試,但時間和空間複雜度太大,但我還是先貼我過的code,待我之後再刷到這時,再更新更快做法

效率更高做法: http://bangbingsyb.blogspot.tw/2014/11/leetcode-merge-k-sorted-lists.html

C++ code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    
public:
     struct cmp 
     { 
        bool operator()(ListNode* x,ListNode*  y) 
        { 
            return x->val > y->val; 
        } 
     }; 
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        int len=lists.size();
        
        for(int i=0;i<len;i++)
        {
            ListNode* par=lists[i]; 
            while(par!=NULL)
            {
                pq.push(par);
                par=par->next;
            }
        }
        ListNode* ori=new ListNode(0);
        ListNode* cur=ori;
        while(!pq.empty())
        {
            cur->next=pq.top();
            pq.pop();
            cur=cur->next;
            
        }
        cur->next=NULL;
        return ori->next;
    }
};

leetcode-22 Generate Parentheses

題意: 給定一數字n, 求出由n個左括弧和n個右括弧所形成的所有合理序列

解題思路: 其實這題一開始看到蠻傻眼的,後來想了想,如何才能合乎規則呢,也就是從頭開始的所有子字串(substring),其中的左括弧數量都要大於等於右括弧數量,當然,我們還要確保左右括弧數量都小於等於n,其實就類似高中排列組合的一路領先問題,所以我們每次都從右邊加括弧,並確保規則成立

code如下:

class Solution {
public:
    vector<string> ans;
   
    vector<string> generateParenthesis(int n) {
        generate("(",2*n,1,0);
        return ans;
    }
    
    void generate(string s,int total,int left,int right)
    {
        if(s.length()==total)
            ans.push_back(s);
        
        else if(s.length()<total)
        {
            if(left>=right)
            {
                if(left<total/2)
                    generate(s+"(",total,left+1,right);
                if(left>right)
                    generate(s+")",total,left,right+1);
            }
        }
       
    }
};

台灣雨量app

終於發布第二個app了,歡迎下載,網址如下:

https://play.google.com/store/apps/details?id=tw.blogspot.httpcodecrazer.taiwanrain

leetcode-21 Merge Two Sorted Lists

題意: 合併兩個已經排序好的linked list

解法: 面對linked list題目時,為了方便處理,都可以自己先創造一個原點(ori),最後再回傳ori->next即可

程式碼如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* ori= new ListNode(0);
        ListNode* head=ori;
        while(l1!=NULL||l2!=NULL)
        {
             if(l1==NULL)
             {
                head->next=l2;
                break;
             }
             if(l2==NULL)
             {
                head->next=l1;
                break;
             }
            if(l1->val<l2->val)
            {
                head->next=l1;
                l1=l1->next;
                head=head->next;
            }
            else
            {
                 head->next=l2;
                 l2=l2->next;
                 head=head->next;
            }
        }
        return ori->next;
    }
};

leetcode-20 Valid Parentheses

題意: 判定括號是否按規則排列

解題思路: stack經典例題,利用C++ STL stack 實現

程式碼如下:

class Solution {
public:
    bool isValid(string s) {
        stack <int> check;
        int len=s.length();
        for(int i=0;i<len;i++)
        {
            if(s[i]=='('||s[i]=='{'||s[i]=='[')
                check.push(s[i]);
            else
            {
                if(check.size()==0)
                    return false;
                if(s[i]==')')
                {
                    if(check.top()=='(')
                        check.pop();
                    else
                        return false;
                }
                else if(s[i]==']')
                {
                    if(check.top()=='[')
                        check.pop();
                    else
                        return false;
                }
                 else
                {
                    if(check.top()=='}')
                        check.pop();
                    else
                        return false;
                }
            }
                    
        }
        if(check.size()!=0)
            return false;
        else
            return true;
    }
};

leetcode-19 remove nth node from end of list

題意: 給定一linked list, 移除倒數第n 個元素,只能遍歷一次

解題思路: 只能掃一次,這個條件還蠻煩的,訣竅就是用一個array把每個指標都存起來,至於linked list可以新增一個頭插在最前面,這樣處理起來會方便許多,這樣複雜度為O(N),空間複雜度為O(N), N為linked list 長度

p.s. leetcode上的解答為使用兩個指標,彼此相距n,同時移動,當其中一指標到達底時,另一指標即為要移除的指標,這個做法時間複雜度為O(N) (雖然和我的作法時間複雜度一樣,但實際上會較慢,因為多掃了n個元素),空間複雜度為O(1)

程式碼如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int count=0;
        ListNode* arr[10000];
        ListNode* ori=new ListNode(0);
        arr[0]=ori;
        ori->next=head;
        
        while(head!=NULL)
        {
            count++;
            arr[count]=head;
            head=head->next;
        }
        
        if(count-n+2<=count)
            arr[count-n]->next=arr[count-n+2];
        else
            arr[count-n]->next=NULL;
        return  ori->next;
        
    }
};

leetcode-18 4sum

題意: 給定數列,求出其中所有四數和為特定值的數組,輸出不可重複

解題思路:其實可以把之前的題目拿來比對一下

之前我們有解過
2 sum, 利用map
3 sum, 轉為 2 sum, 利用map

同理,我們也能把這個題目先轉為3 sum,而後轉2 sum處理, 只是之前解3 sum時, 發現vector 用map實在太慢, 因此這次利用迴圈判定, 來解決數組重複為題,其原理如下,若目前判定的數和前一個相同,則可略過,為什麼呢,因為每個位置只能放一個數,若其與之前相同,則表示此種可能已被判定,故一定要跳過,以免重複

程式碼如下:

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

How to sort filter listview in android

When you use custom arrayadapter and listview in android, you may want to filter and sort the data, however, it is really often that sort and filter work well separately, however when you combine this two, the sort doesn't!
Below is my original code(not work):

public boolean onQueryTextChange(String newText) {
    xAdapter.getFilter().filter(newText, new Filter.FilterListener() {
        @Override
            public void onFilterComplete(int count){
                TextView one= (TextView) findViewById(R.id.xsort);
                one.setOnClickListener(new View.OnClickListener() {
                    @Override
                    public void onClick(View v) {
                        lsort(xListView);
                    }
                });
            }
        });

        return false;
}

After working for many hours, I found that the xListview is the same, it wasn't filtered, so I sort xListview before, then filter it, this time it works perfectly, the code is provided below!

// made newText final
public boolean onQueryTextChange(final String newText) {
    xAdapter.getFilter().filter(newText, new Filter.FilterListener() {
        @Override
            public void onFilterComplete(int count){
                TextView one= (TextView) findViewById(R.id.xsort);
                one.setOnClickListener(new View.OnClickListener() {
                    @Override
                    public void onClick(View v) {
                        lsort(xListView);
                        xAdapter.getFilter().filter(newText)// add this line

                    }
                });
            }
        });

        return false;
}