剑指offer｜41-50题解题思路及代码(Java版)
剑指offer41到50题总览：
- 和为S的连续正数序列
- 和为S的两个数字
- 左旋转字符串
- 反转单词顺序列
- 扑克牌顺子
- 孩子们的游戏(圆圈中最后留下的数)
- 求1+2+3+...+n
- 不用加减乘除做加法
- 把字符串转换成整数
- 数组中重复的数组
41、和为S的连续正数序列
题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。
解题思路
一种方法是硬性计算，如sum=100，则从50个数的和开始，如果是50个数的和，那么这50个数应该是那些连续的数，如果找不到则找49个数的和。直到发现8个数可以，100/8=12，100%8=4，则这8个数的第8/2=4个数应该是12，第8个数应该是16，并且这8个数都为正数，符合要求。
另一种方法是双指针技术，就是相当于有一个窗口，窗口的左右两边就是两个指针，我们根据窗口内值之和来确定窗口的位置和宽度。通过等差数列的计算公式计算窗口内数的和，如果和<sum，则high++；如果和>sum，则low++；如果和=sum，则将窗口内的数加入list，high++，再去寻找别的窗口。
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> final_list = new ArrayList<>();
int low = 1;//窗口左边界
int high = 2;//窗口右边界
while(low < high){
int n = (low+high)*(high-low+1)/2;//计算窗口内数的和
if(n == sum){//和等于sum，将窗口内的数加入list
ArrayList<Integer> list = new ArrayList<>();
for(int i=low; i<=high; i++) {
list.add(i);
}
final_list.add(list);
low++;//继续寻找新窗口，右边界high++;
}else if(n < sum){high++;}//窗口内数的和小于sum，则high++;
else{low++;}//窗口内数的和大于sum，则low++;
}
return final_list;
}
}
42、和为S的两个数字
题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。
解题思路
如果有多组数和为S，则乘积最小的一定是两个数的差值较大的那一组。设置两个指针，一个左指针i，一个右指针j，第一个得到的和为S的一组一定是乘积最小的一组。我们对左指针和右指针所指的数的和进行判断，如果和<sum，则i++；如果和>sum，则j++；如果和=sum，则返回i和i所指向的一组数。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> list = new ArrayList<>();
int i = 0;//左指针，只能右移
int j = array.length-1;//右指针，只能左移
while(i <= j){
if(array[i] + array[j] == sum){//找到了第一个和为sum的一组数
list.add(array[i]);
list.add(array[j]);
break;
}else if (array[i] + array[j] > sum){//和>sum，则右指针左移，让和小一点
--j;
}else{//和<sum，则左指针右移，让和大一点
++i;
}
}
return list;
}
}
43、左旋转字符串
题目描述
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
解题思路
方法很多，可以将两个abcXYZdef连起来，形成abcXYZdefabcXYZdef，再取从n开始的，与原来的字符串一样长的子串。也可以将abcXYZdef分割成两个子串abc和XYZdef，再反向连接成XYZdefabc。
注意事项
- n可能大于str.length。
public class Solution {
public String LeftRotateString(String str,int n) {
if(str.length() == 0 || str.length() == 1){
return str;
}else{
n = n%str.length();//n可能大于str的长度
String back = str.substring(n); //提取子串的后半部分
String front = str.substring(0,n);//提取子串的前半部分
return back+front;//将后半部分提前，连接两个子串
}
}
}
44、反转单词顺序列
题目描述
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
解题思路
方法很多，一种方法是将串split，然后反向连接或用栈；一种方法是先将每个单词反转，再将整个串反转。也可以先整个串反转，再每个单词反转。
注意事项
- 用例中有输入字符串为空格的情况。
public class Solution {
public String ReverseSentence(String str) {
if(str.length()<=1 || str.trim().equals("")){return str;}
char[] chars = str.toCharArray();
int pre_i=0;//上一个空格的下标
int i = 0;//i用来寻找空格，遇到空格则将[pre_i, i-1]之间的字符反转
while(i<chars.length){
if(chars[i] == ' '){//找到空格
reverse(chars, pre_i, i-1);//将[pre_i, i-1]之间的字符反转
while(chars[i] == ' '){//这里其实不用循环只i++也可以，为了防止有多个空格，用了循环。用例中没有多个空格的情况。
i++;
}
pre_i = i;//更新上一个空格的下标
}else{
i++;
}
}
reverse(chars, pre_i, i-1);//i=str.length但最后一个单词还没有反转，反转最后一个单词
reverse(chars, 0, chars.length-1);//将整个串反转
return new String(chars);将char数组转化为String
}
public void reverse(char[] chars, int start, int end){
char temp;
while(start < end){//将头尾指针指向的字符进行交换
temp = chars[start];
chars[start] = chars[end];
chars[end] = temp;
start++;//头指针+1
end--;//尾指针-1
}
}
}
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的个数，并将其他数排序，计算空档的数量，如果0的个数不够填补空档，则返回false。
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public boolean isContinuous(int [] numbers) {
if(numbers.length!=5){return false;}
int count_0 = 0;//计算0的个数
int vacancy = 0;//计算空档的个数
ArrayList<Integer> list = new ArrayList<>();
for(int i=0; i<numbers.length; i++){
if(numbers[i] != 0){//将非0数加入list
list.add(numbers[i]);
}else{//计算0的个数
++count_0;
}
}
Collections.sort(list);//对非零数进行排序
for(int i=1; i<list.size(); i++){//对list中的数遍历，计算空档的个数
if(list.get(i)-list.get(i-1) > 1){//有空档，计算有几个空档
vacancy += list.get(i) - list.get(i-1)-1;
}else if(list.get(i)-list.get(i-1) == 0){//如果出现对子，即相同数，则一定不是顺子，返回false
return false;
}
}
if(vacancy>count_0){return false;}
else{return true;}
}
}
46、孩子们的游戏(圆圈中最后留下的数)
题目描述
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
解题思路
约瑟夫环问题。如果用数组，则注意判断是否已经出列。用java的ArrayList可以，考虑到频繁删除，可用LinkedList。
import java.util.LinkedList;
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(n == 0){return -1;}
if(n == 1){return 0;}
LinkedList<Integer> list = new LinkedList<>();
for(int i=0; i<n; i++){//所有数入LinkedList
list.add(i);
}
int current_index = 0;//当前下标
while(list.size()>1){
current_index = (current_index + m -1) % list.size();//每次current_index指向的小朋友就是喊0的小朋友，所以最后一个小朋友只需往后走m-1步。
list.remove(current_index);//删除喊m-1的小朋友
}
return(list.get(0));//返回最后的一个小朋友的下标
}
}
47、求1+2+3+...+n
题目描述
求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 flag = (sum>1) && ((sum += Sum_Solution(n-1)) > 0);//递归计算，这里有人写的是sum>0，计算结果是一样的。
return sum;
}
}
48、不用加减乘除做加法
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
解题思路
此题就是需要我们用位运算实现加法。主要用到与运算、移位和异或运算。
如计算5->101，7->111
与运算101&111=101，左移一位(101&111)<<1=1010，得到进位值。
异或运算101^111=010，得到不算进位，各位应该得到的值。
之后我们应该将与运算得到的进位值1010和异或运算得到的结果010相加，得到最终结果。这样相加依然会有进位值，我们将1010和010看作新的需要计算和的两个数，继续计算他们的与和异或，直到与运算得到的进位值为0为止。
public class Solution {
public int Add(int num1,int num2) {
while(num2 != 0){//num2为与运算和位移运算的结果，即进位值。
int xor = num1 ^ num2;//异或运算，得到不进位应该得到的值
int and = (num1 & num2) << 1;//与运算和位移运算，计算得到进位值
num1 = xor;//将不进位得到的值看作新的num1
num2 = and;//将进位值看作新的num2，重复以上操作，直到进位值为0
}
return num1;//进位值num2为0，则num1即为我们要得到的两数之和。
}
}
49、把字符串转换成整数
题目描述
将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
输入描述:
输入一个字符串,包括数字字母符号,可以为空
输出描述:
如果是合法的数值表达则返回该数字，否则返回0
解题思路
难在要考虑很多奇怪的情况。
注意事项
- 用例中有-2147483648这个用例，而int的最大值是2147483647，-2147483648无法通过2147483648取反得到。
import java.util.ArrayList;
public class Solution {
public int StrToInt(String str) {
if(str.length() == 0){return 0;}
char[] chars = str.toCharArray();
boolean neg = false;//是否为负值
int index = 0;//index为整数真正开始的地方，跳过正负号，跳过数前面所有的0
if(chars[0]=='-'){//如果第一个字符为负号，则index+1
index = 1;
neg = true;
}else if(chars[0]=='+'){//如果第一个字符为正号，index+1
index = 1;
}//如果没有正负号，则为正数。index=0
if(index>=chars.length){return 0;}//如果字符串为“+”或“-”就结束了，则返回0
//遍历后面的每个字符，跳过前面的0，确定index的值。
while(chars[index] < '1' || chars[index] > '9'){
if(chars[index] == '0' && index+1<chars.length){//如果遇到了1-9之外的数，但这个数是0，且0后面还有数，则index++
++index;
}else{
return 0;//如果遇到了1-9之外的数，1.这个数是0，但0后面没有数了，则转换为整数的结果就是0。2.这个数不是0，是0-9以外的符号，不管后面是否还有数，都不符合转换规则
}
}
ArrayList<Integer> num_list = new ArrayList<>();//将可用数字加入list
for(int i=index; i<chars.length; i++){//遍历0后面的所有字符
if(chars[i] < '0' || chars[i] > '9'){//如果是0-9以外的字符，则不符合转换条件
return 0;
}else{
num_list.add(chars[i]-48);//将字符转化为int，加入list
}
}
int sum = 0;
for(int i=0; i<num_list.size(); i++){//将list中的数加起来
if(neg){
sum -= num_list.get(i)*Math.pow(10,(num_list.size()-1-i));
}else{
sum += num_list.get(i)*Math.pow(10,(num_list.size()-1-i));
}
}
return sum;
}
}
50、数组中重复的数组
题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
解题思路
设置一个与数组长度一样的boolean数组arr，全部置为false。遍历每一个数，如遇到第一个2，则将arr[2]置为true；遇到第一个3，则将arr[3]置为true，直到遇到第二个2，发现arr[2]已经置为true，则将2赋值给duplication[0]，返回true。
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(length == 0){//不知道用例是怎么写的，这里写numbers.length==0会发生空指针异常
duplication[0] = -1;
return false;
}
boolean[] arr = new boolean[length];//设置一个是否访问的登场数组
for(int i=0; i<arr.length; i++){//全部设置为false
arr[i] = false;
}
for(int i=0; i<numbers.length; i++){
if(arr[numbers[i]] == false){//如果没有访问则置为true
arr[numbers[i]] = true;
}else{
duplication[0] = numbers[i];//如果已经访问，则赋值给duplication[0]，返回true
return true;
}
}
return false;
}
}
结尾
如果您发现我的文章有任何错误，或对我的文章有什么好的建议，请联系我！如果您喜欢我的文章，请点喜欢~*我是蓝白绛，感谢你的阅读！
