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