hbk oa

douya 发表于 2015-8-30 12:24
就按我说的那么做就好，他只有一个testcase，不大

谢谢了。。。顺便update一下，我onsite已挂，OA的时候没考到这个题。不过权当刷题自己做了下，没按你说的做，稍微麻烦了点，不过可能快那么一点
、

1. #include <iostream>
   
2. #include <climits>
   
3. #include <string>
   
4. using namespace std;
   
5. 
   
6. /**
   
7. * algorithm class to find the number with:
   
8. * 1) base of 17 representation is palindrome
   
9. * 2) base of 2 representation has 17 consective 1 bits
   
10. */
    
11. class findNextPNumber {
    
12. public:
    
13. /**
    
14.   * @string input, input string representing a number using 17 as base
    
15.   *       which has p form
    
16.   * @return unsigned long long, return the next 17 based palidoromed number
    
17.   *           which has at least 17 consecutive 1 bits
    
18.   */
    
19. unsigned long long findNextPNumber17Bits(const string& input) {
    
20.   string cur = input;
    
21.   string next;
    
22.   while (1) {
    
23.    next = nextPNumber(cur);
    
24.    unsigned long long num = decode(next);
    
25.    if (num == ULLONG_MAX) //
    
26.     return 0;
    
27.    if (count_consecutive_ones(num) >= 17) {
    
28.     return num;
    
29.    }
    
30.    cur = next;
    
31.   }
    
32.   return 0;
    
33. }
    
34. private:
    
35. /**
    
36.   * Test if an input string contains all 'G's (16)
    
37.   * if all is 'G', return true
    
38.   * else return false
    
39.   */
    
40. bool isAll16s(const string &num) {
    
41.   int n = num.size();
    
42.   for (int i = 0; i < n; i++) {
    
43.    if (num[i] != 'g')
    
44.     return false;
    
45.   }
    
46.   return true;
    
47. }
    
48. ;
    
49. /**
    
50.   *  input a string with 17 as base and output
    
51.   *  the value as 10 base
    
52.   */
    
53. unsigned long long decode(const string& in) {
    
54.   unsigned long long result = 0;
    
55.   int n = in.size();
    
56.   for (int i = 0; i < n; i++) {
    
57.    if (isdigit(in[i]))
    
58.     result = result * 17 + in[i] - '0';
    
59.    else
    
60.     result = result * 17 + (10 + in[i] - 'a');
    
61.   }
    
62.   return result;
    
63. }
    
64. ;
    
65. 
    
66. /**
    
67.   *  count the maximum consecutive bits of 1s
    
68.   */
    
69. int count_consecutive_ones(unsigned long long input) {
    
70.   int count = 0;
    
71.   while (input) {
    
72.    input = (input & (input << 1));
    
73.    count++;
    
74.   }
    
75.   return count;
    
76. }
    
77. 
    
78. /**
    
79.   * generate next p number
    
80.   */
    
81. string nextPNumber(const string& num) {
    
82.   if (isAll16s(num))
    
83.    return '1' + string(num.size(), '0') + '1';
    
84.   int n = num.size();
    
85.   int mid = n / 2;
    
86.   int carry = 1;
    
87.   int i = mid - 1;
    
88.   int nums[n];
    
89.   // decode of special chars
    
90.   for (int i = 0; i < n; i++) {
    
91.    if (isdigit(num[i]))
    
92.     nums[i] = num[i] - '0';
    
93.    else
    
94.     nums[i] = 10 + num[i] - 'a';
    
95.   }
    
96.   int j;
    
97.   // If there are odd digits, then increment
    
98.   // the middle digit and store the carry
    
99.   if (n % 2 == 1) {
    
100.    nums[mid] += carry;
     
101.    carry = nums[mid] / 17;
     
102.    nums[mid] %= 17;
     
103.    j = mid + 1;
     
104.   } else
     
105.    j = mid;
     
106. 
     
107.   // Add 1 to the rightmost digit of the left side, propagate the carry
     
108.   // towards MSB digit and simultaneously copying mirror of the left side
     
109.   // to the right side.
     
110.   while (i >= 0) {
     
111.    nums[i] += carry;
     
112.    carry = nums[i] / 17;
     
113.    nums[i] %= 17;
     
114.    nums[j++] = nums[i--]; // copy mirror to right
     
115.   }
     
116.   // encode to special chars
     
117.   string result;
     
118.   for (int i = 0; i < n; i++) {
     
119.    if (nums[i] < 10)
     
120.     result += (nums[i] + '0');
     
121.    else
     
122.     result += (nums[i] - 10 + 'a');
     
123.   }
     
124.   return result;
     
125. }
     
126. ;
     
127. 
     
128. };
     
129. int main() {
     
130. string cur = "19b91";
     
131. findNextPNumber solver;
     
132. cout << solver.findNextPNumber17Bits(cur);
     
133. return 0;
     
134. }

复制代码

ydxdad 发表于 2015-9-2 14:07
谢谢了。。。顺便update一下，我onsite已挂，OA的时候没考到这个题。不过权当刷题自己做了下，没按你说的 ...

嗯嗯，加油！我之前onsite也跪了，挺奇怪的公司

xieqilu1989 发表于 2015-3-13 02:16
卧槽，居然这公司OA还有不同的题目，我的不是这个题目

请问你的是什么题目啊？能分享一下吗？我也马上要做他的OA了。

请问楼主，那个testcase是那个数字啊，想自己写一下看看对不对。谢谢！

ydxdad 发表于 2015-9-2 14:07
谢谢了。。。顺便update一下，我onsite已挂，OA的时候没考到这个题。不过权当刷题自己做了下，没按你说的 ...

请问你OA是什么题呀？能分享一下吗？谢谢

请问这个“下一个具有这两个性质的数”，是说比这个大的数，在17-based里是palidromic的，在二进制里全是"1"的数吗？还是说在2进制*中间*至少有一段是带有17个1的，也就是说可以是11001111111111111111111111111111111111111100000这样的，只要中间有一段有连续17个1。还是说这两个性质可以是比如再19-based里是palindromic的，在2进制里有19个1?

请问楼主你投的什么职位呀

请问有最近的他家电面或者OA的题目吗？ 还是题目一直没变？？