1.Another 16 problems solved.

lintcoder · lintcoder · commit f08eb0122520 · 2017-03-12T21:00:24.000+08:00
diff --git a/167.cpp b/167.cpp
@@ -0,0 +1,33 @@
+vector<int> twoSum(vector<int>& numbers, int target) {
+    vector<int> res(2, -1);
+    int len = numbers.size();
+    for (int i = 0; i < len; ++i)
+    {
+        int index = 0;
+        if (BSearch(numbers, i + 1, len - 1, target - numbers[i], index))
+        {
+            res[0] = i + 1;
+            res[1] = index + 1;
+            break;
+        }
+    }
+    return res;
+}
+
+bool BSearch(vector<int>& numbers, int p, int q, int val, int& index)
+{
+    while (p <= q)
+    {
+        int mid = (p + q) / 2;
+        if (numbers[mid] == val)
+        {
+            index = mid;
+            return true;
+        }
+        else if (numbers[mid] < val)
+            p = mid + 1;
+        else
+            q = mid - 1;
+    }
+    return false;
+}
diff --git a/169.cpp b/169.cpp
@@ -0,0 +1,21 @@
+string convertToBase7(int num) {
+    if (num == 0)
+        return "0";
+    string res;
+    bool flag = true;
+    if (num < 0)
+    {
+        flag = false;
+        num = -num;
+    }
+    while (num != 0)
+    {
+        res.push_back(char(num % 7 + '0'));
+        num /= 7;
+    }
+    reverse(res.begin(), res.end());
+    if (flag == false)
+        res = "-" + res;
+
+    return res;
+}
diff --git a/206.cpp b/206.cpp
@@ -0,0 +1,17 @@
+ListNode* reverseList(ListNode* head) {
+    if (head == NULL || head->next == NULL)
+        return head;
+    ListNode* p = head;
+    ListNode* q = head->next;
+    p->next = NULL;
+    while (q->next != NULL)
+    {
+        ListNode* k = q->next;
+        q->next = p;
+        p = q;
+        q = k;
+    }
+    q->next = p;
+
+    return q;
+}
diff --git a/217.cpp b/217.cpp
@@ -0,0 +1,11 @@
+bool containsDuplicate(vector<int>& nums) {
+    map<int, int> mp;
+    int len = nums.size();
+    for (int i = 0; i < len; ++i)
+    {
+        mp[nums[i]]++;
+        if (mp[nums[i]] > 1)
+            return true;
+    }
+    return false;
+}
diff --git a/268.cpp b/268.cpp
@@ -0,0 +1,7 @@
+int missingNumber(vector<int>& nums) {
+    int len = nums.size();
+    long long sum = 0;
+    for (int i = 0; i < len; ++i)
+        sum += i - nums[i];
+    return sum + len;
+}
diff --git a/350.cpp b/350.cpp
@@ -0,0 +1,17 @@
+vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
+    map<int, int> mp;
+    vector<int> res;
+    int len1 = nums1.size();
+    int len2 = nums2.size();
+    for (int i = 0; i < len1; ++i)
+        mp[nums1[i]]++;
+    for (int i = 0; i < len2; ++i)
+    {
+        if (mp.find(nums2[i]) != mp.end() && mp[nums2[i]] != 0)
+        {
+            res.push_back(nums2[i]);
+            mp[nums2[i]]--;
+        }
+    }
+    return res;
+}
diff --git a/401.cpp b/401.cpp
@@ -0,0 +1,79 @@
+vector<string> readBinaryWatch(int num) {
+    vector<string> res;
+    const int weight[6] = {1, 2, 4, 8, 16, 32};
+    if (num == 0)
+        res.push_back("0:00");
+    else
+    {
+        int beginpos = num >= 7 ? num - 6 : 0;
+        int endpos = num >= 4 ? 4 : num;
+        for (int i = beginpos; i <= endpos; ++i)
+        {
+            vector<string> hour, minute;
+            combination(4, i, weight, hour);
+            combination(6, num - i, weight, minute);
+            int len1 = hour.size(), len2 = minute.size();
+            for (int j = 0; j < len1; ++j)
+            {
+                for (int k = 0; k < len2; ++k)
+                    res.push_back(hour[j] + ":" + minute[k]);
+            }
+        }
+    }
+    return res;
+}
+
+void combination(int total, int n, const int* weight, vector<string>& vec)
+{
+    if (n == 0)
+    {
+        if (total == 4)
+            vec.push_back("0");
+        else
+            vec.push_back("00");
+    }
+    else
+    {
+        docombination(total, n, 0, 0, weight, vec, 0);
+    }
+}
+
+void docombination(int total, int n, int pos, int subsum, const int* weight, vector<string>& vec, int ct)
+{
+    if (ct == n)
+    {
+        if (total == 4 && subsum <= 11)
+        {
+            if (subsum < 10)
+                vec.push_back(string(1, subsum + '0'));
+            else
+                vec.push_back(int2str(subsum));
+        }
+        else if (total == 6 && subsum <= 59)
+        {
+            if (subsum < 10)
+                vec.push_back("0" + string(1, subsum + '0'));
+            else
+                vec.push_back(int2str(subsum));
+        }
+    }
+    else
+    {
+        for (int i = pos; i <= total - n + ct; ++i)
+        {
+            int tmp = subsum + weight[i];
+            docombination(total, n, i + 1, tmp, weight, vec, ct + 1);
+        }
+    }
+}
+
+string int2str(int n)
+{
+    string s;
+    while (n != 0)
+    {
+        s.insert(s.begin(), n % 10 + '0');
+        n /= 10;
+    }
+    return s;
+}
diff --git a/409.cpp b/409.cpp
@@ -0,0 +1,20 @@
+int longestPalindrome(string s) {
+    int alpha[52] = {0};
+    int len = s.size();
+    for (int i = 0; i < len; ++i)
+    {
+        if (islower(s[i]))
+            alpha[s[i] - 'a']++;
+        else
+            alpha[s[i] - 'A' + 26]++;
+    }
+    int sum = 0;
+    int flag = 0;
+    for (int i = 0; i < 52; ++i)
+    {
+        sum += alpha[i] / 2;
+        if (!flag && alpha[i] % 2 == 1)
+            flag = 1;
+    }
+    return sum * 2 + flag;
+}
diff --git a/448.cpp b/448.cpp
@@ -0,0 +1,24 @@
+vector<int> findDisappearedNumbers(vector<int>& nums) {
+    int len = nums.size();
+    int i = 0;
+    while (i < len)
+    {
+        if (nums[i] != i + 1)
+        {
+            int pos = nums[i] - 1;
+            while (nums[pos] != pos + 1)
+            {
+                int tmp = nums[pos];
+                nums[pos] = pos + 1;
+                pos = tmp - 1;
+            }
+        }
+        ++i;
+    }
+    int k = 0;
+    for (int i = 0; i < len; ++i)
+        if (nums[i] != i + 1)
+            nums[k++] = i + 1;
+    nums.resize(k);
+    return nums;
+}
diff --git a/461.cpp b/461.cpp
@@ -0,0 +1,10 @@
+int hammingDistance(int x, int y) {
+    bitset<32> xbit(x);
+    bitset<32> ybit(y);
+    int dist = 0;
+    for (int i = 0; i < 32; ++i)
+        if (xbit[i] != ybit[i])
+            ++dist;
+
+    return dist;
+}
diff --git a/476.cpp b/476.cpp
@@ -0,0 +1,17 @@
+int findComplement(int num) {
+    bitset<32> val(num);
+    int i = 31;
+    while (i >= 0)
+    {
+        if (val[i] == 0)
+            --i;
+        else
+            break;
+    }
+    int sum = 0;
+    for (; i >= 0; --i)
+    {
+        sum = sum * 2 + 1 - val[i];
+    }
+    return sum;
+}
diff --git a/492.cpp b/492.cpp
@@ -0,0 +1,24 @@
+vector<int> constructRectangle(int area) {
+    vector<int> length(2, 0);
+    int limit = sqrt(area);
+    int i = limit;
+    while (i <= area)
+    {
+        if (area % i == 0)
+            break;
+        else
+            ++i;
+    }
+    int j = area / i;
+    if (i > j)
+    {
+        length[0] = i;
+        length[1] = j;
+    }
+    else
+    {
+        length[0] = j;
+        length[1] = i;
+    }
+    return length;
+}
diff --git a/500.cpp b/500.cpp
@@ -0,0 +1,18 @@
+vector<string> findWords(vector<string>& words) {
+    const int pos[26] = {1, 2, 2, 1, 0, 1, 1, 1, 0, 1, 1, 1, 2,
+        2, 0, 0, 0, 0, 1, 0, 0, 2, 0, 2, 0, 2};
+    vector<string> res;
+    int len = words.size();
+    for (int i = 0; i < len; ++i)
+    {
+        int p = pos[tolower(words[i][0]) - 'a'];
+        int sz = words[i].size();
+        int j;
+        for (j = 1; j < sz; ++j)
+            if (pos[tolower(words[i][j]) - 'a'] != p)
+                break;
+        if (j == sz)
+            res.push_back(words[i]);
+    }
+    return res;
+}
diff --git a/504.cpp b/504.cpp
@@ -0,0 +1,21 @@
+string convertToBase7(int num) {
+    if (num == 0)
+        return "0";
+    string res;
+    bool flag = true;
+    if (num < 0)
+    {
+        flag = false;
+        num = -num;
+    }
+    while (num != 0)
+    {
+        res.push_back(char(num % 7 + '0'));
+        num /= 7;
+    }
+    reverse(res.begin(), res.end());
+    if (flag == false)
+        res = "-" + res;
+
+    return res;
+}
diff --git a/506.cpp b/506.cpp
@@ -0,0 +1,43 @@
+vector<string> findRelativeRanks(vector<int>& nums) {
+    vector<string> res;
+    int len = nums.size();
+    if (len == 0)
+        return res;
+    res.resize(len);
+    struct Elem
+    {
+        int val;
+        int pos;
+        Elem(int v, int p):val(v), pos(p){}
+    };
+    vector<Elem> vec;
+    for (int i = 0; i < len; ++i)
+        vec.push_back(Elem(nums[i], i));
+    auto cmp = [=](Elem& a, Elem& b) { return a.val > b.val;};
+    sort(vec.begin(), vec.end(), cmp);
+    for (int i = 0; i < len; ++i)
+    {
+        if (i == 0)
+            res[vec[i].pos] = "Gold Medal";
+        else if (i == 1)
+            res[vec[i].pos] = "Silver Medal";
+        else if (i == 2)
+            res[vec[i].pos] = "Bronze Medal";
+        else
+            res[vec[i].pos] = num2str(i + 1);
+    }
+
+    return res;
+}
+
+string num2str(int num)
+{
+    string str;
+    while (num != 0)
+    {
+        str.push_back(char(num % 10 + '0'));
+        num /= 10;
+    }
+    reverse(str.begin(), str.end());
+    return str;
+}
diff --git a/520.cpp b/520.cpp
