Skip to content

Commit 231d800

Browse files
melody-limelody-li
authored
Merge pull request algorithm007-class02#358 from CodeWolf-G7/master
0312-Week 02
2 parents fe7e0d4 + e0238d2 commit 231d800

10 files changed

Lines changed: 669 additions & 1 deletion

‎Week_01/G20200343040312/test.txt‎

Whitespace-only changes.

‎Week_02/G20200343040312/LeetCode_1_0312.java‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
//给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
2+
//
3+
// 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
4+
//
5+
// 示例:
6+
//
7+
// 给定 nums = [2, 7, 11, 15], target = 9
8+
//
9+
//因为 nums[0] + nums[1] = 2 + 7 = 9
10+
//所以返回 [0, 1]
11+
//
12+
// Related Topics 数组 哈希表
13+
14+
/*
15+
* 查看解答前的思考;
16+
* 1. 方法一，双指针两重循环，不重复---可以根据循环变量起始位置来规避重复，这样还可以避免进“是否重复”的判断
17+
* 即，直接使用j=i+1避免了i==j的判断,而使用i<nums.length-1是为了避免j=i+1溢出
18+
* 2. 短时间内没有想出时间复杂度更短的方法，但根据题目提示应该与哈希表有关，自己还不太会使用它
19+
* */
20+
21+
/**
22+
* 查看解答后的思考：
23+
* 1.一遍哈希表
24+
* 2.两边哈希表
25+
* （哈希表的知识有待学习，暂放[mark],该标志用于快速搜索）
26+
* 3.根据官方题解，自己应该要考虑地更加周全---当没有结果时要抛出错误。即使题目中说“假设每种输入只会对应一个答案”
27+
*
28+
* fixMark:
29+
* 1. 哈希表其实用起来很简单嘛，学习过程详见题目409的注释
30+
* 2. 一遍哈希表就ok
31+
* */
32+
33+
import java.util.Collection;
34+
import java.util.HashMap;
35+
import java.util.Map;
36+
import java.util.Set;
37+
38+
//leetcode submit region begin(Prohibit modification and deletion)
39+
class Solution {
40+
41+
public int[] twoSum(int[] nums, int target) {
42+
/*
43+
* 方法一，双指针*/
44+
// int[] position = new int[2];
45+
// boolean flag = false;
46+
//
47+
// for (int i=0; i<nums.length-1; i++){
48+
// for (int j=i+1; j<nums.length; j++){
49+
// //找到答案后立刻
50+
// if (nums[j]==(target-nums[i])){
51+
// position[0]=i;
52+
// position[1]=j;
53+
// flag=true;
54+
// break;
55+
// }
56+
// }
57+
// if (flag==true){
58+
// break;
59+
// }
60+
// }
61+
// return position;
62+
/*
63+
* 耗时71ms左右（13%），使用内存39.6M（5%）,双指针必然低效*/
64+
65+
Map<Integer, Integer> map = new HashMap<>();
66+
for (int i = 0; i < nums.length; i++) {
67+
int diffence = target - nums[i];
68+
if (map.containsKey(diffence)) {
69+
return new int[]{map.get(diffence), i};
70+
}
71+
map.put(nums[i], i);
72+
}
73+
throw new IllegalArgumentException("No two sum solution");
74+
/**
75+
* 直接将数组的值（当做key）与下标（当做Value）放入Map中，然后利用map.containsKey()逐个查询Map中是否有值与差值相符*/
76+
}
77+
}

‎Week_02/G20200343040312/LeetCode_42_0312.txt‎

Lines changed: 124 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,124 @@
1+
//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
2+
//
3+
// 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Mar
4+
//cos 贡献此图。
5+
//
6+
// 示例:
7+
//
8+
// 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
9+
//输出: 6
10+
// Related Topics 栈 数组 双指针
11+
12+
/**
13+
* 自己的想法：
14+
* 第一想法是，有点像[11]盛最多水的容器，[11]是计算最大，而这里是计算每一部分
15+
* 1.紧相邻两项之间没有雨水
16+
* 2.有雨水的必要条件是，
17+
* 作为边界的两项都>0,且他们（两个下标）之间必定至少有一项的值小于较"矮"的边界，称这样的每一项为“底”
18+
* 3.各部分雨水的面积计算公式-->（较"矮"边界的值-（每一项）底）*1的累和
19+
* 4.如何遍历找到，两边之间有雨水的每一对边界？
20+
* emm不好想到好的方法，直接套公式，然后套用自己的"较"矮"边界的值-（每一项）底）*1的累和"公式
21+
* PS.可以实现（如果没有逻辑上疏漏的话），但感觉自己的思路走了弯路，先看看题解
22+
* */
23+
24+
/**
25+
* 哇，这个精选题解中，按行按列的解法真是太赞了
26+
* 感觉自己刚才想的时候还是没有归到“最小问题上”，导致计算公式有些“黑盒”，没有触及问题更加“小”的计算方式上
27+
* 差了一点点
28+
*
29+
* 还有个“对于每根柱子，找到左边的最大值，再找到右边的最大值，然后；两者中取较小的 ，与“本根”柱子的差就是'本根'柱子上能存放的雨水”
30+
* 这个解法感觉和我的有异曲同工之妙，值得品味
31+
*
32+
* 补，由于时间关系，一些解法还没练习到，只是临摹了一部分。有意思的题目。估计全看会要一天233
33+
* */
34+
//leetcode submit region begin(Prohibit modification and deletion)
35+
class Solution {
36+
public int trap(int[] height) {
37+
/*
38+
* 方法一：对话每根柱子...*/
39+
int sum = 0;
40+
41+
if (height == null || height.length < 3) {
42+
return 0;
43+
}
44+
45+
int[] left = new int[height.length];
46+
left[0] = height[0];
47+
48+
for (int i = 1; i < height.length; i++) {
49+
left[i] = left[i - 1] > height[i] ? left[i - 1] : height[i];
50+
}
51+
52+
int[] right = new int[height.length];
53+
right[height.length - 1] = height[right.length - 1];
54+
55+
for (int i = height.length - 2; i >= 0; i--) {
56+
right[i] = right[i + 1] > height[i] ? right[i + 1] : height[i];
57+
}
58+
for (int i = 1; i < height.length - 1; i++) {
59+
sum += Math.min(left[i], right[i]) - height[i];
60+
}
61+
62+
return sum;
63+
64+
/*
65+
* 方法二：*/
66+
// int sum = 0;
67+
// int max = getMax(height);//找到最大的高度，以便遍历。
68+
// for (int i = 1; i <= max; i++) {
69+
// boolean isStart = false; //标记是否开始更新 temp
70+
// int temp_sum = 0;
71+
// for (int j = 0; j < height.length; j++) {
72+
// if (isStart && height[j] < i) {
73+
// temp_sum++;
74+
// }
75+
// if (height[j] >= i) {
76+
// sum = sum + temp_sum;
77+
// temp_sum = 0;
78+
// isStart = true;
79+
// }
80+
// }
81+
// }
82+
// return sum;
83+
84+
/*
85+
* 双指针*/
86+
// int sum = 0;
87+
// int max_left = 0;
88+
// int max_right = 0;
89+
// int left = 1;
90+
// int right = height.length - 2; // 加右指针进去
91+
// for (int i = 1; i < height.length - 1; i++) {
92+
// //从左到右更
93+
// if (height[left - 1] < height[right + 1]) {
94+
// max_left = Math.max(max_left, height[left - 1]);
95+
// int min = max_left;
96+
// if (min > height[left]) {
97+
// sum = sum + (min - height[left]);
98+
// }
99+
// left++;
100+
// //从右到左更
101+
// } else {
102+
// max_right = Math.max(max_right, height[right + 1]);
103+
// int min = max_right;
104+
// if (min > height[right]) {
105+
// sum = sum + (min - height[right]);
106+
// }
107+
// right--;
108+
// }
109+
// }
110+
// return sum;
111+
112+
}
113+
}
114+
115+
//private int getMax(int[] height) {
116+
// int max = 0;
117+
// for (int i = 0; i < height.length; i++) {
118+
// if (height[i] > max) {
119+
// max = height[i];
120+
// }
121+
// }
122+
// return max;
123+
//}
124+
//leetcode submit region end(Prohibit modification and deletion)

‎Week_02/G20200343040312/LeetCode_49_0312.java‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
//给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
2+
//
3+
// 示例:
4+
//
5+
// 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
6+
//输出:
7+
//[
8+
// ["ate","eat","tea"],
9+
// ["nat","tan"],
10+
// ["bat"]
11+
//]
12+
//
13+
// 说明：
14+
//
15+
//
16+
// 所有输入均为小写字母。
17+
// 不考虑答案输出的顺序。
18+
//
19+
// Related Topics 哈希表 字符串
20+
21+
/**
22+
* 自己的思考：
23+
* 自己想到先排序字符了，但是不知道如何返回成结果这样子的结构，
24+
* java功底不足限制了自己T-T*/
25+
/**
26+
* 查看解答后：
27+
* 官方解法一的思想和自己的一样，学习，后面要多敲几遍
28+
* 另外，阿里代码规范还是要给if带大括号
29+
*
30+
* 官方题解的方法二感觉反而做麻烦了
31+
* */
32+
33+
import java.util.ArrayList;
34+
import java.util.Arrays;
35+
import java.util.HashMap;
36+
import java.util.List;
37+
import java.util.Map;
38+
39+
//leetcode submit region begin(Prohibit modification and deletion)
40+
class Solution {
41+
public List<List<String>> groupAnagrams(String[] strs) {
42+
/*
43+
* 方法一*/
44+
if (strs.length == 0) {
45+
return new ArrayList();
46+
}
47+
Map<String, List> ans = new HashMap<String, List>();
48+
for (String s : strs) {
49+
char[] ca = s.toCharArray();
50+
Arrays.sort(ca);
51+
String key = String.valueOf(ca);
52+
if (!ans.containsKey(key)) {
53+
ans.put(key, new ArrayList());
54+
}
55+
ans.get(key).add(s);
56+
}
57+
return new ArrayList(ans.values());
58+
59+
/*
60+
* 方法二*/
61+
// if (strs.length == 0){
62+
// return new ArrayList();
63+
// }
64+
// Map<String, List> ans = new HashMap<String, List>();
65+
// int[] count = new int[26];
66+
// for (String s : strs) {
67+
// Arrays.fill(count, 0);
68+
// for (char c : s.toCharArray()){
69+
// count[c - 'a']++;
70+
// }
71+
// StringBuilder sb = new StringBuilder("");
72+
// for (int i = 0; i < 26; i++) {
73+
// sb.append('#');
74+
// sb.append(count[i]);
75+
// }
76+
// String key = sb.toString();
77+
// if (!ans.containsKey(key)){
78+
// ans.put(key, new ArrayList());
79+
// }
80+
// ans.get(key).add(s);
81+
// }
82+
// return new ArrayList(ans.values());
83+
}
84+
}
85+
//leetcode submit region end(Prohibit modification and deletion)

0 commit comments

Comments
 (0)