Tag Archives: 找特征

LeetCode Valid Perfect Square

LeetCode Valid Perfect Square Given a positive integer num, write a function which returns True if num is a perfect square else False. Note: Do not use any built-in library function such as sqrt. Example 1:

Input: 16
Returns: True
Example 2:
Input: 14
Returns: False

本题要判断一个数是否是完全平方数。有很多种解法,现列举如下: 解法1。牛顿法。牛顿法本是用来求解函数f(x)=0的根的,可以用来开方。$$f(x)=x^2-num$$等于0的正根就是num的根号。下面就是牛顿法求解f(x)=0的根的更新公式,$$x_{n+1}$$比$$x_n$$更接近f(x)=0的真实根。初始的时候可以随便代一个$$x_0$$到公式中。 对于函数$$f(x)=x^2-num$$,$$f'(x)=2x$$,所以牛顿递推式为$$!x_{n+1}=x_n-\frac{x_n^2-num}{2x_n}=(x_n+num/x_n)/2$$ 所以我们可以初始代入$$x_n=num$$,然后不断用牛顿法,直到x*x<=num时,如果x*x==num,则num为完全平方数,否则不是。 关于牛顿法用于开放的原理介绍,果壳网上有个人介绍得很详细。 代码如下: [cpp] class Solution { public: bool isPerfectSquare(int num) { long long x = num; while (x*x > num) { x = (x + num / x) / 2; } return x*x == num; } }; [/cpp] 本代码提交AC,用时0MS。 解法2。对于num,如果$$x=\frac{num}{2}$$的平方依然大于num,则$$x=\frac{x}{2}$$,如果x的平方依然大于num,则继续对x除以2,不断除,直到x平方小于等于num时,遍历[x,2*x]之间的数,看看x*x==num是否成立,如果成立,说明num是完全平方数,否则不是。这种解法在高级算法里好像讲过。完整代码如下: [cpp] class Solution { public: bool isPerfectSquare(int num) { if (num == 1)return true; long long x = num >> 1; while (x*x > num)x >>= 1; for (int y = x; y <= (x << 1); ++y) { if (y*y == num)return true; } return false; } }; [/cpp] 本代码提交AC,用时3MS。 解法3。观测下面的等式发现完全平方数都是由连续奇数相加而来,所以我们也可以把连续奇数加起来,直到超过num时,看看和与num是否相等。 1 = 1 4 = 1 + 3 9 = 1 + 3 + 5 16 = 1 + 3 + 5 + 7 25 = 1 + 3 + 5 + 7 + 9 36 = 1 + 3 + 5 + 7 + 9 + 11 …. 1+3+…+(2n-1) = (2n-1 + 1)n/2 = n*n 代码如下: [cpp] class Solution { public: bool isPerfectSquare(int num) { long long sum = 1; for (int i = 3; sum < num; i += 2) sum += i; return sum == num; } }; [/cpp] 本代码提交AC,用时3MS。 解法4。二分搜索。l=0,r=num,mid=(l+r)/2,根据mid*mid和num的大小关系一步步缩小范围。复杂度为O(lgn),完整代码如下: [cpp] class Solution { public: bool isPerfectSquare(int num) { long long l = 0, r = num; while (l <= r) { long long mid = (l + r) / 2; long long prod = mid*mid; if (prod == num)return true; if (prod < num)l = mid + 1; else r = mid – 1; } return l*l == num; } }; [/cpp] 本代码提交AC,用时0MS。 注意这个题的代码中,为了防止int越界,都需要用long long。 参考: http://bookshadow.com/weblog/2016/06/26/leetcode-valid-perfect-square/ http://www.cnblogs.com/grandyang/p/5619296.html]]>

LeetCode Reconstruct Original Digits from English

LeetCode Reconstruct Original Digits from English Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order. Note:

  1. Input contains only lowercase English letters.
  2. Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as “abc” or “zerone” are not permitted.
  3. Input length is less than 50,000.
Example 1:
Input: "owoztneoer"
Output: "012"
Example 2:
Input: "fviefuro"
Output: "45"

给定一个用英文单词表示数字的字符串,要求恢复出这个数字字符串,英文字符串是被打乱了的。 这题纯粹是个找规律的题,先写出10个数字的英文单词,然后找找那个字符是每个单词特有的字符,比如可以确定的有:
  • 0:z
  • 2:w
  • 4:u
  • 6:x
  • 8:g
找完上述5个单词之后,剩下的5个单词中每个单词特有的字符为:
  • 1:o
  • 3:t
  • 5:f
  • 7:s
  • 9:i
所以我们首先找到字符和频率的对应关系,然后根据上面的顺序依次减掉相应单词的频率,并把数字放到结果数组中,最后从结果数组中构建结果字符串。完整代码如下: [cpp] class Solution { public: string originalDigits(string s) { vector<int> hash(26, 0); vector<int> digits(10, 0); for (int i = 0; i < s.size(); ++i) { ++hash[s[i] – ‘a’]; } while (hash[‘z’ – ‘a’]) { // 0 ++digits[0]; –hash[‘z’ – ‘a’]; –hash[‘e’ – ‘a’]; –hash[‘r’ – ‘a’]; –hash[‘o’ – ‘a’]; } while (hash[‘w’ – ‘a’]) { // 2 ++digits[2]; –hash[‘t’ – ‘a’]; –hash[‘w’ – ‘a’]; –hash[‘o’ – ‘a’]; } while (hash[‘u’ – ‘a’]) { // 4 ++digits[4]; –hash[‘f’ – ‘a’]; –hash[‘o’ – ‘a’]; –hash[‘u’ – ‘a’]; –hash[‘r’ – ‘a’]; } while (hash[‘x’ – ‘a’]) { // 6 ++digits[6]; –hash[‘s’ – ‘a’]; –hash[‘i’ – ‘a’]; –hash[‘x’ – ‘a’]; } while (hash[‘g’ – ‘a’]) { // 8 ++digits[8]; –hash[‘e’ – ‘a’]; –hash[‘i’ – ‘a’]; –hash[‘g’ – ‘a’]; –hash[‘h’ – ‘a’]; –hash[‘t’ – ‘a’]; } while (hash[‘o’ – ‘a’]) { // 1 ++digits[1]; –hash[‘o’ – ‘a’]; –hash[‘n’ – ‘a’]; –hash[‘e’ – ‘a’]; } while (hash[‘t’ – ‘a’]) { // 3 ++digits[3]; –hash[‘t’ – ‘a’]; –hash[‘h’ – ‘a’]; –hash[‘r’ – ‘a’]; –hash[‘e’ – ‘a’]; –hash[‘e’ – ‘a’]; } while (hash[‘f’ – ‘a’]) { // 5 ++digits[5]; –hash[‘f’ – ‘a’]; –hash[‘i’ – ‘a’]; –hash[‘v’ – ‘a’]; –hash[‘e’ – ‘a’]; } while (hash[‘s’ – ‘a’]) { // 7 ++digits[7]; –hash[‘s’ – ‘a’]; –hash[‘e’ – ‘a’]; –hash[‘v’ – ‘a’]; –hash[‘e’ – ‘a’]; –hash[‘n’ – ‘a’]; } while (hash[‘i’ – ‘a’]) { // 9 ++digits[9]; –hash[‘n’ – ‘a’]; –hash[‘i’ – ‘a’]; –hash[‘n’ – ‘a’]; –hash[‘e’ – ‘a’]; } string ans = ""; for (int i = 0; i < 10; i++) { ans += string(digits[i], ‘0’ + i); } return ans; } }; [/cpp] 本代码提交AC,用时26MS。]]>

LeetCode Battleships in a Board

LeetCode Battleships in a Board Given an 2D board, count how many different battleships are in it. The battleships are represented with 'X's, empty slots are represented with '.'s. You may assume the following rules:

  • You receive a valid board, made of only battleships or empty slots.
  • Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
  • At least one horizontal or vertical cell separates between two battleships – there are no adjacent battleships.
Example:
X..X
...X
...X
In the above board there are 2 battleships. Invalid Example:
...X
XXXX
...X
This is an invalid board that you will not receive – as battleships will always have a cell separating between them. Follow up: Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?
这一题的题意有点难懂,要问一个面板上有多少个舰队,注意是舰队,而不是单个的战舰。比如第一个例子中,为什么有两个舰队呢,左上角单独的X是一个舰队,右边的一列是另一个舰队,所以一共有两个舰队。 题目还限制了舰队只可能是横向或者纵向排列的,而且两个舰队之间至少有一个空位.隔开。 因为题中说所有测试数据都是合法的,且两个舰队之间至少有一个空位.隔开,所以可以用深搜DFS找有多少个X连成的区域,就有多少个舰队。完整代码如下: [cpp] class Solution { public: void dfs(vector<vector<char>>& board, vector<vector<char>>& mark, int i, int j) { if (mark[i][j] == 1)return; if (board[i][j] == ‘.’)return; mark[i][j] = 1; if (i – 1 >= 0) { dfs(board, mark, i – 1, j); } if (i + 1 < board.size()) { dfs(board, mark, i + 1, j); } if (j – 1 >= 0) { dfs(board, mark, i, j – 1); } if (j + 1 < board[i].size()) { dfs(board, mark, i, j + 1); } } int countBattleships(vector<vector<char>>& board) { int ans = 0; vector<vector<char>> mark(board.size(), vector<char>(board[0].size(), 0)); for (int i = 0; i < board.size(); ++i) { for (int j = 0; j < board[i].size(); ++j) { if (mark[i][j] == 0 && board[i][j] == ‘X’) { ++ans; dfs(board, mark, i, j); } } } return ans; } }; [/cpp] 本代码提交AC,用时3MS。 Follow up中提到能否只用O(1)空间,且one-pass,网上题解提到,一个合法舰队的起始点的左边和上边肯定是空位.,否则这个X就会和其左边或者上边的X组成一个更大的舰队。所以我们只需要找面板中其左边和上边是.的X的个数。完整代码如下: [cpp] class Solution2 { public: int countBattleships(vector<vector<char>>& board) { int ans = 0; for (int i = 0; i < board.size(); ++i) { for (int j = 0; j < board[i].size(); ++j) { if (board[i][j] == ‘X’) { if ((i == 0 || board[i – 1][j] == ‘.’) && (j == 0 || board[i][j – 1] == ‘.’)) { ++ans; } } } } return ans; } }; [/cpp] 本代码提交AC,用时6MS。]]>