第一题：子串模糊匹配
从字符串string开始完整匹配子串sub，返回匹配到的字符个数。
sub中如果出现'?'表示可以匹配一到三个除'\0'以外的任意字符。
如果sub还有找不到到匹配的字符，则说明不能完全匹配。
如果能完整匹配，返回匹配到的字符个数，如果有多种匹配方式，返回匹配字符数最少的那个，如果不能完整匹配，返回 -1。
输入描述：
第一行输入字符串 string，长度小于 10000
第二行输入子串 sub，长度小于 100
输出描述：
从 string 开头位置完整匹配 sub，匹配到的字符个数。
// 输入例子1
abcdefg
a?c
// 输出例子1
3
// 输入例子2
aabcddefg
a?c
// 输出例子2
4
// 输入例子3
aabcddefg
b?e
// 输出例子3
-1
// 输入例子4
aabcddefg
a?d
// 输出例子4
5
方法一：采用正则表达式
let str = readline(); // 读取字符串
let key = readline(); // 读取字串
// 例1：str = 'abcdefg' key = 'a?c'
let arr = key.split("?"); // arr = ['a','c']
re = "^"+arr.join(".{1,3}?"); // 拼接出字符串：^a.{1,3}?c
reg = RegExp(re); // 生成正则表达式reg：/^a.{1,3}?c/
const res = reg.exec(str); // 正则匹配，返回匹配到的结果，res是数组形式：["abc"]
console.log(res?res[0].length:-1) // 3
总结：通过子串生成正则表达式，对字符串进行正则匹配，得到匹配结果。
方法二：动态规划解法
第二题：端口号区间合并
输入描述：输入只有一行，即未合并过的端口号。
输出描述：合并端口后输出结果，如果单个端口号可以用区间的形式表示，则优先使用区间；输出结果要按照端口号从小到大排列。
// 输入例子1
6553,1-655,5-1010,1011,1012
// 输出例子1
1-1012,6553
// 输入例子2
5,4,3,2,100,101,103
// 输出例子2
2-5,100-101,103
代码实现：
//端口合并
var input = '6553,1-655,5-1010,1011,1012';
// var input = '5,4,3,2,100,101,103';
var datas = [];
let arr = input.split(',');
// 转成对象数组
// datas = [{6553,6553},{1,655}......]
for (var i = 0; i < arr.length; i++) {
var data = {};
if (arr[i].indexOf('-') !== -1) { // 如果是 1-655 这种情况
let subArr = arr[i].split('-');
data.start = Number(subArr[0]);
data.end = Number(subArr[1]);
datas.push(data);
} else {
data.start = Number(arr[i]);
data.end = Number(arr[i]);
datas.push(data);
}
}
// 对象数组的排序
function compareFunc (prop) {
return function (obj1, obj2) {
var value1 = obj1[prop];
var value2 = obj2[prop];
if (value1 < value2) {
return -1;
} else if (value1 > value2) {
return 1;
} else {
return 0;
}
}
}
datas.sort(compareFunc('start'));
// 区间合并
var temp = null, res = [];
datas.forEach(item => {
if (temp === null || temp.end < item.start - 1) {
res.push(item);
temp = item;
} else if (temp.end < item.end) {
temp.end = item.end;
}
})
// console.log(res);
// 判断输出
for (var i = 0; i < res.length; i++) {
if (i == res.length - 1) {
if (res[i].start == res[i].end) {
console.log(res[i].start);
} else {
console.log(res[i].start + "-" + res[i].end);
}
} else {
if (res[i].start == res[i].end) {
console.log(res[i].start + ",");
} else {
console.log(res[i].start + "-" + res[i].end + ",");
}
}
}
总结
1.往数组中 push 对象，覆盖了之前 push 的值
错误代码：
var data = { start:0, end:0 }
var datas = [];
var arr = [5,4,3,2,100,101,103];
for (var i = 0; i < arr.length; i++) {
data.start = arr[i];
data.end = arr[i];
datas.push(data);
}
原因：把对象定义在外面，始终指向一个地址，每次赋值都赋值给了同一个地址，所以最后赋的值会覆盖之前的值。
改造：把对象定义在循环中，每次循环 datas 都会指向不同的地址，每次都是一个新对象。
var datas = [];
var arr = [5,4,3,2,100,101,103];
for (var i = 0; i < arr.length; i++) {
var data = {};
data.start = arr[i];
data.end = arr[i];
datas.push(data);
}
2.关于 JavaScript 的 sort() 方法
sort()方法可用于将数组进行排序，默认按升序排列数组。
var arr = [1,3,5,9,4];
console.log(arr.sort()); // 输出：[1,3,4,5,9]
这时数据按照从小到大排列，没问题，于是再把数组改成：
var arr = [5,4,3,2,100,101,103];
console.log(arr.sort()); // 输出：[100,101,103,2,3,4,5]
发现和预期的结果不一样。因为sort()方法会调用数组的toString()，然后比较得到的字符串再排序。即使数组中的每一项都是数值，sort() 方法比较的也是字符串。
可通过下面方法打印出数组每一项的 unicode 编码看一下。
let arr = [5,4,3,2,100,101,103];
// 转码方法
function getUnicode (charCode) {
return charCode.charCodeAt(0).toString(16);
}
// 打印转码
arr.forEach(item => {
console.log(getUnicode(String(item)))
});
// 输出：35 34 33 32 31 31 31
解决方法：传入比较函数以指定顺序
sort()方法可以接收一个比较函数作为参数，以便指定哪个值位于哪个值前面。
// 比较函数
function compare (value1, value2) {
if (value1 < value2) {
return -1;
} else if (value1 > value2) {
return 1;
} else {
return 0;
}
}
// 把比较函数传递给 sort() 方法，再对数组进行排序
console.log(arr.sort(compare));
// 输出：[2, 3, 4, 5, 100, 101, 103]
对象数组的排序：
思路：定义一个函数，让它接收一个属性名，然后根据这个属性名来创建一个比较函数并作为返回值返回来。
function compareFunc (prop) {
return function (obj1, obj2) {
var value1 = obj1[prop];
var value2 = obj2[prop];
if (value1 < value2) {
return -1;
} else if (value1 > value2) {
return 1;
} else {
return 0;
}
}
}
var users = [
{name: 'tom', age: 18 },
{name: 'lucy', age: 24 },
{name: 'john', age: 17 }
];
console.log(users.sort(compareFunc('age')));
Java 实现：https://blog.csdn.net/qq_17614297/article/details/78252415