求 [1.. n] 以内的 “峰数”个数, 对于一个数 ,的数位有 个, 的第 i 个数位上的数字为 。 满足下面三个条件的 就是峰数 1.  的数位有奇数个 2.  3.  举个例子: 1345421 , 12321 就是峰数 1235521, 12332, 13523 就不是峰数-笔试面试资料

这是qklbishe.com第19501 篇笔试面试资料
提供答案分析,通过本文《求 [1.. n] 以内的 “峰数”个数,
对于一个数 ,的数位有 个, 的第 i 个数位上的数字为 。
满足下面三个条件的 就是峰数
1.  的数位有奇数个
2. 
3. 
举个例子:
1345421 , 12321 就是峰数
1235521, 12332, 13523 就不是峰数-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:
求 [1.. n] 以内的 “峰数”个数,
对于一个数 求 [1.. n] 以内的 “峰数”个数,   对于一个数 ,的数位有 个, 的第 i 个数位上的数字为 。   满足下面三个条件的 就是峰数   1.  的数位有奇数个   2.    3.    举个例子:   1345421 , 12321 就是峰数   1235521,  12332, 13523 就不是峰数求 [1.. n] 以内的 “峰数”个数,   对于一个数 ,的数位有 个, 的第 i 个数位上的数字为 。   满足下面三个条件的 就是峰数   1.  的数位有奇数个   2.    3.    举个例子:   1345421 , 12321 就是峰数   1235521,  12332, 13523 就不是峰数的数位有 求 [1.. n] 以内的 “峰数”个数,   对于一个数 ,的数位有 个, 的第 i 个数位上的数字为 。   满足下面三个条件的 就是峰数   1.  的数位有奇数个   2.    3.    举个例子:   1345421 , 12321 就是峰数   1235521,  12332, 13523 就不是峰数个,求 [1.. n] 以内的 “峰数”个数,   对于一个数 ,的数位有 个, 的第 i 个数位上的数字为 。   满足下面三个条件的 就是峰数   1.  的数位有奇数个   2.    3.    举个例子:   1345421 , 12321 就是峰数   1235521,  12332, 13523 就不是峰数 的第 i 个数位上的数字为 求 [1.. n] 以内的 “峰数”个数,   对于一个数 ,的数位有 个, 的第 i 个数位上的数字为 。   满足下面三个条件的 就是峰数   1.  的数位有奇数个   2.    3.    举个例子:   1345421 , 12321 就是峰数   1235521,  12332, 13523 就不是峰数
满足下面三个条件的 求 [1.. n] 以内的 “峰数”个数,   对于一个数 ,的数位有 个, 的第 i 个数位上的数字为 。   满足下面三个条件的 就是峰数   1.  的数位有奇数个   2.    3.    举个例子:   1345421 , 12321 就是峰数   1235521,  12332, 13523 就不是峰数就是峰数
1. 求 [1.. n] 以内的 “峰数”个数,   对于一个数 ,的数位有 个, 的第 i 个数位上的数字为 。   满足下面三个条件的 就是峰数   1.  的数位有奇数个   2.    3.    举个例子:   1345421 , 12321 就是峰数   1235521,  12332, 13523 就不是峰数 的数位有奇数个
2. 求 [1.. n] 以内的 “峰数”个数,   对于一个数 ,的数位有 个, 的第 i 个数位上的数字为 。   满足下面三个条件的 就是峰数   1.  的数位有奇数个   2.    3.    举个例子:   1345421 , 12321 就是峰数   1235521,  12332, 13523 就不是峰数
3. 求 [1.. n] 以内的 “峰数”个数,   对于一个数 ,的数位有 个, 的第 i 个数位上的数字为 。   满足下面三个条件的 就是峰数   1.  的数位有奇数个   2.    3.    举个例子:   1345421 , 12321 就是峰数   1235521,  12332, 13523 就不是峰数
举个例子:
1345421 , 12321 就是峰数
1235521, 12332, 13523 就不是峰数

求 [1.. n] 以内的 “峰数”个数,   对于一个数 ,的数位有 个, 的第 i 个数位上的数字为 。   满足下面三个条件的 就是峰数   1.  的数位有奇数个   2.    3.    举个例子:   1345421 , 12321 就是峰数   1235521,  12332, 13523 就不是峰数 没有梦想何必远方
数据范围较小 可以直接暴力枚举+判断
class Solution { public:     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param n int整型       * @return int整型      */     int solve(int n) {         // write code here         int res = 0;         for (int i = 1; i <= n; ++i)             if (check(i)) res++;         return res;     }          bool check(int n)     {         vector<int> p;         while (n)         {             p.push_back(n%10);             n /= 10;         }         reverse(p.begin(), p.end());         int m = (int)p.size();         if (!(m&1)) return false;         int mid = (m+1)/2-1;         int l = mid, r = mid;         while (l > 0 && p[l] > p[l-1]) l--;         while (r < m-1 && p[r] > p[r+1]) r++;         return l <= 0 && r >= m-1;     } };

再贴一个优化过的办法 逻辑稍微有点复杂

class Solution { public:     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param n int整型       * @return int整型      */     int solve(int n) {         // write code here         vector<int> p;         list<int> q;         work(n, p);         int len = (int)p.size(), res = 0;         if (len == 1) return n;         int dp[10][10];         memset(dp, 0, sizeof(dp));         init(dp);         auto calc = [&](int m)->int {             if (!(m&1)) return 0;             int mid = (m+1)/2, ans = 0;             for (int i = mid; i < 10; ++i)                 ans += dp[i-1][mid-1]*dp[i][mid-1];             return ans;         };         for (int i = 1; i < len; i += 2) res += calc(i);         int pre[2][10], post[2][10];         memset(pre, 0, sizeof pre);         memset(post, 0, sizeof post);         function<void(int,int,bool)> getPre = [&](int beg, int end, bool less)         {             if (beg == end)             {                 pre[less][q.back()]++;                 return;             }             int low = (q.empty() ? 1 : q.back()+1);             int up = (less ? 9 : p[beg]);             for (int i = low; i <= up; ++i)             {                 bool le = (i < p[beg]);                 q.push_back(i);                 getPre(beg+1, end, less || le);                 q.pop_back();             }         };         function<void(int,int,bool)> getPost = [&](int beg, int end, bool less)         {             if (beg == end)             {                 post[less][q.front()]++;                 return;             }             int low = 0;             int up = (q.empty() ? 9 : q.back()-1);             if (!less) up = min(up, p[beg]);             for (int i = low; i <= up; ++i)             {                 bool le = (i < p[beg]);                 q.push_back(i);                 getPost(beg+1, end, less || le);                 q.pop_back();             }         };         if (!(len&1)) return res;         getPre(0, (len+1)/2-1, 0);         getPost((len+1)/2, len, 0);         for (int i = 0; i < 2; ++i)             for (int j = 1; j < 10; ++j)             {                 pre[i][j] += pre[i][j-1];                 post[i][j] += post[i][j-1];             }         int mid = (len+1)/2;         for (int i = mid; i < 10; ++i)         {             res += pre[1][i-1] * dp[i][mid-1];             if (i < p[mid-1])                 res += pre[0][i-1] * dp[i][mid-1];             else if (i == p[mid-1])                 res += pre[0][i-1] * (post[0][i-1]+post[1][i-1]);         }         return res;     }          void init(int dp[][10])     {         for (int i = 0; i < 10; ++i)             dp[i][0] = 1;         for (int i = 1; i < 10; ++i)             for (int j = 1; j <= i; ++j)                 dp[i][j] = dp[i-1][j]+dp[i-1][j-1];     }          void work(int n, vector<int> &p)     {         p.resize(0);         while (n)         {             p.push_back(n%10);             n /= 10;         }         reverse(p.begin(), p.end());     } };

今天 09:44:28 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 求 [1.. n] 以内的 “峰数”个数, 对于一个数 ,的数位有 个, 的第 i 个数位上的数字为 。 满足下面三个条件的 就是峰数 1.  的数位有奇数个 2.  3.  举个例子: 1345421 , 12321 就是峰数 1235521, 12332, 13523 就不是峰数-笔试面试资料

提供最优质的资源集合

立即查看 了解详情