1. 判定素数
题目要求:
- 给定一个数字,判定一个数字是否是素数
- 解题思路:
- 素数除了1和其本身再不能被其他数整除,假设一个数C不是素数,那么其一定可以写成 A * B = C 的形式,在所有的可能中一定有A或B是小于等于C的开平方的。
- 还容易忽略的一点是 1不是素数
代码实现:
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); //容易忽略 if(n == 1){ System.out.println(n + "不是素数"); return; } int i; for (i = 2;i <= Math.sqrt(n);i++) { if(n%i == 0) { System.out.println(n + "不是素数"); break; } } if(i > Math.sqrt(n)) { System.out.println(n + "是素数"); } }
2. 奇数位于偶数之前
题目要求:
调整数组顺序使得奇数位于偶数之前。调整之后,不关心大小顺序。
如数组:[1,2,3,4,5,6]
调整后可能是:[1, 5, 3, 4, 2, 6]
解题思路:
本题可以使用2个下标,left 从0下标开始,right 从数组的最后一个元素下标开始;left遇到停下来,right遇到奇数停下来,然后完成交换,重复此操作,直到left和right相等结束
代码实现:
public static void oddNumbersAhead(int[] arr){ int left = 0; int right = arr.length - 1; while (left < right){ while ((arr[left]%2!=1) && (left<right)){ left++; } while ((arr[right]%2!=0) && (left<right)){ right--; } //交换 int tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp; } } public static void main(String[] args){ int[] arr = {1, 2, 3, 4, 5, 6, 7, 8}; oddNumbersAhead(arr); System.out.println(Arrays.toString(arr)); }
3. 多数元素
题目要求:
- 给定一个大小为 n 的数组,找到其中的多数元素;多数元素是指在数组中出现次数 大于 n/2 的元素。
- 你可以假设数组是非空的,并且给定的数组总是存在多数元素。
- 解题思路:
思路1:
- 数组中出现次数超过一半的数字,一定是排好序之后,中间位置的数字。
代码实现:
public static int findNum(int[] arr){ Arrays.sort(arr); return arr[arr.length/2]; } public static void main(String[] args){ int[] arr = {1,1,2,3,4,5,5,5,5,5,5,5,5,5}; int ret = findNum(arr); System.out.println(ret); }
思路2:
- 抵消法,设置一个计数器count、一个比较值 ret (初始为数组首元素的值),数组中值和ret进行比较,多数元素的个数一定比其他所有元素的个数要多;其他元素会被多数元素的抵消掉,最终留下来的一定时多数元素!
代码实现:
public static int findNum(int[] arr){ int ret = arr[0]; int count = 0; for (int i = 0; i < arr.length; i++) { if(arr[i] == ret){ count++; }else{ count--; } if(count == 0){ ret = arr[i+1]; } } return ret; } public static void main(String[] args){ int[] arr = {1,1,2,3,4,5,5,5,5,5,5,5,5,5}; int ret = findNum(arr); System.out.println(ret); } }
4. 存在连续三个奇数的数组
题目要求:
- 给你一个整数数组 arr,请你判断数组中是否存在连续三个元素都是奇数的情况:如果存在,请返回 true ;否则,返回 false 。
解题思路:
- 数字是连续出现的,所以我们只需要定义一个计数器,如果连续出现的次数超过3,则返回true。
代码实现:
public static boolean isCoiledThreeOdd(int[] arr){ int count = 0; for (int i = 0; i < arr.length; i++) { if(arr[i] % 2 == 1){ count++; if(count == 3){ return true; } }else{ count = 0; } } return false; } public static void main(String[] args){ int arr[] = {2,4,6,8,3,5,7,1,2,3}; boolean ret = isCoiledThreeOdd(arr); System.out.println(ret); }
5. 字符串最后一个单词的长度
题目要求:
解题思路:
思路1:
找到字符串中最后一个空格的下标位置记录下来,再用字符中最后一个字符的下标减去空格的下标得到得就是最后一个单词的长度(见代码中的方法一和方法二)。
思路2:
利用split()方法将字符串以空格分割放到一个字符串数组当中,求出数组中最后一个字符串的长度即可。
代码实现:
public class Main{ public static void main(String [] args) throws Exception{ //方法一 /*int index = -1; Scanner scan = new Scanner(System.in); String str = scan.nextLine(); for(int i = str.length()-1; i >= 0; i--){ if(str.charAt(i) == ' '){ index = i; break; } } System.out.println(str.length() - 1 - index); */ //方法二 /*Scanner scan = new Scanner(System.in); String str = scan.nextLine(); int index = str.lastIndexOf(' '); System.out.println(str.length() - 1 - index); */ //方法三 Scanner scan = new Scanner(System.in); String str = scan.nextLine(); String[] s = str.split(" "); System.out.println(s[s.length-1].length()); } }