LeetCode（44）
C/C++（18）
2016年夏天开始，跟着学校的一个leetcode群每天做一题。下面记录下过程中没来得及做的，或者没做好的，或者个人觉得得留意下的题目，以备更好的回顾。菜鸟一个~
未做的题目（有空补上）：
112. Path Sum
241. Different Ways to Add Parentheses
3. Longest Substring
Without Repeating Characters
没做好的题目：
Count of Range Sum: 归并排序的另类应用
10. Regular Expression Matching、动态规划、递归，回溯
& 动态规划（虽然思想简单，但想不出来）
& BST &分治 &BIT &ST&
值得我注意下的题目：
：我是迭代的，有的用递归，也有用二进制的方法（001代表取集合的最后一个元素）
：我用的是字典树，慢。看到群里有用哈希的，有空写下。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：10303次
排名：千里之外
原创：59篇
转载：17篇
(1)(1)(7)(2)(4)(4)(9)(19)(9)(1)(1)(3)(5)(3)(7)leetcode解题目录 - 推酷
leetcode解题目录
参考文献：
&不过本文准备用超链接的方式连接到相应解答页面，不断更新中
Clone Graph
Word Ladder II
Surrounded Regions
Word Ladder
Binary Tree Level Order Traversal
BFS|前序遍历
Binary&Tree&Level&Order&Traversal&II
BFS|前序遍历
Binary Tree Zigzag Level Order Traversal&
BFS|前序遍历
每一层顺序分别对待
Implement strStr()
Copy List with Random Pointer
Remove Duplicates from Sorted Array
Remove Duplicates from Sorted Array II
Set Matrix Zeroes
First Missing Positive
Evaluate Reverse Polish Notation
Largest Rectangle in Histogram
记录重要位置
Minimum Window Substring
Simplify Path
Longest Valid Parentheses
Valid Parentheses
Container With Most Water
记录重要位置
Best Time to Buy and Sell Stock
Best Time to Buy and Sell Stock II
Best Time to Buy and Sell Stock III
Length of Last Word
Search Insert Position
Search for a Range
Spiral Matrix
简化为子问题
Spiral Matrix II
简化为子问题
Reorder List
快慢指针&链表倒序
Linked List Cycle
Linked List Cycle II
Reverse Linked List II
Partition List
Remove Duplicates from Sorted List
Remove Duplicates from Sorted List II
Merge Two Sorted Lists
Rotate List
Reverse Nodes in k-Group
Swap Nodes in Pairs
Remove Nth Node From End of List
Text Justification
简化为子问题
模拟加法运算
Valid Number
Add Binary
模拟加法运算
Insert Interval
Merge Intervals
Multiply Strings
模拟乘法运算
Trapping Rain Water
Valid Sudoku
Roman to Integer
Integer to Roman
Reverse Integer
ZigZag Conversion
Add Two Numbers
模拟加法运算
Median of Two Sorted Arrays
String to Integer (atoi)
Next Permutation
STL经典算法
Recover Binary Search Tree
Single Number
Single Number II
Construct Binary Tree from Preorder and Inorder Traversal
前序中序遍历
Binary Tree Preorder Traversal
Flatten Binary Tree to Linked List
Interleaving String
Unique Binary Search Trees
Word Break
Word Break II
Distinct Subsequences
Decode Ways
Scramble String
Maximal Rectangle
Edit Distance
Climbing Stairs
Minimum Path Sum
Unique Paths
Unique Paths II
Jump Game II
Maximum Subarray
Wildcard Matching
Substring with Concatenation of All Words
Merge Sorted Array
Construct Binary Tree from Inorder and Postorder Traversal
后序中序遍历
Binary Tree Postorder Traversal
Combinations
Permutation Sequence
N-Queens II
Permutations
Permutations II
Combination Sum
Combination Sum II
Sudoku Solver
Longest Substring Without Repeating Characters
Max Points on a Line
排除相同的点
Longest Common Prefix
Longest Palindromic Substring
Insertion Sort List
Rotate Image
矢量旋转与平移
Longest Consecutive Sequence
Search in Rotated Sorted Array
类二分查找
Search in Rotated Sorted Array II
类二分查找
特殊考虑相等数据
类二分查找
Divide Two Integers
Gas Station
类合并排序
Merge k Sorted Lists
Sort Colors
类快速排序
Remove Element
类快速排序
Search a 2D Matrix
类杨氏矩阵
Restore IP Addresses
Sum Root to Leaf Numbers
Binary Tree Maximum Path Sum
opulating Next Right Pointers in Each Node
Populating Next Right Pointers in Each Node II
Path Sum II
Maximum Depth of Binary Tree&
Minimum Depth of Binary Tree
Balanced Binary Tree
Symmetric Tree
Same Tree&
Validate Binary Search Tree
Unique Binary Search Trees II
Binary Tree Inorder Traversal
Pascal's Triangle
Pascal's Triangle II
Convert Sorted List to Binary Search Tree
快慢指针&反中序遍历
Convert Sorted Array to Binary Search Tree
反中序遍历
Subsets II
Word Search
Count and Say
Generate Parentheses
Letter Combinations of a Phone Number
Regular Expression Matching
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致Given a string&s&and a dictionary of words&dict, determine if&s&can be segmented into a space-separated sequence of one or more dictionary words.
For example, givens&=&"leetcode",dict&=&["leet", "code"].
Return true because&"leetcode"&can be segmented as&"leet code".
解题思路：
问题： 根据给定的单词字典，判断一个字符串是否可以全部被分割为有效单词。
第一个问题，给定一个字符串， 怎么判断它是不是一个有效单词呢？
本人首先想到是之前做过的 &，打算用 Trie Tree 结构来判断一个字符串是不是一个有效单词。
后来才知道，&unordered_set 是&C++ 自带的数据结构，能直接用来检索一个字符串是否为有效单词。囧。看来对 C++ 还不够熟悉。
值得一提的是，用 Trie Tree 实现的算法也通过了 LeetCode 的测试，当然，unordered_set 的完成效率更快。
第二个问题，如何判断一个字符串是否可以全部被分割为有效单词，即原问题。
假设将字符串 s 分割为两段，[0,i-1], [i, n-1]，如果[0, i-1] 为有效单词，[i, n-1]为有效单词集合，那么 s 就是一个有效字符串。
将 i 从 1 到 n-1 遍历一次，求得 s 是否是一个有效字符串。
第三个问题，效率满，出现很多反复求解的子问题。
DP思路，即表格法，记录已计算结果。
vector&int&
bool isMatch(string s, unordered_set&string&& wordDict){
unordered_set&string&::iterator us_iter = wordDict.find(s);
if (us_iter != wordDict.end()) {
return true;
for (int i = 1 ; i & s.size(); i++) {
string leftS = s.substr(0, i);
unordered_set&string&::iterator leftS_iter = wordDict.find(leftS);
if (leftS_iter != wordDict.end()) {
bool isWordR;
if (v[i] != -1) {
isWordR = v[i];
isWordR = isMatch(s.substr(i, s.size() - i), wordDict);
v[i] = isWordR;
if (isWordR) {
return true;
return false;
bool wordBreak(string s, unordered_set&string&& wordDict) {
vector&int& tmp(s.size(), -1);
bool res = isMatch(s, wordDict);
阅读(...) 评论()(Lydia海小姐)
(fancyfrees)
第三方登录：LeetCode: Spiral Matrix
来源：博客园

Spiral MatrixGiven a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.For example,Given the following matrix:[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]You should return [1,2,3,6,9,8,7,4,5].
Solution 1:
使用递归，一次扫描一整圈，然后用x,y记录这个圈的左上角，递归完了都+1。rows, cols记录还没扫的有多少。思想比较简单，但相当容易出错。起码提交了5次才最后过。
注意：1. 扫描第一行跟最后一行要扫到底部为止，而扫描左列和右列只需要扫中间的。
1
8
9 10 11 12
例如以上例子： 你要 先扫1234, 然后是8，然后是12 11 10 9 然后是 5.
不能这样：123, 4 8, 12 11 10 , 9 5。 用后者的方法在只有一个数字 1的时候 就完全不会扫到它。
 

 1 public List&Integer& spiralOrder1(int[][] matrix) {
 2
List&Integer& ret = new ArrayList&Integer&();
 3
if (matrix == null || matrix.length == 0 
 4
|| matrix[0].length == 0) {
 5
rec(matrix, 0, 0, matrix.length, matrix[0].length, ret);
 9
return
11
public static void rec(int[][] matrix, int x, int y, int rows, int cols, List&Integer& ret) {
14
if (rows &= 0 || cols &= 0) {
15
return;
16
// first line
19
for (int i = 0; i & i++) {
20
ret.add(matrix[x][y + i]);
21
// right column
24
for (int i = 1; i & rows - 1; i++) {
25
ret.add(matrix[x + i][y + cols - 1]);
26
// down row
29
if (rows & 1) {
30
for (int i = cols - 1; i &= 0; i--) {
31
ret.add(matrix[x + rows - 1][y + i]);
32
// left column. GO UP.
36
if (cols & 1) {
37
for (int i = rows - 2; i & 0; i--) {
38
ret.add(matrix[x + i][y]);
39
rec (matrix, x + 1, y + 1, rows - 2, cols - 2, ret);
43
}

View Code
 
Solution 2:

感谢以上文章作者提供的思路，我们可以用x1,y1记录左上角，x2,y2记录右下角，这样子我们算各种边界值会方便好多。也不容易出错。

 1 /*
 2
Solution 2:
 3
REF: http://blog.csdn.net/fightforyourdream/article/details/?reload
 4
此算法比较不容易算错
 5
public List&Integer& spiralOrder2(int[][] matrix) {
 7
List&Integer& ret = new ArrayList&Integer&();
 8
if (matrix == null || matrix.length == 0 
 9
|| matrix[0].length == 0) {
10
int x1 = 0;
14
int y1 = 0;
15
int rows = matrix.
17
int cols = matrix[0].
18
while (rows &= 1 && cols &= 1) {
20
// Record the right down corner of the matrix.
21
int x2 = x1 + rows - 1;
22
int y2 = y1 + cols - 1;
23
// go through the WHOLE first line.
25
for (int i = y1; i &= y2; i++) {
26
ret.add(matrix[x1][i]);
27
// go through the right column.
30
for (int i = x1 + 1; i & x2; i++) {
31
ret.add(matrix[i][y2]);
32
// go through the WHOLE last row.
35
if (rows & 1) {
36
for (int i = y2; i &= y1; i--) {
37
ret.add(matrix[x2][i]);
38
// the left column.
42
if (cols & 1) {
43
for (int i = x2 - 1; i & x1; i--) {
44
ret.add(matrix[i][y1]);
45
// in one loop we deal with 2 rows and 2 cols.
49
rows -= 2;
50
cols -= 2;
51
x1++;
52
y1++;
53
return
56
}

View Code
Solution 3:

感谢水中的鱼大神。这是一种相当巧妙的思路，我们这次可以用Iterator来实现了，记录2个方向数组，分别表示在x方向，y方向的前进方向。1表示右或是下，-1表示左或是向上，0表示不动作。
// 1: means we are visiting the row by the right direction.// -1: means we are visiting the row by the left direction.int[] x = {1, 0, -1, 0};
// 1: means we are visiting the colum by the down direction.// -1: means we are visiting the colum by the up direction.int[] y = {0, 1, 0, -1};
这种方向矩阵将会很常用在各种旋转数组上。
 

 1 /*
 2
Solution 3:
 3
使用方向矩阵来求解
 4
public List&Integer& spiralOrder(int[][] matrix) {
 7
List&Integer& ret = new ArrayList&Integer&();
 8
if (matrix == null || matrix.length == 0 
 9
|| matrix[0].length == 0) {
10
int rows = matrix.
14
int cols = matrix[0].
15
int visitedRows = 0;
17
int visitedCols = 0;
18 
19
// indicate the direction of x
// 1: means we are visiting the row by the right direction.
22
// -1: means we are visiting the row by the left direction.
23
int[] x = {1, 0, -1, 0};
24
// 1: means we are visiting the colum by the down direction.
26
// -1: means we are visiting the colum by the up direction.
27
int[] y = {0, 1, 0, -1};
28
// 0: right, 1: down, 2: left, 3: up.
30
int direct = 0;
31
int startx = 0;
33
int starty = 0;
34
int candidateNum = 0;
36
int step = 0;
37
while (true) {
38
if (x[direct] == 0) {
39
// visit Y axis.
40
candidateNum = rows - visitedR
41
} else {
42
// visit X axis
43
candidateNum = cols - visitedC
44
if (candidateNum &= 0) {
47
break;
48
ret.add(matrix[startx][starty]);
51
step++;
52
if (step == candidateNum) {
54
step = 0;
55
visitedRows += x[direct] == 0 ? 0: 1;
56
visitedCols += y[direct] == 0 ? 0: 1;
57
// move forward the direction.
59
direct ++;
60
direct = direct%4;
61
// 根据方向来移动横坐标和纵坐标。
64
startx += y[direct];
65
starty += x[direct];
66
return
69
}

View Code
 
SOLUTION 4 (December 2nd 更新):
对solution 2改进了一下，使用top,bottom,right,left记录四个角。程序更简洁漂亮。

 1 public class Solution {
 2
public List&Integer& spiralOrder(int[][] matrix) {
 3
List&Integer& ret = new ArrayList&Integer&();
 4
if (matrix == null ||matrix.length == 0) {
 5
// 注意在非法的时候，应该返回空解，而不是一个NULL值
 6
return
 7
// Record how many rows and cols we still have.
10
int rows = matrix.
11
int cols = matrix[0].
12
// The four coners.
14
int top = 0;
15
int left = 0;
16
int bottom = rows - 1;
17
int right = cols - 1;
18
// every time we go through two rows and two cols.
20
for (; rows & 0 && cols & 0; rows -= 2, cols -= 2, top++, left++, bottom--, right--) {
21
// the first line.
22
for (int i = i &= i++) {
23
ret.add(matrix[top][i]);
24
// the right column.
27
for (int i = top + 1; i & i++) {
28
ret.add(matrix[i][right]);
29
if (rows & 1) {
33
for (int j = j &= j--) {
34
ret.add(matrix[bottom][j]);
35
// the left column.
39
if (cols & 1) {
40
for (int i = bottom - 1; i & i --) {
41
ret.add(matrix[i][left]);
42
return
47
}
48 }

View Code
 redo:
可以不用rows/cols来记录行列数。只需要判断四个边界是否相撞即可。

 1 public List&Integer& spiralOrder3(int[][] matrix) {
 2
List&Integer& ret = new ArrayList&Integer&();
 3
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
 4
return
 5
int rows = matrix.
 8
int cols = matrix[0].
 9
int left = 0;
11
int right = cols - 1;
12
int top = 0;
13
int bottom = rows - 1;
14
while (left &= right && top &= bottom) {
16
// line top.
17
for (int i = i &= i++) {
18
ret.add(matrix[top][i]);
19
for (int i = top + 1; i &= bottom - 1; i++) {
23
ret.add(matrix[i][right]);
24
// line bottom.
27
if (top != bottom) {
28
for (int i = i &= i--) {
29
ret.add(matrix[bottom][i]);
30
if (left != right) {
35
for (int i = bottom - 1; i &= top + 1; i--) {
36
ret.add(matrix[i][left]);
37
left++;
41
right--;
42
top++;
43
bottom--;
44
return
47
}

View Code
 
GitHub CODE: 

免责声明：本站部分内容、图片、文字、视频等来自于互联网，仅供大家学习与交流。相关内容如涉嫌侵犯您的知识产权或其他合法权益，请向本站发送有效通知，我们会及时处理。反馈邮箱&&&&。
学生服务号
在线咨询，奖学金返现，名师点评，等你来互动