5 problems solved.

lintcoder · lintcoder · commit 8ddbe4678d28 · 2018-04-28T16:51:10.000+08:00
diff --git a/src/151.cpp b/src/151.cpp
@@ -0,0 +1,31 @@
+void reverseWords(string &s) {
+     int len = s.size();
+     vector<string> word;
+
+     int index = s.find_first_not_of(' ');
+     if (index == string::npos)
+     {
+         s = "";
+         return;
+     }
+
+     while (index != string::npos && index < len)
+     {
+     	int pos = s.find_first_of(' ', index);
+     	if (pos == string::npos)
+     	{
+     		word.push_back(s.substr(index));
+     		break;
+     	}
+     	else
+     	{
+     		word.push_back(s.substr(index, pos-index));
+     		index = s.find_first_not_of(' ', pos);
+     	}
+     }
+     len = word.size();
+     s = "";
+     for (int i = len-1; i > 0; --i)
+         s += word[i] + " ";
+     s += word[0];
+    }
diff --git a/src/165.cpp b/src/165.cpp
@@ -0,0 +1,90 @@
+int compareVersion(string version1, string version2) {
+        int len1 = version1.size();
+        int len2 = version2.size();
+        int i = 0, j = 0;
+        while (i < len1 && j < len2)
+        {
+            int pos1 = version1.find('.', i);
+            int pos2 = version2.find('.', j);
+            if (pos1 == string::npos)
+            {
+                if (pos2 == string::npos)
+                    return docmp(version1.substr(i), version2.substr(j));
+                else
+                {
+                    string mainversion2 = version2.substr(j, pos2 - j);
+                    int res = docmp(version1.substr(i), mainversion2);
+                    if (res != 0)
+                        return res;
+                    else
+                        return -1 * is_subversion_zero(version2.substr(pos2 + 1));
+                }
+            }
+            else
+            {
+                string subversion1 = version1.substr(i, pos1 - i);
+                if (pos2 == string::npos)
+                {
+                    int res = docmp(subversion1, version2.substr(j));
+                    if (res != 0)
+                        return res;
+                    else
+                        return is_subversion_zero(version1.substr(pos1 + 1));
+                }
+                else
+                {
+                    string subversion2 = version2.substr(j, pos2 - j);
+                    int res = docmp(subversion1, subversion2);
+                    if (res != 0)
+                        return res;
+                    else
+                    {
+                        i = pos1 + 1;
+                        j = pos2 + 1;
+                    }
+                }
+            }
+        }
+        return 0;
+    }
+
+    int docmp(const string& version1, const string& version2)
+    {
+        int first_num1 = version1.find_first_not_of('0');
+        int first_num2 = version2.find_first_not_of('0');
+        string v1, v2;
+        if (first_num1 == string::npos)
+            v1 = "0";
+        else
+            v1 = version1.substr(first_num1);
+        if (first_num2 == string::npos)
+            v2 = "0";
+        else
+            v2 = version2.substr(first_num2);
+        int len1 = v1.size();
+        int len2 = v2.size();
+        if (len1 < len2)
+            return -1;
+        else if (len1 == len2)
+        {
+            if (v1 < v2)
+                return -1;
+            else if (v1 == v2)
+                return 0;
+            else
+                return 1;
+        }
+        else
+            return 1;
+    }
+
+    int is_subversion_zero(const string& str)
+    {
+        int len = str.size();
+        for (int i = 0; i < len; ++i)
+        {
+            if (str[i] != '0' && str[i] != '.')
+                return 1;
+        }
+        return 0;
+    }
diff --git a/src/2.cpp b/src/2.cpp
@@ -0,0 +1,46 @@
+ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
+        if (l1 == nullptr)
+        	return l2;
+        if (l2 == nullptr)
+        	return l1;
+
+        int sum = l1->val + l2->val;
+        int ct = sum/10;
+        ListNode* h = new ListNode(sum%10);
+        ListNode* node = h;
+        l1 = l1->next;
+        l2 = l2->next;
+        while (l1 && l2)
+        {
+        	sum = l1->val + l2->val + ct;
+        	node->next = new ListNode(sum%10);
+        	ct = sum/10;
+        	node = node->next;
+            l1 = l1->next;
+            l2 = l2->next;
+        }
+        while (l1)
+        {
+        	sum = l1->val + ct;
+        	node->next = new ListNode(sum%10);
+        	ct = sum/10;
+        	node = node->next;
+            l1 = l1->next;
+        }
+        while (l2)
+        {
+        	sum = l2->val + ct;
+        	node->next = new ListNode(sum%10);
+        	ct = sum/10;
+        	node = node->next;
+            l2 = l2->next;
+        }
+        if (ct != 0)
+        {
+        	node->next = new ListNode(ct);
+            node = node->next;
+        }
+        node->next = nullptr;
+
+        return h;
+    }
diff --git a/src/43.cpp b/src/43.cpp
@@ -0,0 +1,59 @@
+string multiply(string num1, string num2) {
+     int len1 = num1.size();
+     int len2 = num2.size();
+     if (len1 == 0 || len2 == 0)
+     	return "";
+     if (num1 == "0" || num2 == "0")
+        return "0";
+
+     vector<string> subsum;
+     vector<int> digitlen;
+     int sum, ct;
+     for (int i = len2-1; i >= 0; --i)
+     {
+        if (num2[i] == '0')
+            continue;
+        sum = 0;
+        ct = 0;
+     	string s(len2-1-i, '0');
+     	for (int j = len1-1; j >= 0; --j)
+     	{
+     		sum = (num2[i]-'0') * (num1[j]-'0') + ct;
+     		s.push_back(sum%10+'0');
+     		ct = sum/10;
+     	}
+     	if (ct > 0)
+     		s.push_back(ct+'0');
+     	subsum.push_back(s);
+     	digitlen.push_back(s.size());
+     }
+
+     string res;
+     int len = subsum.size();
+     int i = 0;
+     ct = 0;
+     while (true)
+     {
+     	sum = 0;
+     	bool flag = false;
+     	for (int j = 0; j < len; ++j)
+     	{
+     		if (i < digitlen[j])
+     		{
+     			sum += subsum[j][i] - '0';
+     			flag = true;
+     		}
+     	}
+     	if (!flag)
+     		break;
+     	sum += ct;
+     	res.push_back(sum%10+'0');
+     	ct = sum/10;
+     	++i;
+     }
+     if (ct > 0)
+     	res.push_back(ct+'0');
+
+     reverse(res.begin(), res.end());
+     return res;
+   }
diff --git a/src/791.cpp b/src/791.cpp
@@ -0,0 +1,16 @@
+string customSortString(string S, string T) {
+        int len = S.size();
+        if (len <= 1)
+        	return T;
+
+        vector<int> prio(26, -1);
+        for (int i = 0; i < len; ++i)
+        	prio[S[i]-'a'] = i;
+
+        auto cmp = [=](char a, char b) {
+        	return prio[a-'a'] < prio[b-'a'];
+        };
+
+        sort(T.begin(), T.end(), cmp);
+        return T;
+    }
