有人问我这个问题:
String s = "abc"; // creates one String object and one
// reference variable
In this simple case, "abc" will go in the pool and s will refer to it.
String s = new String("abc"); // creates two objects,
// and one reference variable*
基于以上细节,在下面的代码的println语句之前创建了多少个String对象和多少个引用变量？
String s1 = "spring ";
String s2 = s1 + "summer ";
s1.concat("fall ");
s2.concat(s1);
s1 += "winter ";
System.out.println(s1 + " " + s2);
我的回答是这个代码片段的结果是春冬春夏
有两个参考变量,s1和s2.共创建了八个String对象:"spring","summer"(lost),"spring summer","fall"(lost),"spring fall"(lost),"spring spring spring"(丢失) ),"冬天"(丢失),"春天的冬天"(此时"春天"丢失).
在此过程中,八个String对象中只有两个不会丢失.
这是对的吗？
有人问我这个问题:
您将获得两个整数列表,每个整数都按升序排序,每个整数的长度为n.两个列表中的所有整数都不同.您希望找到两个列表的并集的第n个最小元素.(也就是说,如果您连接列表并按升序对结果列表进行排序,则该元素将位于第n个位置.)
我的解决方案:假设列表是0索引的.
O(n)解决方案:一个直接的解决方案是观察数组已经排序,因此我们可以合并它们,并在n步之后停止.第一个n-1元素不需要复制到新数组中,因此该解决方案需要O(n)时间和O(1)内存.
O(log2 n)解决方案:O(log2 n)解决方案在每个列表上使用交替二分搜索.简而言之,它采用第一个列表(l1 [p1])中当前搜索间隔中的中间元素,并在l2中搜索它.由于元素是唯一的,我们将找到最多2个最接近l1 [p1]的值.根据它们相对于l1 [p1-1]和l1 [p1 + 1]及其指数p21和p22的值,我们要么返回第n个元素,要么递归:如果是(最多)3中的任何一个的总和l1中的索引可以与l2中的(最多)2个索引中的一个组合,以便l1 [p1']和l2 [p2']在两个列表的排序并集中彼此相邻并且p1'+ p2'= n或p1'+ p2'= n + 1,我们返回5个元素中的一个.如果p1 + p2> n,我们在l1中递归搜索间隔的左半部分,否则我们递归到正确的间隔.这样,对于l1中的O(log n)个可能的中点,我们在l2中进行O(log n)二进制搜索.因此运行时间为O(log2 n).
O(log n)解决方案:假设列表l1和l2对其任何元素具有持续访问时间,我们可以使用修改版本的二进制搜索来获得O(log n)解决方案.最简单的方法是在其中一个列表中搜索索引p1,并在另一个列表中计算相应的索引p2,以便始终p1 + p2 = n.(这假定列表是从1开始索引的.)首先,我们检查一个列表的所有元素都小于另一个列表中的任何元素的特殊情况:如果l1 [n] <l2 [0]返回l1 [n].如果l2 [n] <l1 [0]返回l2 [n].如果我们在此步骤之后找不到第n个最小元素,请使用近似伪代码调用findNth(1,n):
findNth(start,end)
p1 = (start + end)/2
p2 = n-p1
if l1[p1] < l2[p2]:
if l1[p1 + 1] > l2[p2]:
return l2[p2]
else:
return findNth(p1+1, end)
else:
if l2[p2 + 1] > l1[p1]:
return l1[p1]
else: …