百科问答小站 logo
百科问答小站 font logo



这个号称「微软的面试题」,该如何解答? 第1页

  

user avatar   be5invis 网友的相关建议: 
      

什么时候加上了绝对值……

带绝对值就是 Partition Problem 了,有一个伪多项式的 DP 算法,思路大概是这样的:

       var cache = ...; function P(a, j, l, s) { // a[0..j] 中有长度为 l 且总和为 s 的子集吗?     if(cache.has(j, l, s)) return cache.find(j, l, s) // 缓存     if(l === 0 && s === 0) return cache.save(j, l, s, true);     if(l === 0 && s !== 0 || j === 0 && l > 0 || j === 0 && s !== 0) return cache.save(j, l, s, false);     return cache.save(j, l, s, P(a, j - 1, l, s) || P(a, j - 1, l - 1, s - a[j - 1])) }  for(var s = Math.floor((sum(a) + sum(b)) / 2); s >= 0; s--){     if(P(a.concat(b), n * 2, n, s)) { ... } }      

不带绝对值的话

先要说清楚定义,因为如果只能交换 ab 中的对应项,那么很简单的贪心法就能解决;如果可以多次任意交换,那么就是排序完切割;如果是一次交换若干对的话,是 2n×2n 的二分图最佳匹配,用 KM。




  

相关话题

  程序员怎么赚钱? 
  华为最近又开始招人了,华为最近怎么了呢? 
  游戏或者APP出了bug,该不该骂程序员? 
  微软选择在2014年这个时候公开MS-DOS 2.0和Word for Windows 1.1A的源代码,有什么意义? 
  你是怎么误打误撞做了程序猿? 
  如何看待 2020 年 10 月内测版的知乎盐值体系?对此你有什么想法? 
  微软对于诺基亚是仁至义尽还是无情抛弃? 
  微软会继续改善 Windows 10 的更新策略吗? 
  微软有哪些被市场遗忘或烂尾的项目? 
  很厉害的程序员都读过CSAPP,SICP,操作系统,算法导论,编译原理这些书吗? 

前一个讨论
如何评价微软2016年3月18日Windows 10 Mobile推送放弃绝大多数旧机型的决定?
下一个讨论
如何评价微软PowerShell将支持SSH?





© 2024-06-17 - tinynew.org. All Rights Reserved.
© 2024-06-17 - tinynew.org. 保留所有权利