Java练习题第二篇

改变原有数组元素的值

实现一个方法 transform, 以数组为参数, 循环将数组中的每个元素 乘以 2 并设置到对应的数组元素上
例如： 原数组为 {1, 2, 3}, 修改之后为 {2, 4, 6}

public static void main(String[] args) {

    int[] arr = {1,2,3};
    transform(arr);
//打印for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
}
public static void transform(int[] str) {
    //循环将数组中的每个元素 乘以 2
    for (int i = 0; i < str.length; i++) {
        str[i] = str[i]*2;
    }
}

• 直接用循环找到每个元素*2，最后在赋值回去

求数组的平均值

实现一个方法 avg, 以数组为参数, 求数组中所有元素的平均值(注意方法的返回值类型).

public static void main(String[] args) {
    int[] arr = {1,2,3,4,5,6,7,8,9,10};
    double ret = avg(arr);
    System.out.println(ret);
}
public static double avg(int[] arr) {
    double sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
    }
    sum /= arr.length;
    return sum;
}

• 数组的所有元素加起来，除于数组的元素个数，很简单

奇数位于偶数之前

调整数组顺序使得奇数位于偶数之前。调整之后，不关心大小顺序。
如数组：[1,2,3,4,5,6]
调整后可能是：[1, 5, 3, 4, 2, 6]

public static void main(String[] args) {
    int[] arr = {1,2,3,4,5,6,7,8,9,10};
    und(arr);
    System.out.println(Arrays.toString(arr));
}
public static void und(int[] n) {
    int left = 0;
    int right = n.length-1;
    while(left < right) {
        while(n[left] % 2 == 1 && left < right) {
            left++;
        }
        while(n[right] % 2 == 0 && left < right) {
            right--;
        }
        int tmp = n[left];
        n[left] = n[right];
        n[right] = tmp;
    }

• 第一个while 循环是判断整体
  第二个while 循环是判断如果是奇数，那么left 加 1，直到它指向偶数，
  第三个while 循环是判断它是不是奇数，不是 right 减 1，直到它指向奇数
  最后就是 left 和 right 互换，以上所有的判断条件都是在left小于 right

二分查找

public static void main(String[] args) {
    int[] arr = {1,2,3,4,5,6,7,8,9,10};
    int ret = Arrays.binarySearch(arr,5);
    System.out.println(ret);
}

• 使用Java 的二分查找Arrays.binarySearch

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

public static void main(String[] args) {
    int[] nums = {1,8,2,7,3,5,6,9};
    int target = 6;
    int[] ret = sic(nums,target);
    System.out.println(Arrays.toString(ret));
}
public static int[] sic(int[] arr,int k) {
    //存储数组下标
    int[] kas = new int[2];
    for (int i = 0; i < arr.length-1; i++) {
        for (int j = i+1; j < arr.length-1; j++) {
            if(arr[i] + arr[j] == k) {
                kas[0] = i;
                kas[1] = j;
            }
        }
    }
    return kas;
}

• 这直接暴力求解，每一个数组加上之后的数组看是否等于target，如果等于用数组返回下标
• 用二个for 循环搞定

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

public static void main(String[] args) {
    int[] arr = {2,2,3,3,5,6,6};
    int ret = uc(arr);
    System.out.println(ret);
}
public static int uc(int[] n) {
   int ret = 0;
    for(int i = 0; i < n.length;i++){
      ret = ret ^ n[i]; 
    }
   return ret;
}

• 二个相同的数字 异或 都是等于 0
  0 异或 任何数字 等于 任何数字

多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

投机取巧的方法：

public static void main(String[] args) {
    int[] arr = {3,2,3,2,2};
    int ret = rys(arr);
    System.out.println(ret);
}
public static int rys(int[] n) {
    Arrays.sort(n);
    return n[n.length/2];
}

• 先进行排序，再找数组的长度除于2，因为多数元素就是超过一半的数字
• 例如：有10个元素，多数元素肯定是超过 5 的，最少是 6 个以上，所以进行排序，打印最中间的元素

投票法：

public static void main(String[] args) {
        int[] arr = {1,2,1,2,1,2,1};
        int ret = fkc(arr);
        System.out.println(ret);
    }

    public static int fkc(int[] n) {
        int ret = n[0];
        int count = 0;
        for (int i = 0; i < n.length; i++) {
            if(n[i] == ret) {
                count++;
            }else {
                count--;
            }
            if(count == 0) {
                ret = n[i+1];
            }
        }
        return ret;
    }

• 投票法：
  假如有二个不同的阵营，如果遇到相同阵营的，那么就加1，不同阵营就减1
  最后剩下的就是人数最都的阵营

存在连续三个奇数的数组

public static void main(String[] args) {
    int[] arr= {1,2,3,5,7,8,10};
    boolean ret = fas(arr);
    System.out.println(ret);
}
public static boolean fas(int[] n) {
    int count = 0;
    for (int i = 0; i < n.length; i++) {
        if(n[i] % 2 == 1) {
            count++;
            if(count == 3) {
                return true;
            }
        }
        else {
            count = 0;
        }
    }
    return false;
}

• 历遍整个数组，如果出现 奇数，用计数器加加，不是就把计数器归零，因为不是连续的，要把计数器重置
• 判断计数器如果等于 3 时，跳出返回，表示数组中有 3 个奇数是连续的