Solved 10 problems.

lintcoder · lintcoder · commit 3c857858397c · 2018-04-17T21:06:52.000+08:00
diff --git a/src/14.cpp b/src/14.cpp
@@ -0,0 +1,38 @@
+string longestCommonPrefix(vector<string>& strs) {
+        string prefix;
+        int sz = strs.size();
+        if (sz == 0)
+            return prefix;
+        else if (sz == 1)
+            return strs[0];
+        else
+        {
+            int minlen = strs[0].size();
+            for (int i = 1; i < sz; ++i)
+            {
+                int len = strs[i].size();
+                if (len < minlen)
+                    minlen = len;
+            }
+            
+            int i, j = 0;
+            while (j < minlen)
+            {
+                char c = strs[0][j];
+                for (i = 1; i < sz; ++i)
+                {
+                    if (strs[i][j] != c)
+                        break;
+                }
+                if (i != sz)
+                    break;
+                else
+                {
+                    prefix.push_back(c);
+                    ++j;
+                }
+            }
+            
+            return prefix;
+        }
+    }
diff --git a/src/203.cpp b/src/203.cpp
@@ -0,0 +1,32 @@
+ListNode* removeElements(ListNode* head, int val) {
+        ListNode* p = head, *q;
+        while (p != NULL && p->val == val)
+        {
+            q = p->next;
+            delete p;
+            p = q;
+        }
+        if (p == NULL)
+            return NULL;
+        head = p;
+        q = p->next;
+        while (q != NULL)
+        {
+            while (q != NULL && q->val == val)
+            {
+                ListNode* k = q->next;
+                delete q;
+                q = k;
+            }
+            if (q != NULL)
+            {
+                p->next = q;
+                p = q;
+                q = q->next;
+            }
+            else
+                p->next = q;
+        }
+        
+        return head;
+    }
diff --git a/src/219.cpp b/src/219.cpp
@@ -0,0 +1,38 @@
+bool containsNearbyDuplicate(vector<int>& nums, int k) {
+        int sz = nums.size();
+        vector<Elem> vec;
+        for (int i = 0; i != sz; ++i)
+            vec.push_back(Elem(nums[i], i));
+        sort(vec.begin(), vec.end(), cmp);
+        
+        int i = 0, j = 0;
+        while (i < sz)
+        {
+            int val = vec[i].val;
+            j = i + 1;
+            while (j < sz && vec[j].val == val)
+            {
+                if (vec[j].pos - vec[i].pos <= k)
+                    return true;
+                else
+                {
+                    i = j;
+                    ++j;
+                }
+            }
+            if (j == sz)
+                return false;
+            else
+                i = j;
+        }
+        return false;
+    }
+    struct Elem{
+        int val;
+        int pos;
+        Elem(int v, int p) : val(v), pos(p){}
+    };
+    static bool cmp(Elem a, Elem b)
+    {
+        return a.val < b.val || a.pos < b.pos; 
+    }
diff --git a/src/234.cpp b/src/234.cpp
@@ -0,0 +1,36 @@
+bool isPalindrome(ListNode* head) {
+        ListNode* p = head;
+        int num = 0;
+        while (p != NULL)
+        {
+            p = p->next;
+            num++;
+        }
+        int lim = num / 2;
+        int n = 0;
+        if (lim > 0)
+        {
+            ListNode* h = head;
+            ListNode* q = h->next;
+            h->next = NULL;
+            n++;
+            while (n < lim)
+            {
+                p = q->next;
+                q->next = h;
+                h = q;
+                q = p;
+                n++;
+            }
+            if (num % 2 == 1)
+                q = q->next;
+            while (h != NULL && q != NULL)
+            {
+                if (h->val != q->val)
+                    return false;
+                h = h->next;
+                q = q->next;
+            }
+        }
+        return true;
+    }
diff --git a/src/290.cpp b/src/290.cpp
@@ -0,0 +1,40 @@
+bool wordPattern(string pattern, string str) {
+        vector<string> bijection(26, "");
+        set<string> stjection;
+        int sz = pattern.size();
+        
+        if (sz == 0)
+            return false;
+        char c;
+        int index = 0, pos = 0;
+        for (int i = 0; i != sz; ++i)
+        {
+            c = pattern[i];
+            if (i < sz - 1)
+                pos = str.find(' ', index);
+            else
+                pos = sz;
+            if (pos == -1)
+                return false;
+            else
+            {
+                string s = str.substr(index, pos - index);
+                string bi = bijection[c - 'a'];
+                if (bi != "")
+                {
+                    if (bi != s)
+                        return false;
+                }
+                else
+                {
+                    if (stjection.find(s) != stjection.end())
+                        return false;
+                    bijection[c - 'a'] = s;
+                    stjection.insert(s);
+                }
+            }
+            index = pos + 1;
+        }
+        
+        return true;
+    }
diff --git a/src/303.cpp b/src/303.cpp
@@ -0,0 +1,16 @@
+public:
+    NumArray(vector<int> nums) {
+            int len = nums.size();
+            arry.assign(len, 0);
+            for (int i = 0; i < len; ++i)
+                arry[i] = nums[i];
+        }
+    
+    int sumRange(int i, int j) {
+        int sum = arry[i];
+        for (int m = i + 1; m <= j; ++m)
+            sum += arry[m];
+        return sum;
+    }
+private:
+    vector<int> arry;
diff --git a/src/507.cpp b/src/507.cpp
@@ -0,0 +1,11 @@
+bool checkPerfectNumber(int num) {
+        if (num <= 1)
+        	return false;
+        int lim = sqrt(num);
+        int sum = 1;
+        for (int i = 2; i <= lim; ++i)
+        	if (num % i == 0)
+        		sum += i + num/i;
+        	
+        return sum == num;
+    }
diff --git a/src/58.cpp b/src/58.cpp
@@ -0,0 +1,18 @@
+int lengthOfLastWord(string s) {
+        int sz = s.size();
+        int len = 0;
+        int p = 0, q = 0;
+        while (p < sz)
+        {
+            p = s.find_first_not_of(' ', q);
+            if (p == string::npos)
+                break;
+            q = s.find(' ', p);
+            if (q == string::npos)
+                break;
+            len = q - p;
+        }
+        if (q == string::npos)
+            len = sz - p;
+        return len;
+    }
diff --git a/src/633.cpp b/src/633.cpp
@@ -0,0 +1,11 @@
+bool judgeSquareSum(int c) {
+        int lim = sqrt(c/2);
+        for (int i = 0; i <= lim; ++i)
+        {
+            int remain = c - i*i;
+            int tmp = sqrt(remain);
+            if (tmp * tmp == remain)
+                return true;
+        }
+        return false;
+    }
diff --git a/src/88.cpp b/src/88.cpp
@@ -0,0 +1,23 @@
+void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
+        int* arr = new int[m + n];
+        int i = 0, j = 0, k = 0;
+        while (i < m && j < n)
+        {
+            if (nums1[i] <= nums2[j])
+            {
+                arr[k++] = nums1[i];
+                i++;
+            }
+            else
+            {
+                arr[k++] = nums2[j];
+                j++;
+            }
+        }
+        while (i < m)
+            arr[k++] = nums1[i++];
+        while (j < n)
+            arr[k++] = nums2[j++];
+        nums1.assign(arr, arr + m + n);
+        delete[] arr;
+    }
