这是我的一个面试问题.给定N个元素的数组,其中元素恰好出现N/2次,其余N/2个元素是唯一的.你如何找到运行时间更好的元素？
请记住元素没有排序,你可以假设N是偶数.例如,
input array [] = { 10, 2, 3, 10, 1, 4, 10, 5, 10, 10 }
所以这里10次出现5次,即N/2次.
我知道O(n)运行时的解决方案.但仍期待通过O(log n)了解更好的解决方案.
我必须在接下来的几个星期里采访一些C++候选人,作为公司最资深的程序员,我希望能够弄清楚这些人是否知道他们在做什么.
那么有人有任何建议吗？
我个人不喜欢被留在一个房间来填写一些C++问题,所以我宁愿做一个更复杂的测试,我可以跟访谈者谈谈他们的方法等等.也就是说他们是否得到正确的答案并不重要,因为他们如何处理我感兴趣的问题.我不在乎他们是否理解语言的模糊特征,但我确实关心他们对指针有很好的理解以及理解指针和引用之间的差异.我也很想知道他们如何处理给定问题的优化,因为在我看来,固态快速代码是必须的.
因此,我们将非常感谢您对这些方面的任何建议!
问题我是在面试时给出的.我接近解决方案,但不幸的是没有解决它.
假设我们有一个包含N个类型的序列long.并且我们确切地知道,在这个序列中,每个数字确实恰好发生n次,除了恰好出现m次的一个数字(0 < m < n).我们如何通过O(N)运算和O(1)额外内存找到该数字？
对于最简单的情况(当n = 2且m = 1时),我们应该做的只是xor按顺序对每个数字执行累加.结果将等于所需的数字.但是我在试图处理任意的m和n时陷入困境.
我很欣赏实际的C++解决方案.
编辑:我们先验地知道m和n的实际值.
例.我们知道n = 3且m = 2.序列(N = 8)是
5 11 5 2 11 5 2 11
在这种特殊情况下,正确的答案是2,因为它只发生了两次.
我试过下面的代码.我从其他一些帖子中获取了这段代码,这些帖子根据作者是正确的.但是当我尝试跑步时,它并没有给我确切的结果.
这主要是按顺序打印偶数和奇数值.
public class PrintEvenOddTester {
public static void main(String ... args){
Printer print = new Printer(false);
Thread t1 = new Thread(new TaskEvenOdd(print));
Thread t2 = new Thread(new TaskEvenOdd(print));
t1.start();
t2.start();
}
}
class TaskEvenOdd implements Runnable {
int number=1;
Printer print;
TaskEvenOdd(Printer print){
this.print = print;
}
@Override
public void run() {
System.out.println("Run method");
while(number<10){
if(number%2 == 0){
System.out.println("Number is :"+ number);
print.printEven(number);
number+=2;
}
else {
System.out.println("Number is :"+ number);
print.printOdd(number);
number+=2;
}
}
}
}
class Printer …给定n×n实数矩阵.您可以擦除任何数字(从0到n)的行和任何数字(从0到n)的列,然后计算剩余条目的总和.想出一个算法,找出要擦除的行和列,以便最大化该总和.
例如,给定
A = [1,51,3,1,100,199,3], maxSum = 51 + 1 + 199 = 251.
显然max(oddIndexSum,evenIndexSum)也不能正常工作.
我遇到的主要问题是我无法为元素提出选择标准.在给定选择标准的情况下,拒绝标准是微不足道的.
标准最大子序列算法似乎不适用于此处.我尝试过一种动态编程方法,但也无法想出.我能想到的唯一方法是使用遗传算法的方法.
你会怎么做？
给定一个字符串,找出使该单词成为回文所需的最小字符数.例子:
ABBA : 0 (already a palindrome) ABB: 1 FAE: 2 FOO: 1
这个问题与从两个字符串中找到最长序列或子字符串的类型略有不同.
给定两个大小相同的字符串N,找到每个字符串中最长的子字符串,使得子字符串包含相同的字符包.
两个子串可能不一定具有相同的序列.但他们必须拥有相同的字符包.
例如,
a = ABCDDEGF b = FPCDBDAX
最长匹配的字符包是ABCDD(来自a的ABCDD,来自b的CDBDA)
如何解决这个问题呢？
UPDATE
目标是从每个输入字符串中找到子字符串,以便它们具有相同的字符包.通过说"子串",它们必须是连续的字符.
更新:最初我想到了一种动态编程方法.它的工作原理如下.
为了比较相同长度K的两袋字符,需要O(K)时间来实现.将每个字符串转换为缩短形式:
ABCDDEGF -> A1B1C1D2E1G1F1
FPCDBDAX -> A1B1C1D2F1P1X1
缩短形式是按字母表排序的字母表,后跟字符串中的频率数.构造,排序和比较缩短形式总共需要O(K)时间.(虽然可以通过使用字符数组来实现)
如果两个字符的缩短形式具有相同的字符和相应的频率,则它们是相同的.
此外,需要O(logK)时间才能找到两个字符串之间的差异字符.
现在,对于两个输入字符串:
最坏的情况是O(N 3),最好的情况是O(N).有什么好主意吗？
我正在尝试使用带有处理程序(c#)的jquery ajax上传文件.问题是,当我调用处理程序时,我得到了
context.Request.File.Count=0
这是aspx代码:
<!--aspx file code-->
<script language="javascript" type="text/javascript">
$().ready(function ()
{
$('#save').click(function (e)
{
CalluploaderHandler();
});
});
function CalluploaderHandler()
{
$.ajax({
type: "POST",
url: "Services/UPloader.ashx",
contentType: "application/json; charset=utf-8",
success: OnComplete,
error: OnFail
});
return false;
}
function OnComplete(result)
{
alert('Success');
}
function OnFail(result)
{
alert('Request failed');
}
</script>
</head>
<body>
<form enctype="multipart/form-data">
<label for="file">
Filename:</label>
<input name="file" id="file" type="file">
<input id="save" name="submit" value="Submit" type="submit">
</form>
</body>
</html>
c#代码处理程序:
/* handler*/
public void ProcessRequest(HttpContext context)
{
string savedFileName = …当使用clang(libclang)和特定函数clang_parseTranslationUnit和clang_reparseTranslationUnit时,我有一个关于解析性能的问题.
我正在尝试优化这个过程,但我已经完全没有想法了.情况如下 - 我有一个.cpp源代码,其中包含很多头文件.这个标题很少变化.然而.cpp源代码变化很大,我需要经常重新解析它.因此,有可能"预编译/预编译"所有标头并创建.pch文件,然后在解析.cpp时使用它.但问题是,我只能使用一个.pch.所以,我需要从所有包含的头文件中创建一个.pch.但是,稍后,当我包含一些其他头文件时,我需要重新解析所有头文件,即使它们根本没有更改.此外,这是问题,我需要明确知道,.cpp中包含哪些标头(这不是很方便,因为这意味着,我必须扫描至少包括我自己,然后创建一个.pch然后在解析.cpp源时使用它.
还有其他选择来优化流程吗？我希望,当我使用clang_parseTranslationUnit和后来的clang_reparseTranslationUnit时,实际上将以这种方式优化解析(至少所有未更改的头,不需要再次重新解析).但是,它并不像那样.