首页 > 代码库 > 44. Decode Ways && Gray Code
44. Decode Ways && Gray Code
Decode Ways
A message containing letters from A-Z
is being encoded to numbers using the following mapping:
‘A‘ -> 1‘B‘ -> 2...‘Z‘ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example, Given encoded message "12"
, it could be decoded as "AB"
(1 2) or "L"
(12).
The number of ways decoding "12"
is 2.
思想: 动态规划,分析:
12121212: 前面为1 或者 (前面是2 且 当前值 < 7) : f(n) = f(n-1) +f (n-2);
1202: 当前值为 0,前面是 1 或 2, f(n) = f(n-2). 否则,返回 0。
其他情况, f(n) = f(n-1);
class Solution {public: int numDecodings(string s) { int n = s.size(); if(n == 0 || s[0] == ‘0‘) return 0; vector<int> f(n+1); f[0] = f[1] = 1; for(int index = 2; index <= n; ++index) { if(‘0‘ == s[index-1]) { if(‘1‘ == s[index-2] || ‘2‘ == s[index-2]) f[index] = f[index-2]; else return 0; } else if(‘1‘ == s[index-2] || ( ‘2‘ == s[index-2] && s[index-1] < ‘7‘)) f[index] = f[index-1] + f[index-2]; else f[index] = f[index-1]; } return f[n]; }};
Gray Code
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]
. Its gray code sequence is:
00 - 001 - 111 - 310 - 2
Note: For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1]
is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
思想: 方法比较巧妙。 每次改变循环一轮,只改变最高位 0 ->1。
class Solution {public: vector<int> grayCode(int n) { vector<int> vec(1, 0); for(int i = 0; i < n; ++i) { int v = 1 << i; for(int j = vec.size()-1; j >= 0; --j) vec.push_back(vec[j]+v); } return vec; }};
44. Decode Ways && Gray Code