月度归档:2013年11月

LeetCode:Search in Rotated Sorted Array

Search in Rotated Sorted Array:http://oj.leetcode.com/problems/search-in-rotated-sorted-array/
关键点:旋转前数组有序,无重复元素。


参考解法:
由于旋转前数组有序,故旋转后,数组被分为两个有序的子区间(无旋转时为一个有序区间)。
算法同样采用折半查找的思想进行搜索,但上下界firstlast的更新相比常规的折半查找略微复杂。
在下面的高亮行11进行判断时,若if判断成立,由旋转前数组有序的条件可知firstmid之间的元素都有序(在一个有序子区间中),故在高亮行12时若if仍成立,则target[first,mid)之间,否则在[mid+1,last)之间。
同上述分析,在高亮行18时若if成立,则target[mid+1,last)之间。
// 时间复杂度O(log n),空间复杂度O(1)
class 

Sublime Text:”output not utf-8″错误

在Sublime Text 3下编译Python时发生"output not utf-8"错误,使用下述方法后解决。
但该方法应该可以推广到用于解决Sublime Text 2及编译其它语言时发生的此错误。

  1. Windows系统在cmd下输入 chcp 获取当前活动代码页(中文系统默认为936)。Python标准encoding:http://docs.python.org/2/library/codecs.html#standard-encodings
  2. Sublime Text菜单选择Tools -> Build System ->New Build System...。
  3. 在新的Build System文件中输入以下内容后保存到Packages文件夹下(Packages/User)。
{
   "cmd": ["python", "-u", "$file"],
   "file_regex": "^[ ]*File "(...*?)", line ([0-9]*)",
   "selector": "source.python",
   "path": "C:\Python27",
   "encoding": 

LeetCode:Remove Duplicates from Sorted Array II

接前一题(Remove Duplicates from Sorted Array),但元素最多允许出现的次数由1变为2。
LeetCode OJ地址:http://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
关键点:数组已排序,不分配另一个数组,返回去重后数组长度,每个元素最多出现两次。


我的解法1:
1.遍历数组,将其中重复次数在两次以上的所有元素进行标记(mark,此处使用A[0]-1作为mark,对于A[0]本身为最小int时可能存在问题?)。
2.从第一个重复次数在两次以上且该数第三次出现的位置开始遍历,当元素不是被标记的元素时,将该元素往前移动。
算法需要执行两次循环及一次STL的find操作,虽然时间复杂度在O(n),但实际效果并不好,且代码冗长。
对于一个测试用例,算法在执行过程中的数组状态如下代码中的高亮行所示。
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if (0 

LeetCode:Remove Duplicates from Sorted Array

开始尝试刷LeetCode提升下算法功力,打算所有算法先自己尝试编写,再参考Frank Dai(SoulMachine)在GitHub上的题解
Remove Duplicates from Sorted Array:
关键点:数组已排序,不分配另一个数组,返回去重后数组长度,每个元素只出现一次。


我的解法:
算法主要思路为不断前向查找,当找到一个不再重复的元素时,将该元素复制到已经去重的最后一个元素的下一个相邻位置。前向查找及元素复制位置由索引frontback维护。
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        // 边界测试
        if (0 == n)
            return 0;

        // front 指向当前需要判断是否需要被去重的元素
        //