12 problems solved.

lintcoder · lintcoder · commit 5fac3f77c649 · 2018-05-11T14:23:43.000+08:00
diff --git a/src/138.cpp b/src/138.cpp
@@ -0,0 +1,29 @@
+RandomListNode *copyRandomList(RandomListNode *head) {
+        if (head == nullptr)
+          return nullptr;
+        RandomListNode* h = head;
+        map<RandomListNode*, int> mp;
+        map<int, RandomListNode*> mp_cp;
+
+        int i = 0, j = 0;
+        RandomListNode* head_cp = new RandomListNode(h->label);
+        RandomListNode* node = head_cp;
+        mp[h] = i++;
+        mp_cp[j++] = head_cp;
+        h = h->next;
+
+        while (h != nullptr)
+        {
+          node->next = new RandomListNode(h->label);
+          node = node->next;
+          mp[h] = i++;
+          mp_cp[j++] = node;
+          h = h->next;
+        }
+        for (auto m : mp)
+        {
+          if (m.first->random != nullptr)
+              mp_cp[m.second]->random = mp_cp[mp[m.first->random]];
+        }
+        return head_cp;
+    }
diff --git a/src/240.cpp b/src/240.cpp
@@ -0,0 +1,17 @@
+bool searchMatrix(vector<vector<int>>& matrix, int target) {
+     int row = matrix.size();
+     if (row == 0)
+     return false;
+     int col = matrix[0].size();
+     int i = 0, j = col - 1;
+     while (i < row && j >= 0)
+     {
+     	if (matrix[i][j] == target)
+     		return true;
+     	else if (matrix[i][j] < target)
+     		++i;
+     	else
+     		--j;
+     }
+     return false;
+    }
diff --git a/src/529.cpp b/src/529.cpp
@@ -0,0 +1,70 @@
+vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) 
+    {
+        int posR = click[0], posC = click[1];
+        if (board[posR][posC] == 'M')
+        {
+            board[posR][posC] = 'X';
+            return board;
+        }
+        else
+        {
+            int row = board.size(), col = board[0].size();
+            updateAdjacentSquare(board, posR, posC, row, col);
+            return board;
+        }   
+    }
+
+    void updateAdjacentSquare(vector<vector<char>>& board, int r, int c, int row, int col)
+    {
+        if (board[r][c] == 'E')
+        {
+            int num = 0;
+            if (checkAdjacent(board, r, c, row, col, num))
+            {
+                board[r][c] = num + '0';
+                return;
+            }
+            else
+            {
+                board[r][c] = 'B';
+                if (r > 0)
+                    updateAdjacentSquare(board, r-1, c, row, col);
+                if (r < row - 1)
+                    updateAdjacentSquare(board, r+1, c, row, col);
+                if (c > 0)
+                    updateAdjacentSquare(board, r, c-1, row, col);
+                if (c < col - 1)
+                    updateAdjacentSquare(board, r, c+1, row, col);
+                if (r > 0 && c > 0)
+                    updateAdjacentSquare(board, r-1, c-1, row, col);
+                if (r > 0 && c < col - 1)
+                    updateAdjacentSquare(board, r-1, c+1, row, col);
+                if (r < row - 1 && c > 0)
+                    updateAdjacentSquare(board, r+1, c-1, row, col);
+                if (r < row - 1 && c < col - 1)
+                    updateAdjacentSquare(board, r+1, c+1, row, col);
+            }
+        }
+    }
+
+    bool checkAdjacent(vector<vector<char>>& board, int r, int c, int row, int col, int& num)
+    {
+        if (r > 0 && board[r - 1][c] == 'M')
+            num++;
+        if (r < row - 1 && board[r + 1][c] == 'M')
+            num++;
+        if (c > 0 && board[r][c - 1] == 'M')
+            num++;
+        if (c < col - 1 && board[r][c + 1] == 'M')
+            num++;
+        if (r > 0 && c > 0 && board[r-1][c-1] == 'M')
+            num++;
+        if (r > 0 && c < col - 1 && board[r-1][c+1] == 'M')
+            num++;
+        if (r < row - 1 && c > 0 && board[r+1][c-1] == 'M')
+            num++;
+        if (r < row - 1 && c < col - 1 && board[r+1][c+1] == 'M')
+            num++;
+
+        return num != 0;
+    }
diff --git a/src/565.cpp b/src/565.cpp
@@ -0,0 +1,22 @@
+int arrayNesting(vector<int>& nums) {
+        int len = nums.size();
+        int maxcount= 1;
+        int i = 0;
+        while (i < len)
+        {
+        		int j = i;
+        		int ct = 1;
+        		while (nums[j] != j && nums[j] != -1)
+        		{
+        			int tmp = nums[j];
+        			nums[j] = -1;
+        			j = tmp;
+        			ct++;
+        		}
+        		if (ct - 1 > maxcount)
+        			maxcount = ct - 1;
+        		++i;
+        }
+
+        return maxcount;
+    }
diff --git a/src/61.cpp b/src/61.cpp
@@ -0,0 +1,30 @@
+ListNode* rotateRight(ListNode* head, int k) {
+     if (head == nullptr || head->next == nullptr)
+     return head;
+
+     ListNode* h = head;
+     int len = 0;
+     while (h != nullptr)
+     {
+     	++len;
+     	h = h->next;
+     }
+     int n = k % len;
+     if (n == 0)
+     	return head;
+     h = head;
+     int i = 0, limit = len - n;
+     ListNode* node = nullptr;
+     while (i < limit)
+     {
+     	node = h;
+     	h = h->next;
+     	++i;
+     }
+     node->next = nullptr;
+     node = h;
+     while (node->next != nullptr)
+     	node = node->next;
+     node->next = head;
+     return h;
+    }
diff --git a/src/655.cpp b/src/655.cpp
@@ -0,0 +1,56 @@
+vector<vector<string>> printTree(TreeNode* root) {
+        vector<vector<string>> res;
+        if (root == nullptr)
+            return res;
+        struct Elem
+        {
+        	int val;
+        	int pos;
+        	Elem(int v, int p): val(v), pos(p){}
+        };
+
+        vector<vector<Elem>> levelvec;
+        deque<TreeNode*> dq;
+        levelvec.push_back(vector<Elem>(1, Elem(root->val, 0)));
+        dq.push_back(root);
+        int sz = 0;
+        int layer = 0;
+        while ((sz = dq.size()) != 0)
+        {
+        	vector<Elem> vec;
+        	for (int i = 0; i != sz; ++i)
+        	{
+        		TreeNode* node = dq[i];
+        		if (node->left != nullptr)
+        		{
+        			dq.push_back(node->left);
+        			vec.push_back(Elem(node->left->val, levelvec[layer][i].pos * 2));
+        		}
+        		if (node->right != nullptr)
+        		{
+        			dq.push_back(node->right);
+        			vec.push_back(Elem(node->right->val, levelvec[layer][i].pos * 2 + 1));
+        		}
+        	}
+        	dq.erase(dq.begin(), dq.begin() + sz);
+        	levelvec.push_back(vec);
+        	layer++;
+        }
+        
+        int num = pow(2, layer) - 1;
+        for (int i = 0; i < layer; ++i)
+        	res.push_back(vector<string>(num, string("")));
+        
+        for (int i = 0; i < layer; ++i)
+        {
+        	int len = levelvec[i].size();
+            int r = pow(2, layer - i);
+            int base = (r - 1)/2;
+        	for (int j = 0; j < len; ++j)
+        	{
+        		res[i][base + r * levelvec[i][j].pos] = to_string(levelvec[i][j].val);
+        	}
+        }
+
+        return res;
+    }
diff --git a/src/678.cpp b/src/678.cpp
@@ -0,0 +1,50 @@
+bool checkValidString(string s) {
+        int len = s.size();
+        if (len == 0)
+        	return true;
+
+        int left = 0, star = 0;
+        vector<int> pos1(len, 0);
+        vector<int> pos2(len, 0);
+        int i = 0, j = 0, k = 0;
+        while (i < len)
+        {
+        	if (s[i] == '(')
+        	{
+        		++left;
+        		pos1[j++] = i;
+        	}
+        	else if (s[i] == ')')
+        	{
+        		if (left > 0)
+        		{
+        			--left;
+        			pos1[--j] = -1;
+        		}
+        		else if (star > 0)
+        		{
+        			--star;
+        			pos2[--k] = -1;
+        		}
+        		else
+        			return false;
+        	}
+        	else
+        	{
+        		++star;
+        		pos2[k++] = i;
+        	}
+        	++i;
+        }
+        if (j > k)
+        	return false;
+
+        while (j > 0)
+        {
+        	int m = pos1[--j];
+        	while (pos2[--k] < m);
+        	if (k < j)
+        		return false;
+        }
+        return true;
+    }
diff --git a/src/721.cpp b/src/721.cpp
@@ -0,0 +1,50 @@
+vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
+        int num = accounts.size();
+        if (num == 0 || num == 1)
+        	return accounts;
+
+        vector<vector<string>> res;
+        map<string, vector<int>> mp;
+
+        for (int i = 0; i < num; ++i)
+        {
+        	int len = accounts[i].size();
+        	for (int j = 1; j < len; ++j)
+        		mp[accounts[i][j]].push_back(i);
+        }
+
+        vector<int> access(num, 0);
+        for (int i = 0; i < num; ++i)
+        {
+        	if (access[i] == 1)
+        		continue;
+        	access[i] = 1;
+        	set<string> account;
+        	merge(accounts, access, mp, i, account);
+
+        	vector<string> ac(account.size()+1, "");
+        	ac[0] = accounts[i][0];
+        	copy(account.begin(), account.end(), ac.begin()+1);
+        	sort(ac.begin()+1, ac.end());
+        	res.push_back(ac);
+        }
+	    return res;
+    }
+    void merge(const vector<vector<string>>& accounts, vector<int>& access, map<string, vector<int>>& mp, int index, set<string>& ac)
+    {
+        ac.insert(accounts[index].begin()+1, accounts[index].end());
+        int len = accounts[index].size();
+        for (int i = 1; i < len; ++i)
+        {
+            int n = mp[accounts[index][i]].size();
+            for (int j = 0; j < n; ++j)
+            {
+                int m = mp[accounts[index][i]][j];
+                if (access[m] == 0)
+                {
+                    access[m] = 1;
+                    merge(accounts, access, mp, m, ac);
+                }
+            }
+        }
+    }
diff --git a/src/726.cpp b/src/726.cpp
diff --git a/src/817.cpp b/src/817.cpp
diff --git a/src/825.cpp b/src/825.cpp
diff --git a/src/831.cpp b/src/831.cpp
