Skip to content

Commit 175fdf2

Browse files
GeekUniversityGeekUniversity
authored
Merge pull request #98 from GitGarden2019/master
第三周作业#35
2 parents 805cdb3 + a79ae71 commit 175fdf2

9 files changed

Lines changed: 722 additions & 0 deletions

‎Week_02/id_35/LeetCode_03_35.java‎

Lines changed: 131 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,131 @@
1+
package com.leecode.week02;
2+
3+
import com.sun.org.apache.xpath.internal.operations.Bool;
4+
5+
import java.util.HashMap;
6+
import java.util.HashSet;
7+
import java.util.Map;
8+
import java.util.Set;
9+
10+
/**
11+
* https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
12+
* 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
13+
*/
14+
public class LeetCode_03_35 {
15+
public void printAllSubstring(String s){
16+
char[] chs=s.toCharArray();
17+
for(int i=0;i<s.length();i++){
18+
for(int j=i+1;j<s.length();j++){
19+
System.out.println(s.substring(i,j));
20+
}
21+
}
22+
}
23+
public static void main(String[] args) {
24+
LeetCode_03_35 lc=new LeetCode_03_35();
25+
System.out.println(lc.lengthOfLongestSubstring("abcabcbb"));
26+
System.out.println(lc.lengthOfLongestSubstring("abc abcbb"));
27+
System.out.println(lc.lengthOfLongestSubstring("bb bbb"));
28+
System.out.println(lc.lengthOfLongestSubstring(" "));
29+
System.out.println(lc.lengthOfLongestSubstring("au"));
30+
System.out.println(lc.lengthOfLongestSubstring("abcabcbb"));
31+
System.out.println(lc.lengthOfLongestSubstring("abbbcd"));
32+
33+
//1.给定一个字符串，先输出看子串都有哪些
34+
//暴力枚举
35+
lc.printAllSubstring("abcabcbb");
36+
37+
38+
}
39+
40+
41+
public int lengthOfLongestSubstring(String s){
42+
if(s.isEmpty()){
43+
return 0;
44+
}
45+
46+
if(s.length()==1){
47+
return 1;
48+
}
49+
50+
int longest=0;
51+
52+
char[] chs=s.toCharArray();
53+
Set<Character> set=new HashSet<>();
54+
for(int i=0;i<s.length();i++){
55+
set.add(chs[i]);
56+
int subLen=1;
57+
for(int j=i+1;j<s.length();j++){
58+
59+
if(set.contains(chs[j])){ //有重复字符,则循环终止
60+
set.clear();
61+
break;
62+
}else{
63+
set.add(chs[j]);
64+
}
65+
subLen++;
66+
}
67+
longest=Math.max(longest,subLen);
68+
69+
set.clear();
70+
71+
}
72+
return longest;
73+
}
74+
75+
76+
public int lengthOfLongestSubstring_v1(String s) {
77+
if(s.isEmpty()){
78+
return 0;
79+
}
80+
81+
if(s.length()==1){
82+
return 1;
83+
}
84+
85+
int longest=0;
86+
87+
char[] chs=s.toCharArray();
88+
Set<Character> set=new HashSet<>();
89+
for(int i=0;i<s.length();i++){
90+
set.add(chs[i]);
91+
int subLen=1;
92+
for(int j=i+1;j<s.length();j++){
93+
94+
if(set.contains(chs[j])){ //有重复字符,则循环终止
95+
set.clear();
96+
break;
97+
}else{
98+
set.add(chs[j]);
99+
}
100+
subLen++;
101+
}
102+
longest=Math.max(longest,subLen);
103+
104+
set.clear();
105+
106+
}
107+
return longest;
108+
}
109+
110+
/*Map<String, Boolean> cache=new HashMap<>();
111+
public boolean hasRepeatingChar(String s){
112+
113+
if(cache.containsKey(s)){
114+
return cache.get(s);
115+
}
116+
117+
char[] chs=s.toCharArray();
118+
Set<Character> characters=new HashSet<>();
119+
for (char ch:chs) {
120+
if(characters.contains(ch)){
121+
cache.put(s,true);
122+
return true;
123+
}else {
124+
characters.add(ch);
125+
}
126+
127+
}
128+
cache.put(s,false);
129+
return false;
130+
}*/
131+
}

‎Week_02/id_35/LeetCode_242_35.java‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
package com.leecode.week02;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
7+
* 输入: s = "anagram", t = "nagaram"
8+
* 输出: true
9+
*/
10+
public class LeetCode_242_35 {
11+
public static void main(String[] args) {
12+
LeetCode_242_35 lc=new LeetCode_242_35();
13+
System.out.println(lc.isAnagram("anagram","nagaram"));
14+
15+
System.out.println(lc.isAnagram("rat","art"));
16+
System.out.println(lc.isAnagram("rat"," car"));
17+
//Arrays.equals("anagram".toCharArray(),"nagaram".toCharArray());
18+
}
19+
20+
public boolean isAnagram(String s, String t)
21+
{
22+
if(s==null||t==null||s.length()!=t.length()){
23+
return false;
24+
}
25+
int[] sArr=new int[128];
26+
int[] tArr=new int[128];
27+
char[] sChs=s.toCharArray();
28+
char[] tChs=t.toCharArray();
29+
30+
for(int i=0;i<sChs.length;i++){
31+
sArr[sChs[i]]++;
32+
tArr[tChs[i]]++;
33+
}
34+
35+
36+
return Arrays.equals(sArr,tArr);
37+
}
38+
39+
public boolean isAnagram_v0(String s, String t) {
40+
if(s.length()!=t.length()){
41+
return false;
42+
}
43+
char[] bys= s.toCharArray();
44+
Arrays.sort(bys);
45+
46+
char[] byt= t.toCharArray();
47+
Arrays.sort(byt);
48+
49+
int i = 0;
50+
int n = byt.length;
51+
while (n-- != 0) {
52+
if (bys[i] != byt[i])
53+
return false;
54+
i++;
55+
}
56+
57+
return true;
58+
}
59+
60+
/**
61+
*大神的做法
62+
*
63+
* public boolean isAnagram(String s, String t) {
64+
* if(s == null || t == null || s.length() != t.length()) return false;
65+
* int[]one = new int[128];
66+
* int[]two = new int[128];
67+
* for(char c: s.toCharArray()) one[c]++;
68+
* for(char c: t.toCharArray()) two[c]++;
69+
*
70+
* return Arrays.equals(one,two);
71+
* }
72+
*/
73+
}

‎Week_02/id_35/Leetcode_01_35.java‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
package com.leecode.week02;
2+
3+
import java.util.*;
4+
5+
/**
6+
* https://leetcode.com/problems/two-sum/
7+
* Given an array of integers, return indices of the two numbers such that they add up to a specific target.
8+
*
9+
* You may assume that each input would have exactly one solution, and you may not use the same element twice.
10+
*/
11+
public class Leetcode_01_35 {
12+
public static void main(String[] args) {
13+
Leetcode_01_35 lc=new Leetcode_01_35();
14+
int[] nums={2, 7, 11, 15};
15+
int target=9;
16+
System.out.println(Arrays.toString(lc.twoSum(nums,target)));
17+
System.out.println(Arrays.toString(lc.twoSum_v1(nums,target)));
18+
19+
}
20+
21+
22+
/**
23+
* 确定了一个元素之后另一个元素其实也确定了,一次遍历过程中因为要通过下标访问，所以提取不到另一个元素
24+
* 思路:遍历之后把元素的位置缓存起来
25+
* @param nums
26+
* @param target
27+
* @return
28+
*/
29+
public int[] twoSum(int[] nums, int target){
30+
31+
Map<Integer,Integer> cache=new HashMap<>();
32+
33+
for (int i=0;i<nums.length;i++){
34+
int num=nums[i];
35+
int other=target-num;
36+
if(cache.keySet().contains(other)){
37+
return new int[]{cache.get(other),i};
38+
}else {
39+
cache.put(num,i);
40+
}
41+
}
42+
43+
return null;
44+
}
45+
46+
/**
47+
*两次遍历，先找到第一个元素，剩下的元素再接着找，时间复杂度是O(n^2)
48+
* @param nums
49+
* @param target
50+
* @return
51+
*/
52+
public int[] twoSum_v1(int[] nums, int target) {
53+
int r1=-1,r2=-1;
54+
55+
for(int i=0;i<nums.length;i++){
56+
r1=i;
57+
int other=target-nums[r1];
58+
59+
for (int j=i+1;j<nums.length;j++){
60+
if(other==nums[j]){
61+
r2=j;
62+
break;
63+
}
64+
}
65+
66+
if(r2!=-1){
67+
break;
68+
}
69+
70+
}
71+
72+
return new int[]{r1,r2};
73+
}
74+
}

‎Week_03/id_35/Leetcode_102_35.java‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
package com.leecode.week03;
2+
3+
import com.leecode.TreeNode;
4+
5+
import java.util.ArrayDeque;
6+
import java.util.ArrayList;
7+
import java.util.List;
8+
import java.util.Queue;
9+
10+
/**
11+
* https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
12+
* 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
13+
*/
14+
public class Leetcode_102_35 {
15+
public static void main(String[] args) {
16+
Leetcode_102_35 lc=new Leetcode_102_35();
17+
//int[] arr={3,2,9,-1,-1,10,-1,-1,8,-1,11,-1};
18+
//[3,9,20,null,null,15,7]
19+
int[] arr={3,9,20,-1,-1,-1,15,7};
20+
// int[] arr={3,2};
21+
TreeNode treeNode=TreeNode.createBinaryV1(arr,arr.length);
22+
23+
List<List<Integer>> list= lc.levelOrder(treeNode);
24+
System.out.println(list);
25+
26+
}
27+
28+
/**
29+
* 思考过程，我是做了多叉树按层次遍历的题目之后来做这道题目的
30+
*
31+
* @param root
32+
* @return
33+
*/
34+
public List<List<Integer>> levelOrder(TreeNode root) {
35+
36+
List<List<Integer>> list=new ArrayList<>();
37+
if(root==null){
38+
return list;
39+
}
40+
41+
Queue<TreeNode> queue=new ArrayDeque<>();
42+
queue.offer(root);
43+
44+
while (!queue.isEmpty()){
45+
int queueSize=queue.size();
46+
List<Integer> ls =new ArrayList<>(queueSize);
47+
48+
for(int i=0;i<queueSize;i++){
49+
TreeNode node =queue.poll();
50+
ls.add(node.val);
51+
if(node.left!=null){
52+
queue.offer(node.left);
53+
54+
}
55+
56+
if(node.right!=null){
57+
queue.offer(node.right);
58+
59+
}
60+
61+
}
62+
63+
list.add(ls);
64+
}
65+
66+
return list;
67+
}
68+
69+
70+
}

0 commit comments

Comments
 (0)