浏览全部代码：请戳
本文谨代表个人思路，欢迎讨论;)
1041. Be Unique (20)
题意
给出 N (<=105)个数（数值范围为 [1, 104]），找到其中不重复的第一个数字。比如给出5 31 5 88 67 88 17 ， 答案是 31 。
分析
简单模拟题，开一个大数组int a[10001];，以读入的数为下标，记录 count:a[index] ++;。结果输出第一个存储为 1 的下标:if (a[index] == 1)。
1042. Shuffling Machine (20)
题意
背景是洗牌机的洗牌过程。过程是给定洗牌的每张牌的位置替换序列，由原来的次序算出最后的牌的平排列。
比如原有的次序为S3, H5, C1, D13, J2，
给定的洗牌顺序为4, 2, 5 ,3 ,1，那么一次洗牌的结果为：J2, H5, D13, S3, C1。
如果需要两次洗牌，则结果为C1, H5, S3, J2, D13。
输入为对一整副牌（54 张）的洗牌策略，以及洗牌次数 N，要求计算出最后的洗牌结果。
分析
简单 hash 题。
1043. Is It a Binary Search Tree (25)
题意
二叉搜索树的定义就不重复了，题目新定义了一个镜像二叉搜索树，就是将一颗二叉搜索树所有节点的左右子树交换后的二叉树。
输入是一个二叉树的前序排列，要求判定是否是一个二叉搜索树或者镜像二叉搜索树。如果是，输出该树后序遍历的序列。
分析
解题思路：
- 1.BST 很特殊，实质上 BST 的所有节点的顺序排列就是中序遍历了。
- 2.要检查树是否是 BST 或者镜像 BST，只需按照重建树的思路，在每次重建的过程中做适当检查即可。检查思路是：检查前序遍历序列中，根节点之后的节点排序是否符合 BST 的二分规则（即前一段都是小于根节点的，后一段都是大于根节点的）。
- 3.最后的输出是后序遍历。过程中其实并不用构建整个树，直接在处理过程中，按后序的方式存储节点到队列中即可。
更多相关分析，参见博文《根据前中后序和层序重建二叉树》。
1044. Shopping in Mars (25)
题意
火星人购物使用钻石链，每颗钻石都有一定的价值。付款是，要求从钻石链上找到所有刚好能匹配到商品价值的连续的钻石子链，如果没有， 则找到超过商品价值的最小的钻石子链。
比如钻石链为3 2 1 5 4 6 8 7，商品价值为15，则候选的方案有：第 4 到第 6 颗的子链5 4 6，第 7 到第 8 颗：8 7。
输入为一个钻石链以及商品的价值，要求找到所有满足条件的分割方案，按起始点从小到大排序输出。
分析
由于时间限制有些严格，需要做足够的优化：
- 1.为了便于计算某个区间的累加值，在存储钻石串时，可以在
index位置存储包括当前钻石在内的之前所有钻石价值的累加和。 - 2.使用两层循环遍历所有可能，在遍历以位置 i 为其实坐标的子串时，不应该将结束位置初始化为 i，而是应该是以
i-1为起始位置的搜索过程中的 break 时的 结束位置的下标减 1.
其中第 2 条的证明如下：
算法中首先计算以i为起始位置的子串的累加值。假定计算到j满足累加值等于或者刚好大于商品价值m。之后，结束以i位置开始的子串的探寻，进入下一阶段以 i+1 为起始位置的搜索。
由于[i, j]的累加和刚好等于m，则[i, j - 1]的累加和肯定小于m，那么[i + 1, j - 1]的累加和也肯定小于m。
综上述，在以i+1为起始位置的搜索中，可以初始化结束位置为上一次搜索结束的位置减一，即j - 1.
1045. Favorite Color Stripe (30)
题意
Eva 对彩色条有特殊的癖好，对于一条五颜六色的彩带，她会减掉其中一些颜色块，让整个彩带的颜色顺序匹配到自己的一个颜色喜好顺序上。
举例来说，她喜欢的颜色顺序为{2 3 1 5 6}，给定的彩带的颜色顺序为{2 2 4 1 5 5 6 3 1 1 5 6}，那么经过她的剪辑，留下的彩带的可能选项有：{2 2 1 1 1 5 6} {2 2 1 5 5 5 6}，{2 2 1 5 5 6 6}和{2 2 3 1 1 5 6}。
我们的任务是找到其中最长的剪辑可能。
分析
这是经典的最长递增子序列问题(LIS)，递增在这里体现为子序列的颜色顺序要遵照 Eva 的对颜色的喜好顺序。使用动态规划解决。
- 1.剔除不在 Eva 喜欢颜色列表中的颜色。
- 2.DP 的状态： 用
length[max]数组存储状态，length[i]表示到彩带的第 i 个位置为止，包含该颜色的符合 Eva 喜好顺序的子串长度的最长值。记得在每次 - 3.DP 的子问题：
length[i]等于在其之前的所有lengths[j]跟i位置颜色组合后的最长子串值。
1046. Shortest Distance (20)
题意
给定在圆环上的几个点的相对位置，要求计算不同点之间的距离。
分析
简单模拟。
1047. Student List for Course (25)
题意
根据每名学生填报的课程，按顺序输出每门课程的学生名单。其中学生总量为 N(<=40000)，课程总量为 K(<=2500)。学生姓名为 3 个大写英文字符加一个数字。
分析
倒排索引的模拟。可以针对学生姓名做 hash 方式的优化。
1048. Find Coins (25)
题意
给定一系列硬币，以及一个商品的价格。要求从硬币中找到两个硬币让他们的组合等于商品的价格。如果有多个，输出有用最小单个值的硬币组合。
分析
首先，硬币中币值不小于商品价格的可以过滤掉。遍历过程中，使用 hash 标记的方法，设定一个coins[MAXVALUE]（其中 MAXVALUE 为商品价格的最大值）记录已有的币值种类，
在遍历的过程中，一边将读入的硬币增加到coins[]中，一边计算满足条件的最小币值。
1049. Counting Ones (30)
题意
给定一个正整数 N(<=230)，要求计算所有小于 N 的正整数的各个位置上，1 出现的次数之和。
分析
比较有思维难度的一题，核心在于找规律。10ms 的时间限制表明了不能用常规的循环遍历来解决。需要从简单的 case 找规律，逐步扩大到常规的情况。
详情参见《编程之美》P132 页《1 的数目》。
1050. String Subtraction (20)
题意
给定两个字符串，S1 和 S2,要求将 S2 中的字符从 S1 串中剔除。
分析
用 Hash 的方式标记需要剔除的字符。