剑指offer(41-53题)题解
41 和为S的连续正数序列
题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
思路： 这题几个要求：大于等于两个序列，正整数，连续。至于对list长度返回的要求直接重写个排序接口即可。
所以这题笔者大概想到2个思路：
方法一：动态穷举试探（较为简单）
这个穷举并不是所谓的暴力遍历，不从每个数都进行循环试起。如果从每个数都试起那么整个进行的次数太多。我们用一个类似拉链的动态滑动试探。我们都知道：连续相加和相等，如果数很小那么就很长，如果数很大就很短。
- 所以我们用
left和right标记左右，用一个value记录这个区间的和。 - 如果value大了那就左面往右试探一位，如果value小了那么right就往右加变长一位。
- 重复上述操作。一直到中间两位长度的截至，记录所有满足题意的条件。
法一的ac的代码为：
import java.util.*;
public class Solution {
public static ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum)
{
ArrayList<ArrayList<Integer> > list=new ArrayList<ArrayList<Integer>>();
int left=1,right=2,value=3;
while(left<=sum/2)
{
if(value==sum)
{
ArrayList<Integer>list1=new ArrayList<Integer>();
for(int i=left;i<=right;i++)
{
list1.add(i);
}
list.add(list1);
value-=left;left++;
}
else if(value>sum)
{
value-=left;left++;
}
else {
right++;value+=right;
}
}
list.sort(compare);
return list;
}
static Comparator<ArrayList<Integer>>compare=new Comparator<ArrayList<Integer>>() {
public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
// TODO Auto-generated method stub
return o2.size()-o1.size();
}
};
}
方法二：数学转化 既然是连续的数字之和。那么请看下面的分析：
/**
* 分析 a + (a+1) --- + b =(a+b) * n/2 =sum 其中n是a-b的个数
* (a+b) * (b-a+1)=sum * 2
* 令a+b=m a=a b=m-a
* m*(m-2a+1)=sum * 2
* 利用求sum * 2 的因数遍历m 求出a,b若a大于0、且不为小数、a!=b即为一个序列
*/
大致分析是这样的：
- 首先连续相加是可以转化成乘法的(有时间可以了解唯一分解定理)
- 然后比如 sum * 2 =a * b 可能其中a是平均数，也可能b是平均数。但是你需要考虑所有和都大于0. 且为整数。
- 比如 求和为15.右
[1, 2, 3, 4, 5], [4, 5, 6], [7, 8]三组数据。而求和分别为((1+5)/2)5=15`=>`65=30,((4+6)/2)3=15`=>`103=30,((7+8)/2)2=15`=>`152=30.其实你就是需要将所有a*b=30所有情况列举，然后看看能否复原成功。复原公式在上面的。并且其中a,b需要换位考虑能否成功的。当然求因数的一些技巧不需要详细讲述了，只需要遍历根号(n)+1即可。
具体代码为：
import java.util.*;
public class Solution {
public static ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
int value=sum*2;
ArrayList<ArrayList<Integer> > list=new ArrayList<ArrayList<Integer>>();
int a=0,b=0;
for(int i=1;i*i<value+1;i++)
{
if(value%i==0)
{
a=(i+1-value/i)/2;b=i-a;
if(a>0&&i-a*2+1==value/i&&b>a)
{
ArrayList<Integer>list2=new ArrayList<Integer>();
for(int j=a;j<=b;j++)
{
list2.add(j);
}
list.add(list2);
}
a=(value/i+1-i)/2;b=value/i-a;
if(a>0&&value/i-a*2+1==i&&b>a)
{
ArrayList<Integer>list2=new ArrayList<Integer>();
for(int j=a;j<=b;j++)
{
list2.add(j);
}
list.add(list2);
}
}
}
list.sort(compare);
return list;
}
static Comparator<ArrayList<Integer>>compare=new Comparator<ArrayList<Integer>>() {
public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
// TODO Auto-generated method stub
return o2.size()-o1.size();
}
};
}
42 和为S的两个数字
题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述
对应每个测试案例，输出两个数，小的先输出。 思路： 这题和上一题的方案一思想差不多。用个左右标记位置。从两边向中间逼近。两个数相加如果大于目标，那么最右侧位置right往左移动一下，如果小于目标，左侧的left向右移动增加，当出现第一个满足条件的即可停止。因为要求
乘积最小嘛。
实现代码为：
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
int small=0,big=0;//小大两个数
int l=0, r=array.length-1;
while(l<r)
{
if(array[l]+array[r]==sum)
{
small=array[l];big=array[r];
break;
}
else if (array[l]+array[r]<sum) {
l++;
}
else if (array[l]+array[r]>sum) {
r--;
}
}
ArrayList<Integer>list=new ArrayList<Integer>();
if(small==big)return list;
list.add(small);
list.add(big);
return list;
}
}
43 左旋转字符串
题目描述
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
思路： 可以看似循环链表类似的问题。但是直接求就好了。因为只旋转一次，相当于把前面一部分挪到后面就可以了。要考虑旋转的长度是否大于整个字符串的长度。
实现代码：
public class Solution {
public String LeftRotateString(String str,int n) {
if(str.equals(""))return str;
n=n%str.length();
return str.substring(n)+str.substring(0,n);
}
}
44 翻转单词顺序列
题目描述
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
思路：
经典字符串处理题。字符串问题就是有很多坑点、边界问题、特殊情况等等。要考虑空串、一个单词等等情况。当然，具体处理就是字符一个个读取，遇到空格的时候特殊处理一下。处理方式可能不唯一。也可以考虑字符串分割等等。
实现代码为：
public class Solution {
public static String ReverseSentence(String str) {
String value="";
StringBuilder sBuilder=new StringBuilder();
for(int i=0;i<str.length();i++)
{
if(str.charAt(i)!=' ')
{
sBuilder.append(str.charAt(i));
}
else {
value=sBuilder.toString()+" "+value;
sBuilder=new StringBuilder();
}
}
if(sBuilder.length()>0)
{
value=sBuilder.toString()+" " +value;
value=value.substring(0,value.length()-1);
}
return value;
}
}
45 扑克牌顺序
题目描述
LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
思路：
首先要理清楚题意。就是给你五张牌让你判断是不是顺子，然而这五张可能有若干张鬼(0)可以随意的陪。这也有点小贪心的思想的。我们的处理思路事这样的：
- 先给五张牌进行排序。然后前面用个数值记录有几个鬼。
- 然后从非鬼开始判断是否连续，如果和前一个不连续
如果有鬼用鬼前一个数往后补一张一直到连续，如果没鬼了还不连续那就说明那是真的完成不了。 - 如果最后未能遍历所有牌。或者有相同牌(非鬼)那么一定不是顺子。
实现代码为：
import java.util.Arrays;
public class Solution {
public static boolean isContinuous(int [] numbers) {
if(numbers.length<5)return false;
Arrays.sort(numbers);
System.out.println(Arrays.toString(numbers));
int wang=0;
int pre=0;
for(int i=0;i<5;i++)
{
if(numbers[i]==0)wang++;
else {
if(pre==0) {pre=numbers[i];}//第一个数
else if(numbers[i]==pre) {return false;}//相同牌
else if(numbers[i]==pre+1) {pre++;}
else {
while(numbers[i]>pre+1)
{
if(wang>0){wang--;pre++;}
else if(wang<=0) {return false;}
}
pre++;
}
}
}
return true;
}
}
46 孩子们的游戏
题目描述
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1) 如果没有小朋友，请返回-1
思路： 经典约瑟夫环问题。可用链表进行模拟，也可用List借助数学方法一个个移出效率会高一些。笔者这里用了个链表过了。后面用数学模拟链表的方法效率更高，大过年的先不写了，后面会补的！
实现代码为：
public class Solution {
static class node
{
int val;
public node(int value) {
this.val=value;
}
node next;
}
public static int LastRemaining_Solution(int n, int m) {
if(n<=0||m<2)return -1;
node head=new node(0);
node team=head;
for(int i=1;i<n;i++)
{
team.next=new node(i);
team=team.next;
}
team.next=head;
int index=0;
while (head.next!=head) {
if(index==m-2)
{
head.next=head.next.next;
index=0;
}
else {
index++;
}
head=head.next;
}
return head.val;
}
}
至于笔者最初写的效率并不高。至于数学模拟，笔者最初记得还是分类讨论的：是否越界之类。而可以直接加上一段size长度求余相当于接上那么一段！
在这里插入图片描述
47 求1+2+。。。+n
题目描述
求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
思路：
这个真的没想到，看了下评论区的方法真的是恍然大悟。虽然我们不能用逻辑语句实现我们的逻辑，但是我们可以用&&之类的运算符帮助我们实现逻辑。a&&b这个逻辑当a是false的时候后面就不会执行了。这就是逻辑与的短路特性。我们调用递归或者其他方法借助逻辑与的短路特性就可以实现停止了。
实现代码为：
public class Solution {
public int Sum_Solution(int n) {
boolean jud= (n>0)&&((n+= Sum_Solution(n-1))>0);
return n;
}
}
参考评论区：
对于评论区还有一些其他方法也挺精妙，但是可能自己很难有那么高认识，先了解吧。
48 不用加减乘除做加法★
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
思路： 这个我以前就知道跟二进制有关，知道有这个东西不过没仔细研究。我觉得这题大家可以自己独立研究一下。能够加深对二进制和位运算的印象和认识。
当然，做这题前，建议稍微了解下四种常用的位运算与或非 异或。
对于二进制的运算：0+0=0，0+1=1,1+1=0(进位)
对于加法的一个二进制运算。如果不进位那么就是非常容易的。这时候相同位都为0则为0，0和1则为1.满足这种运算的异或(不相同取1，相同取0)和或(有一个1则为1)都能满足.
但事实那像这么容易？肯定有进位的运算啊！对于进位的两数相加，这种核心思想为：
- 用两个数，一个正常m相加(不考虑进位的)。用
异或a^b就是满足这种要求，先不考虑进位(如果没进位那么就是最终结果)。 - 另一个专门考虑进位的n。两个1需要进位。所以我们用
a&b与记录需要进位的。但是还有个问题，进位的要往上面进位，所以就变成这个需要进位的数左移一位。 - 然后就变成m+n重新开始上面直到不需要进位的(会停止的，不可能一直进位)。
在这里插入图片描述
实现代码为：
public class Solution {
public int Add(int num1,int num2) {
/*
* 5+3 5^3 5&3
* 0101 0110 0001
* 0011
*/
int a=num1^num2;
int b=num1&num2;
b=b<<1;
if(b==0)return a;
else {
return Add(a, b);
}
}
}
49 把字符串转换成整数
题目描述
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0
输入描述:
输入一个字符串,包括数字字母符号,可以为空 输出描述: 如果是合法的数值表达则返回该数字，否则返回0 示例1
输入
+2147483647 1a33
输出
2147483647 0
思路：
这题是个麻烦题，主要是有几个越界的字符串需要处理。你又不能使用api，建议你使用long型转换成功判断是否越界可能更方便些。但是笔者挑战了下自己用int型硬刚过的。
你要考虑正负(整数最小和负数最大)，需要考虑是否为非法字符串。数值是否操作越界(尤其注重int类型最大最小附近)。
我的处理思路这样的：记录正负，每次都进行加操作，记录操作前数值，如果操作后符号变化那就越界直接返回0。否则进行到最后返回。
实现代码为：
public class Solution {
public static int StrToInt(String str) {
if(str.equals(""))return 0;
int check = 0;//判断首位是不是符号
int zhengfu = 1;//正负号用1和-1表示
if (str.charAt(0) == '+' || str.charAt(0) == '-')// 符号位判断下
{
check=1;
zhengfu=str.charAt(0)=='+'?1:-1;
}
int index = check == 0 ? 0 : 1;// 初始位置
int value = 0;
int team=zhengfu;
for (; index < str.length(); index++) {
if (str.charAt(index) >= '0' && str.charAt(index) <= '9') {
value = value * 10 + (str.charAt(index) - '0')*zhengfu;
if(value/team<0)return 0;
team=value;
//System.out.println(value+" "+zhengfu);
} else {
return 0;
}
}
return value;
}
}
50 数组中重复的数字
题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
思路： 因为数组中的数范围已经确定了，也不大，不需要用hashmap。直接用一个数组即可。遍历一个加一个，这个位置的数为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) {
int count[]=new int[length+1];
for(int i=0;i<length;i++)
{
if(++count[numbers[i]]>1)
{
duplication[0]=numbers[i];
return true;
}
}
return false;
}
}
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]。不能使用除法。
思路：
这题刚开始还没想到，刚开始还想着用啥位运算？刚开始想着怎么用总数变成对应的数，但是人家要求不能用除法。得用乘法。(不要按照公式每个每个的死算，这样太低效)。其实把上面等式右侧看成两部分就行了。A[0]*A[1]*...*A[i-1]和A[i+1]*...*A[n-1]。
在具体处理上，我们使用两个数组，一个数组leftmut[]记录从左向右的叠乘，一个数组rightmut[]记录从右向左的叠乘。这样正常情况下每个位置的B[i]就变成了leftmut[i-1]*rightmut[i+1].当然，特殊情况和边界需要特殊考虑下！
实现代码为：
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
//特殊情况暂不考虑
int len=A.length;
int B[]=new int[len];
if(len<2)return B;
int leftmut[]=new int [len];
int rightmut[]=new int [len];
leftmut[0]=A[0];
rightmut[len-1]=A[len-1];
for(int i=1;i<len;i++)
{
leftmut[i]=A[i]*leftmut[i-1];//从左向右递乘法
rightmut[len-1-i]=A[len-1-i]*rightmut[len-i];//从右向左递乘法
}
B[0]=rightmut[1];
B[len-1]=leftmut[len-2];
for(int i=1;i<len-1;i++)
{
B[i]=leftmut[i-1]*rightmut[i+1];
}
return B;
}
}
52 正则表达式匹配
题目描述
请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
思路： 这题后面要优化，感觉我写的逻辑太乱了。本来想能不能先把非符号去掉。。能不能dp。。想不出来。进了讨论区瞅了眼发现递归妙用。
遇到相同的或者.就往下递归匹配。遇到x*就分类讨论看看pattern能不能前进(2位)，str能不能前进。把所有可能都递归下去(有真就行)。但是感觉这样效率真的不高啊。。。虽然过了。后面代码和逻辑都要优化。
实现代码：
import java.util.Arrays;
public class Solution {
public static boolean match(char[] str, char[] pattern)
{
if(str.length==0)//匹配串为0
{
if(pattern.length==0)return true;
else {
if(pattern.length%2==1)return false;
else {
for(int i=1;i<pattern.length;i++)
if(pattern[i]!='*')return false;
return true;
}
}
}
else if (pattern.length==0) {//匹配串为0，肯定不行
return false;
}
else {
if(pattern.length==1)
{
if(pattern[0]==str[0]||pattern[0]=='.')
{
if(str.length==1)
return true;
}
return false;
}
else {
if(pattern[1]=='*')
{
if(pattern[0]=='.')
{
return match(Arrays.copyOfRange(str, 1, str.length),pattern)||match(str, Arrays.copyOfRange(pattern, 2, pattern.length));
}
if(pattern[0]==str[0])
{
return match(Arrays.copyOfRange(str, 1, str.length), pattern)||match(Arrays.copyOfRange(str, 1, str.length), Arrays.copyOfRange(pattern, 2, pattern.length))||match(str, Arrays.copyOfRange(pattern, 2, pattern.length));
}
else {
return match(str, Arrays.copyOfRange(pattern, 2, pattern.length));
}
}
else {
if (pattern[0]==str[0]||pattern[0]=='.') {
return match(Arrays.copyOfRange(str, 1, str.length), Arrays.copyOfRange(pattern, 1, pattern.length));
}
else {
return false;
}
}
}
}
}
}
参考讨论区
讨论区的比萨大叔讲的挺好的，另外就是我这里事用数组拷贝来比较，而他用数组指标代替其实效率更高的。空间可以重复利用，并且数组复制占用太多空间还是递归的！！可以参考下！
链接：https://www.nowcoder.com/questionTerminal/45327ae22b7b413ea21df13ee7d6429c?f=discussion
来源：牛客网
public class Solution {
public boolean match(char[] str, char[] pattern) {
if (str == null || pattern == null) {
return false;
}
int strIndex = 0;
int patternIndex = 0;
return matchCore(str, strIndex, pattern, patternIndex);
}
public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
//有效性检验：str到尾，pattern到尾，匹配成功
if (strIndex == str.length && patternIndex == pattern.length) {
return true;
}
//pattern先到尾，匹配失败
if (strIndex != str.length && patternIndex == pattern.length) {
return false;
}
//模式第2个是*，且字符串第1个跟模式第1个匹配,分3种匹配模式；如不匹配，模式后移2位
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);
}
}
//模式第2个不是*，且字符串第1个跟模式第1个匹配，则都后移1位，否则直接返回false
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) {
return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
}
return false;
}
}
53 表示数值的字符串
题目描述
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
思路： 经典字符串处理题！字符串问题其实还是比较麻烦的。因为可能会有很多纰漏，需要考虑点比较多。这题需要考虑的点大致有：
- 最多有两个独立数字 e(E)前面可为小数或者整数，而后面只能为整数
- 正负号只能在独生数字开始
- 除了数字、
+-.Ee其他字符均非法 - 只有前面有小数点。注意e(E)前后不能为空(小数点也是只不过这题数据较弱没写也过了可以自己添上)
逻辑实现上，可以用一些int类似数组标记独立数字，小数点数字长度啥的。然后对字符串进行各个分类讨论，判断各个符号出现次数，是否合法等等。详细可以参考代码：
//数据比较弱。12.e+4 12. 这类需要特殊判断
public static boolean isNumeric(char[] str) {
boolean smallpoint=false;//小数点
boolean ise=false;//是否遇到e
int localindex=0;//当前数字指标
for(int i=0;i<str.length;i++)
{
if(localindex==0&&(str[i]=='+'||str[i]=='-'))
{
localindex++;continue;
}
else if (str[i]=='.'&&localindex>0) {
if(smallpoint||ise)//当有小数点或者在e后面
return false;
else {
smallpoint=true;
}
}
else if ((str[i]=='e'||str[i]=='E')&&localindex>0) {
if(ise)return false;
else {
ise=true;localindex=0;
}
}
else if (str[i]>='0'&&str[i]<='9') {
localindex++;
}
else {
return false;
}
}
if (localindex>0) {
return true;
}
else
return false;
}
腾讯云开发者
