Longest Palindromic Substring Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. tag: string 9/23/2015 update Same algorithm as described as follows, but neater I think. class Solution { […]
Reverse Integer Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 click to show spoilers. Have you thought about this?Here are some good questions to ask before coding. Bonus points for you if you have already thought through this! If the integer’s […]
Min Stack Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) — Push element x onto stack. pop() — Removes the element on top of the stack. top() — Get the top element. getMin() — Retrieve the minimum element in the stack. […]
Binary Tree Preorder Traversal Given a binary tree, return the preorder traversal of its nodes’ values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [1,2,3]. Note: Recursive solution is trivial, could you do it iteratively? tag: stack 不能再简单的题了，先序遍历。 即使说不让用递归，也可以很好的解出来。做此题时需要知道一个思想，递归的本质其实就是进程内存中维护着一个栈。这在计算机系统概论，也就是Patt上的那门课上，他着重解释过。所以如果不让我们用递归的话，那就加个栈吧！ 为了比较速度，我把两种方法都贴上。应该是使用栈的方法更快。 版本一：使用递归 /** * Definition for binary […]
Pascal’s Triangle Given numRows, generate the first numRows of Pascal’s triangle. For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] tag: array 没什么算法技巧，了解帕斯卡三角的计算公式就好。不过也算是动态规划的一种吧。 1. A[i][j] = A[i – 1][j – 1] + A[i – 1][j] 2. A[i][1] = A[i][end] = 1 线性时间复杂度，常数空间复杂度。 class Solution { […]
Single Number Given an array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? tag: hash table, bit manipulation 异或有一个很神奇的属性，可以把奇数个元素挑出来。本质是因为： 1. 异或具有交换性 A^B = B^A 2. 0与一个数异或等于它本身 所以该数列中，可以看成把出现两次的元素交换在临近位置，异或之后为0，最后剩下0与出现一次的元素异或，为该元素本身。 一次AC。 […]
Restore IP Addresses Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example: Given “25525511135”, return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter) tag: backtracking, string 花了我好久才搞通这题！ 其实大方向是对的，带剪枝的回溯算法。先一个个插dot进去，发现不行后再返回上一层，逐个测试。 有三个点需要注意： 1. 传参数时，result是要随时被更改的，所以传参时要传它的引用。即使我是调用它的push_back()函数，也需要传引用，这个好奇怪。 2. substr的参数是(index, count)表示取[index, index + cout)的子字符串。开始我以为是[start, end)。结果改了好久，在本地上cout才测试出来。 3. stoi不能转换过长的字符串，否则会报RUN TIME ERROR 错误。所以我在stoi函数前，加了s.size() […]
Largest Rectangle in Histogram Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]. The largest rectangle is shown […]
有时候在使用vim的时候，显示中文为乱码，这个时候我们可以修改vimrc文件解决问题！ 首先，你需要搞清楚vimrc所在的位置。一般来说，在linux系统里，应该是这样 Linux: /usr/share/vim/vimrc在Windows系统，应该是在vim的安装目录 Windows: c:\program files\vim\vimrc我目前使用的是Windows7 ，路径显示为 C:\Program Files\Vim\_vimrc 这里所说的都是全局设定，打开vimrc文件后，只需要在文件最后添加以下代码就可以了： set fileencodings=utf-8,gb2312,gbk,gb18030 set termencoding=utf-8 set fileformats=unix set encoding=prc 这样，你的vim中文乱码问题就解决了！ 需要注意的是，在Windows7和vista下，由于加强版的管理员权限，你用vim直接打开vimrc文件，所做的修改是无法保存的！哪怕你使用的 是:wq! 命令！一个简单的方法就是先在开始里面用管理员权限启动vim，然后通过vim打开vimrc文件做修改就可以了！ 原文链接： http://www.2cto.com/os/201111/110622.html
Maximal Rectangle Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area. tags: array, stack, hash table, dynamic programming 很烦leetcode的一点就是，大部分题都不给时间复杂度和空间复杂度的要求。还得自己一点点来试。 这也是我见到的tag最多的一题，难度也为hard。 先写了暴力的O(nm)^2的算法，超时。 版本一：暴力搜索，O((nm)^2)。超时 class Solution { public: /** * assume the size of 2D array is n*m. * this […]
