leetCode解题报告5道题(六)

题目一：

Longest Substring Without Repeating Characters

 Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

这道题目的其实考察的就是指针问题而已，由于我是用java,就相当于两个变量对应两个下标，来移动这两个下标就可以解决这个问题了。

我拿一个例子来说明这道题目吧：

如：字符串：wlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmco

思想：我们可以知道，按照顺序下去，当下标pos指向 “4” （第二个字符b） 时，我们知道，这样子的话，前面的长度就被确定了，就是4了，下次，当我们要再算下一个不重复子串的长度的时候便只能从这个下标为4的字符开始算了。

根据这样的简要分析，我们要注意这道题目的陷阱

1、字符并不只是a-z的字母，有可能是其他的特殊字符或者阿拉伯数字等等，这样子我们可以想到我们也许需要256个空间(ASCII码总数)来存储每个字符上一次出现的位置下标信息。我们记作 position[i],  i 表示字符 c 的 ASCII编码, position[i] 表示字符 c 上一次出现的位置下标。

2、我们需要一个下标变量来指向此次子串的开始位置，记做 start 变量，当下次 pos 指向的当前字符 对应的值 position[i] 的位置在 start 变量的前面的话，那么我们就忽略不考虑（因为我们这次计算子串是从start开始的，所以前面的出现重复的字符就不管了）

分析完了之后，我们就看下代码里面的解释吧！

AC代码：

题目二：

Rotate Image

 

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

分析：题目要求我们把一个二维的矩阵在原数组上做顺时针90度的旋转。这道题目其实只需要在草稿纸上把图一画，不难发现，其实矩阵只需要通过一次 对角线(“ \ ”) 的翻转，然后再经过一次 竖直线(" | ")的翻转就可以得到我们最终想要的结果!

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)

分析：做这道题目之前我们首先要明白一些基本概念。首先ipV4地址一共由4位组成，4位之前用"."隔开，每一位必须满足是数字从0到255的范围内。如果字符串任意组合之后，满足了一共有4位，并且每一位都合法的话，那么这个字符串便是满足题意的字符串了。我们可以将它加入结果集。

解题思路：居然是做这种多种情况的，很明显我们要用递归的方法来解决，而递归有个终止状态，终止状态我们很容易知道就是剩下要处理的字符串的长度为0了，这时候我们再判断已经得到的字符串是否是合法的Ip即可。详细的看代码和注释理解！

AC代码：（436ms）

AC代码：（网友提供，392ms）

题目四：

ZigZag Conversion（挺恶心的，题目看懂就相当于做完了）

 

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line:  "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

分析：只是把字符串先按照" 反N " [即： | / |  ]的形状“平铺”，然后把之后得到的一行的字符串串起来就得到了最后的结果字符串。

需要注意的是，两竖之间的“过度” " / " 那一列的行数为 nRows - 2; 而其他的列为nRows行

这样讲太难理解了，看图解理解一下吧！

仔细观察这个题目的规律是解决这道题目的关键，比如它有几个陷阱，一个是中间夹着的短边" / " 的长度问题，另一个是方向问题，“ | ”的方向是从上往下，而“ / ” 的方向是从下往上的.

AC代码：

题目五：

Set Matrix Zeroes

 

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.