ARTS 打卡 (20.09.07-20.09.13)

用户头像
小王同学
关注
发布于: 2020 年 09 月 13 日



Algorithm



leetcode 第10题 Regular Expression Matching

动态规划解法

class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] f = new boolean[m + 1][n + 1];
f[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p.charAt(j - 1) == '*') {
f[i][j] = f[i][j - 2];
if (matches(s, p, i, j - 1)) {
f[i][j] = f[i][j] || f[i - 1][j];
}
}
else {
if (matches(s, p, i, j)) {
f[i][j] = f[i - 1][j - 1];
}
}
}
}
return f[m][n];
}
public boolean matches(String s, String p, int i, int j) {
if (i == 0) {
return false;
}
if (p.charAt(j - 1) == '.') {
return true;
}
return s.charAt(i - 1) == p.charAt(j - 1);
}
}

leetcode第12题 Ineger To Roman

自己写的解法,占用空间第并且执行效率不高

class Solution {
public String intToRoman(int num) {
String result = "";
Map<Integer, String> relation = new HashMap<>();
relation.put(1, "I");
relation.put(5, "V");
relation.put(10, "X");
relation.put(50, "L");
relation.put(100, "C");
relation.put(500, "D");
relation.put(1000, "M");
boolean b = true;
int temp = 0;
int times = 1;
while (b) {
temp = num % 10;
num = num / 10;
if (num == 0) {
b = false;
}
for (int i = 1; i <= temp; i++) {
if(temp == 4 || temp == 9) {
result = relation.get(times) + relation.get((temp + 1) * times) + result;
break;
} else if (temp < 4) {
for (int j = 0; j < temp; j++) {
result = relation.get(times) + result;
}
break;
} else if (temp == 5) {
result = relation.get(times * temp) + result;
break;
} else if( temp > 5 && temp < 9) {
String tempResult = relation.get(5 * times);
for (int j = 5; j < temp; j++) {
tempResult = tempResult + relation.get(times);
}
result = tempResult + result;
break;
}
}
times *= 10;
}
return result;
}
}

官方给出的贪心算法

public static String solution(int num) {
int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
StringBuilder stringBuilder = new StringBuilder();
int index = 0;
while (index < 13) {
// 特别注意:这里是等号
while (num >= nums[index]) {
// 注意:这里是等于号,表示尽量使用大的"面值"
stringBuilder.append(romans[index]);
num -= nums[index];
}
index++;
}
return stringBuilder.toString();
}

Review:

Item3:

通过将构造函数私有化或者使用枚举将实例变为单例

通过静态工厂实现单例

public class Elvis {
private static final Elvis INSTANCE = new Elvis();
private Elvis() { ... }
public static Elvis getInstance() { return INSTANCE; }
public void leaveTheBuilding() { ... }
}

优点:

1、该API清楚的表明这是一个单例,由于实例是被static final修饰的,所以每次获取的实例都是相同的实例

2、工厂方法可以在不修改类本身的情况下,决定是否使用单例,工厂方法返回唯一的实例,但是它可以被修改为为调用它的每个线程返回一个单独的实例。

3、你可以编写通用的静态工厂来生成单例对象。

4、可以使用静态工厂实现Supplier。

5、单例对象实现序列化时仅仅用实现Serializable接口是不够的,要保证单例,必须将实例字段加transient修饰,并提供readResolve方法,否则在每次反序列化时会创建新对象。

Tip:

Throwable 和 Exception的区别

之前一直没有想过这两者的区别,最近看了一下

Exception是Throwable的子类

Throwable派生出了Exception和Error

Error是一种严重的问题,应用程序不应该捕捉它。 Exception一般可能是程序和业务上的错误,是可以恢复的。

Share:

https://cloud.tencent.com/developer/article/1173106



用户头像

小王同学

关注

还未添加个人签名 2019.03.04 加入

还未添加个人简介

评论

发布
暂无评论
ARTS 打卡 (20.09.07-20.09.13)