题目描述

LeetCode 3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

题目即要求找到一个字符串中不含重复字符的最长子串。子串（substring）必须是连续的，子序列（subsequence）才可以是不连续的。

算法分析

暴力解法当然是以每一个字符为起始位置，往后直到遇到重复字符为止。这样时间复杂度为O(n^2)的解法显然是不能通过的。

题目描述

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

原题链接

题目要求在一个给定数组中，找到乘积最大的连续子数组。这题并不难，显然，原数组中对于乘积造成影响的显然只是元素的正负值。对于绝对值而言，除0以外，毫无疑问是单调递增的。

算法分析

尝试用动态规划来解决，利用dp[i]来表示“以nums[i]作为最后一个元素的连续乘积”。但是，显然dp[i]不能简单的由dp[i-1]给出。我们有这样一种假设：如果nums[i]<0，那么我们要使dp[i]最大，则会希望dp[i-1]是一个很小的负数；如果nums[i]>0，那么我们要使dp[i]最大，则会希望dp[i-1]是一个很大的正数。因此，可以考虑同时用两个值，一个最大值和一个最小值，来维护当前状态。

因此，现在考虑使用两个动态规划的数组max_product和min_product。对于nums[i]，进行分类讨论：

• max_product[i-1]>0 && min_product[i-1]<0

  • nums[i]>0，则有：

    max_product[i] = nums[i]*max_product[i-1]

    min_product[i] = nums[i]*min_product[i-1])

  • nums[i]<0，则有：

    max_product[i] = nums[i]*min_product[i-1]

    min_product[i] = nums[i]*max_product[i-1]

  • nums[i]==0，则有：

    max_product[i] = nums[i]

    min_product[i] = min_product[i-1]

    Read more »

题目描述

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1 2 3 4 5

>1 0 1 0 0 >1 0 1 1 1 >1 1 1 1 1 >1 0 0 1 0 >

>

Return 4.

原题链接

算法分析

考虑使用动态规划解决。首先需要找到状态转移方程。

最直接会想到使用dp[i][j]来表示“在matrix[0][0]到matrix[i][j]中所能找到的最大的正方形面积”。但是显然，dp[i][j]这一状态是很难用之前的某些状态来表示的。

不妨尝试使用dp[i][j]来表示“以matrix[i][j]作为正方形右下角的方形面积”，这样只需找到所有dp[i][j]中的最大值即可。这样仍然有一定难度表示，因此可以转化为用dp[i][j]表示“以matrix[i][j]作为正方形右下角的正方形边长”。想找到状态转移方程，首先考虑dp[i][j]和之前的哪些状态有关，显然是dp[i-1][j]，dp[i][j-1]和dp[i-1][j-1]。不难知道，当matrix[i][j]为‘0’是，dp[i][j]必然是为0的，下面考虑matrix[i][j]是’1’时的情况：

首先，最理想的是下面这种情况：

1
2
3

1 1 1
1 1 1
1 1 X

此时，matrix[1][2]，matrix[2][1]和matrix[1][1]都分别是某一个方形的右下角，且边长分别是2，2，2，加上matrix[2]后，恰好能将当前已有的方形边长增加1。即dp[2][2]为3。

Go搭建web服务器

使用go语言搭建一个简单的web服务器是非常方便的，一个简单的例子如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// main.go
package main

import (
    "fmt"
    "log"
    "net/http"
)

func sayhelloName(w http.ResponseWriter, r *http.Request) {
    fmt.Fprintf(w, "Hello!") // 这个写入到w的是输出到客户端的
}

func main() {
    http.HandleFunc("/", sayhelloName) // 设置访问的路由
    port := ":9090"  // 设置监听的端口
    err := http.ListenAndServe(port, nil) // 开始监听
    if err != nil {
        log.Fatal("ListenAndServe: ", err)  // 输出错误日志
    }
    fmt.Printf("Server listen at: %s", port)
}

题目描述

Patching Array
Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:
nums = [1, 3], n = 6
Return 1.

Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].

Example 3:
nums = [1, 2, 2], n = 5
Return 0.

题目大意是，给定一个有序地数组nums，以及一个数n。要求在数组中加入一些数，使得在[1, n]范围内的所有数都能由nums中的一个或一些数通过求和得到。求在数组中加入数字的最小数量。

算法分析

要解决这道题目，首先明白一个规律：假设当前我们通过数组的前i个数，已经能通过求和覆盖[1, m]内的所有值，那么当我们再利用数组的第i+1个数，即nums[i+1]，能得到的范围是什么呢？答案是[1, nums[i+1] + m]。在有了nums[i+1]的基础上，分别加上[1, m]内的所有值即可。

基本解法

题目描述

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

题目大意是：给定一个数字组成的三角形，要求从顶层到底层，找到一条最小路径。使得在这条路径上所有数之和是所有路径中最小的。往下一层走时，你只能访问到与当前位置相邻的两个数。

算法分析

利用动态规划的思想可以很快的解决问题。对于每一层的每一个数，都可以有一个值minValue，代表“从顶层开始到这里结束的最小路径和”。而这个值显然是“当前数值”与“左上方数的minValue”或“右上方数的minValue”之和。即状态方程如下：

1

minValue[current] = min{ minValue[left_top], minValue[right_top] } + currentValue

基本解法

题目描述

316.Remove Duplicate Letters
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:
Given “bcabc”
Return “abc”

Given “cbacdcbc”
Return “acdb”

题目大意是，给定一个字符串s，s只由小写字母组成。要求去掉s中重复的字母，且当有多个结果时，要返回字母序最小的结果。

算法分析

根据题目不难想到可以用贪心算法来求解：
假设得到的目标结果为s，那么最理想情况下自然是s[0] == 'a'，s[1] == 'b'…（假设字母a和b都存在的话。由此，我们可以先令result为空，每次在后面加上一个字母。且满足：这个字母为当前字符串中字母序最小的一个。但是，为了确保不会将原字符串s中含有的字母去掉，在这个基本条件以外，还需要满足一个特殊条件，即若某一字符只在字符串中出现过一次，那么它必须立刻被选择。

题目描述

133 Clone Graph
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

   1
  / \
 /   \
0 --- 2
     / \
     \_/

题目虽然讲了很多内容，包括OJ中序列化的图的表示法，但是题目所要求的复制一个图，实际上只是考察了图的遍历。根据给定的一个UndirectedGraphNode* node，由该点出发，遍历整个图，并以此创建一个新的和原来一样的无向图即可。