dieyushi's Blog

前言

今天事情好多，到最后终于可以静下心来好好想想题目了。最后终于理解了怎么用O(n)的时间复杂度求最长回文字串。记录一下。

一些题外话，一直用着redcarpet来渲染markdown，却一直没有配置。。今天把extensions加上了，可以用表格和autolink了～

redcarpet:
    extensions: ["no_intra_emphasis", "fenced_code_blocks", "autolink", "tables", "with_toc_data"]

题目

Longest Palindromic Substring

前言

这几天已经习惯依照Leetcoder来做题了，今天一刷新，就看到页面404了。还好我还有一个打开着的页面。在博客上备份一份。

原文地址http://leetcode.cloudfoundry.com/

昨天到今天一直没静下心来好好想想算法，导致这两天就做了一道题，太惭愧了。不过题目难度为5,想了好久的算法啊。

Median of Two Sorted Arrays

• 题目链接：http://leetcode.com/onlinejudge#question_4
• 解题思路：题目求两个以排序队列的中位数，可以看成求两个队列中第k小的数。

Find the k-th smallest number

• 解题思路：
  • 有k个比目标更小的数，将k分成两份，一份在A的前端，一份在B的前端，设k = i + j
  • 如果A[i-1] > B[j-1],说明B前端的j个数不可能出现我们要找的数。
  • 同理，如果A[i-1] < B[j-1],说明A前端的i个数不可能出现我们要找的数。
  • 如果A[i-1] == B[j-1],那么A[i-1]或者B[j-1]就是我们要找的。
  • 考虑边界情况。如k==1, m==0。
  • 重复以上步骤，直到返回。

昨天晚上有别的事情，没来的记录和总结，今天上午补上，大概做了六七个小时吧，解决了7道题，难度都是中低等的题目。还是要继续提高啊。

题目

Reverse Integer

• 题目链接：http://leetcode.com/onlinejudge#question_7
• 解题思路：很简单的一个题目，从最高位开始，得到每一位的值，组起来就可以了。
• 实现：

int reverse(int x){
    int ret = 0;

    while (x){
        ret = ret * 10 + x % 10;
        x = x / 10;
    }

    return ret;
}

前言

转眼间2013年都要进入5月了，马上就进入毕业季了，开始准备笔试+面试，看到很多人推荐leetcode,我也准备去刷一边上面的题目，复习下算法的知识。很长一段时间以来，写程序都用Python或Golang，重新使用C++还真有点不习惯。整整一下午加晚上就完成了四道题。代码惨不忍睹啊，看来想要写出bug free的代码还是任重道远啊。

题目

回到题目本身，leetcode的难度不算特别大，有很大一部分比较简单的题目，按照这个网站(链接)的整理，第一天我只挑选了较为简答的难度为3的题目（难度区间1-5）。下面记录下我的解题思路。