20240506
实现一个方法 transform, 以数组为参数, 循环将数组中的每个元素 乘以 2 , 并设置到对应的数组元素上. 例如 原数组为 {1, 2, 3}, 修改之后为 {2, 4, 6}
public static void transform(int[] array){
for (int i = 0; i < array.length; i++) {
array[i] *= 2;
}
}
public static void main(String[] args) {
int[] array = {1,2,3};
transform(array);
System.out.println(Arrays.toString(array));
}结果：
调整数组顺序使得奇数位于偶数之前。调整之后，不关心大小顺序。
如数组：[1,2,3,4,5,6]
调整后可能是：[1, 5, 3, 4, 2, 6]
public static void test(int[] array){
int i = 0;
int j = array.length - 1;
while(i < j){
while(i < j && array[i] % 2 != 0){
i++;
}
while(i < j && array[j] % 2 == 0){
j--;
}
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
public static void main(String[] args) {
int[] array = {1,2,3,4,5,6};
test(array);
System.out.println(Arrays.toString(array));
}解析：
给定一个有序整型数组, 实现二分查找
public static int binarySearch(int[] array,int key){
int left = 0;
int right = array.length - 1;
while(left <= right){
int mid = (left + right)/2;
if(array[mid] < key){
left = mid + 1;
}else if(array[mid] > key){
right = mid - 1;
}else{
return mid;
}
}
return -1;
}
public static void main(String[] args) {
int[] array = {1,2,3,4,5,6,7,8,9,10};
int ret = binarySearch(array,3);
if(ret == -1){
System.out.println("not found");
}else{
System.out.println("找到了，下标是："+ ret);
}
}给定一个整型数组，实现冒泡排序（升序）
错误示例：
正确示例：
public static void bubbleSort(int[] arr){
boolean flg = false;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if(arr[j] > arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
flg = true;
}
}
if(flg == false){
break;
}
}
}
public static void main(String[] args) {
int[] arr = {1,3,2,2,4};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
} 解析：
进一步进行了优化，当数据在排序过程当中有序了，会在某一趟排序后，发现数据没有交换。
所以，每一趟排序完，都去检查是否发生了交换，没有交换证明数据已近有序，不需要再进行剩余趟数的排序了。
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
下面是自己实现：
public static int[] test(int[] arr,int target){
for(int i=0;i<arr.length-1;i++){
for(int j = i+1;j<arr.length;j++){
if(arr[i] + arr[j] == target){
return new int[]{i,j};
}
}
}
return null;
}
public static void main(String[] args) {
int[] nums = {2,7,11,15};
int[] arr = test(nums,9);
System.out.println(Arrays.toString(arr));
}下面是答案实现：
本题最重要的一句话：假设每种输入只会对应一个答案
也就意味着不会有多个答案，暴力求解就是挨个匹配查找即可
public static int[] twoSum(int[] nums,int target){
int[] result = new int[2];
//双向指针i和j，i从前向后遍历，j从后向i遍历
//若arr[i]+arr[j]=target，即为题解
for(int i=0;i<nums.length-1;i++){
for(int j = nums.length - 1;j > i;j--){
if(nums[i] + nums[j] == target){
result[0] = i;
result[1] = j;
}
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {2,7,11,15};
int[] arr = twoSum(nums,9);
System.out.println(Arrays.toString(arr));
}可以用哈希表来提升效率，后面学习之后再来改进
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
下面是自己实现：
public static int test(int[] arr){
for (int i = 0; i < arr.length; i++) {
int x = arr[i];
int j = 0;
int count = 0;
while(j < arr.length){
if(arr[j] == x){
count++;
//这里加了判断若count已经大于1，提前结束循环
if(count > 1){
break;
}
}
j++;
}
if(count == 1){
return x;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {2,2,1,3,4,3,8,4,8,2,9,2,9};
int tmp = test(arr);
if(tmp == -1){
System.out.println("没找到");
}else{
System.out.println("找到了，该数字是：" + tmp);
}
}下面是答案实现：
本题主要考察运算符：异或。
异或的特点是：
1、n ^ n = 0；即两个相同的数字异或是0
2、0 ^ n = n；即0和任何数字进行异或，结果就是那个任何数字。
public static int singleNumber(int[] nums){
//用异或运算的性质可以巧妙的解决这个问题
//因为数组中只有一个数字出现一次
//则其他出现两次的数字用异或运算后都是0
//最终整个数组异或运算的结果即为所求
int ret = 0;
for(int i : nums){
ret ^= i;
}
return ret;
}
public static void main(String[] args) {
int[] arr = {4,1,2,1,2};
int tmp = singleNumber(arr);
if(tmp == 0){
System.out.println("没找到");
}else{
System.out.println("找到了，该数字是：" + tmp);
}
}给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
例子：
自己实现：
public static int test(int[] arr){
for (int i = 0; i < arr.length; i++) {
int x = arr[i];
int j = 0;
int count = 0;
while(j < arr.length){
if(arr[j] == x){
count++;
//这里加了判断若count已经大于数组长度的1/2，提前结束循环
if(count > arr.length/2){
return x;
}
}
j++;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {2,2,1,1,1,2,2};
int tmp = test(arr);
if(tmp == -1){
System.out.println("没找到");
}else{
System.out.println("找到了，该数字是：" + tmp);
}
}答案实现：
数组中出现次数超过一半的数字，一定是排好序之后，中间位置的数字。
//将数组排序后，数组n/2的元素一定是众数
public static int majorityElement(int[] arr) {
Arrays.sort(arr);
return arr[arr.length/2];
}
public static void main(String[] args) {
int[] arr = {2,2,1,1,1,2,2};
int tmp = majorityElement(arr);
System.out.println(tmp);
}给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false 。
自己实现：
public static boolean test(int[] arr){
for (int i = 0; i < arr.length; i++) {
int x = arr[i];
int j = 0;
int count = 0;
while(j < arr.length){
if(arr[j] % 2 != 0){
count++;
//这里加了判断若count已经大于数组长度的1/2，提前结束循环
if(count > 2){
return true;
}
}else{
count = 0;
}
j++;
}
}
return false;
}
public static void main(String[] args) {
int[] arr = {1,2,34,3,4,5,7,23,12};
boolean tmp = test(arr);
if(tmp == false){
System.out.println("不存在连续三个元素都是奇数的情况");
}else{
System.out.println("存在连续三个元素都是奇数的情况");
}
}答案实现：
数字是连续出现的，所以我们只需要定义一个计数器，如果连续出现的次数超过3，则返回true。
public static boolean threeConsecutiveOdds(int[] arr){
//引入标记位记录连续出现奇数的个数
int count = 0;
for (int i = 0; i < arr.length; i++) {
if(isConsecutiveOdd(arr[i])){
//出现奇数，count++;
count++;
if(count == 3){
//出现连着三个奇数，返回true
return true;
}
}else{
//碰到偶数，count重置
count = 0;
}
}
return false;
}
public static boolean isConsecutiveOdd(int num){
return num % 2 != 0;
}
public static void main(String[] args) {
int[] arr = {1,2,34,3,4,5,7,23,12};
boolean tmp = threeConsecutiveOdds(arr);
if(tmp == false){
System.out.println("不存在连续三个元素都是奇数的情况");
}else{
System.out.println("存在连续三个元素都是奇数的情况");
}
}获取一个数二进制序列中所有的偶数位和奇数位，分别输出二进制序列。
思路：
一个数的二进制位数为32，下标为0~31
想要得到一个整数中的每一个二进制数字，只有让它每个二进制数字都按位与（&）上1
按位与：与0得0，与1得1
代码如下：需要注意的是for循环的开始条件与结束条件
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入一个数字：");
int n = sc.nextInt();
//从左往右数
System.out.print("二进制奇数位：");
for (int i = 31; i >= 1 ; i-=2) {
System.out.print(((n>>i) & 1) + " ");
}
System.out.println();//换行
System.out.print("二进制偶数位：");
for (int i = 30; i >= 0 ; i-=2) {
System.out.print(((n>>i) & 1) + " ");
}
}