1.10 problems solved.

lintcoder · lintcoder · commit d8638eae93ec · 2017-10-29T10:33:14.000+08:00
diff --git a/122.cpp b/122.cpp
@@ -0,0 +1,31 @@
+int maxProfit(vector<int>& prices) {
+     int len = prices.size();
+     if (len <= 1)
+     	return 0;
+     int pr = prices[0];
+     int profit = 0;
+     int i = 1;
+     while (i < len)
+     {
+     	if (prices[i] <= pr)
+        {
+            pr = prices[i];
+            ++i;
+        }
+     	else
+     	{
+     		while (i + 1 < len && prices[i + 1] >= prices[i])
+     			++i;
+     		profit += prices[i]-pr;
+     		if (i >= len - 2)
+     			break;
+     		else
+     		{
+     			pr = prices[i + 1];
+     			i += 2;
+     		}
+     	}
+     }
+
+     return profit;  
+    }
diff --git a/13.cpp b/13.cpp
@@ -0,0 +1,62 @@
+int romanToInt(string s) {
+        map<char, int> mp;
+        mp['I'] = 1;
+        mp['V'] = 5;
+        mp['X'] = 10;
+        mp['L'] = 50;
+        mp['C'] = 100;
+        mp['D'] = 500;
+        mp['M'] = 1000;
+
+        int len = s.size();
+        char c = s[0];
+        int sum = 0;
+        int val = mp[c];
+        int i = 1;
+        bool flag = true;
+        while (i < len)
+        {
+            if (s[i] == c)
+            {
+                val += mp[c];
+                if (!flag)
+                {
+                    sum += val;
+                    val = 0;
+                    flag = true;
+                    ++i;
+                    if (i == len)
+                        break;
+                    c = s[i];
+                    val = mp[c];
+                    ++i;
+                }
+                else
+                    ++i;
+            }
+            else if (mp[s[i]] < mp[c])
+            {
+                sum += val;
+                val = mp[s[i]];
+                c = s[i];
+                flag = false;
+                ++i;
+            }
+            else
+            {
+                sum += -val + mp[s[i]];
+                val = 0;
+                flag = true;
+                ++i;
+                if (i == len)
+                    break;
+                c = s[i];
+                val = mp[c];
+                ++i;
+            }
+        }
+        if (val != 0)
+        	sum += val;
+
+        return sum;
+    }
diff --git a/447.cpp b/447.cpp
@@ -0,0 +1,50 @@
+int numberOfBoomerangs(vector<pair<int, int>>& points) {
+        int sz = points.size();
+        int** distance = new int* [sz];
+        for (int i = 0; i != sz; ++i)
+            distance[i] = new int[sz];
+        for (int i = 0; i != sz; ++i)
+        {
+            for (int j = i; j != sz; ++j)
+            {
+                if (i == j)
+                    distance[i][j] = 0;
+                else 
+                {
+                    int dx = points[i].first - points[j].first;
+                    int dy = points[i].second - points[j].second;
+                    distance[j][i] = distance[i][j] = dx * dx + dy * dy;
+                }
+            }
+            sort(distance[i], distance[i] + sz);
+        }
+        
+        int sum = 0;
+        for (int i = 0; i != sz; ++i)
+        {
+            int tmpdist = distance[i][0];
+            int j = 1;
+            int cnt = 1;
+            while (j < sz)
+            {
+                if (distance[i][j] == tmpdist)
+                    ++cnt;
+                else
+                {
+                    if (cnt > 1)
+                        sum += cnt * (cnt - 1);
+                    tmpdist = distance[i][j];
+                    cnt = 1;
+                }
+                ++j;
+            }
+            if (cnt > 1)
+                sum += cnt * (cnt - 1);
+        }
+
+        for (int i = 0; i != sz; ++i)
+            delete[] distance[i];
+        delete[] distance;
+        
+        return sum;
+    }
diff --git a/530.cpp b/530.cpp
@@ -0,0 +1,25 @@
+int getMinimumDifference(TreeNode* root) {
+        vector<int> vec;
+        add2vec(vec, root);
+        sort(vec.begin(), vec.end());
+        
+        int len = vec.size();
+        int min_diff = abs(vec[1] - vec[0]);
+        for (int i = 2; i < len; ++i)
+        {
+            int diff = abs(vec[i] - vec[i - 1]);
+            if (diff < min_diff)
+                min_diff = diff;
+        }
+        
+        return min_diff;
+    }
+    
+    void add2vec(vector<int>& vec, TreeNode* root)
+    {
+        if (root == NULL)
+            return;
+        vec.push_back(root->val);
+        add2vec(vec, root->left);
+        add2vec(vec, root->right);
+    }
diff --git a/538.cpp b/538.cpp
@@ -0,0 +1,46 @@
+TreeNode* convertBST(TreeNode* root) {
+        if (root == nullptr)
+        	return nullptr;
+        deque<int> dq;
+        if (root->left != nullptr)
+        	getBSTValue(root->left, dq);
+        dq.push_back(root->val);
+        if (root->right != nullptr)
+        	getBSTValue(root->right, dq);
+
+        int len = dq.size();
+        int sum = dq[len - 1];
+        for (int i = len - 2; i >= 0; --i)
+        {
+        		int val = dq[i];
+        		dq[i] += sum;
+        		sum += val;
+        }
+
+        int count = 0;
+        if (root->left != nullptr)
+        	setBSTValue(root->left, dq, count);
+        root->val = dq[count++];
+        if (root->right != nullptr)
+        	setBSTValue(root->right, dq, count);
+
+        return root;
+    }
+
+    void getBSTValue(TreeNode* node, deque<int>& dq)
+    {
+        if (node->left != nullptr)
+            getBSTValue(node->left, dq);
+        dq.push_back(node->val);
+        if (node->right != nullptr)
+            getBSTValue(node->right, dq);
+    }
+
+    void setBSTValue(TreeNode* node, deque<int>& dq, int& count)
+    {
+        if (node->left != nullptr)
+            setBSTValue(node->left, dq, count);
+        node->val = dq[count++];
+        if (node->right != nullptr)
+            setBSTValue(node->right, dq, count);
+    }
diff --git a/551.cpp b/551.cpp
@@ -0,0 +1,39 @@
+bool checkRecord(string s) {
+        size_t len = s.size();
+        if (len <= 1)
+            return true;
+        
+        int num_A = 0, num_L = 0;
+        char status = s[0];
+        if (status == 'A')
+            num_A++;
+        else if (status == 'L')
+            num_L++;
+        size_t i = 1;
+        while (i < len)
+        {
+            if (s[i] == 'P')
+            {
+                status = s[i];
+                num_L = 0;
+            }
+            else if (s[i] == 'A')
+            {
+                if (num_A == 1)
+                    return false;
+                num_A = 1;
+                num_L = 0;
+                status = s[i];
+            }
+            else
+            {
+                if (num_L == 2)
+                    return false;
+                num_L++;
+                status = s[i];
+            }
+            i++;
+        }
+        
+        return true;
+    }
diff --git a/563.cpp b/563.cpp
@@ -0,0 +1,14 @@
+int findTilt(TreeNode* root) {
+        if (root == NULL)
+            return 0;
+        else
+            return abs(subSum(root->left) - subSum(root->right)) + findTilt(root->left) + findTilt(root->right);
+    }
+
+    
+    int subSum(TreeNode* node)
+    {
+        if (node == NULL)
+            return 0;
+        return node->val + subSum(node->left) + subSum(node->right);
+    }
diff --git a/598.cpp b/598.cpp
@@ -0,0 +1,17 @@
+int maxCount(int m, int n, vector<vector<int>>& ops) {
+        int row = ops.size();
+        if (row == 0)
+        	return m*n;
+        int col = ops[0].size();
+
+        int minrow = ops[0][0], mincol = ops[0][1];
+        for (int i = 1; i < row; ++i)
+        {
+            if (ops[i][0] < minrow)
+                minrow = ops[i][0];
+            if (ops[i][1] < mincol)
+                mincol = ops[i][1];
+        }
+
+        return minrow * mincol;
+    }
diff --git a/599.cpp b/599.cpp
@@ -0,0 +1,54 @@
+vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
+        using SI = map<string, int>;
+        SI mp1, mp2;
+        int len1 = list1.size(), len2 = list2.size();
+        if (len1 == 0 || len2 == 0)
+            return {};
+        
+        for (int i = 0; i < len1; ++i)
+        {
+            mp1.insert(pair<string, int>(list1[i], i));
+        }
+        for (int i = 0; i < len2; ++i)
+        {
+            mp2.insert(pair<string, int>(list2[i], i));
+        }
+        
+        vector<string> res;
+        int index = 0, ct = 0;
+        int maxindex = 0;
+        for (int i = 0; i < len1; ++i)
+        {
+            if (mp2.find(list1[i]) != mp2.end())
+            {
+                string s = list1[i];
+                int sumindex = mp1[s] + mp2[s];
+                if (maxindex == 0)
+                {
+                    if (ct == 0)
+                    {
+                        maxindex = sumindex;
+                        ct++;
+                        res.push_back(s);
+                    }
+                }
+                else
+                {
+                    if (maxindex == sumindex)
+                    {
+                        res.push_back(s);
+                        ct++;
+                    }
+                    else if (maxindex > sumindex)
+                    {
+                        res.push_back(s);
+                        maxindex = sumindex;
+                        index = ct;
+                        ct++;
+                    }
+                }
+            }
+        }
+        
+        return vector<string>(res.begin() + index, res.end());
+    }
diff --git a/690.cpp b/690.cpp
@@ -0,0 +1,24 @@
+int getImportance(vector<Employee*> employees, int id) {
+        map<int, Employee*> mp;
+        int len = employees.size();
+        for (int i = 0; i < len; ++i)
+        	mp.insert(pair<int, Employee*>(employees[i]->id, employees[i]));
+
+        deque<Employee*> dq;
+        dq.push_back(mp[id]);
+        int sum = 0;
+        while (!dq.empty())
+        {
+        	int sz = dq.size();
+        	for (int i = 0; i < sz; ++i)
+        	{
+        		sum += dq[i]->importance;
+        		len = dq[i]->subordinates.size();
+        		for (int j = 0; j < len; ++j)
+        			dq.push_back(mp[dq[i]->subordinates[j]]);
+        	}
+        	dq.erase(dq.begin(), dq.begin() + sz);
+        }
+
+        return sum;
+    }
