Skip to content

Commit 69cf9f3

Browse files
leosanqingleosanqing
committed
1. 新增部分题目
1 parent 3be385d commit 69cf9f3

9 files changed

Lines changed: 423 additions & 31 deletions

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/easy/_617_mergeTwoBinaryTree.java‎

Lines changed: 16 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -7,18 +7,18 @@
77
*
88
* 示例： Input:
99
* Tree 1 Tree 2
10-
* 1 2
11-
* / \ / \
12-
* 3 2 1 3
13-
* / \ \
14-
* 5 4 7
15-
* Output:
16-
* Merged tree:
17-
* 3
18-
* / \
19-
* 4 5
20-
* / \ \
21-
* 5 4 7
10+
* 1 2
11+
* / \ / \
12+
* 3 2 1 3
13+
* / \ \
14+
* 5 4 7
15+
* Output:
16+
* Merged tree:
17+
* 3
18+
* / \
19+
* 4 5
20+
* / \ \
21+
* 5 4 7
2222
*
2323
*
2424
* 思路： 使用递归遍历二叉树，然后对两者进行操作
@@ -33,10 +33,12 @@ static class TreeNode{
3333

3434
}
3535
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
36-
if(t1 == null)
36+
if(t1 == null) {
3737
return t2;
38-
if(t2 == null)
38+
}
39+
if(t2 == null) {
3940
return t1;
41+
}
4042
t1.val += t2.val;
4143
t1.left = mergeTrees(t1.left,t2.left);
4244
t1.right = mergeTrees(t1.right,t2.right);

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/easy/array/_14_longestCommonPrefix.java‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package com.leosanqing.leetcode.easy.array;
2+
3+
/**
4+
* @Author: rtliu
5+
* @Date: 2020/7/3 下午5:08
6+
* @Package: com.leosanqing.leetcode.easy.array
7+
* @Description: Write a function to find the longest common prefix string amongst an array of strings.
8+
* If there is no common prefix, return an empty string "".
9+
* <p>
10+
* Example 1:
11+
* Input: ["flower","flow","flight"]
12+
* Output: "fl"
13+
* <p>
14+
* Example 2:
15+
* Input: ["dog","racecar","car"]
16+
* Output: ""
17+
* Explanation:
18+
* There is no common prefix among the input strings.
19+
* @Version: 1.0
20+
*/
21+
public class _14_longestCommonPrefix {
22+
// public static void main(String[] args) {
23+
// BigInteger bigDecimal = BigInteger.valueOf(Math.pow(2, 478));
24+
// System.out.println(bigDecimal);
25+
// }
26+
27+
28+
public static void main(String[] args) {
29+
String[] strings = new String[]{"aa","a"};
30+
31+
System.out.println(longestCommonPrefix(strings));
32+
}
33+
public static String longestCommonPrefix(String[] strs) {
34+
if(strs == null ||strs.length == 0){
35+
return "";
36+
}
37+
38+
String pre = strs[0];
39+
for (int i = 1; i < strs.length; i++) {
40+
// 每次减去一个字符，找最长的公共前缀
41+
while(strs[i].indexOf(pre) != 0){
42+
pre = pre.substring(0,pre.length()-1);
43+
}
44+
}
45+
46+
return pre;
47+
}
48+
49+
50+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/easy/num/_7_reverseInteger.java‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.leosanqing.leetcode.easy.num;
2+
3+
/**
4+
* @Author: rtliu
5+
* @Date: 2020/7/3 下午3:19
6+
* @Package: com.leosanqing.leetcode.easy.num
7+
* @Description:
8+
* ` Given a 32-bit signed integer, reverse digits of an integer.
9+
* ` Example 1:
10+
* ` Input: 123
11+
* ` Output: 321
12+
* ` Example 2:
13+
* ` Input: -123
14+
* ` Output: -321
15+
* ` Example 3:
16+
* ` Input: 120
17+
* ` Output: 21
18+
* ` Note:
19+
* ` Assume we are dealing with an environment which could only store integers
20+
* ` within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem,
21+
* ` assume that your function returns 0 when the reversed integer overflows.
22+
* @Version: 1.0
23+
*/
24+
public class _7_reverseInteger {
25+
public static void main(String[] args) {
26+
_7_reverseInteger reverseInteger = new _7_reverseInteger();
27+
System.out.println(reverseInteger.reverse(-1200));
28+
}
29+
public int reverse(int x) {
30+
long res = 0;
31+
while (x != 0) {
32+
res *= 10;
33+
res += x % 10;
34+
x /= 10;
35+
}
36+
return (int)res == res ? (int)res : 0;
37+
}
38+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/easy/num/_9_palindromeNumber.java‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package com.leosanqing.leetcode.easy.num;
2+
3+
/**
4+
* @Author: rtliu
5+
* @Date: 2020/7/3 下午3:24
6+
* @Package: com.leosanqing.leetcode.easy.num
7+
* @Description: `
8+
* ` Determine whether an integer is a palindrome.
9+
* ` An integer is a palindrome when it reads the same backward as forward.
10+
* `
11+
* ` Example 1:
12+
* ` Input: 121
13+
* ` Output: true
14+
* ` Example 2:
15+
* ` Input: -121
16+
* ` Output: false
17+
* ` Explanation:
18+
* ` From left to right, it reads -121.
19+
* ` From right to left, it becomes 121-.
20+
* ` Therefore it is not a palindrome.
21+
* ` Example 3:
22+
* ` Input: 10
23+
* ` Output: false
24+
* ` Explanation:
25+
* ` Reads 01 from right to left. Therefore it is not a palindrome.
26+
* @Version: 1.0
27+
*/
28+
public class _9_palindromeNumber {
29+
30+
public static void main(String[] args) {
31+
System.out.println(isPalindrome(12121));
32+
}
33+
34+
public static boolean isPalindrome(int x) {
35+
// 如果小于0 或者大于零 但是以0结尾的都不是
36+
if (x < 0 || (x !=0 && x % 10 == 0)) {
37+
return false;
38+
}
39+
40+
int rev = 0;
41+
// 只需要一半，就可以进行匹配
42+
while (x > rev) {
43+
rev = rev *10 + x%10;
44+
x /=10;
45+
}
46+
return rev == x || x == rev/10;
47+
}
48+
49+
/**
50+
* 使用字符串
51+
* @param x
52+
* @return
53+
*/
54+
public static boolean isPalindrome2(int x) {
55+
// 如果小于0 或者大于零 但是以0结尾的都不是
56+
if (x < 0 || (x !=0 && x % 10 == 0)) {
57+
return false;
58+
}
59+
60+
String s = String.valueOf(x);
61+
62+
for (int i = 0; i < s.length()/2; i++) {
63+
if (s.charAt(i) != s.charAt(s.length()-i-1)){
64+
return false;
65+
}
66+
}
67+
return true;
68+
}
69+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/array/_11_containerWithMostWater.java‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package com.leosanqing.leetcode.medium.array;
2+
3+
/**
4+
* @Author: rtliu
5+
* @Date: 2020/7/3 下午4:44
6+
* @Package: com.leosanqing.leetcode.medium.array
7+
* @Description: ` Given n non-negative integers a1, a2, ..., an ,
8+
* ` where each represents a point at coordinate (i, ai).
9+
* ` n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).
10+
* ` Find two lines, which together with x-axis forms a container,
11+
* ` such that the container contains the most water.
12+
* <p>
13+
* <p>
14+
* ` Note: You may not slant the container and n is at least 2.
15+
* ` The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7].
16+
* ` In this case, the max area of water (blue section) the container can contain is 49.
17+
* `
18+
* ` Example:
19+
* <p>
20+
* ` Input: [1,8,6,2,5,4,8,3,7]
21+
* ` Output: 49
22+
* @Version: 1.0
23+
*/
24+
public class _11_containerWithMostWater {
25+
26+
public int maxArea(int[] height) {
27+
int i = 0, j = height.length - 1;
28+
int max = 0;
29+
while (i < j) {
30+
31+
if (height[i] < height[j]) {
32+
max = Math.max(max, (j - i) * height[i++]);
33+
34+
} else {
35+
max = Math.max(max, (j - i) * height[j--]);
36+
}
37+
}
38+
return max;
39+
}
40+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/array/_16_3num_closest.java‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package com.leosanqing.leetcode.medium.array;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* @Author: rtliu
7+
* @Date: 2020/7/6 上午10:51
8+
* @Package: com.leosanqing.leetcode.medium.array
9+
* @Description: ` Given an array nums of n integers and an integer target,
10+
* ` find three integers in nums such that the sum is closest to target.
11+
* ` Return the sum of the three integers.
12+
* ` You may assume that each input would have exactly one solution.
13+
* ` Example 1:
14+
* ` Input:
15+
* ` nums = [-1,2,1,-4],>
16+
* ` Output: 2
17+
* ` Explanation:
18+
* ` The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
19+
* @Version: 1.0
20+
*/
21+
public class _16_3num_closest {
22+
public static void main(String[] args) {
23+
24+
int[] ints = {
25+
1, 2, 4, 8, 16, 32, 64, 128};
26+
System.out.println(threeSumClosest(ints,82));
27+
}
28+
29+
/**
30+
* 时间复杂度O(n²)
31+
* 设置两个游标，然后进行遍历
32+
* @param nums
33+
* @param target
34+
* @return
35+
*/
36+
public static int threeSumClosest(int[] nums, int target) {
37+
int result = nums[0] + nums[1] + nums[nums.length - 1];
38+
int sum;
39+
// 先对大小进行排序
40+
Arrays.sort(nums);
41+
for (int i = 0; i < nums.length; i++) {
42+
43+
// start 可以跳过之前的。因为之前的已经比较过
44+
int start = i+1, end = nums.length - 1;
45+
46+
while (start < end) {
47+
sum = nums[i] + nums[start] + nums[end];
48+
49+
if (sum > target) {
50+
end--;
51+
} else {
52+
start++;
53+
}
54+
if (Math.abs(result - target) > Math.abs(sum - target)){
55+
result = sum;
56+
}
57+
}
58+
}
59+
return result;
60+
}
61+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/array/_17_letter_combinations_of_a_phone_number.java‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package com.leosanqing.leetcode.medium.array;
2+
3+
import java.util.LinkedList;
4+
import java.util.List;
5+
6+
/**
7+
* @Author: rtliu
8+
* @Date: 2020/7/6 上午11:22
9+
* @Package: com.leosanqing.leetcode.medium.array
10+
* @Description: ` ` Given a string containing digits from 2-9 inclusive,
11+
* ` ` return all possible letter combinations that the number could represent.
12+
* ` ` A mapping of digit to letters (just like on the telephone buttons) is given below.
13+
* ` ` Note that 1 does not map to any letters.
14+
* ` ` Example:
15+
* ` ` Input: '23'
16+
* ` ` Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf'].
17+
* @Version: 1.0
18+
*/
19+
public class _17_letter_combinations_of_a_phone_number {
20+
21+
public static void main(String[] args) {
22+
23+
System.out.println(letterCombinations("5465768"));
24+
}
25+
26+
public static List<String> letterCombinations(String digits) {
27+
char[] charArray = digits.toCharArray();
28+
29+
List<String> list = new LinkedList<>();
30+
char[][] map = {
31+
{},
32+
{},
33+
{'a', 'b', 'c'},
34+
{'d', 'e', 'f'},
35+
{'g', 'h', 'i'},
36+
{'j', 'k', 'l'},
37+
{'m', 'n', 'o'},
38+
{'p', 'q', 'r', 's'},
39+
{'t', 'u', 'v'},
40+
{'w', 'x', 'y', 'z'},
41+
};
42+
43+
backtrack(charArray, list, map, new StringBuilder(), 0);
44+
return list;
45+
46+
}
47+
48+
49+
private static void backtrack(char[] digits, List<String> list, char[][] map, StringBuilder sb, int offset) {
50+
if (offset == digits.length) {
51+
list.add(sb.toString());
52+
return;
53+
}
54+
55+
// 获得 map 的索引
56+
int index = digits[offset] - '0';
57+
// 遍历每个按键的所有情况
58+
for (int i = 0; i < map[index].length; i++) {
59+
// 挨个追加值
60+
sb.append(map[index][i]);
61+
backtrack(digits, list, map, sb, offset + 1);
62+
// 删除
63+
sb.deleteCharAt(sb.length() - 1);
64+
}
65+
}
66+
}

0 commit comments

Comments
 (0)