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 […]

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 […]