11601 Week 8

作者 QIFAN 日期 2016-10-24
11601 Week 8

CMU 11601 Coding BootCamp


知识点整理

  • Python Tutorial。因为这周开始作业用Python写,对比了Java与Python的相似与不同。

In-Class

  • 期中考,败在了DP的问题上
  • 给一个排球比分,问所有可能的路径数量。也是DP,还是跪了。

Homework

Part 1

给一个数组,求出所有连续subarray的XOR结果。
我的坑在于理解错了“连续”,认为是连续的元素,其实只需要是位置连续。
Trick之处在于XOR自身为0。对于size为N的数组,第i位(从0位开始)在子集中出现的总次数为$(i+1) * (n-i)$,因此:

  • 若N为偶数,所有元素都出现偶数次,所以subarray的XOR结果为0;
  • 若N为奇数,当i为偶数时的元素出现了奇数次,所以只需将这些数XOR。

Part 2

Python Parser,好坑啊只过了两个case,恶补python

Shuffle

Interviewee

Interviewer