剑指Offer（java答案）（41-50）
2019-05-25 本文已影响0人
壮少Bryant
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探索之路
