10 problems solved.

lintcoder · lintcoder · commit 2e109d82ad27 · 2018-05-06T20:56:51.000+08:00
diff --git a/src/143.cpp b/src/143.cpp
@@ -0,0 +1,45 @@
+void reorderList(ListNode* head) {
+     if (head == nullptr || head->next == nullptr || head->next->next == nullptr)
+     return;
+
+     ListNode* h = head;
+     int i = 0;
+     while (h != nullptr)
+     {
+     	h = h->next;
+     	++i;
+     }
+     int n = i%2 == 0 ? i/2 : i/2+1;
+     h = head;
+     ListNode* fronthalf = h;
+     ListNode* node = h;
+     while (n-- > 1)
+     	node = node->next;
+     ListNode* s = node->next;
+     node->next = nullptr;
+
+     node = s;
+     ListNode* backhalf = node;
+     node = node->next;
+     backhalf->next = nullptr;
+     s = nullptr;
+     while (node != nullptr)
+     {
+     	s = node->next;
+     	node->next = backhalf;
+     	backhalf = node;
+     	node = s;
+     }
+     head = fronthalf;
+     node = fronthalf;
+     s = backhalf;
+     while (node != nullptr && s != nullptr)
+     {
+     	ListNode* tmp = node->next;
+     	node->next = s;
+     	node = tmp;
+     	ListNode* tmp2 = s->next;
+     	s->next = tmp;
+     	s = tmp2;
+     }
+    }
diff --git a/src/144.cpp b/src/144.cpp
@@ -0,0 +1,20 @@
+vector<int> preorderTraversal(TreeNode* root) {
+        vector<int> res;
+        if (root == nullptr)
+        	return res;
+        deque<TreeNode*> dq;
+        dq.push_back(root);
+
+        while (!dq.empty())
+        {
+        	TreeNode* node = dq.back();
+        	dq.pop_back();
+        	res.push_back(node->val);
+        	if (node->right != nullptr)
+        		dq.push_back(node->right);
+        	if (node->left != nullptr)
+        		dq.push_back(node->left);
+        }
+
+        return res;
+    }
diff --git a/src/477.cpp b/src/477.cpp
@@ -0,0 +1,23 @@
+int totalHammingDistance(vector<int>& nums) {
+	    int len = nums.size();
+	    if (len < 2)
+	    	return 0;
+
+        vector<bitset<32>> bs(len, bitset<32>(0));
+        for (int i = 0; i < len; ++i)
+        	bs[i] = nums[i];
+
+        int ct = 0;
+        int flag[32][2] = {0};
+        for (int i = 0; i < len; ++i)
+        {
+        	for (int j = 0; j < 32; ++j)
+        	{
+        		flag[j][bs[i][j]]++;
+        	}
+        }
+
+        for (int i = 0; i < 32; ++i)
+        	ct += flag[i][0] * flag[i][1];
+        return ct;
+    }
diff --git a/src/503.cpp b/src/503.cpp
@@ -0,0 +1,57 @@
+vector<int> nextGreaterElements(vector<int>& nums) {
+         vector<int> res;
+         int sz = nums.size();
+
+         for (int i = 0; i < sz; ++i)
+         {
+            if (!findNextGreater(nums, res, nums[i], (i+1)%sz, (i+sz-1)%sz, sz))
+                res.push_back(-1);
+         }
+
+         return res;
+     }
+
+     bool findNextGreater(const vector<int>& nums, vector<int>& res, int val, int p, int q, int sz)
+     {
+        if (p == q)
+        {
+            if (nums[p] > val)
+            {
+                res.push_back(nums[p]);
+                return true;
+            }
+            else
+                return false;
+        }
+        else if (p == q - 1)
+        {
+            if (nums[p] > val)
+            {
+                res.push_back(nums[p]);
+                return true;
+            }
+            if (nums[q] > val)
+            {
+                res.push_back(nums[q]);
+                return true;
+            }
+            return false;
+        }
+        else if (p < q)
+        {
+            int mid = (p + q)/2;
+            if (findNextGreater(nums, res, val, p, mid-1, sz))
+                return true;
+            if (nums[mid] > val)
+            {
+                res.push_back(nums[mid]);
+                return true;
+            }
+            return findNextGreater(nums, res, val, mid+1, q, sz);
+        }
+        else
+        {
+            return findNextGreater(nums, res, val, p, sz - 1, sz) || findNextGreater(nums, res, val, 0, q, sz);
+        }
+
+     }
diff --git a/src/547.cpp b/src/547.cpp
@@ -0,0 +1,38 @@
+int findCircleNum(vector<vector<int>>& M) {
+        int num = M.size();
+        int count = 0;
+        for (int i = 0; i < num; ++i)
+        {
+            if (M[i][i] == 1)
+            {
+                M[i][i] = -1;
+                for (int j = 0; j < num; ++j)
+                {
+                    if (j != i && M[i][j] == 1)
+                    {
+                        M[i][j] = M[j][i] = -1;
+                        doSubFind(M, j, num);
+                    }
+                }
+                count++;
+            }
+        }
+
+        return count;
+    }
+
+    void doSubFind(vector<vector<int>>& M, int row, const int num)
+    {
+        if (M[row][row] == 1)
+        {
+            M[row][row] = -1;
+            for (int i = 0; i < num; ++i)
+            {
+                if (i != row && M[row][i] == 1)
+                {
+                    M[row][i] = M[i][row] = -1;
+                    doSubFind(M, i, num);
+                }
+            }
+        }
+    }
diff --git a/src/648.cpp b/src/648.cpp
@@ -0,0 +1,46 @@
+string replaceWords(vector<string>& dict, string sentence) {
+        auto cmp = [](string& a, string& b) {
+        	return a.size() < b.size();
+        };
+        sort(dict.begin(), dict.end(), cmp);
+
+        string res;
+        int index = 0;
+        int len = sentence.size();
+        int num = dict.size();
+        while (index < len)
+        {
+                string replacestr;
+        		int pos = sentence.find(' ', index);
+        		if (pos == string::npos)
+        		{
+        			replacestr = sentence.substr(index);
+        			findRoot(dict, num, replacestr);
+        			res += " " + replacestr;
+        			break;
+        		}
+        		else
+        		{
+        			replacestr = sentence.substr(index, pos - index);
+        			findRoot(dict, num, replacestr);
+        			res += " " + replacestr;
+        			index = pos + 1;
+        		}
+        }
+
+        return res.substr(1);
+    }
+
+    void findRoot(const vector<string>& dict, int num, string& replacestr)
+    {
+    		int len = replacestr.size();
+    		for (int i = 0; i < num; ++i)
+    		{
+    			int sz = dict[i].size();
+    			if (sz < len && dict[i] == replacestr.substr(0, sz))
+    			{
+    				replacestr = dict[i];
+    				break;
+    			}
+    		}
+    }
diff --git a/src/676.cpp b/src/676.cpp
@@ -0,0 +1,48 @@
+public:
+    /** Initialize your data structure here. */
+    MagicDictionary() {
+        if (!mdict.empty())
+            mdict.clear();
+    }
+    
+    /** Build a dictionary through a list of words */
+    void buildDict(vector<string> dict) {
+        int len = dict.size();
+        for (int i = 0; i < len; ++i)
+        {
+            int sz = dict[i].size();
+            if (mdict.find(sz) == mdict.end())
+                mdict.insert(pair<int, list<string>>(sz, list<string>(1, dict[i])));
+            else
+                mdict[sz].push_back(dict[i]);
+        }
+    }
+    
+    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
+    bool search(string word) {
+        int len = word.size();
+        if (mdict.find(len) == mdict.end())
+            return false;
+        else
+        {
+            for (auto iter = mdict[len].begin(); iter != mdict[len].end(); ++iter)
+                if (check(word, *iter, len))
+                    return true;
+            return false;
+        }
+    }
+
+private:
+    map<int, list<string>> mdict;
+    bool check(const string& a, const string& b, int len)
+    {
+        int ct = 0;
+        for (int i = 0; i < len; ++i)
+            if (a[i] != b[i])
+            {
+                ++ct;
+                if (ct == 2)
+                    return false;
+            }
+        return ct == 1;
+    }
diff --git a/src/725.cpp b/src/725.cpp
@@ -0,0 +1,59 @@
+vector<ListNode*> splitListToParts(ListNode* root, int k) {
+     vector<ListNode*> res;
+     if (root == nullptr)
+     {
+         res.insert(res.end(), k, nullptr);
+         return res;
+     }
+
+     int len = 0;
+     ListNode* h = root;
+     while (h != nullptr)
+     {
+     	++len;
+     	h = h->next;
+     }
+     int each = len/k;
+     int remain = len%k;
+     int i = 0;
+
+     h = root;
+     while (i < k)
+     {
+     	if (i < remain)
+     	{
+     		ListNode* node = h;
+     		ListNode* pre = h;
+     		for (int j = 0; j < each+1; ++j)
+     		{
+     			pre = node;
+     			node = node->next;
+     		}
+     		pre->next = nullptr;
+     		res.push_back(h);
+     		h = node;
+     	}
+     	else
+     	{
+     		if (h == nullptr)
+     		{
+     			res.push_back(nullptr);
+     		}
+     		else
+     		{
+     			ListNode* node = h;
+     			ListNode* pre = h;
+     			for (int j = 0; j < each; ++j)
+     			{
+     				pre = node;
+     				node = node->next;
+     			}
+     			pre->next = nullptr;
+     			res.push_back(h);
+     			h = node;
+     		}
+     	}
+     	++i;
+     }
+     return res;   
+    }
diff --git a/src/86.cpp b/src/86.cpp
diff --git a/src/92.cpp b/src/92.cpp
