剑指Offer（java答案）（41-50）

41、和为S的两个数字

题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，任意输出一对。
输入数组{1，2，4，7，11，15}和15，输出4，11

import java.util.ArrayList;
public class Solution {
    /*
    * i,j分别表示数组两端下表
    * 当array[i]+array[j]>S时，j-- 尾端向前移动，两数据和增大
    * 当array[i]+array[j]=S时，将array[i],array[j]依次添加到ArrayList中
    * 当array[i]+array[j]<S时，i++前段向后移动，两数据和减小
    */
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (array == null || array.length < 2) {
            return list;
        }
        int i=0,j=array.length-1;
        while(i<j){
            if(array[i]+array[j]==sum){
            list.add(array[i]);
            list.add(array[j]);
                return list;
           }else if(array[i]+array[j]>sum){
                j--;
            }else{
                i++;
            }
             
        }
        return list;
    }
}

扩展题：和为S的连续正数序列

描述：输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

import java.util.ArrayList;

public class Solution {
    public static ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        if (sum < 3)
            return list;
        ArrayList<Integer> l = new ArrayList<Integer>();
        int small = 2;
        int middle = (1 + sum) / 2;//因为至少连续2个且顺序增加，所以取中间值
        l.add(1);
        l.add(2);
        int s = 3;
        if (s == sum) {
            list.add(new ArrayList<Integer>(l));
        }

        while (small <= middle) {
            small++;
            s += small;
            l.add(small);
            if (s == sum) {
                list.add(new ArrayList<Integer>(l));
            }
      //两个指针，若大，减去左边数字，若小，加右边数字
            while (s > sum && small <= middle) {
                s -= l.remove(0);
                if (s == sum) {
                    list.add(new ArrayList<Integer>(l));
                }
            }

        }
        return list;
    }
}

42、反转单词

描述：反转英文单词，例如，“student. a am I”反转成“I am a student.”

思想：就是先翻转所有字符，再逐个单词翻转

public class Solution {
     public String ReverseSentence(String str) {
         if(str==null||str.trim().equals(""))// trim掉多余空格
             return str;
         String[] words = str.split(" ");// 以空格切分出各个单词
         StringBuffer buffer = new StringBuffer();
         for(int i=0;i<words.length;i++){

             buffer.append(reverse1(words[i].toCharArray(), 0, words[i].length()-1)).append(" ");
         }
         if(buffer.length()>0)
             buffer.deleteCharAt(buffer.length()-1);// 删除最后一个空格
         return reverse1(buffer.toString().toCharArray(), 0, buffer.length()-1);
      
 }
    private String reverse1(char[] str, int l, int r) {
         // TODO Auto-generated method stub
         if(l>r)
             return "";
         char tmp;
         while(l<r){
             tmp = str[l];
             str[l] = str[r];
             str[r] = tmp;
             l++;
             r--;
         }
         return String.valueOf(str);
     }
}

扩展题：字符串左移n位，abcde，左移2位，cdeab

思路：前n位反转，后几位反转，最后总的反转

public class Solution {
    public String LeftRotateString(String str,int n) {
        char[] chars = str.toCharArray();        
        if(chars.length < n) return "";
        reverse(chars, 0, n-1);
        reverse(chars, n, chars.length-1);
        reverse(chars, 0, chars.length-1);
        StringBuilder sb = new StringBuilder(chars.length);
        for(char c:chars){
            sb.append(c);
        }
        return sb.toString();
    }
     
    public void reverse(char[] chars,int low,int high){
        char temp;
        while(low<high){
            temp = chars[low];
            chars[low] = chars[high];
            chars[high] = temp;
            low++;
            high--;
        }
    }
}

44、扑克牌的顺序

从扑克牌中抽取5张牌，判断是否连续，大小王是任意数字

思路：选取5张牌，首先去0，然后进行排序，最大值减最小值是否小于等于4，大于4，为false，
然后相邻相减应该大于0小于5，否的为false

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    public boolean isContinuous(int [] numbers) {
        if(numbers == null || numbers.length == 0 || numbers.length > 5){
            return false;
        }
        ArrayList<Integer> al = new ArrayList<>();
        int len = numbers.length;
        int count = 0;
        for(int i = 0; i < len; i++){
        //必须去0，因为0可以是任意数字，如0，2，3，5，6，也是连续的
            if(0 == numbers[i]){
                count++;
            }else{
                al.add(numbers[i]);
            }      
        }
         //非0的排序
        Collections.sort(al);
        int len1 = al.size();
        //大于4，肯定false
        if(Math.abs(al.get(0) - al.get(len1 - 1)) > 4){
            return false;
        }
        for(int i = 0; i < len1 - 1; i++){
         //相邻的只差，大于0不能重复，大于4肯定false
            int temp = al.get(i + 1) - al.get(i);
            if(0 < temp && temp < 5){
                continue;
            }else{
                return false;
            }
        }
        return true;
    }
}

45、约瑟夫环问题：圆圈中最后一个数字

题目描述：一个环，每次删除第m个数字，求最后一个数字，如0，1，2，3，4这5个数字，从0开始每次删除第3个数字，则依次删除2，0，4，1，最后一个数字是3

第一种解法：数组O(m*N)

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n<1||m<1) return -1;
        int[] array = new int[n];
        int i = -1,step = 0, count = n;
        while(count>0){   //跳出循环时将最后一个元素也设置为了-1
            i++;          //指向上一个被删除对象的下一个元素。
            if(i>=n) i=0;  //模拟环。
            if(array[i] == -1) continue; //跳过被删除的对象。
            step++;                     //记录已走过的。
            if(step==m) {               //找到待删除的对象。
                array[i]=-1;
                step = 0;
                count--;
            }        
        }
        return i;//返回跳出循环时的i,即最后一个被设置为-1的元素
    }
}

第二种：链表,O(N)

import java.util.*;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if (m == 0 || n == 0) {
            return -1;
        }
        ArrayList<Integer> data = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            data.add(i);
        }
        int index = -1;
        while (data.size() > 1) {
        //重点是此步
            index = (index + m) % data.size();
            data.remove(index);
            index--;
        }
        return data.get(0);
    }

}

第三种better解法：约瑟夫经典解法，O(N)，空间复杂度O(1)

public class Solution {
    public int LastRemaining_Solution(int n,int m) {
        if(n==0) return -1;
         
       int s=0;
       for(int i=2;i<=n;i++){
           s=(s+m)%i;
       }
       return s;
    }
}

46、求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 result = 0;
        int a = 1;
        boolean value = ((n!=0) && a == (result = Sum_Solution(n-1)));
        result += n;    
        return result;
    }
 
}

47、不用加减乘除做加法

题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

思路：首先看十进制是如何做的： 5+7=12，三步走

第一步：相加各位的值，不算进位，得到2。

第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。

第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。

同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111 第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。

第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。

第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。
继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。

public class Solution {
    public int Add(int num1,int num2) {
        while (num2!=0) {
            int temp = num1^num2;//不算进位，各位相加
            num2 = (num1&num2)<<1;//得到进位数
            num1 = temp;//与进位数相加，即循环以上操作
        }
        return num1;
    }
}

49、把字符串转换成整数

此题主要是注意细节：
1、功能测试：输入有+-号情况，区分正负数和0
2、特殊输入：空字符串情况，输入非数字字符串情况，如a12
3、边界值：最大正整数和最小负整数溢出情况

public class Solution {
    public int StrToInt(String str)
    {
        if (str.equals("") || str.length() == 0)//空字符串情况
            return 0;
        char[] a = str.toCharArray();
        int i = 0;
        boolean fuhao = true;//+-符号位
        if (a[0] == '-'){
            fuhao = false;
            i = 1;//第一位如果是-号，则从第二位开始循环
        }           
        int sum = 0;
        for (; i < a.length; i++)
        {
            if (a[i] == '+')
                continue;
            if (a[i] < 48 || a[i] > 57)
                return 0;//有非数字字符
            sum = sum * 10 + a[i] - 48;
            
            //判断是否溢出，正整数最大0X7FFF FFFF,最小负整数0X8000 0000
            if((fuhao && sum > 0X7fffffff) || (!fuhao && sum < 0X80000000)){
                sum = 0;
                break;
            }
            
        }
        return fuhao ? sum : sum * -1;
    }
}

声明：此文章为本人原创，如有转载，请注明出处

如果您觉得有用，欢迎关注我的公众号，我会不定期发布自己的学习笔记、AI资料、以及感悟，欢迎留言，与大家一起探索AI之路。

AI探索之路