Java算法篇（一）
前言: 本篇博客是自己以一个星期为周期来记录的，周一到周五课程比较多，只能晚上来刷算法。加上还有其他事情，刷题时间不是特别多。周末的话还有其他的事情。如果本篇博客中存在错误，欢迎指导纠正，自己也是菜鸟水平，请多多包含！！！
一、替换空格
剑指offer：请实现⼀个函数，将⼀个字符串中的每个空格替换成“%20”
输入：We Are Happy
输出：We%20Are%20Happy
这里我采用了二种方法：① 常规方法； ② 使用 API 解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public class Solution {
public static String replaceSpace(StringBuffer str){
int length = str.length();
StringBuffer result = new StringBuffer();
for(int i = 0; i< length; i++){
char b = str.charAt(i);
if(String.valueOf(b).equals(" ")){
result.append("%20");
}else{
result.append(b);
}
}
return result.toString();
}
public static String replaceSpace2(StringBuffer str){
return str.toString().replaceAll("\\s","%20");
}
public static void main(String[] args) {
StringBuffer str = new StringBuffer("We Are Happy");
String s = Solution.replaceSpace(str);
String s1 = Solution.replaceSpace2(str);
System.out.println(s1);
}
}
|
输出结果：
二、最长公共前缀
Leetcode: 编写⼀个函数来查找字符串数组中的最⻓公共前缀。如果不存在公共前缀，返回空字符串 “”。
示例 1:
1
2
| 输⼊: ["flower","flow","flight"]
输出: "fl"
|
示例 2:
1
2
3
| 输⼊: ["dog","racecar","car"]
输出: ""
解释: 输⼊不存在公共前缀。
|
结题思路：先利用Arrays.sort(strs)为数组排序，再将数组第一个元素和最后元素的字符从前往后对比即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| public class Main {
public static String replaceSpace(String[] strs){
if(!checkStr(strs)){
return "";
}
int len = strs.length;
StringBuilder res = new StringBuilder();
Arrays.sort(strs);
int m = strs[0].length();
int n = strs[len - 1].length();
int num = Math.min(m,n);
for(int i = 0; i < num; i++){
if(strs[0].charAt(i) == strs[len -1].charAt(i)){
res.append(strs[0].charAt(i));
}else{
break;
}
}
return res.toString();
}
private static boolean checkStr(String[] strs){
boolean flag = false;
if(strs != null){
for(int i=0; i <strs.length; i++){
if(strs[i] != null && strs[i].length() != 0){
flag = true;
}else{
flag = false;
break;
}
}
}
return flag;
}
public static void main(String[] args) {
String[] strs = { "customer", "car", "cat" };
System.out.println(Main.replaceSpace(strs));
}
}
|
三、回文串
1、最长回文串
LeetCode: 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构建过程中，请注意区分大小写。比如：“Aa” 不能当做一个回文串。注意： 假设字符串的长度不会超过1010。
回⽂串： “回⽂串”是⼀个正读和反读都⼀样的字符串，⽐如“level”或者“noon”等等就是回⽂串。
——百度百科 地址： https://baike.baidu.com/item/%E5%9B%9E%E6%96%87%E4%B8%B2/1274921?fr=aladdin
示例 1:
1
2
3
4
5
6
7
8
| 输⼊:
"abccccdd"
输出:
7
解释:
我们可以构造的最⻓的回⽂串是"dccaccd", 它的⻓度是 7。
|
构成回文串的两种情况：
- 字符出现次数为双数的组合
- 字符出现次数为双数的组合+一个值出现一次的字符
统计字符串出现的次数即可，双数才能构成回文。因为允许中间一个数单独出现，比如：“adcba”,所以如果最后有字母落单，总长度可以加1.首先将字符串转变为数组。然后遍历给数组，判断对应字符是否在hashset中，如果不在就加进去，如果在就让count++，然后移除该字符！这样就能找到出现次数为双数的字符个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public int longestPalindrome(String s){
if(s.length() == 0){
return 0;
}
HashSet<Character> hashSet = new HashSet<>();
char[] chars = s.toCharArray();
int count = 0;
for(int i = 0; i < chars.length; i++){
if(!hashSet.contains(chars[i])){
hashSet.add(chars[i]);
}else{
hashSet.remove(chars[i]);
count++;
}
}
return hashSet.isEmpty()?count * 2 : count * 2 +1;
}
|
微信
支付宝
