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 […]
Pow(x, n) Implement pow(x, n). 数据结构书上的原题,也是一个经典题.直接上手写了,但第一次没过.因为没考虑到n为负数的情况.第二次AC. 时间复杂度O(logn) C++: class Solution { public: double pow(double x, int n){ return n<0?1/_pow(x,-n):_pow(x,n); } double _pow(double x, int n) { if (n == 0){ return 1; } else if(n == 1){ return x; } else{ double y = pow(x, n / 2); if(n % […]
Combination Sum Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times. Note: All numbers (including target) will be positive integers. Elements […]
