华为OD机试题

第一题动态规划不就是确定a[0],a[1],a[2]，后面直接a[n]=a[n-1]+a[n-2]+a[n-3]，或者直接来个条件判断也行。如果用递归没用好，而且N比较大的话，直接给你栈溢出。😏 第二题就是滑动数组，双指针写。 第三题没看懂楼主的意思，感觉是字符串处理，但不含有回文子串还是回文串我就不清楚了，回文子串可能会比较难，回文串就相当简单了。

第一题可以用动态规划的吧。。。

OD岗位需要性格测试吗

第三题看成N进制的问题，循环加1，满足条件或者溢出停止，这样不就能找出最先出现的了，进位问题处理好，判断子串

第一题，DP，状态方程：dp[i] = dp[i - 1] + dp[i - 3] 第二题，排序后从第一位开始找满足条件的最小数，可二分查找。 第三题，先找出字符串中第一个构成回文的index，比如"abcecba"中index为4的'c&(2248)#39;，然后让这一位加1破坏回文，这一位之后的字符全重置为'a'保证最小。循环这种操作直到没有回文子串出现。 例子： "abcdcbea"  N=5 1.找到index=4的'c&(2248)#39;，字符串变为：abcddaaa 2.找到index=4的'd'，字符串变为：abcdeaaa 3.找到index=6的'a&(417)#39;，字符串变为：abcdeaba 4.找到index=7的'a'，字符串变为：abcdeabb 5.找到index=7的'b&(1071)#39;，字符串变为：abcdeabc 字符串找第一位回文子串条件： char[i] == char[i - 1] || char[i] == char[i - 2] 先把字符串转成字符数组，处理方便。 全重置为'a'的方法还可以优化。

和我一摸一样的题😅

public class Test4 {     public static void main(String[] args) {         System.out.println(xx(50));     }     public static int xx(int step){         if(step == 1){             return 1;         }else if(step == 2){             return 1;         }else if(step == 3){             return 2;         }         return xx(step-1)+xx(step-3);     } }

第三题补充几个小函数: char charPlusPlus(char c) { return (c + 1); } char charmo(char a,char b) { return  ((a-'a&(417)#39;)%(b-'a&(417)#39;) + 'a&#39;); } int chardivid(char a, char b) { return a/b; } bool isNoPalindrome(string s) { bool ret = true; if (s.size() < 2) { return true; } for (int l = 2; l <= s.size(); l++) { for (int i = 0; i + l -1 < s.size(); i++) { string tmp = s.substr(i, l); string tmp1 = tmp; reverse(tmp1.begin(), tmp1.end()); if (tmp == tmp1) { return false; } } } return ret; }

第三题做了个字符串加法,但感觉有简单的方法: string max_string(int num, int k) { char max = 'a&(417)#39; + char(k - 1); return string(num, max); } string stringPlusPlus(string s, int k) {  char max = 'a&(417)#39; + char(k - 1);  char over = charPlusPlus(max);  string max_s = max_string(s.size(), max);  char cur;  int carry;  if (s == max_s)  {   return max_s + 'a&(417)#39;;  }  for (int i = s.size() - 1; i >= 0; i--)  {   if (i == s.size() - 1)   {    cur = s[i]+1;    s[i] = charmo(cur,over);    carry = chardivid(cur,over);   }   else   {    if (carry)    {     cur = s[i] + carry;     s[i] = charmo(cur, over);     carry = chardivid(cur, over);    }   }  }  return s; } int main() {  string input("cba");  int k = 5;  while (1)  {   input = stringPlusPlus(input, k);   if (isNoPamlid(input))   {    cout << "************success**************" << endl;    cout << input << endl;    break;   }   else if (input.size() > 2&& input.substr(0,2) == max_string(2,k))   {    cout << "none" << endl;    break;   }  }  return 0; }

问下楼主机考的成绩算通过了么？我下周也需要面试OD😂，谢谢

第三题大脑烧了都想不到什么好的方法。。。。

OD是什么？不是华为直聘吗？

华为笔试时长多少呀

楼主是科软的吗