Skip to content

Commit 573d647

Browse files
HanqingZhengHanqingZheng
authored
Merge pull request gzc426#6 from gzc426/master
asd
2 parents e148a4d + dd54252 commit 573d647

File tree

21 files changed

+842
-0
lines changed

21 files changed

+842
-0
lines changed

‎018429.c

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
int firstUniqChar(char* s) {
2+
int ascii[256]={0};
3+
int i=0,len;
4+
while(s[i]!='\0')
5+
{
6+
i++;
7+
}
8+
len=i;
9+
for(i=0;i<len;i++)
10+
{
11+
ascii[s[i]]++;
12+
}
13+
i=0;
14+
while(ascii[s[i]]!=1&&i<len) i++;
15+
if(i==len)
16+
return -1;
17+
return i;
18+
}

‎2018.11.28-leetcode151/018429.md

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
int top=0;
2+
void push(char c,char* stack)
3+
{
4+
stack[top++]=c;
5+
}
6+
char pop(char* stack)
7+
{
8+
return stack[--top];//写入s1
9+
}
10+
void reverseWords(char *s) {
11+
int i=0,j=0,flag=0;
12+
while(s[i]!='\0') i++;
13+
char* stack = (char*)malloc(i);
14+
char* s1 = (char*)malloc(i+1);
15+
i--;
16+
while(i>=0)
17+
{
18+
if(s[i]==' ')
19+
{
20+
while(top!=0)//如果栈不为空
21+
{
22+
flag=1;
23+
s1[j++]=pop(stack);
24+
}
25+
if(flag==1)
26+
{
27+
s1[j++]=' ';
28+
flag=0;//重置flag
29+
}
30+
i--;
31+
}
32+
else
33+
{
34+
push(s[i--],stack);
35+
}
36+
}
37+
if(s[++i]!=' ')
38+
{
39+
while(top!=0)//如果栈不为空
40+
s1[j++]=pop(stack);
41+
s[j]=' ';
42+
}
43+
else
44+
j--;
45+
s1[j]='\0';
46+
s = strcpy(s,s1);
47+
free(s1);
48+
}

‎2018.11.29-leetcode443/妮可.md

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
```java
2+
package sy181203;
3+
4+
import java.util.ArrayList;
5+
import java.util.Arrays;
6+
7+
public class leetcode_443压缩字符串
8+
{
9+
10+
public static void main(String[] args)
11+
{
12+
char[] chars = {'a','b','b','b','c','c','b','b','b','b','b','b','b','b','b','b','b','b'};
13+
System.out.println(Arrays.toString(chars));
14+
15+
System.out.println(compress(chars));
16+
17+
}
18+
19+
public static int compress(char[] chars)
20+
{
21+
if(chars.length==0)
22+
return 0;
23+
int m=0,i=0,j;
24+
while(i<chars.length)//外层循环控制总次数
25+
{
26+
j=i;
27+
chars[m++]=chars[i];
28+
int k=0;//统计重复字母数
29+
while(j<chars.length && chars[i]==chars[j])//内层循环判断是不是同一个字母
30+
{
31+
k++;
32+
j++;
33+
}
34+
StringBuilder sb=new StringBuilder();
35+
if(k!=1)//k=1不用再加数字
36+
{
37+
while(k!=0)//除来减小,到0出循环
38+
{
39+
System.out.println("k%10 "+(k%10));
40+
sb.append((char)(k%10+48));
41+
k/=10;
42+
}
43+
}
44+
System.out.println("sb ==="+sb.toString());
45+
sb.reverse();//
46+
System.out.println("sbre ==="+sb.toString());
47+
for(char c:sb.toString().toCharArray())
48+
49+
{
50+
System.out.println("c="+c);
51+
chars[m++]=c;
52+
}
53+
i=j;//置位
54+
}
55+
System.out.println(Arrays.toString(chars));
56+
return m;
57+
}
58+
59+
}
60+
```

‎2018.11.30-leetcode890/妮可.md

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
```java
2+
package sy181203;
3+
4+
import java.util.ArrayList;
5+
import java.util.List;
6+
7+
/**
8+
* @author suyuan
9+
*
10+
你有一个单词列表 words 和一个模式 pattern，你想知道 words 中的哪些单词与模式匹配。
11+
12+
如果存在字母的排列 p ，使得将模式中的每个字母 x 替换为 p(x) 之后，
13+
我们就得到了所需的单词，那么单词与模式是匹配的。
14+
15+
（回想一下，字母的排列是从字母到字母的双射：每个字母映射到另一个字母，没有两个字母映射到同一个字母。）
16+
17+
返回 words 中与给定模式匹配的单词列表。
18+
19+
你可以按任何顺序返回答案。
20+
21+
22+
23+
示例：
24+
25+
输入：words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
26+
输出：["mee","aqq"]
27+
解释：
28+
"mee" 与模式匹配，因为存在排列 {a -> m, b -> e, ...}。
29+
"ccc" 与模式不匹配，因为 {a -> c, b -> c, ...} 不是排列。
30+
因为 a 和 b 映射到同一个字母。
31+
32+
33+
提示：
34+
35+
1 <= words.length <= 50
36+
1 <= pattern.length = words[i].length <= 20
37+
38+
*/
39+
public class leetcode_890查找和替换模式
40+
{
41+
42+
public static void main(String[] args)
43+
{
44+
String[] wordsStrings= {"ddd","abc","deq","mee","aqq","dkd","ccc"};
45+
String pattern = "abb";
46+
System.out.println(findAndReplacePattern(wordsStrings, pattern));
47+
48+
}
49+
50+
public static List<String> findAndReplacePattern(String[] words, String pattern)
51+
{
52+
List<String> list=new ArrayList<String>();
53+
for(int i=0;i<words.length;i++)
54+
{
55+
if(words[i].length()==pattern.length())
56+
{
57+
if(isMatch(words[i], pattern))
58+
list.add(words[i]);
59+
}
60+
}
61+
return list;
62+
}
63+
64+
public static boolean isMatch(String word,String pattern)
65+
{
66+
//不用map,弄个布隆过滤器,双射
67+
//直接映射char对应的int值,就不用存数值了
68+
int [] map=new int[128];
69+
int [] isUse=new int[128];
70+
for(int i=0;i<word.length();i++)
71+
{
72+
int p=pattern.charAt(i);
73+
int w=word.charAt(i);
74+
if(map[p]==0 && isUse[w]==0)//没有匹配过
75+
{
76+
map[p]=w;
77+
isUse[w]=1;
78+
}
79+
else if (map[p]!=w) {
80+
return false;
81+
}
82+
}
83+
return true;
84+
}
85+
86+
}
87+
```

‎2018.12.04-leetcode101/Despacito.md

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
# leetcode 101 Symmetric Tree
2+
## 1. Description
3+
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
4+
5+
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
6+
7+
1
8+
/ \
9+
2 2
10+
/ \ / \
11+
3 4 4 3
12+
13+
But the following [1,2,2,null,3,null,3] is not:
14+
15+
1
16+
/ \
17+
2 2
18+
\ \
19+
3 3
20+
21+
**Note:**
22+
23+
Bonus points if you could solve it both recursively and iteratively.
24+
25+
## 2. Solution
26+
```python
27+
# Definition for a binary tree node.
28+
# class TreeNode:
29+
# def __init__(self, x):
30+
# self.val = x
31+
# self.left = None
32+
# self.right = None
33+
34+
class Solution:
35+
def isSymmetric(self, root):
36+
"""
37+
:type root: TreeNode
38+
:rtype: bool
39+
"""
40+
if root == None:
41+
return True
42+
return self.comroot(root.left, root.right)
43+
44+
def comroot(self, left, right):
45+
if left == None and right == None:
46+
return True
47+
elif left == None or right == None:
48+
return False
49+
elif left.val != right.val:
50+
return False
51+
return self.comroot(left.left, right.right) and self.comroot(left.right, right.left)
52+
```

‎2018.12.05-leetcode102/Be a fresh man.md

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
## 102_(二叉树的层次遍历)Binary Tree Level Order Traversal
2+
## 1 问题描述、输入输出与样例
3+
### 1.1 问题描述
4+
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。<br>
5+
### 1.2 输入与输出
6+
输入：<br>
7+
* TreeNode* root：二叉树的根节点指针<br>
8+
输出：<br>
9+
* vector<vector<int>>：层次遍历的结果，是一个二维矢量的形式
10+
### 1.3 样例
11+
#### 1.3.1 样例1
12+
输入: 给定二叉树: [3,9,20,null,null,15,7],
13+
14+
3
15+
/ \
16+
9 20
17+
/ \
18+
15 7
19+
20+
输出:
21+
22+
[
23+
[3],
24+
[9,20],
25+
[15,7]
26+
]
27+
28+
## 2 思路描述与代码
29+
### 2.1 思路描述（基于队列的二叉树层次遍历）
30+
二叉树的层次遍历可以利用队列来做，其思路也很简单。<br>
31+
这里为了把每层的结果记录下来，对BFS的代码结构稍微改动了下，即里面用了个 for 循环做当前层遍历。<br>
32+
```cpp
33+
初始化二叉树层次遍历的二维矢量 res ;
34+
头结点入队;
35+
while( 队列不空 ){
36+
初始化当前层的遍历结果 level;
37+
获取当前层的数目数 len;
38+
for( int i = 0; i < len; i++ ){
39+
取出当前层的节点tmp并保存至 level;
40+
左右孩子非空则入队;
41+
}
42+
将 level 保存至 res ;
43+
}
44+
返回 res ;
45+
```
46+
比如给定二叉树: [3,9,20,null,null,15,7];<br>
47+
首先根节点3入队，然后进入 while 循环;<br>
48+
此时队列不空，有1个元素3，for 循环后有 res = {[3]}, 队列里面有元素[9, 20];<br>
49+
此时队列不空，有元素[9, 20]，for 循环后有 res = {[3],[9,20]}, 队列里面有元素[15, 7];<br>
50+
此时队列不空，有元素[15, 7]，for 循环后有 res = {[3],[9,20], [15,7]}, 队列里面没有元素;<br>
51+
此时队列空后，返回 res = {[3],[9,20], [15,7]} 。
52+
53+
### 2.2 代码
54+
```cpp
55+
vector<vector<int>> levelOrder(TreeNode* root) {
56+
vector<vector<int>> res;
57+
//如果输入为空
58+
if (root == NULL) {
59+
return res;
60+
}
61+
//队列做BFS
62+
queue<TreeNode*> q;
63+
q.push(root);
64+
while( !q.empty() ){
65+
//获取当前层的数目
66+
int len = q.size();
67+
vector<int> level;
68+
TreeNode* tmp;
69+
for( int i = 0; i < len; i++ ){
70+
//取一节点放入当前层的结果矢量里
71+
tmp = q.front();
72+
q.pop();
73+
level.push_back(tmp->val);
74+
//当前层所有的节点如果有孩子节点则压入队列
75+
if(tmp->left){
76+
q.push(tmp->left);
77+
}
78+
if(tmp->right){
79+
q.push(tmp->right);
80+
}
81+
}
82+
res.push_back(level);
83+
}
84+
return res;
85+
}
86+
```
87+
## 3 思考与拓展
88+
### 3.1 思考
89+
本题，利用队列做二叉树的层次遍历并保存结果。当然你可以利用堆栈做，但是保存结果的方式不一样而已。
90+
#### 3.1.1 其他方法
91+
#### 3.1.1.1 基于堆栈的二叉树层次遍历
92+
思路还是一致的，只是数据结构换了而已。在每层遍历的时候，需要改动的地方有:
93+
1. 入堆栈要右子树(如果有的话)先入，左子树(如果有的话)后入;
94+
2. 当前层遍历结果 level 要反序再 push_back 至 res。
95+
#### 3.1.2 复杂度分析
96+
方法|空间复杂度|时间复杂度
97+
--- | --- | ---
98+
基于队列的二叉树层次遍历|O(2^h),h是树的高度|O(n)
99+
基于堆栈的二叉树层次遍历|O(2^h),h是树的高度|O(n)，由于多了一步反序，所以会比基于队列的慢一点
100+
#### 3.1.3 难点分析
101+
1. 采用什么数据结果做层次遍历
102+
2. 如何保存每层的遍历结果
103+
### 3.2 拓展
104+
如果让你[锯齿形层次遍历](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/)呢？

0 commit comments

Comments
 (0)