小编pol*_*nts的帖子

我有一段时间有一个有趣的面试经历.问题开始很简单:

Q1:我们有包含数字的袋子1,2,3,..., 100.每个数字只出现一次,因此有100个数字.现在从包里随机挑出一个号码.找到丢失的号码.

当然,我之前听过这个采访问题,所以我很快回答了以下问题:

A1:嗯,这些数字的总和1 + 2 + 3 + … + N是(N+1)(N/2)(见维基百科:算术系列之和).因为N = 100,总和是5050.

因此,如果包中存在所有数字,则总和将是精确的5050.由于缺少一个数字,总和将小于此数值,差异就是该数字.所以我们可以在O(N)时间和O(1)空间中找到丢失的数字.

在这一点上,我认为我做得很好,但突然之间,这个问题发生了意想不到的变化:

Q2:这是正确的,但是现在如果缺少两个数字你会怎么做？

我之前从未见过/听过/考虑过这种变化,所以我惊慌失措,无法回答这个问题.面试官坚持要知道我的思考过程,所以我提到也许我们可以通过与预期产品进行比较来获得更多信息,或者可能在从第一遍获得一些信息后再做第二遍,但我真的只是拍摄在黑暗中而不是实际上有一条清晰的解决方案.

面试官确实试图鼓励我说有第二个等式确实是解决问题的一种方法.在这一点上,我有点不高兴(因为事先不知道答案),并询问这是一般的(阅读:"有用")编程技术,还是只是一个技巧/问题答案.

面试官的回答让我感到惊讶:你可以概括一下找到3个缺失数字的技巧.实际上,您可以将其概括为找到k个缺失的数字.

Qk:如果行李中缺少k个号码,您会如何有效地找到它？

这是几个月前,我仍然无法弄清楚这种技术是什么.显然有一个?(N)时间下限,因为我们必须扫描所有数字至少一次,但是访问者坚持解决技术的时间和空间复杂度(减去O(N)输入扫描的时间)在k而不是N中定义.

所以这里的问题很简单:

• 你会如何解决Q2？
• 你会如何解决Q3？
• 你怎么解决Qk？

澄清

• 通常有1个 …

问题:

• 什么是Java中的原始类型,为什么我经常听说不应该在新代码中使用它们？
• 如果我们不能使用原始类型,它有什么替代方案,它是如何更好的？

我在求职面试中被问到这个问题,我想知道其他人如何解决这个问题.我对Java最熟悉,但欢迎使用其他语言的解决方案.

给定一组数字,nums返回一个数字数组products,其中products[i]是所有数字的乘积nums[j], j != i.

Input : [1, 2, 3, 4, 5]
Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
      = [120, 60, 40, 30, 24]

Run Code Online (Sandbox Code Playgroud)

您必须在O(N)不使用除法的情况下执行此操作

以下代码段使用输出进行注释(如ideone.com上所示):

print "100" < "2"      # True
print "5" > "9"        # False

print "100" < 2        # False
print 100 < "2"        # True

print 5 > "9"          # False
print "5" > 9          # True

print [] > float('inf') # True
print () > []          # True

有人可以解释为什么输出是这样的？

实施细节

• 这种行为是由语言规范强制执行的,还是由实现者决定的？
• 任何主要的Python实现之间是否存在差异？
• Python语言版本之间是否存在差异？

我对这Map<?,?>不是一个事实感到惊讶Collection<?>.

我认为如果宣布这样的话会有很多意义:

public interface Map<K,V> extends Collection<Map.Entry<K,V>>

毕竟,一个Map<K,V>是集合Map.Entry<K,V>,不是吗？

那么为什么没有这样实现呢？

感谢Cletus提供了最权威的答案,但我仍然想知道为什么,如果您已经可以查看Map<K,V>as Set<Map.Entries<K,V>>(via entrySet()),它不仅仅是扩展该界面.

如果a Map是a Collection,那么元素是什么？唯一合理的答案是"键值对"

确切地说,interface Map<K,V> extends Set<Map.Entry<K,V>>会很棒!

但这提供了非常有限(并且不是特别有用)的Map抽象.

但如果是这种情况那么为什么entrySet界面指定？它必须以某种方式有用(我认为这个位置很容易争论!).

您不能询问给定键映射到的值,也不能删除给定键的条目而不知道它映射到的值.

我不是说这就是它的全部内容Map!它可以而且应该保留所有其他方法(除了entrySet现在多余的方法)!

根据文档,该方法String.valueOf(Object obj)返回:

如果参数是null,那么一个字符串等于"null"; 否则,obj.toString()返回值.

但是当我尝试这样做时怎么样:

System.out.println("String.valueOf(null) = " + String.valueOf(null));

它会引发NPE而不是？(如果你不相信,请亲自尝试!)

    Exception in thread "main" java.lang.NullPointerException
    at java.lang.String.(Unknown Source)
    at java.lang.String.valueOf(Unknown Source)

怎么会发生这种情况？文档对我说谎吗？这是Java中的一个主要错误吗？

我可以用什么类在Java中读取整数变量？

据我了解,有几种方法(也许还有其他方法)Map在Java中创建一个浅表副本:

Map<String, Object> data = new HashMap<String, Object>();
Map<String, Object> shallowCopy;

// first way
shallowCopy = new HashMap<String, Object>(data);

// second way
shallowCopy = (Map<String, Object>) ((HashMap<String, Object>) data).clone();

一种方式优于另一种方式,如果是这样,为什么？

值得一提的是,第二种方式是"Unchecked Cast"警告.所以你必须添加@SuppressWarnings("unchecked")以解决它,这有点刺激(见下文).

@SuppressWarnings("unchecked")
public Map<String, Object> getDataAsMap() {
    // return a shallow copy of the data map
    return (Map<String, Object>) ((HashMap<String, Object>) data).clone();
}

我越了解它的力量java.lang.reflect.AccessibleObject.setAccessible,我就越能对它做什么感到惊讶.这是根据我对问题的回答改编的(使用反射来更改静态最终File.separatorChar以进行单元测试).

import java.lang.reflect.*;

public class EverythingIsTrue {
   static void setFinalStatic(Field field, Object newValue) throws Exception {
      field.setAccessible(true);

      Field modifiersField = Field.class.getDeclaredField("modifiers");
      modifiersField.setAccessible(true);
      modifiersField.setInt(field, field.getModifiers() & ~Modifier.FINAL);

      field.set(null, newValue);
   }
   public static void main(String args[]) throws Exception {      
      setFinalStatic(Boolean.class.getField("FALSE"), true);

      System.out.format("Everything is %s", false); // "Everything is true"
   }
}

你可以做真正令人发指的事情:

public class UltimateAnswerToEverything {
   static Integer[] ultimateAnswer() {
      Integer[] ret = new Integer[256];
      java.util.Arrays.fill(ret, 42);
      return ret;
   }   
   public static void main(String args[]) throws Exception { …

_{这是一系列教育正则表达式文章的第二部分.它显示了向前看符号和嵌套引用如何可以用来匹配非正规languge ^ñ b ^ñ.嵌套引用首先介绍在:这个正则表达式如何找到三角形数字？}

其中一种原型非常规语言是:

L = { a^ñ b^ñ: n > 0 }

这是所有非空字符串的语言,由一些数字a后跟相同数量的字符串组成b.在这个语言字符串的例子有ab,aabb,aaabbb.

这种语言可以通过泵浦引理显示为非规则的.它实际上是一种原型上下文无关语言,可以通过无上下文语法 生成S ? aSb | ab.

尽管如此,现代正则表达式实现清楚地认识到的不仅仅是常规语言.也就是说,它们不是形式语言理论定义的"规则".PCRE和Perl支持递归正则表达式,.NET支持平衡组定义.更少的"花哨"特征,例如反向引用匹配,意味着正则表达式不规则.

但这个"基本"功能有多强大？L例如,我们可以用Java正则表达式识别吗？我们也许可以结合lookarounds和嵌套引用,并具有与如工作模式String.matches来匹配字符串一样ab,aabb,aaabbb,等？

参考

• perlfaq6:我可以使用Perl正则表达式来匹配平衡文本吗？
• MSDN - 正则表达式语言元素 - 平衡组定义
• pcre.org - PCRE手册页
• regular-expressions.info - Lookarounds和分组和反向引用
• java.util.regex.Pattern

相关问题

• 外观是否影响正则表达式可以匹配哪些语言？
• .NET Regex Balancing Groups与PCRE递归模式