【程序1】
题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？
private static int Fb(int i) {
//不允许小于0的数
if (i <= 0) {
return -1;
}
//Fb(1)=1, Fb(2)=1
if (i == 1 || i == 2) {
return 1;
}
//递归调用
return Fb(i-1) + Fb(i-2);
}
public static void main(String[] args) {
int M=6; //输入第几个月，自填
System.out.print("Rabbit total: " + Fb(M));
}
【程序2】
题目：判断101-200之间有多少个素数，并输出所有素数。
解析：质数又称素数。一个大于1的自然数，除了1和它自身外，不能整除其他自然数的数叫做质数。
public static void main(String[] args) {
int count = 0;
for(int i=101; i<=200; i++) { //遍历从101到200所有自然数
for(int j=2; j < i; j++) { //从2到i-1遍历
if (i%j == 0) { //除了1和自身外，还能被整除，不是素数，跳出内循环。
break;
}
if (j == (i-1)) { //如果j指针遍历到i-1，仍然不能被整除，则认为i是素数
count ++;
System.out.print(i + ", ");
}
}
}
System.out.print("\nTotal: " + count);
}
输出结果：
101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
Total: 21
算法改进：
第一个对i的for循环，偶数肯定不是素数，直接跳过，只遍历奇数，每次+2；
第二个对j的for循环，不需要把i的值完全遍历，只需要遍历到i的开平方根即可，即Math.sqrt(i)。
代码改进：
public static void main(String[] args) {
int count = 0;
for(int i=101; i<=200; i+=2) { //遍历从101到200所有奇数
boolean flag = true;
for(int j=2; j <= Math.sqrt(i); j++) { //从2到sqrt(i)遍历
if (i%j == 0) { //除了1和自身外，还能被整除，不是素数，跳出内循环。
flag = false;
break;
}
}
if (flag == true) {
count ++;
System.out.print(i + ", ");
}
}
System.out.print("\nTotal: " + count);
}
【程序3】
快速找出一个数组中的两个数字，让这两个数字之和等于一个给定的值、
例如给定一个无序数组：{3, 7, 10, 4, 9, 2, 5, 6}，找出其中两个数字之和等于10
//冒泡排序，使其变成一个从小到大的有序序列
private static void bubbleSort(int[] list) {
int temp;
for (int i=0; i<list.length; i++) {
for (int j=list.length-1; j>i; j--) {
if (list[j] < list[j-1]) {
temp = list[j-1];
list[j-1] = list[j];
list[j] = temp;
}
}
}
}
private static void sum(int[] list) {
int i = 0;
int j = list.length-1;
while (i < j) {
if (list[i] + list[j] == 10) {
System.out.print( list[i] + " + " + list[j] + " = 10");
return;
} else if (list[i] + list[j] > 10) {
j --;
} else if (list[i] + list[j] < 10) {
i ++;
}
}
System.out.print( "No number equals 10 in array" );
}
public static void main(String[] args) {
int[] list = {3, 7, 10, 4, 9, 2, 5, 6};
//排序
bubbleSort(list);
//求和
sum(list);
}
【程序4】一个数组，负数放左边，正数放右边
例如：给定数组{-3, 7, 10, -4, -9, 2, 5, -6}
private static void sort(int[] list) {
//设置左右指针，i从左遍历，j从右遍历
int i = 0;
int j = list.length-1;
//i始终要小于j，否则数组越界
while (i < j) {
//若list[i] 为负数，继续向右遍历
while (i < list.length && list[i] < 0) {
i ++;
}
//若list[i] 为负数，继续向左遍历
while (j >= 0 && list[j] > 0 ) {
j --;
}
//i始终要小于j
if (i < j) {
//正负数交换
swap(list, i, j);
}
}
}
private static void swap(int[] list, int left, int right) {
int temp;
temp = list[right];
list[right] = list[left];
list[left] = temp;
}
public static void main(String[] args) {
int[] list = {-3, 7, 10, -4, -9, 2, 5, -6};
sort(list);
for (int i=0; i<list.length; i++) {
System.out.print( list[i] + ", " );
}
}
【程序5】找出数组中重复次数最多的数，要求时间复杂度O(n)
public static void main(String[] args) {
int[] arr = {1,1,2,2,3,4,4,4,4,5,5,5,6,6};
//以arr数组中的数作为key，重复一次value值递增，最后统计key对应最大的value值
//即为重复次数最多的数
Map<Integer, Integer> map = new HashMap<Integer, Integer>( );
for(int i=0; i<arr.length; i++) {
if (map.containsKey( arr[i] )) {
map.put( arr[i], map.get( arr[i] ) + 1 );
} else {
map.put( arr[i], 1 );
}
}
//找出map中最大value值对应的key
Collection<Integer> count = map.values();
int maxCount = Collections.max( count );
int maxKey = -1;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == maxCount) {
maxKey = entry.getKey();
}
}
System.out.print( "Number: " + maxKey );
}
【程序6】将两个排好序的链表合并成一个有序链表，要求时间复杂度O(n)
//定义单链表，数据域data，next 指针
static class ListNode {
int data;
ListNode next;
public ListNode (int data) {
this.data = data;
}
}
public static void main(String[] args) {
//初始化第一个单链表：1->3->7->9
ListNode list_node = new ListNode( 1 );
ListNode l2 = new ListNode( 3 );
list_node.next = l2;
ListNode l3 = new ListNode( 7 );
l2.next = l3;
ListNode l4 = new ListNode( 9 );
l3.next = l4;
printListNode(list_node);
System.out.print( "\n" );
//初始化第二个单链表：2->4->6->8
ListNode node = new ListNode( 2 );
ListNode node2 = new ListNode( 4 );
node.next = node2;
ListNode node3 = new ListNode( 6 );
node2.next = node3;
ListNode node4 = new ListNode( 8 );
node3.next = node4;
printListNode(node);
System.out.print( "\n" );
ListNode merge = mergingSort(list_node, node);
printListNode(merge);
}
private static ListNode mergingSort (ListNode listNode1, ListNode listNode2) {
//如果其中一条链表为null，无需合并，直接返回另外一条链表
if (listNode1 == null) {
return listNode2;
} else if (listNode2 == null) {
return listNode1;
}
//定义一个临时链表存储
ListNode mergedNode = new ListNode( 0 );
ListNode temp = mergedNode;
//遍历链表1和链表2，data更小的数复制到临时链表中，知道其中一个链表遍历完，跳出循环
while (listNode1 != null && listNode2 != null) {
if (listNode1.data <= listNode2.data) {
temp.next = listNode1;
listNode1 = listNode1.next;
} else {
temp.next = listNode2;
listNode2 = listNode2.next;
}
temp = temp.next;
}
//如果其中一条链表未遍历完，直接合并到临时链表尾部
if (listNode1 != null) {
temp.next = listNode1;
} else if (listNode2 != null) {
temp.next = listNode2;
}
return mergedNode.next;
}
//输出链表
private static void printListNode (ListNode node) {
if (node == null) {
return;
}
while (node != null) {
System.out.print( node.data );
node = node.next;
if (node != null) {
System.out.print( " -> " );
}
}
}
【测序7】打印出所有的 "水仙花数 "，所谓 "水仙花数 "是指一个三位数，其各位数字立方和等于该数本身。例如：153是一个 "水仙花数 "，因为153=1的三次方＋5的三次方＋3的三次方。
public static void main(String[] args) {
int a; //百分位
int b; //十分位
int c; //个位
for (int i=101; i<1000; i++) {
a = i/100;
b = (i%100)/10;
c = (i%100)%10;
if (i == Math.pow( a, 3 ) + Math.pow( b, 3 ) + Math.pow( c,3 )) {
System.out.println( i );
}
}
}
网友评论