2018头条春招笔试题解

怼烎@ 2022-05-29 13:27 260阅读 0赞

原文链接：[https://www.nowcoder.com/discuss/70299?type=2&order=0&pos=9&page=2][https_www.nowcoder.com_discuss_70299_type_2_order_0_pos_9_page_2]

头条题目: [ https://blog.csdn.net/flushhip/article/details/79685488][https_blog.csdn.net_flushhip_article_details_79685488]

头条测试: [https://blog.csdn.net/flushhip/article/details/79562199][https_blog.csdn.net_flushhip_article_details_79562199]

第一题：

双指针：

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div> 
     <br> 
    </div> 
    <div> 
     <br> 
    </div></td> 
   <td> 
    <div> 
     <div> 
      <code>#include &lt;bits/stdc++.h&gt;</code> 
     </div> 
     <div> 
      <code>using</code> 
      <code>namespace</code> 
      <code>std;</code> 
     </div> 
     <div> 
      <code>typedef</code> 
      <code>long</code> 
      <code>long</code> 
      <code>ll;</code> 
     </div> 
     <div> 
      <code>const</code> 
      <code>int</code> 
      <code>N = 1e6+7;</code> 
     </div> 
     <div> 
      <code>int</code> 
      <code>a[N];</code> 
     </div> 
     <div> 
      <code>int</code> 
      <code>main()</code> 
     </div> 
     <div> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>int</code> 
      <code>n,k;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>scanf</code> 
      <code>(</code> 
      <code>"%d%d"</code> 
      <code>,&amp;n,&amp;k);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>i=0;i&lt;n;++i) </code> 
      <code>scanf</code> 
      <code>(</code> 
      <code>"%d"</code> 
      <code>,&amp;a[i]);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>sort(a, a+n);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>n = unique(a, a+n) -a;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>int</code> 
      <code>r = 0, ans=0;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>l=0; l&lt;n;++l)</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>while</code> 
      <code>(r&lt;n&amp;&amp;a[r]-a[l]&lt;k) ++r;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>if</code> 
      <code>(r==n) </code> 
      <code>break</code> 
      <code>;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>if</code> 
      <code>(a[r]-a[l] == k) ++ans;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>printf</code> 
      <code>(</code> 
      <code>"%d\n"</code> 
      <code>, ans);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>return</code> 
      <code>0;</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

第二题：

BFS

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div> 
     <br> 
    </div></td> 
   <td> 
    <div> 
     <div> 
      <code>#include &lt;bits/stdc++.h&gt;</code> 
     </div> 
     <div> 
      <code>using</code> 
      <code>namespace</code> 
      <code>std;</code> 
     </div> 
     <div> 
      <code>typedef</code> 
      <code>pair&lt;</code> 
      <code>int</code> 
      <code>,</code> 
      <code>int</code> 
      <code>&gt; pii;</code> 
     </div> 
     <div> 
      <code>map&lt;pair&lt;</code> 
      <code>int</code> 
      <code>,</code> 
      <code>int</code> 
      <code>&gt; , </code> 
      <code>int</code> 
      <code>&gt; mp;</code> 
     </div> 
     <div> 
      <code>int</code> 
      <code>main()</code> 
     </div> 
     <div> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>int</code> 
      <code>n;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>scanf</code> 
      <code>(</code> 
      <code>"%d"</code> 
      <code>,&amp;n);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>queue&lt;pii&gt; q;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>q.push(make_pair(1, 1));</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>mp[make_pair(1,1)]=0;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>while</code> 
      <code>(!q.empty())</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>pii pr = q.front();q.pop();</code> 
     </div> 
     <div> 
      <code>//&nbsp; &nbsp; &nbsp; &nbsp; printf("%d %d\n",pr.first, pr.second);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>if</code> 
      <code>(pr.first == n)</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>printf</code> 
      <code>(</code> 
      <code>"%d\n"</code> 
      <code>, mp[pr]);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>exit</code> 
      <code>(0);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>pii t=pr;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>t.second = t.first; t.first*=2;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>if</code> 
      <code>(!mp.count(t))</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>q.push(t);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>mp[t] = mp[pr]+1;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>t=pr;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>t.first=t.first+t.second;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>if</code> 
      <code>(!mp.count(t))</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>q.push(t);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>mp[t] = mp[pr]+1;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>return</code> 
      <code>0;</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

第三题：

模拟。

<table> 
 <tbody> 
  <tr> 
   <td>&nbsp;</td> 
   <td> 
    <div> 
     <div> 
      <code>#include &lt;bits/stdc++.h&gt;</code> 
     </div> 
     <div> 
      <code>using</code> 
      <code>namespace</code> 
      <code>std;</code> 
     </div> 
     <div> 
      <code>typedef</code> 
      <code>long</code> 
      <code>long</code> 
      <code>ll;</code> 
     </div> 
     <div> 
      <code>char</code> 
      <code>s[107];</code> 
     </div> 
     <div> 
      <code>char</code> 
      <code>G[5][10][8] = { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>{ </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"6...6"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>},</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>{ </code> 
      <code>"6...6"</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>, </code> 
      <code>"6...6"</code> 
      <code>, </code> 
      <code>"6...."</code> 
      <code>, </code> 
      <code>"6...."</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>, </code> 
      <code>"6...6"</code> 
      <code>, </code> 
      <code>"6...6"</code> 
      <code>},</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>{ </code> 
      <code>"6...6"</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>},</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>{ </code> 
      <code>"6...6"</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>, </code> 
      <code>"6...."</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>, </code> 
      <code>"6...6"</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>, </code> 
      <code>"6...6"</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>},</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>{ </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"....6"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>, </code> 
      <code>"66666"</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>};</code> 
     </div> 
     <div> 
      <code>ll cal()</code> 
     </div> 
     <div> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>int</code> 
      <code>n = </code> 
      <code>strlen</code> 
      <code>(s);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>ll sum=0, cur=0, prd=1;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>i=0; i&lt;n; ++i)</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>if</code> 
      <code>(</code> 
      <code>isdigit</code> 
      <code>(s[i])) cur=cur*10+s[i]-</code> 
      <code>'0'</code> 
      <code>;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>else</code> 
      <code>if</code> 
      <code>(s[i] == </code> 
      <code>'-'</code> 
      <code>)</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>sum+=prd*cur;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>cur=0;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>prd=-1;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>else</code> 
      <code>if</code> 
      <code>(s[i] == </code> 
      <code>'+'</code> 
      <code>)</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>sum+=prd*cur;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>cur=0;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>prd=1;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>else</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>prd*=cur;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>cur=0;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>return</code> 
      <code>sum+prd*cur;</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
     <div> 
      <code>int</code> 
      <code>main()</code> 
     </div> 
     <div> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>int</code> 
      <code>T;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>scanf</code> 
      <code>(</code> 
      <code>"%d"</code> 
      <code>,&amp;T);</code> 
      <code>while</code> 
      <code>(T--)</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>scanf</code> 
      <code>(</code> 
      <code>"%s"</code> 
      <code>, s);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>ll ans = cal();</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>i=0; i&lt;5; ++i)</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>vector&lt;</code> 
      <code>int</code> 
      <code>&gt; v;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>ll tmp = ans;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>while</code> 
      <code>(tmp) v.push_back(tmp%10),tmp/=10;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>reverse(v.begin(), v.end());</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>if</code> 
      <code>(v.empty()) v.push_back(0);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>j=0; j&lt;v.size(); ++j)</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>printf</code> 
      <code>(</code> 
      <code>"%s%s"</code> 
      <code>,G[i][v[j]], j+1==v.size()?</code> 
      <code>"\n"</code> 
      <code>:</code> 
      <code>".."</code> 
      <code>);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; </code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp; </code> 
      <code>return</code> 
      <code>0;</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

第四题：

只能从均值大的集合往均值小的集合里放。

取数只能取出现次数等于1的数  
放数只能放没出现过的数  
从小的数开始放可以使均值小的集合均值上升慢，均值大的集合均值上升快，这样最优。

第五题：BFS

[https_www.nowcoder.com_discuss_70299_type_2_order_0_pos_9_page_2]: https://www.nowcoder.com/discuss/70299?type=2&order=0&pos=9&page=2
[https_blog.csdn.net_flushhip_article_details_79685488]: https://blog.csdn.net/flushhip/article/details/79685488
[https_blog.csdn.net_flushhip_article_details_79562199]: https://blog.csdn.net/flushhip/article/details/79562199