第一题 149. Max Points on a Line

题目描述

平面上有n个点，找出共线的点的最大个数

算法

很容易想到O(n^3)的解法，通过起点i，终点j枚举直线，然后枚举中间点k，依次判断k与i,j是否共线，统计最大值。

代码还有问题，有一种test case过不了

第一题 392. Is Subsequence

算法

利用两个指针不断的指示位置，向前推进

第一题 357. Count Numbers with Unique Digits

题目描述

给定一个非负整数n，计算所有各位数字均不同的数字x的个数，其中0 ≤ x < 10^n。

算法

对于n = 1，f(1) = 10

对于n = 2, f(2) = 9 9 (对于10位我们可以选择1 - 9九个数字，对于个位，我们可以选择0-9十个数字，但是需要与之前的个位数字不相同，所以为9)

同理，n = 3，f(3) = 9 9 * 8
最终的结果为 f(1) + f(2) + f(3)

第一题 256. Paint House

算法

这题是动态规划的题目，主要采用的方法是将之前对应的每种选择的可能性的最小值都记录下来，然后不断向后更新。这样，每一次更新，只需要执行n次计算(利用之前存储的计算结果)，满足动态规划的算法定义

第一题 70. Climbing Stairs

算法

利用动态规划来进行计算。分析这个问题，我们发现每遇到一个新的n，我们总是有三种方式从之前的状态到达这个新的状态，分别是A[n-2] + 2, A[n-2] + 1 + 1, A[n-1] + 1即两步之前的走一个2步，2步之前的走2个1步，1步之前的走一个1部可以到达我们目前所在的n处。但是需要注意的是，这三种方式中，A[n-2] + 1 + 1与A[n-1]一部分是重复的，所以最终对于一个新的状态n，所有的可能性为A[n-1] + A[n-2]

第一题 152. Maximum Product Subarray

算法

O(n)的复杂度，从后往前遍历整个数组，然后记录下当前的最大值和最小值

maxnow = Math.max(Math.max(maxpre * nums[i], minpre * nums[i]),nums[i]);
minow = Math.min(Math.min(minpre * nums[i], maxpre * nums[i]), nums[i]);

这一步可以更新当前最大最小值，如果为0的话，max和min都可以清除为0，非常关键的一步

第一题 339. Nested List Weight Sum

算法

相当于一个广度优先遍历，先将每一层的所有点存入一个List中，对于每一层的List,计算当层value的值的大小。之后对应每一层，都做一个相应的计算

关于云计算

距离CMU神课15619-Cloud Computing 截课已经过去快一个月了。在刚结束的时候，一直想对这门课做个总结，主要总结这门课的内容，加强对所学到知识点的理解。

第一题 15. 3Sum

算法

自己的

先将整个数组进行排序，然后在数组中找下一个，然后再找最后一个。自己的方法与别人的整个思路大致相似，但是由于没利用数组已经是sort过这个条件，导致复杂度是O(n^3)相当慢

• 重点，当一个Array是排序过的时候，找寻合适的数字的时候可以考虑从双向查找，尾到头同时头到尾。这样时间复杂度会减少很多
  阅读全文 »

第一题 287. Find the Duplicate Number

算法

这道题是非常有意思的一题，由于题目要求不能够改变Array本来的结构，相当于只是read形式的，所以另一道相似题目用的转负442 Find All Duplicates in an Array的方法就暂时用不了了。
在这道题中，我们要使用的在链表中求环的方式来进行这道题目的求解。由于题目中已经说明必定存在一个环，那么我们可以将环想象成以下样子的。