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 […]
Minimum Path Sum Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. tag: array, dynamic programming […]
Edit Distance Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character tag: […]
Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree. For example: Given the below binary tree, 1 / \ 2 3 Return 6. Tags: tree, depth-first-search 10/10/2015 udpate divide-and-conquer approach o(n) solution, use […]
