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 […]
0. 写在前面 笔者把Linux装在了USB3.0的U盘上。但运行速度还是很慢。于是想更改Linux的Boot Loader，让它在每次启动时，把整个操作系统加载到内存。这样Linux的运行速度将有极大的提升。()此外，为了保存系统更改，作者把U盘上的一个分区挂载到/home位置。这样用户的数据（音乐、文档、应用程序等）就会在关机后得到保存。但是，系统数据（安装的Package，设置等）在重启后还是会被还原，文末给出了一个解决办法。 本文章翻译自：Making Ubuntu Fast using RAM (Updated and Simplified)和 Making Ubuntu Insanely Fast using RAM 。笔者适当地修改了原文的流程，并增添了一些终端命令的解释，使之更适合大陆用户和Linux初学者。 谨向原文作者terminator14和GNU开源社区的贡献者们致敬。 1. 适用人群 觉得Linux运行较慢，电脑内存较大(最少2G，推荐4G或更多)，爱折腾的同学。 2. 总体流程 a. 将系统文件拷贝到临时文件夹； b. 将临时文件夹中的文件制作成内存可载入的映像； c. 更改Boot Loader，新增启动项，并将其指向我们制作的映像； d. 重启，享受飞一般的感觉(insanely fast)。 3. 操作步骤 3.1 原料 一份Linux内核的操作系统。文章以Ubuntu 14.04为例，其他发行版本与之类似。 注：Linux是一些操作系统的内核(Kernel)。Linux是开源的（免费且公开），很多发行商将Linux打包，并添加了自己开发的系统程序和图形界面(GUI)，于是便有了各种不同的发行版本(Distribution)。常见的发行版本有Ubuntu，Red Hat，Debian，CentOS等，但他们的内核都是Linux。 举个例子：Android的内核是开源的，很多手机厂商（如三星，HTC）把Android的内核做修改优化，添加了自己的系统程序和图形界面封装成ROM，或继续开发硬件，制作成手机发售。但他们本质上都是Android机。 这里，Android内核就相当于Linux，而三星，HTC发行的ROM就相当于Ubuntu，Red Hat。 3.2检查磁盘容量 在Ubuntu命令行中输入： sudo du -hcs […]
Maximum Depth of Binary Tree Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Show Tags Tree Depth-first Search 没啥说的，深度优先搜索(Depth-first Search)，直接在网站上敲代码，一遍AC。 /** * Definition for binary tree * struct […]
Find Peak Element A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is […]
Intersection of Two Linked Lists Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3 begin to intersect at […]
