Monthly Archives: June 2017

LeetCode Valid Triangle Number

Leave a reply

LeetCode Valid Triangle Number Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle. Example 1: 

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3
Note:
  1. The length of the given array won’t exceed 1000.
  2. The integers in the given array are in the range of [0, 1000].
给定一个数组，问从中能取出所少个三元数组，使得取出的三个数能构成一个三角形。 首先明确三条线段构成三角形的条件是任意两边之和要大于第三遍。 先上暴力，直接dfs枚举出所有的三元组，判断能构成三角形，则方案数加1。代码如下： [cpp] class Solution { private: void dfs(int &ans, vector<int>& nums, vector<int>& cand, int idx) { if (cand.size() == 3) { int &a = cand[0], &b = cand[1], &c = cand[2]; if (a + b > c&&a + c > b&&b + c > a) { ++ans; //cout << a << "\t" << b << "\t" << c << endl; } return; } for (int i = idx; i < nums.size(); ++i) { if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return; cand.push_back(nums[i]); dfs(ans, nums, cand, i + 1); cand.pop_back(); } } public: int triangleNumber(vector<int>& nums) { int ans = 0; vector<int> cand; sort(nums.begin(), nums.end()); dfs(ans, nums, cand, 0); return ans; } }; [/cpp] 本代码提交TLE：219 / 243。数组最大长度是1000，则所有的组合数有1000*999*998=997002000，确实有点大。。。 后来我发现，报TLE的大数据，虽然有1000个数，但是有很多都是重复的，真正不同的数大概只有100个左右。所以我就想，先对数据去重，在所有互异的数中dfs。然后根据每条边重复的次数来求组合数。 比如样例中，互异的数是[2,3,4]，dfs发现[2,3,4]可以构成三角形，则所有由[2,3,4]构成的三角形的个数应该是count[2]*count[3]*count[4]=2*1*1=2。 所以我们先对数组做个hash，统计数值及其出现频率的关系。注意，因为边的长度最大也只为1000，所以用一个1000长的数组来hash比用map或者unordered_map占用的内存更少，否则会MLE。 然后分三类情况进行计算：1. 三条边互不相同；2.有两条边的值相等；3.三条边的值都相等。 其中第一种情况用常规的DFS求解。第二种和第三种情况就是简单的枚举。 还需要注意一点是，边长为0的值需要过滤掉。 完整代码如下： [cpp] class Solution { private: void dfs(int& ans, vector<int>& count, vector<int>& nums, vector<int>& cand, int idx) { if (cand.size() == 3) { int &a = cand[0], &b = cand[1], &c = cand[2]; if (a + b > c&&a + c > b&&b + c > a) { ans += count[a] * count[b] * count[c]; // 三边各异 //cout << a << "\t" << b << "\t" << c << endl; } return; } for (int i = idx; i < nums.size(); ++i) { if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return; cand.push_back(nums[i]); dfs(ans, count, nums, cand, i + 1); cand.pop_back(); } } public: int triangleNumber(vector<int>& nums) { vector<int> mii(1001, 0); for (const auto& i : nums)++mii[i]; // hash vector<int> distinct; for (int i = 1; i < 1001; ++i) { if (mii[i] > 0)distinct.push_back(i); } int ans = 0; vector<int> cand; dfs(ans, mii, distinct, cand, 0); // 三边互不相同 int n = distinct.size(); for (int i = 0; i < n; ++i) { if (mii[distinct[i]] >= 3) { // 三边相同 int &d = mii[distinct[i]]; ans += (d*(d – 1)*(d – 2)) / 6; } for (int j = i + 1; j < n; ++j) { if (mii[distinct[i]] >= 2) { // 两条边一样 int &a = distinct[i], &b = distinct[i], &c = distinct[j]; if (a + b > c&&a + c > b&&b + c > a) { ans += (mii[a] * (mii[a] – 1) / 2)*mii[c]; } } if (mii[distinct[j]] >= 2) { // 两条边一样 int &a = distinct[i], &b = distinct[j], &c = distinct[j]; if (a + b > c&&a + c > b&&b + c > a) { ans += (mii[b] * (mii[b] – 1) / 2)*mii[a]; } } } } return ans; } }; [/cpp] 本代码提交AC，用时1589MS。]]>

LeetCode Design Compressed String Iterator

Leave a reply

LeetCode Design Compressed String Iterator Design and implement a data structure for a compressed string iterator. It should support the following operations: next and hasNext. The given compressed string will be in the form of each letter followed by a positive integer representing the number of this letter existing in the original uncompressed string. next() – if the original string still has uncompressed characters, return the next letter; Otherwise return a white space. hasNext() – Judge whether there is any letter needs to be uncompressed. Note: Please remember to RESET your class variables declared in StringIterator, as static/class variables are persisted across multiple test cases. Please see here for more details. Example: 

StringIterator iterator = new StringIterator("L1e2t1C1o1d1e1");
iterator.next(); // return 'L'
iterator.next(); // return 'e'
iterator.next(); // return 'e'
iterator.next(); // return 't'
iterator.next(); // return 'C'
iterator.next(); // return 'o'
iterator.next(); // return 'd'
iterator.hasNext(); // return true
iterator.next(); // return 'e'
iterator.hasNext(); // return false
iterator.next(); // return ' '
本题设计了一种压缩字符串格式，即把多个连续相同字符用单个字符已经频率代替了，比如”L1e2t1C1o1d1e1″展开其实就是”LeetCode”。现在要针对这种压缩字符串，设计一个迭代器，实现next和hasNext函数。 我一开始上暴力，即首先把压缩字符串展开成常规字符串，然后直接下标操作。代码如下： [cpp] class StringIterator { private: string line; int cur, n; public: StringIterator(string compressedString) { line = ""; cur = n = 0; vector<char> letters; vector<int> rep; string digits = ""; for (int i = 0; i < compressedString.size(); ++i) { if (isalpha(compressedString[i])) { letters.push_back(compressedString[i]); if (digits != "") { rep.push_back(atoi(digits.c_str())); digits = ""; } } else digits += string(1, compressedString[i]); } rep.push_back(atoi(digits.c_str())); for (int i = 0; i < letters.size(); ++i) { line += string(rep[i], letters[i]); } n = line.size(); } char next() { if (cur < n)return line[cur++]; else return ‘ ‘; } bool hasNext() { return cur < n; } }; [/cpp] 本代码MLE了。因为有个样例是“a1234567890b1234567890”，我表示无语，如果展开确实会MLE。 其实写上面的代码的时候我就知道可以优化，不对压缩字符串展开，而是表示成(a,1234567890)和(b,1234567890)，next的时候只对频率递减。这样只需要存储少量字符以及对应的频率。 代码如下： [cpp] typedef long long ll; class StringIterator { private: int cur, n; vector<char> letters; vector<ll> rep; public: StringIterator(string compressedString) { cur = n = 0; string digits = ""; for (int i = 0; i < compressedString.size(); ++i) { if (isalpha(compressedString[i])) { letters.push_back(compressedString[i]); if (digits != "") { rep.push_back(atoll(digits.c_str())); digits = ""; } } else digits += string(1, compressedString[i]); } rep.push_back(atoi(digits.c_str())); n = letters.size(); } char next() { if (rep[cur] > 0) { char ans = letters[cur]; –rep[cur]; return ans; } else { if (cur == n – 1)return ‘ ‘; else { char ans = letters[++cur]; –rep[cur]; return ans; } } } bool hasNext() { return cur < n – 1 || (cur == n – 1 && rep[cur] > 0); } }; [/cpp] 本代码提交AC，用时13MS。]]>

LeetCode Merge Two Binary Trees

Leave a reply

LeetCode Merge Two Binary Trees Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree. Example 1: 

Input:
	Tree 1                     Tree 2
          1                         2
         / \                       / \
        3   2                     1   3
       /                           \   \
      5                             4   7
Output:
Merged tree:
	     3
	    / \
	   4   5
	  / \   \
	 5   4   7
Note: The merging process must start from the root nodes of both trees.
上午又参加了一场LeetCode的比赛，第三题花了不少时间，第四题在11:06分AC了，但是比赛好像在11:00就结束了。。。无语，排名只有376。 这题要求把两棵二叉树合并，如果对应位置都有节点，则新节点的值等于两个老节点的值之和，否则等于有值的那个节点。 简单题，直接递归merge就好。代码如下： [cpp] class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if (t1 == NULL&&t2 == NULL)return NULL; if (t1 == NULL&&t2 != NULL)return t2; if (t1 != NULL&&t2 == NULL)return t1; TreeNode* left = mergeTrees(t1->left, t2->left); TreeNode* right = mergeTrees(t1->right, t2->right); TreeNode* root = new TreeNode(t1->val + t2->val); root->left = left; root->right = right; return root; } }; [/cpp] 本代码提交AC，用时49MS。]]>

LeetCode Rotate Function

Leave a reply

LeetCode Rotate Function Given an array of integers A and let n to be its length. Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow: F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]. Calculate the maximum value of F(0), F(1), ..., F(n-1). Note: n is guaranteed to be less than 105. Example: 

A = [4, 3, 2, 6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.
给定一个数组A，和函数F(k)，其中F(k) = 0 * Bk[0] + 1 * Bk[1] + … + (n-1) * Bk[n-1]，数组B为数组A顺时针旋转k次后的新数组。要求所有F(k)的最大值。 仔细观察样例，会发现$$F(k)=\sum_{i=0}^{n-1}((k+i)\%n)*a_i$$。于是可以算出所有的F(k)，然后求最大值。代码如下： [cpp] class Solution { public: int maxRotateFunction(vector<int>& A) { if (A.empty())return 0; int ans = INT_MIN, n = A.size(); for (int k = 0; k < n; ++k) { int cur = 0; for (int i = 0; i < n; ++i) { cur += ((k + i) % n)*A[i]; } ans = max(ans, cur); } return ans; } }; [/cpp] 本代码提交TLE，复杂度是O(kn)，遇到大数据时超时了。 如果再仔细研究一下样例，会发现一个更优的递推公式：$$F(k)=F(k-1)+sum-n*A[n-k]$$。这样直接根据前一项F(k-1)，可以在O(1)时间算出下一项F(k)。总的时间复杂度只有O(n)。代码如下： [cpp] class Solution { public: int maxRotateFunction(vector<int>& A) { if (A.empty())return 0; int n = A.size(), sum = 0, f0 = 0; for (int i = 0; i < n; ++i) { sum += A[i]; f0 += i*A[i]; } int ans = f0, pre = f0; for (int i = 1; i < n; ++i) { int cur = pre + sum – n * A[n – i]; ans = max(ans, cur); pre = cur; } return ans; } }; [/cpp] 本代码提交AC，用时16MS。]]>

LeetCode Palindrome Partitioning

Leave a reply

131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

本题要求把字符串s分割成若干个子串，使得每个子串都是回文串。如果有多种分割方法，输出所有的分割方案。 很有意思的一道题。我是这样做的：首先用DP求出任意一个子串s[i,…,j]是否为回文串，这就相当于知道了s中哪几个位置可以切割；然后就在s中DFS每个割点，求出所有的分割方案。
DP求s[i,…,j]是否为回文串的过程是这样的，如果s[i]==s[j]，且dp[i+1][j-1]也是回文串，则dp[i][j]也是回文串。所以我们需要先求到长度比较短的s[i+1,j-1]是否为回文串，然后再求长度更长的是否为回文串。所以在helper函数的外层循环是子串的长度。

求到了任意一个子串是否为回文串之后，DFS每个割点就好了，这个和枚举排列情况很类似，就不再赘述了。完整代码如下：

class Solution {
private:
    void helper(const string& s, vector<vector<int> >& dp)
    {
        int n = s.size();
        for (int i = 0; i < n; ++i)
            dp[i][i] = 1; // 单个字符自身就是回文串
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len – 1 < n; ++i) {
                if (s[i] == s[i + len – 1] && ((i + 1 <= i + len – 2 && dp[i + 1][i + len – 2] == 1) || i + 1 > i + len – 2)) {
                    dp[i][i + len – 1] = 1;
                }
            }
        }
    }
    void dfs(const string& s, vector<vector<int> >& dp, vector<vector<string> >& ans, vector<string>& cand, int idx)
    {
        if (idx == s.size()) {
            ans.push_back(cand);
            return;
        }
        for (int i = idx; i < s.size(); ++i) {
            if (dp[idx][i] == 1) {
                cand.push_back(s.substr(idx, i – idx + 1));
                dfs(s, dp, ans, cand, i + 1);
                cand.pop_back();
            }
        }
    }
public:
    vector<vector<string> > partition(string s)
    {
        int n = s.size();
        vector<vector<int> > dp(n, vector<int>(n, 0));
        helper(s, dp);
        vector<vector<string> > ans;
        vector<string> cand;
        dfs(s, dp, ans, cand, 0);
        return ans;
    }
};

本代码提交AC，用时6MS。

二刷。不用DP提前判断，而是每次都暴力判断是否为回文：

class Solution {
public:
	bool IsPal(const string &s, int l, int r) {
		if (l > r)return false;
		if (l == r)return true;
		while (l < r) {
			if (s[l] != s[r])break;
			++l;
			--r;
		}
		return l >= r;
	}
	void DFS(vector<vector<string>> &ans, vector<string> &cur, string &s, int idx) {
		int n = s.size();
		if (idx >= n) {
			ans.push_back(cur);
			return;
		}
		for (int i = idx; i < n; ++i) {
			if (IsPal(s, idx, i)) {
				cur.push_back(s.substr(idx, i - idx + 1));
				DFS(ans, cur, s, i + 1);
				cur.pop_back();
			}
		}
	}
	vector<vector<string>> partition(string s) {
		vector<vector<string>> ans;
		vector<string> cur;
		DFS(ans, cur, s, 0);
		return ans;
	}
};

本代码提交AC，用时12MS，比第一种方法慢，还是第一种方法提前求DP更高效。

LeetCode Pacific Atlantic Water Flow

Leave a reply

LeetCode Pacific Atlantic Water Flow Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges. Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower. Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean. Note:

  1. The order of returned grid coordinates does not matter.
  2. Both m and n are less than 150.
Example: 
Given the following 5x5 matrix:
  Pacific ~   ~   ~   ~   ~
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
给定一个矩阵，每个元素表示一个方格中水柱的高度，左上角是太平洋，右下角是大西洋，问哪些坐标的水柱既能流向太平洋，又能流向大西洋。注意每个水柱能流向和它同样高或者比它第的地方。 一看就是DFS或者BFS的题。 拍脑袋解法。对于每个坐标，我们DFS看能否分别到达太平洋或者大西洋。代码如下： [cpp] vector<vector<int>> dirs = { { 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 } }; // 0:left, 1:up, 2:right, 3:down class Solution4 { private: int m, n; bool isOk(int x, int y) { return x >= 0 && x < m&&y >= 0 && y < n; } // type=0:Pacific; 1:Atlantic bool dfs(vector<vector<int>>& matrix, vector<vector<int>>& visited, int x, int y, const int& type) { for (int i = 0; i < dirs.size(); ++i) { int xx = x + dirs[i][0], yy = y + dirs[i][1]; if (isOk(xx, yy) && visited[xx][yy] == 0 && matrix[x][y] >= matrix[xx][yy]) { visited[xx][yy] = 1; if (dfs(matrix, visited, xx, yy, type)) { visited[xx][yy] = 0; return true; } visited[xx][yy] = 0; } else if ((type == 0 && (xx < 0 || yy < 0)) || (type == 1 && (xx >= m || yy >= n))) { return true; } } return false; } public: vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) { if (matrix.empty() || matrix[0].empty())return{}; m = matrix.size(), n = matrix[0].size(); vector<vector<int>> visited(m, vector<int>(n, 0)); vector<pair<int, int>> ans; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { visited[i][j] = 1; if (dfs(matrix,visited,i,j,0)&&dfs(matrix,visited,i,j,1)) ans.push_back(pair<int, int>(i, j)); visited[i][j] = 0; } } return ans; } }; [/cpp] 本代码提交AC，用时702MS。 这种DFS的解法重复计算非常多，比如(a,b)这个点DFS时会经过(a-1,b-1)，而(a-1,b-1)之前其实已经DFS过了。可以在DFS的过程中记录下经过的点的DFS状态，比如在DFS(a,b)时，走到(a-1,b-1)，先查状态，发现(a-1,b-1)到不了大西洋，那现在这条路就没必要继续DFS下去了；相反，如果查状态发现(a-1,b-1)能到大西洋，则后续不需要再DFS其他路径了。 保存状态的DFS版本如下： [cpp] vector<vector<int>> dirs = { { 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 } }; // 0:left, 1:up, 2:right, 3:down // memory version class Solution3 { private: int m, n; bool isOk(int x, int y) { return x >= 0 && x < m&&y >= 0 && y < n; } bool dfs(vector<vector<int>>& matrix, vector<vector<int>>& visited, int x, int y, const int& type, vector<vector<vector<int>>>& mem) { for (int i = 0; i < dirs.size(); ++i) { int xx = x + dirs[i][0], yy = y + dirs[i][1]; if (isOk(xx, yy) && visited[xx][yy] == 0 && matrix[x][y] >= matrix[xx][yy]) { if (mem[xx][yy][type] == 1) { mem[x][y][type] = 1; return true; } else if (mem[xx][yy][type] == 0)continue; visited[xx][yy] = 1; if (dfs(matrix, visited, xx, yy, type, mem)) { mem[x][y][type] = 1; visited[xx][yy] = 0; return true; } visited[xx][yy] = 0; } else if ((type == 0 && (xx < 0 || yy < 0)) || (type == 1 && (xx >= m || yy >= n))) { mem[x][y][type] = 1; return true; } } mem[x][y][type] = 0; return false; } public: vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) { if (matrix.empty() || matrix[0].empty())return{}; m = matrix.size(), n = matrix[0].size(); vector<vector<int>> visited(m, vector<int>(n, 0)); vector<vector<vector<int>>> mem(m, vector<vector<int>>(n, vector<int>(2, -1))); vector<pair<int, int>> ans; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { visited[i][j] = 1; if (mem[i][j][0] == -1) dfs(matrix, visited, i, j, 0, mem); if (mem[i][j][1] == -1) dfs(matrix, visited, i, j, 1, mem); visited[i][j] = 0; if (mem[i][j][0] == 1 && mem[i][j][1] == 1) ans.push_back(pair<int, int>(i, j)); } } return ans; } }; [/cpp] 无奈，在第112/113这个数据上WA了，但是这个数据太大了，面对的是汪洋大海，调试太费劲，暂时没fix bug。 看了下讨论区，发现主流解法是从海洋开始BFS，分别从大西洋和太平洋BFS，记录下两个海洋分别能访问到的点，最后如果某个点同时被两个海洋访问到了，则说明该点既能到达大西洋，也能到达太平洋。 代码如下： [cpp] vector<vector<int>> dirs = { { 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 } }; // 0:left, 1:up, 2:right, 3:down class Solution { private: int m, n; bool isOk(int x, int y) { return x >= 0 && x < m&&y >= 0 && y < n; } void bfs(vector<vector<int>>& matrix, queue<pair<int, int>>& Q, vector<vector<int>>& visited) { while (!Q.empty()) { auto f = Q.front(); Q.pop(); visited[f.first][f.second] = 1; for (int i = 0; i < dirs.size(); ++i) { int x = f.first + dirs[i][0], y = f.second + dirs[i][1]; if (isOk(x, y) && visited[x][y] == 0 && matrix[f.first][f.second] <= matrix[x][y]) { Q.push(pair<int, int>(x, y)); } } } } public: vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) { if (matrix.empty() || matrix[0].empty())return{}; m = matrix.size(), n = matrix[0].size(); vector<vector<int>> pacific(m, vector<int>(n, 0)), atlantic(m, vector<int>(n, 0)); queue<pair<int, int>> pQ, aQ; for (int i = 0; i < m; ++i) { // vertical pQ.push(pair<int, int>(i, 0)); aQ.push(pair<int, int>(i, n – 1)); } for (int i = 0; i < n; ++i) { // horizontal pQ.push(pair<int, int>(0, i)); aQ.push(pair<int, int>(m – 1, i)); } bfs(matrix, pQ, pacific); bfs(matrix, aQ, atlantic); vector<pair<int, int>> ans; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (pacific[i][j] == 1 && atlantic[i][j] == 1) ans.push_back(pair<int, int>(i, j)); } } return ans; } }; [/cpp] 本代码提交AC，用时减少到45MS。 对于类似的搜索题目，如果是求单个点能否达到目的地，则从起始点或者目的点开始BFS/DFS的效果都是一样的。但是如果要求所有能到达目的点的点，则从目的点开始BFS就能一次性找到这些点，而从每个起始点开始BFS/DFS就非常费劲了。]]>

LeetCode Largest Divisible Subset

Leave a reply

LeetCode Largest Divisible Subset Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0. If there are multiple solutions, return any subset is fine. Example 1: 

nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)
Example 2: 
nums: [1,2,4,8]
Result: [1,2,4,8]
给定一个数组，求满足这样一个条件的最大子集：该子集中的任意两个元素a和b满足a%b==0或者b%a==0。通过样例能够很好的理解这个题意。 这题的解法和最长上升子序列的求法很类似，用DP求解。首先对数组从小到大排序，然后对于第i个数nums[i]，定义dp[i]表示包含nums[i]、满足divisible subset条件、且nums[i]在该子集中是最大元素的子集的最大元素个数。其实就是把dp[i]直观的理解为以nums[i]结尾的满足divisible subset条件的最大子集合的大小。 求解dp[i]的递归方法是，遍历比nums[i]小的所有数nums[j]，如果nums[i]%nums[j]，则说明nums[i]可以扔到nums[j]所在的子集合中，所以dp[i]=dp[j]+1。遍历所有的j，找一个最大的dp[i]。 因为本题要输出具体的解，所以还定义一个数组parent[i]表示dp[i]的最大值是从哪个j来的。最后输出最优解的时候，j不断的递归往前找即可。 完整代码如下： [cpp] class Solution { public: vector<int> largestDivisibleSubset(vector<int>& nums) { if (nums.empty())return{}; sort(nums.begin(), nums.end()); int n = nums.size(), maxLen = 0, maxIdx = 0; vector<int> dp(n, 1), parent(n, -1); for (int i = 0; i < n; ++i) { for (int j = i – 1; j >= 0; –j) { if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; parent[i] = j; } } if (dp[i] > maxLen) { maxLen = dp[i]; maxIdx = i; } } vector<int> ans; while (maxIdx != -1) { ans.push_back(nums[maxIdx]); maxIdx = parent[maxIdx]; } return ans; } }; [/cpp] 本代码提交AC，用时39MS。 参考：https://www.hrwhisper.me/leetcode-largest-divisible-subset/]]>

LeetCode Super Pow

Leave a reply

LeetCode Super Pow Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array. Example1: 

a = 2
b = [3]
Result: 8
Example2: 
a = 2
b = [1,0]
Result: 1024
快速幂的进阶版，超级幂。要求$$a^B=a^{[b_0,b_1,b_2,…b_{n-1}]}$$，其中的B用一个数组来表示，数组中的元素都是个位数，分别从高位到低位。比如第二个样例表示的是$$2^10$$。 我一开始把$$a^B=a^{[b_0,b_1,b_2,…b_{n-1}]}$$展开成$$a^B=a^{b_0*10^{n-1}+b_1*10^{n-2}+…}$$，对于每一项都用快速幂算出$$10^{n-i-1}$$，然后用快速幂算出$$a^{b_i*10^{n-i-1}}$$，最后累乘起来。但是很不幸WA或者TLE。 后来看了网上的题解，发现真是巧妙，这不就类似于多项式计算时层层嵌套的方法吗，一时想不起来那个叫什么名字了。比如我们要算$$a^{[b_0,b_1,b_2]}$$，本来是$$a^{b_0*10^2+b_1*10+b_2}$$。但是我们计算是可以这样算，先算$$C_0=a^{b_0}$$；递归到$$b_1$$时，在算到$$b_0$$的基础上，有$$C_1=(a^{b_0})^{10}*a^{b_1}=C_0^{10}*a^{b_1}$$；递归到$$b_2$$时，有$$C_2=((a^{b_0})^{10}*a^{b_1})^{10}*a^{b_2}=C_1^{10}*a^{b_2}$$。把$$C_2$$展开其实就是$$a^{b_0*10^2+b_1*10+b_2}$$。 完整代码如下： [cpp] typedef unsigned long long ull; class Solution { private: const static int MOD = 1337; ull fastPow(ull x, ull y) { ull ans = 1; while (y) { if (y & 1)ans = (ans*x) % MOD; y >>= 1; x = (x*x) % MOD; } return ans; } public: int superPow(int a, vector<int>& b) { ull ans = 1; for (int i = 0; i < b.size(); ++i) { ans = fastPow(ans, 10)*fastPow(a, b[i]) % MOD; } return ans; } }; [/cpp] 本代码提交AC，用时9MS。]]>

LeetCode Bulls and Cows

Leave a reply

299. Bulls and Cows299. Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called “bulls”) and how many digits match the secret number but locate in the wrong position (called “cows”). Your friend will use successive guesses and hints to eventually derive the secret number.

Write a function to return a hint according to the secret number and friend’s guess, use A to indicate the bulls and B to indicate the cows. 

Please note that both secret number and friend’s guess may contain duplicate digits.

Example 1:

Input: secret = "1807", guess = "7810"

Output: "1A3B"

Explanation: 1 bull and 3 cows. The bull is 8, the cows are 0, 1 and 7.

Example 2:

Input: secret = "1123", guess = "0111"

Output: "1A1B"

Explanation: The 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow.

Note: You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.299. Bulls and Cows

类似猜数字问题。假设秘密数字是”1807″，对方猜了一个数字是”7810″，问猜对了多少位，又有多少位是没猜对，但是秘密数字中出现了。比如这里猜对了第2位，都是’8’；’7’、’1’和’0’虽然没猜对位置，但是秘密数字中也有’1’、’0’和’7’，所以算完全猜对了1个数位，猜对了3个数，但位置不对，输出”1A3B”。 简单题，先对秘密数字建立数字和频率的hash表，然后遍历猜测数字，如果对应位相等，则完全猜对一个；如果对应位不相等，但是在秘密数字的hash表中，且频率大于0，则猜对第二类。 完整代码如下：

class Solution {
public:
    string getHint(string secret, string guess)
    {
        unordered_map<char, int> uci;
        for (const auto& c : secret)
            ++uci[c];
        int a = 0, b = 0;
        for (int i = 0; i < guess.size(); ++i) {
            if (guess[i] == secret[i]) {
                ++a;
                –uci[secret[i]];
            }
        }
        for (int i = 0; i < guess.size(); ++i) {
            if (guess[i] != secret[i] && uci[guess[i]] > 0) {
                ++b;
                –uci[guess[i]];
            }
        }
        return to_string(a) + "A" + to_string(b) + "B";
    }
};

本代码提交AC，用时6MS。需要注意的是，两类数字的判断需要分开，只有先判断了对应位数字完全一样的数位，才判断第二类位置不对但数对的情况。比如

Secret number:  "1122"
Friend's guess: "1222"

如果混在一起判断的话，对于guess中的第一个2，Secret是1，但Secret中有2，所以这个2被分类为位置错，但数字对的情况，从而Secret中的2的频率减少为1，导致最后一个2，虽然数字和位置完全一样，但是Secret中2的频率已经是0了，无法判断为A类。所以需要完全判断完A类之后，才判断B类。

二刷。因为只有0-9这10个数字，可以用数组代替hash：

class Solution {
public:
	string getHint(string secret, string guess) {
		int n = secret.size();
		int a = 0, b = 0;
		vector<int> s(10, 0), g(10, 0);
		for (int i = 0; i < n; ++i) {
			if (secret[i] == guess[i])++a;
			else {
				++s[secret[i] - '0'];
				++g[guess[i] - '0'];
			}
		}
		for (int i = 0; i < 10; ++i) {
			b += min(s[i], g[i]);
		}
		return to_string(a) + "A" + to_string(b) + "B";
	}
};

本代码提交AC，用时4MS。

LeetCode Matchsticks to Square

Leave a reply

LeetCode Matchsticks to Square Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time. Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has. Example 1: 

Input: [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
Example 2: 
Input: [3,3,3,3,4]
Output: false
Explanation: You cannot find a way to form a square with all the matchsticks.
Note:
  1. The length sum of the given matchsticks is in the range of 0 to 10^9.
  2. The length of the given matchstick array will not exceed 15.
卖火柴的小女孩有一堆长度不等的火柴棒，问用这些火柴棒能否围成一个正方形。 因为最多有15根火柴棒，所以可以DFS求解。 首先判断所有火柴棒的长度之和是否为4的倍数，如果是，则和除以4等于edge，也就是我们的目标是把所有火柴棒分成和等于edge的四等份。DFS的思路就是尝试把每根火柴棒放到第一、二、三、四份中，不断的递归求解。但是需要一些剪枝策略，否则会TLE。 先上代码： [cpp] class Solution { private: bool dfs(const vector<int>& nums, int idx, const int &edge, vector<int>& sums) { if (idx == nums.size() && sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == sums[3])return true; if (idx == nums.size())return false; for (int i = 0; i < 4; ++i) { if (sums[i] + nums[idx] <= edge) { // (2) int j = i; while (–j >= 0) { if (sums[i] == sums[j])break; // (3) } if (j != -1)continue; sums[i] += nums[idx]; if (dfs(nums, idx + 1, edge, sums))return true; sums[i] -= nums[idx]; } } return false; } public: bool makesquare(vector<int>& nums) { int n = nums.size(); if (n < 4)return false; sort(nums.begin(), nums.end(),greater<int>()); // (1) int sum = 0; for (int i = 0; i < n; ++i)sum += nums[i]; if (sum % 4 != 0)return false; vector<int> sums = { 0,0,0,0 }; return dfs(nums, 0, sum / 4, sums); } }; [/cpp] 本代码提交AC，用时6MS。 第(1)个剪枝策略的含义是先对所有火柴棒的长度从大到小排序，为什么从大到小排序呢，因为我们的dfs过程中的for循环总是首先尝试把每根火柴棒放到第一个组份中，如果本身无解，则从小到大的策略会慢慢累积和，直到最后加上很长的火柴棒才会发现不满足if语句无解；而如果从大到小排序的话，一开始的累加和就很大，如果无解，则很快能发现不满足if。 第(2)个剪枝策略的含义是只有当把这根火柴棒加到这个组份中不会超过预定的edge，才把它加入，然后递归。这个很显然的。 第(3)个剪枝策略参考讨论区，如果递归的时候发现某一个组份当前的和等于之前某个组份的和，因为之前那个组份已经递归过了，所以本质上这次递归会和上次递归一样，可以continue掉。]]>