强烈推荐
51.构建乘积数组

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]。不能使用除法。
import java.util.ArrayList;
public class Solution {
//暴力解决
public int[] multiply1(int[] A) {
int[] B = new int[A.length];
for(int i = 0; i < A.length; i++){
int temp = 1;
for(int j = 0; j < B.length; j++){
if(i != j){
temp *= A[j];
}
}
B[i] = temp;
}
return B;
}
//剑指offer上算法思想,时间复杂度O(n)
public int[] multiply(int[] A){
int length = A.length;
int[] B = new int[length];
if(length != 0 ){
B[0] = 1;
//计算下三角连乘
for(int i = 1; i < length; i++){
B[i] = B[i-1] * A[i-1];
}
int temp = 1;
//计算上三角
for(int j = length-2; j >= 0; j--){
temp *= A[j+1];
B[j] *= temp;
}
}
return B;
}
}
作者:Jason分类:【offer】浏览(308)评论(0)
52.正则表达式匹配

52.正则表达式匹配
题目描述
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配
public class Solution {
//剑指offer书上算法思想
public boolean match(char[] str, char[] pattern)
{
if(str.length <= 0 && pattern.length <= 0)
return true;
return matchCore(str,pattern,0, 0);
}
public static boolean matchCore(char[] str, char[] pattern, int s, int p){
if(s == str.length && p == pattern.length)
return true;
if(s != str.length && p == pattern.length)
return false;
//处理遇到*的情况
if(p + 1 < pattern.length && pattern[p + 1] == '*'){
if((s != str.length && pattern[p] == str[s]) || (pattern[p] == '.' && s != str.length)){
return matchCore(str, pattern, s, p + 2)//相当于*匹配零个,模式串上移动两个
|| matchCore(str, pattern, s + 1, p);//字符串上移动一个,模式上保持不变
}else{
return matchCore(str, pattern, s, p + 2);
}
}
//两个字符相等,或者匹配.
if((s != str.length && pattern[p] == str[s]) || (pattern[p] == '.' && s != str.length))
return matchCore(str, pattern, s + 1, p + 1);
return false;
}
//投机取巧法
public boolean match2(char[] str, char[] pattern){
String regex = String.valueOf(pattern);
String s = String.valueOf(str);
return s.matches(regex);
}
}
作者:Jason分类:【offer】浏览(304)评论(0)
44.翻转单词顺序列

44.翻转单词顺序列
题目描述
牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?
public class Solution {
//利用java中String函数,简单明了
public String ReverseSentence1(String str) {
if(str.trim().isEmpty())
return str;
String[] temp = str.split(" ");
String res = "";
int i = temp.length - 1;
for(; i > 0; i--){
res = res + temp[i] + " ";
}
return res + temp[0];
}
//利用剑指offer上思想,两次反转字符串
public String ReverseSentence(String str) {
if(str.trim().isEmpty())
return str;
char[] c = str.toCharArray();
Reverse(c, 0, c.length - 1);
int pBegin = 0, pEnd = 0;
while(pBegin < c.length){
if(c[pBegin] == ' '){
pBegin++;
pEnd++;
}else if(c[pEnd] == ' '){
Reverse(c, pBegin, pEnd - 1);
pBegin = ++pEnd;
}else if(pEnd == c.length - 1){
Reverse(c, pBegin, pEnd);
pBegin = ++pEnd;
}else
pEnd++;
}
return String.valueOf(c);
}
public static void Reverse(char[] c, int begin, int end){
if(begin >= end)
return;
while(begin < end){
char temp = c[begin];
c[begin] = c[end];
c[end] = temp;
begin++;
end--;
}
}
}
作者:Jason分类:【offer】浏览(288)评论(0)