第51题：构建乘积数组
难易度：⭐⭐
题目描述:
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1]。
其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。
要求：不能使用乘法
注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];
题目分析：
我想很多人肯定会写出这样的代码：
public class Solution {
public int[] multiply(int[] A) {
int[] B = new int[A.length];
for(int i = 0;i < B.length;i++){
B[i] = getBOfIndexI(A,i);
}
return B;
}
public static int getBOfIndexI(int[] A,int i){
int res = 1;
for(int j = 0;j < A.length;j++){
if(j == i){
continue;
}
res *= A[j];
}
return res;
}
}
这样的话，这个算法的时间复杂度就变成了O(n ^ 2),是否有更快的算法呢？
《剑指offer》本书中的思路是这样的：
将求解数组B转换为一个矩阵，可以看出B0到Bn-1的值实际上是矩阵每一个行对应的成绩，自然而然地，我们可以将矩阵划分为上倒三角和下三角形
下三角符合的范围为 index 从1到n-1 依次递增
满足：
B[i] = B[i - 1] * A[i - 1];上倒三角复合的范围为，从下到下，index n-2 到 0 依次递减
满足：
temp = 1;B[i] = temp * A[i + 1];temp = B[i];代码如下：
public class Solution {
public int[] multiply(int[] A) {
if(A == null){
return null;
}
int[] B = new int[A.length];
if(A.length > 1){
B[0] = 1;
for(int i = 1;i < A.length;i++){
B[i] = B[i - 1] * A[i - 1];
}
int temp = 1;
for(int i = A.length - 2;i >=0;i--){
temp *= A[i + 1];
B[i] *= temp;
}
}
return B;
}
}
只要把矩阵画出来，那么代码逻辑其实并不复杂。
第52题：正则表达式匹配
难易度：⭐⭐⭐⭐
请实现一个函数用来匹配包括'.'和'*'的正则表达式。
模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
题目解析：
本题是一道我觉得难度比较大的题目，重点是要看pattern的下一个字符是否为' * '
当pattern中的第二个字符是' * '的时候
如果pattern[patternIndex] == str[strIndex] 或者是pattern[patternIndex] == ' . '时
有如下几种情况：
- pattern向后移动两个字符
- 字符串向后移动一个字符，pattern向后移动2个字符
- 字符串向后移动一个字符，pattern不动
否则 pattern向后移动两个字符，有可能完成匹配
当pattern中的第二个字符不是 ' * '时，只有满足pattern[patternIndex] == str[strIndex] 或者是pattern[patternIndex] == ' . '时，字符串和pattern同时向后移动1个字符可能完成匹配的情况
代码如下：
public class Solution {
public boolean match(char[] str, char[] pattern){
if(str == null || pattern == null){
return false;
}
return process(str,pattern,0,0);
}
public static boolean process(char[] str,char[] pattern,int strIndex,int patternIndex){
if(strIndex == str.length && patternIndex == pattern.length){
return true;
}
if(strIndex != str.length && patternIndex == pattern.length){
return false;
}
// 模式的下一个字符是'*'
if(patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*'){
// 当前的pattern和str的字符匹配时，即：pattern[patternIndex] == str[strIndex] || pattern[patternIndex] == '.'
if(strIndex < str.length && pattern[patternIndex] == str[strIndex] || strIndex < str.length && pattern[patternIndex] == '.'){
return process(str,pattern,strIndex + 1,patternIndex)
|| process(str,pattern,strIndex,patternIndex + 2)
|| process(str,pattern,strIndex + 1,patternIndex + 2);
}else{
return process(str,pattern,strIndex,patternIndex + 2);
}
}
if(strIndex < str.length && pattern[patternIndex] == str[strIndex] || strIndex < str.length && pattern[patternIndex] == '.' ){
return process(str,pattern,strIndex + 1,patternIndex + 1);
}
return false;
}
}
第53题：表示数值的字符串
难易度：⭐⭐⭐
题目描述:
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。
但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
解析：
又是一道憋了半天没想出来的题目
看了原书的解析，可以将数字的格式用如下的形式表示
A[.[B]][e|EC]或者.B[e|EC]来表示
其中A和C都是整数可以带有正负号，而B则是一个无符号的整数
代码如下：
public class Solution {
private int index = 0;
public boolean isNumeric(char[] str) {
boolean res = scanInteger(str);
if(index < str.length && str[index] == '.'){
index++;
res = scanUnsignedInteger(str) || res;
}
if(index < str.length && (str[index] == 'e' || str[index] == 'E')){
index++;
res = res && scanInteger(str);
}
return res && index == str.length;
}
private boolean scanInteger(char[] str){
if(index < str.length && (str[index] == '+' || str[index] == '-')){
index++;
}
return scanUnsignedInteger(str);
}
private boolean scanUnsignedInteger(char[] str){
int before = index;
while(index < str.length && str[index] <= '9' && str[index] >= '0'){
index++;
}
return index > before;
}
}
值得一提的是第一次我提交的代码中
或运算的顺序写反了，这个是一个很容易踩到坑的地方，因为断路特性，所以应该将scanUnsignedInteger(str)写到前面，说到底还是对代码的理解程度不够，二刷的时候一定好好把这道题写上个几百遍(吹牛逼的)
第54题：字符流中第一个不重复的字符
难易度：⭐
题目描述:
请实现一个函数用来找出字符流中第一个只出现一次的字符。
例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。
当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
如果当前字符流没有存在出现一次的字符，返回#字符。
本题的思路应该很快就能想到使用哈希表这种数据结构
代码如下：
import java.util.HashMap;
import java.util.Map.Entry;
public class Solution {
private int index = 0;
private HashMap<Character,Integer> map = new HashMap<>();
//Insert one char from stringstream
public void Insert(char ch)
{
if(map.containsKey(ch)){
map.put(ch,-1);
}else{
map.put(ch,index++);
}
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce(){
char res = '#';
int minIndex = Integer.MAX_VALUE;
for(Entry<Character,Integer> entry : map.entrySet()){
if(entry.getValue() != -1 && entry.getValue() < minIndex){
minIndex = entry.getValue();
res = entry.getKey();
}
}
return res;
}
}
网友评论