算法学习之剑指offer（九）
2024-09-01 12:16:21
一
题目描述
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
public class Solution {
public int Sum_Solution(int n) {
int sum=n;
boolean re = (n>0)&&((sum+=Sum_Solution(n-1))>0);
return sum;
}
}二
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
import java.math.BigInteger;
public class Solution {
public int Add(int num1,int num2) {
BigInteger a = new BigInteger (num1+"");
BigInteger b = new BigInteger (num2+"");
return a.add(b).intValue();
}
}三
题目描述
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
输入描述:
输入一个字符串,包括数字字母符号,可以为空
输出描述:
如果是合法的数值表达则返回该数字，否则返回0
示例1
输入
+2147483647
1a33
输出
2147483647
0
public class Solution {
public int StrToInt(String str) {
if (str.equals("") || str.length() == 0)
return 0;
char[] chars = str.toCharArray();
int sum=0,fuhao=0,length=chars.length;
if(chars[fuhao]=='-')
fuhao=1;
for(int i=fuhao;i<length;i++){
if (chars[i] == '+')
continue;
if (chars[i] < 48 || chars[i] > 57)
return 0;
sum = sum*10+chars[i]-48;
}
return fuhao==0?sum:sum*-1;
}
}四
题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个，赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(numbers==null||numbers.length==0)
return false;
int[] new_numbers = new int[length];
for(int i=0;i<length;i++){
new_numbers[numbers[i]]++;
}
for(int i=0;i<length;i++){
if(new_numbers[i]>1){
duplication[0]=i;
return true;
}
}
return false;
}
}五
题目描述
给定一个数组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[] multiply(int[] A) {
//弄一个矩阵，矩阵里的1代表多余的数，然后分两部分算。每部分的每一行都可以借助上一行
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 tmp=1;
for(int i=length-2;i>=0;i--){
tmp*=A[i+1];
B[i]*=tmp;
}
}
return B;
}
}六
题目描述
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
public class Solution {
public boolean match(char[] str, char[] pattern) {
if (str == null || pattern == null) {
return false;
}
return matchCore(str, 0, pattern, 0);
}
public boolean matchCore(char[] str, int strIndex, char[] pattern, 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] == '*') {
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) {
return matchCore(str, strIndex, pattern, patternIndex + 2)//模式后移2，视为x*匹配0个字符
|| matchCore(str, strIndex + 1, pattern, patternIndex + 2)//视为模式匹配1个字符
|| matchCore(str, strIndex + 1, pattern, patternIndex);//*匹配1个，再匹配str中的下一个
} else {
return matchCore(str, strIndex, pattern, patternIndex + 2);
}
}
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) {
return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
}
return false;
}
/**第二种方法
// .* 匹配一切
if(pattern.length == 2
&& pattern[0] == '.'
&& pattern[1] == '*') return true;
// 两个序列入栈
Stack<Character> ori = new Stack<>();
Stack<Character> pat = new Stack<>();
for (int i = 0; i < str.length; i++) {
ori.push(str[i]);
}
for (int i = 0; i < pattern.length; i++) {
pat.push(pattern[i]);
}
// 从尾匹配，解决*重复前一个字符的问题
while (!ori.empty() && !pat.empty()){
// 如果是两个不相同的字母，匹配失败
if(Character.isLetter(pat.peek())
&& !pat.peek().equals(ori.peek()))
return false;
// 两个相同的字母，匹配成功，两个栈顶各弹出已经匹配的字符
if(Character.isLetter(pat.peek())
&& pat.peek().equals(ori.peek())){
ori.pop();
pat.pop();
}else if(pat.peek().equals('.')){ // 如果模式串是 ‘.’，直接把它替换为所需的字符入栈
pat.pop();
pat.push(ori.peek());
}else{ // 模式串是 *
pat.pop();
if(pat.peek().equals(ori.peek())){ // *的下一个是目标字符，则重复它再重新压入*
pat.push(ori.peek());
pat.push('*');
ori.pop();
}else{ // 否则从模式栈弹栈，直到找到匹配目标串的字符，或遇到.
while (!pat.empty()
&& !pat.peek().equals(ori.peek())
&& !pat.peek().equals('.')) pat.pop();
// 如果遇到了‘.’ 直接替换为目标字符，再重新压入*
if(!pat.empty() && pat.peek() == '.'){
pat.pop();
pat.push(ori.peek());
pat.push('*');
}
}
}
}
// 两栈空，则匹配成功
if(ori.empty() && pat.empty()) return true;
// 如果模式栈不空
// 仅当模式栈中的*可以‘吃掉’多余的字符时匹配成功
// 例如 aa* / aa*bb* ,而不可以是baa*
if(ori.empty() && !pat.empty()
&& pat.peek().equals('*')){
char c = pat.pop();
while (!pat.empty()){
if(c == '*'
|| pat.peek() == '*'
|| c == pat.peek())
c = pat.pop();
else return false;
}
return true;
}
// 其他情况均不成功
return false;
**/
}最新文章
- EF MYSQL 不能选择实体框架版本
- VBA常用函数
- Biee 迁移和刷新GUIDs
- mysql中模糊查询的四种用法介绍
- Weka回归
- 用Express搭建 blog (一)
- removeCss
- hdu 4739 Zhuge Liang's Mines (简单dfs)
- TCP/IP三次握手，四次断开
- 驱动调试-根据oops定位错误代码行
- Mdoelsim10.4怎么脚本单独仿真ISE14.7 IP核
- SAP中的一些简称及简要介绍
- js中的arguments用法
- Light OJ 1007
- python_day4
- JAVA中MAP转LIST
- vue组件通信方式总结
- 自定义NSOperation下载图片
- spring---transaction（1）---源代码分析(事务的拦截器TransactionInterceptor)
- idea 设置黑色背景