Skip to content

Commit 0c41d0b

Browse files
dan322dan322
committed
week two homework
1 parent 37f5f32 commit 0c41d0b

File tree

6 files changed

+632
-8
lines changed

6 files changed

+632
-8
lines changed

‎Week 01/id_201/LeetCode_11_containerMaxWater‎

Lines changed: 5 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -6,11 +6,10 @@ class Solution {
66
public int maxArea(int[] height) {
77
int maxAreaSize = 0, area, i = 0, j = height.length - 1, currentMin, minHeight;
88
while (i < j) {
9-
if (height[i] < height[j] && minHeight > height[i++]) {
10-
continue;
9+
if (height[i] < height[j]) {
10+
currentMin = height[i++];
1111
} else {
12-
currentMin = height[j];
13-
j++;
12+
currentMin = height[j--];
1413
}
1514
if (currentMin <= minHeight)
1615
continue;
@@ -30,11 +29,9 @@ class Solution {
3029
int maxAreaSize = 0, area = 0, i = 0, j = height.length - 1;
3130
while (i < j) {
3231
if (height[i] < height[j]) {
33-
area = height[i] * (j - i);
34-
i++;
32+
area = height[i] * (j - i++);
3533
} else {
36-
area = height[j] * (j - i);
37-
j++;
34+
area = height[j] * (j-- - i);
3835
}
3936
if (maxAreaSize < area)
4037
maxAreaSize = area;

‎Week 01/id_201/LeetCode_283_moveZeroes.java‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
//给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
2+
//
3+
// 示例:
4+
//
5+
// 输入: [0,1,0,3,12]
6+
//输出: [1,3,12,0,0]
7+
//
8+
// 说明:
9+
//
10+
//
11+
// 必须在原数组上操作，不能拷贝额外的数组。
12+
// 尽量减少操作次数。
13+
//
14+
// Related Topics 数组 双指针
15+
16+
17+
18+
//leetcode submit region begin(Prohibit modification and deletion)
19+
class Solution {
20+
21+
/**
22+
* 时间复杂度 O(N)
23+
* 双指针， I 指针遍历所有元素， J指针代表0元素的开始位置 （下一个非零元素放置位置）
24+
* 交换零元素和非零元素的值
25+
* （该交换是对于下一个补全0元素方法的优化 EXAMPL： [0 , 0 , 0, 1] 在该场景下只需要交换一次，而下一种方法需要操作N次）
26+
* 一个简单的实现是，如果当前元素是非 0 的，那么它的正确位置最多可以是当前位置或者更早的位置。如果是后者，则当前位置最终将被非 0 或 0 占据，该非 0 或 0 位于大于 “cur” 索引的索引处。我们马上用 0 填充当前位置，这样不像以前的解决方案，我们不需要在下一个迭代中回到这里。
27+
*
28+
* 换句话说，代码将保持以下不变：
29+
*
30+
* 慢指针（lastnonzerofoundat）之前的所有元素都是非零的。
31+
* 当前指针和慢速指针之间的所有元素都是零。
32+
* 因此，当我们遇到一个非零元素时，我们需要交换当前指针和慢速指针指向的元素，然后前进两个指针。如果它是零元素，我们只前进当前指针。
33+
*
34+
* 链接：https://leetcode-cn.com/problems/move-zeroes/solution/yi-dong-ling-by-leetcode/
35+
* @param nums
36+
*/
37+
public void moveZeroes(int[] nums) {
38+
for (int i = 0, j = 0; i < nums.length; i++) {
39+
if (nums[i] != 0) {
40+
nums[j++] = nums[i];
41+
if (i != j++)
42+
nums[i] = 0;
43+
}
44+
}
45+
}
46+
47+
48+
/**
49+
* 时间复杂度 O(N)
50+
* @param nums
51+
*/
52+
public void moveZeroes1(int[] nums) {
53+
for (int i = 0, j = 0; i < nums.length; i++) {
54+
if (nums[i] != 0) {
55+
nums[j++] = nums[i];
56+
}
57+
}
58+
while (j < nums.length) {
59+
nums[j++] = 0;
60+
}
61+
}
62+
63+
/**
64+
* snowball
65+
* https://leetcode.com/problems/move-zeroes/discuss/172432/THE-EASIEST-but-UNUSUAL-snowball-JAVA-solution-BEATS-100-(O(n))-%2B-clear-explanation
66+
* @param nums
67+
*/
68+
public void moveZeroes2 (int[] nums) {
69+
public void moveZeroes(int[] nums) {
70+
int snowBallSize = 0;
71+
for (int i=0;i<nums.length;i++){
72+
if (nums[i]==0){
73+
snowBallSize++;
74+
}
75+
else if (snowBallSize > 0) {
76+
int t = nums[i];
77+
nums[i]=0;
78+
nums[i-snowBallSize]=t;
79+
}
80+
}
81+
}
82+
}
83+
84+
}
85+
//leetcode submit region end(Prohibit modification and deletion)

‎Week 01/id_201/LeetCode_70_climbStairs‎

Lines changed: 158 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,158 @@
1+
//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
2+
//
3+
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
4+
//
5+
// 注意：给定 n 是一个正整数。
6+
//
7+
// 示例 1：
8+
//
9+
// 输入： 2
10+
//输出： 2
11+
//解释： 有两种方法可以爬到楼顶。
12+
//1. 1 阶 + 1 阶
13+
//2. 2 阶
14+
//
15+
// 示例 2：
16+
//
17+
// 输入： 3
18+
//输出： 3
19+
//解释： 有三种方法可以爬到楼顶。
20+
//1. 1 阶 + 1 阶 + 1 阶
21+
//2. 1 阶 + 2 阶
22+
//3. 2 阶 + 1 阶
23+
//
24+
// Related Topics 动态规划
25+
26+
27+
28+
//leetcode submit region begin(Prohibit modification and deletion)
29+
class Solution {
30+
/**
31+
* top down (自顶向下)
32+
* 最后一步只有走一步 或走两步两种可能
33+
* 所以，求到N的所有可能转化为 到N-1的可能 + 到N-2的可能
34+
* 时间复杂度为O(N)
35+
*/
36+
/**
37+
* #1
38+
* @param n
39+
* @return
40+
*/
41+
public int climbStairs(int n) {
42+
int[] stepsArr = new int[n + 1];
43+
stepsArr[0] = 0;
44+
return getSteps(n, stepsArr);
45+
}
46+
47+
public int getSteps(int n, int[] stepsArr) {
48+
if (stepsArr[n] == 0) {
49+
if (n < 4) {
50+
stepsArr[n] = n;
51+
} else {
52+
stepsArr[n] = getSteps(n - 1) + getSteps(n - 2);
53+
}
54+
}
55+
return stepsArr[n];
56+
}
57+
58+
/**
59+
* #2
60+
* improvement of #1
61+
* @param n
62+
* @return
63+
*/
64+
public int climbStairs1(int n) {
65+
int[] stepArr = new int[n + 1];
66+
stepArr[1] = 1;
67+
stepArr[2] = 2;
68+
return getSteps2(n, stepArr);
69+
}
70+
71+
public int getSteps2(int n, int[] steps) {
72+
if (steps[n] == 0) {
73+
steps[n] = getSteps2(n - 1, steps) + getSteps2(n - 2, steps);
74+
}
75+
return steps[n];
76+
}
77+
78+
/**
79+
* bottom - up (从下往上分析)
80+
* 非波拉契数列
81+
*/
82+
public int climbStairs2(int n) {
83+
if (n < 4) {
84+
return n;
85+
}
86+
int preOne = 2, preTwo = 1, current;
87+
for (int i = 2; i < n; i++) {
88+
current = preOne + preTwo;
89+
preTwo = preOne;
90+
preOne = current;
91+
}
92+
return current;
93+
}
94+
95+
/**
96+
* simplified code
97+
* @param n
98+
* @return
99+
*/
100+
public int climsStairs3(int n) {
101+
int a = 1, b = 1;
102+
while (n-- > 0) {
103+
a = (b += a) -a;
104+
}
105+
return a;
106+
}
107+
108+
/**
109+
* 自底向上分析 (暴力法/优化版【存储中间值】)
110+
* 在每一级台阶上有两种选择，走一步或者是走2步
111+
* 则到第N级台阶上的可能性是前面所有可能性的和
112+
*/
113+
/**
114+
* #3
115+
* 时间复杂度为O(2^n)
116+
* @param n
117+
* @return
118+
*/
119+
public int climbStairs4 (int n) {
120+
return climsStair(0, n);
121+
}
122+
123+
public int climsStair (int currentStair, int aimStair) {
124+
if (currentStair > aimStair) {
125+
return 0;
126+
}
127+
if (currentStair == aimStair) {
128+
return 1;
129+
}
130+
return climsStair(currentStair + 1, aimStair) + climsStair(currentStair + 2, aimStair);
131+
}
132+
133+
/**
134+
* #4 improvement of #3
135+
* 时间复杂度为O(N)
136+
* @param n
137+
* @return
138+
*/
139+
public int climbStairs5 (int n) {
140+
int[] stepsArr = new int[n + 1];
141+
return climsStair1(0, n, stepsArr);
142+
}
143+
144+
public int climsStair1 (int currentStair, int aimStair, int[] stepsArr) {
145+
if (currentStair > aimStair) {
146+
return 0;
147+
}
148+
if (currentStair == aimStair) {
149+
return 1;
150+
}
151+
if (stepsArr[n] == 0) {
152+
stepsArr[n] = climsStair1(currentStair + 1, aimStair) + climsStair1(currentStair + 2, aimStair);
153+
}
154+
return stepsArr[n];
155+
}
156+
157+
}
158+
//leetcode submit region end(Prohibit modification and deletion)

‎Week 02/id_201/LeetCode_242_validAnagram‎

Lines changed: 119 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,119 @@
1+
//给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
2+
//
3+
// 示例 1:
4+
//
5+
// 输入: s = "anagram", t = "nagaram"
6+
//输出: true
7+
//
8+
//
9+
// 示例 2:
10+
//
11+
// 输入: s = "rat", t = "car"
12+
//输出: false
13+
//
14+
// 说明:
15+
//你可以假设字符串只包含小写字母。
16+
//
17+
// 进阶:
18+
//如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
19+
// Related Topics 排序 哈希表
20+
21+
22+
23+
//leetcode submit region begin(Prohibit modification and deletion)
24+
class Solution {
25+
26+
/**
27+
* #1
28+
* 遍历S, T字符串，获取各个字母出现的次数
29+
* 比较各字母出现的次数是否相等
30+
* 时间复杂度为O(N)
31+
* hashmap
32+
* @param s
33+
* @param t
34+
* @return
35+
*/
36+
public boolean isAnagram(String s, String t) {
37+
char[] charArrS = s.toCharArray();
38+
char[] charArrT = t.toCharArray();
39+
if (charArrS.length != charArrT.length) {
40+
return false;
41+
}
42+
char[] occurTimes1 = new char[26];
43+
char[] occurTimes2 = new char[26];
44+
for (int i = 0; i < charArrS.length; i++) {
45+
occurTimes1[charArrS[i] - 'a']++;
46+
occurTimes2[charArrT[i] - 'a']++;
47+
}
48+
return Arrays.equals(occurTimes1, occurTimes2);
49+
}
50+
51+
/**
52+
* #2 improvement of #1
53+
* @param s
54+
* @param t
55+
* @return
56+
*/
57+
public boolean isAnagram2 (String s, String t) {
58+
char[] charArrS = s.toCharArray();
59+
char[] charArrT = t.toCharArray();
60+
if (charArrS.length != charArrT.length) {
61+
return false;
62+
}
63+
int[] occurTimes = new int[26];
64+
for (int i = 0; i++ < s.length;) {
65+
occurTimes[charArrS[i] - 'a']++;
66+
occurTimes[charArrT[i] - 'a']--;
67+
}
68+
for (int j = 0; j++ < occurTimes.length) {
69+
if (occurTimes[j] != 0)
70+
return false;
71+
}
72+
return true;
73+
}
74+
75+
/**
76+
* #1 improvement of #1, #2
77+
* @param s
78+
* @param t
79+
* @return
80+
*/
81+
public boolean isAnagram3 (String s, String t) {
82+
char[] charArrS = s.toCharArray();
83+
char[] charArrT = t.toCharArray();
84+
if (charArrS.length != charArrT.length) {
85+
return false;
86+
}
87+
int[] occurTimes = new int[26];
88+
for (int i = 0; i++ < s.length;) {
89+
occurTimes[charArrS[i] - 'a']++;
90+
}
91+
for (int j = 0; j++ < t.length;) {
92+
occurTimes[charArrT[i] - 'a']--;
93+
if (occurTimes[charArrT[i] - 'a'] < 0)
94+
return false;
95+
}
96+
return true;
97+
}
98+
99+
/**
100+
* 将字符串转化为char数组
101+
* 对数组进行排序
102+
* 比较排序后的数组是否相等
103+
* 时间复杂度 O(NlogN)
104+
* care: if string length is not equal then return false
105+
* @param s
106+
* @param t
107+
* @return
108+
*/
109+
public boolean isAnagram1 (String s, String t) {
110+
if (s.length ! = t.length)
111+
return false;
112+
char[] charS = s.toCharArray();
113+
Arrays.sort(charS);
114+
char[] charT = t.toCharArray();
115+
Arrays.sort(charT);
116+
return Arrays.equals(charS, charT);
117+
}
118+
}
119+
//leetcode submit region end(Prohibit modification and deletion)

0 commit comments

Comments
 (0)