剑指Offer之Java算法习题精讲数组与字符和等差数列

剑指Offer之Java算法习题精讲数组与字符和等差数列

在剑指Offer面试题中，数组和等差数列相关的算法习题十分常见，该攻略将针对这些习题进行详细的讲解。

数组

在Java中，数组是一种非常基础的数据类型，它可以存储一组具有相同类型的数据。数组的下标从0开始，可以使用array[index]的方式获取数组中特定下标的元素。下面讲解两道涉及数组的算法题：

1. 在排序数组中查找数字

题目描述：

在一个排序数组中查找数字，统计某个数字在排序数组中出现的次数。

示例1:

输入：[1, 2, 3, 3, 3, 4, 5], 3

输出：3

解释：数字3在数组中出现了3次。

思路：

由于数组是排序的，因此可以使用二分查找的方式来查找数字。具体来说，我们可以先利用二分查找找到某个数字出现的第一个位置和最后一个位置，然后根据这两个位置的差值求出该数字在数组中出现的次数。

代码实现：

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int first = binarySearch(array, k);
        int last = binarySearch(array, k + 1);
        return (first == array.length || array[first] != k) ? 0 : last - first;
    }

    private int binarySearch(int[] array, int target){
        int left = 0, right = array.length;
        while(left < right){
            int mid = (left + right) / 2;
            if(array[mid] >= target) right = mid;
            else left = mid + 1;
        }
        return left;
    }
}

2. 数组中出现次数超过一半的数字

题目描述：

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

示例1:

输入：[1, 2, 3, 2, 2,2, 5, 4, 2], 3

输出：2

解释：数字2在数组中出现了5次，占数组长度的一半以上。

思路：

由于该数字出现的次数超过数组长度的一半，因此可以使用摩尔投票法来查找该数字，具体步骤如下：

1. 初始化候选数字为数组的第一个数字，计数器为1；
2. 从第二个数字开始遍历数组，遇到相同的数字则计数器加1，否则计数器减1；
3. 如果计数器减至0，则更新候选数字为当前的数字，并将计数器置为1；
4. 遍历完成后，得到的候选数字就是出现次数超过一半的数字。

代码实现：

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int count = 0, candidate = 0;
        for(int num : array){
            if(count == 0) candidate = num;
            if(num == candidate) count++;
            else count--;
        }
        int cnt = 0;
        for(int num : array){
            if(num == candidate) cnt++;
        }
        return cnt > array.length / 2 ? candidate : 0;
    }
}

等差数列

在数学中，等差数列是指一组数之间差值相等的数列。在Java中，可以使用for循环等控制结构来处理等差数列的问题。下面讲解一道关于等差数列的算法题：

1. 请你设计一个收银程序

题目描述：

设计一个收银程序，要求输入商品数量和单价，并计算出总价。如果商品数量大于等于3个，则会进行折扣，折扣的价格就是数量为3的商品单价的一半。

示例1:

输入：3 10.0

输出：27.5

解释：商品数量为3，单价为10.0，折扣价格为5.0，因此总价为(10.0 + 10.0 + 10.0 / 2) = 27.5

思路：

首先需要读取输入数据，可以使用Scanner类来实现。然后根据商品数量来计算折扣价格和总价。最后输出结果就可以了。

代码实现：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        double p = sc.nextDouble();
        double price = n * p;
        if(n >= 3) price -= p / 2;
        System.out.printf("%.1f", price);
    }
}

以上就是本次攻略的内容，通过对数组和等差数列相关算法的讲解，希望能够对大家进行帮助。