1305 2018-11-24 2020-06-25

前言：牛客网剑指Offer编程题43~48题。

一、左旋转字符串

1、题目描述

考点知识迁移能力，对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。

2、我的代码

static class FortyThree {
    public String LeftRotateString(String str,int n) {
        if (str == null || str.length() == 0) {
            return str;
        }
        char[] chars = str.toCharArray();
        //n = n % str.length();
        char[] temp = new char[n];
        for (int i = 0; i < n; i++) {
            temp[i] = chars[i];
        }
        for (int i = 0; i < chars.length - n; i++) {
            chars[i] = chars[i + n];
        }
        for (int i = 0; i < n; i++) {
            chars[chars.length - 1 - i]  = temp[n - 1 - i];
        }
        return String.valueOf(chars);
    }
}

3、别人的代码

剑指Offer上面提供的解答是三次翻转，具体思路如下：假设给定提交abcdefg 3，那么首先翻转abcdefg为cbadefg，然后再翻转cbadefg为cbagfed，最后翻转所有得defgabc。思路巧是巧妙，学习一下吧。

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--;
    }
}

二、翻转单词顺序列

1、题目描述

考点知识迁移能力，例如，“student. a am I”，翻转单词顺序使其为“I am a student.”。

2、我的代码

还是用上面的思想

static class FortyFour {
    public String ReverseSentence(String str) {
        if (str == null || str.length() == 0 || !str.contains(" ")) {
            return str;
        }
        char[] chars = str.toCharArray();
        reverse(chars, 0, chars.length - 1);
        int begin = 0, end = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == ' ') {
                end = i;
                reverse(chars, begin, end - 1);
                begin = end + 1;
            }
        }
        if (begin == end + 1) {
            reverse(chars, begin, chars.length - 1);
        }
        return String.valueOf(chars);
    }

    private void reverse(char[] chars, int start, int end) {
        char temp;
        while (start < end) {
            temp = chars[start];
            chars[start] = chars[end];
            chars[end] = temp;
            start++;
            end--;
        }
    }
}

三、扑克牌顺子

1、题目描述

考点抽象建模能力，大\小王可以看成任何数字,并且A看作1,J为11,Q为12,K为13，且为了方便起见,你可以认为大小王是0(有两个大小王)，判断输入的5个数是否为顺子。

2、我的代码

static class FortyFive {
    public boolean isContinuous(int [] numbers) {
        if (numbers.length != 5) {
            return false;
        }
        quickSort(numbers, 0, numbers.length - 1);
        if (numbers[0] != 0) {
            for (int i = 0; i < numbers.length - 1; i++) {
                if (numbers[i] + 1 != numbers[i + 1]) {
                    return false;
                }
            }
            return true;
        } else {
            int kingCount = 0;
            for (int i = 0; i < numbers.length - 1; i++) {
                if (numbers[i] == 0) {
                    kingCount++;
                }
            }
            for (int i = kingCount; i < numbers.length - 1; i++) {
                if (numbers[i] == numbers[i + 1]) {
                    return false;
                }
            }
            int needValue = 0;
            for (int i = numbers.length - 1; i > kingCount; i--) {
                int temp = numbers[i] - numbers[i - 1];
                if (temp != 1) {
                    needValue += temp - 1;
                }
            }
            if (kingCount < needValue) {
                return false;
            } else {
                return true;
            }
        }
    }

    private void quickSort(int[] nums, int start, int end) {
        if (start >= end || start < 0 || end > nums.length - 1) {
            return;
        }
        int index = start;
        for (int i = start; i <= end; i++) {
            if (nums[i] < nums[index]) {
                int temp = nums[i];
                for (int j = i; j > start; j--) {
                    nums[j] = nums[j - 1];
                }
                nums[start] = temp;
                index++;
            }
        }
        quickSort(nums, start, index - 1);
        quickSort(nums, index + 1, end);
    }

    private static void test() {
        int[] arr = {5, 4, 3, 2, 1, 8, 7, 6, 9};
        new FortyFive().quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

四、圆圈中最后剩下的数

1、题目描述

考点抽象建模能力，0, 1, ..., n - 1这几个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈剩下的最后一个数字。

2、我的代码

static class FortySix {
    public int LastRemaining_Solution(int n, int m) {
        if (n <= 0 || m <= 0) {
            return -1;
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int cur = 0;
        while (list.size() != 1) {
            cur += m - 1;
            while (cur > list.size() - 1) {
                cur = cur - list.size();
                System.out.println("返回头坐标" + cur);
            }
            int r = list.remove(cur);
            System.out.println("移除" + r + "通过位置" + cur);
        }
        return list.get(0);
    }

    private static void test() {
        int result = new FortySix().LastRemaining_Solution(5, 3);
        System.out.println(result);
    }
}

五、求1+2+3+...+n

1、题目描述

考点思维发散能力，求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

2、我的代码

感觉是有点违背题目要求了。

public int Sum_Solution(int n) {
    if (n == 0) {
        return 0;
    }
    return Sum_Solution(n - 1) + n;
}

3、别人的代码

public int Sum_Solution(int n) {
    int sum = n;
    boolean ans = (n>0)&&((sum+=Sum_Solution(n-1))>0);
    return sum;
}

聪明人还是多啊。

六、不用加减乘除做加法

1、题目描述

考点思维发散能力，写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

2、别人的代码

一看到这个题目，我第一反应就是为运算，但看了许久，也不是很懂。

首先看十进制是如何做的： 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;
    }
}    

3、别人的代码2

我比较喜欢这种，人才啊。

public int Add(int num1,int num2) {
    if(num1>0){
        while(num1--!=0)
            num2++;
    }
    else if(num1<0){
        while(num1++!=0)
            num2--;
    }
    return num2;
}

一天6道题完工。

总访问次数: 316次, 一般般帅 创建于 2018-11-24, 最后更新于 2020-06-25