同步操作将从 Java精选/Ebooks 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
归并排序可以说是链表排序中最佳的选择,能够保证最好和最坏时间复杂度都是nlogn,而且在数组排序中广受开发人反感的空间复杂度在链表排序中也从O(n)降到了O(1)。
归并排序的一般分为四步:
1)将需要排序数组(链表)取中点并一分为二,拆分为两个链表:head和second两个子链表;
2)使用递归方式对左半部分子链表进行归并排序;
3)使用递归方式对右半部分子链表进行归并排序;
4)将两个半部分子链表进行合并(merge),得到结果。
首先用快慢指针(快慢指针思路,快指针一次走两步,慢指针一次走一步,快指针在链表末尾时,慢指针恰好在链表中点)的方法找到链表中间节点,然后使用递归对两个子链表排序,把两个排好序的子链表合并成一条有序的链表。
程序代码,为了方便输出查看结果,使用Gson包,不需要可以去除相关代码:
import com.google.gson.Gson;
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class LinkedInsertSort {
/**
* @author 公众号:Java精选
* @param args
*/
public static void main(String[] args) {
ListNode node = new ListNode(4);
node.next = new ListNode(3);
LinkedInsertSort lss = new LinkedInsertSort();
System.out.println(new Gson().toJson(lss.mergeSort(node)));
}
public ListNode mergeSort(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode mid = getMid(head);// 获取链表中间节点
// 把链表从之间拆分为两个链表:head和second两个子链表
ListNode second = mid.next;
mid.next = null;
// 对两个子链表排序
ListNode left = mergeSort(head);
ListNode right = mergeSort(second);
return merge(right, left);
}
// 两个有序链表的归并
private ListNode merge(ListNode l1, ListNode l2) {
// 辅助节点,排好序的节点将会链接到dummy后面
ListNode dummy = new ListNode(0);
ListNode tail = dummy;// tail指向最后一个排好序的节点
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next; // 移动tail指针
}
if (l1 != null)
tail.next = l1;
else
tail.next = l2;
return dummy.next;
}
// 返回链表之间节点
private ListNode getMid(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode slow = head;
ListNode faster = head.next;
while (faster != null && faster.next != null) {
slow = slow.next;
faster = faster.next.next;
}
return slow;
}
}
输出结果
{"val":3,"next":{"val":4}}
假设三个字符串s1、s2、s3,验证s3是否是由s1和s2交错组成的。注意是s1与s2交错组成s2字符串。
两个字符串s和t交错的定义与过程如下,其中每个字符串都会被分割成若干非空子字符串:
s=s1+s2+...+sn
t=t1+t2+...+tm
|n-m|<=1
交错是s1+t1+s2+t2+s3+t3+...或者t1+s1+t2+s2+t3+s3+...
提示:a+b意味着字符串a和b连接。
示例1
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例2
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false
程序代码
class Solution {
public static void main(String[] args) {
String s1 = "ab", s2 = "cd", s3 = "acbd";
System.out.println(isInterleave(s1, s2, s3));
}
public static boolean isInterleave(String s1, String s2, String s3) {
if ((s1.length() + s2.length()) != s3.length())
return false;
boolean[][] dp = new boolean[s2.length() + 1][s1.length() + 1];
dp[0][0] = true;
for (int i = 1; i <= s1.length(); i++) {
dp[0][i] = dp[0][i - 1] && s1.charAt(i - 1) == s3.charAt(i - 1) ? true : false;
}
for (int i = 1; i <= s2.length(); i++) {
dp[i][0] = dp[i - 1][0] && s2.charAt(i - 1) == s3.charAt(i - 1) ? true : false;
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
dp[i][j] = (dp[i][j - 1] && s1.charAt(j - 1) == s3.charAt(i + j - 1))
|| (dp[i - 1][j] && s2.charAt(i - 1) == s3.charAt(i + j - 1));
}
}
return dp[s2.length()][s1.length()];
}
}
运行结果
true
程序分析:分子与分母的变化规律,分母等于前一个分子,分子是前一个分子加当前分母之和。关注Java精选公众号,内涵算法题100+道面试题,其他面试题3000+道题。
程序代码如下:
package com.jingxuan.system;
public class Fenshu20 {
public static void main(String[] args) {
float fm = 1f;
float fz = 1f;
float temp;
float sum = 0f;
for (int i = 0; i < 20; i++) {
temp = fm;
fm = fz;
fz = fz + temp;
sum += fz / fm;
System.out.println(fz + "/" + fm);
}
System.out.println("这个数列的前20项之和为" + sum);
}
}
运行结果如下:
2.0/1.0
3.0/2.0
5.0/3.0
8.0/5.0
13.0/8.0
21.0/13.0
34.0/21.0
55.0/34.0
89.0/55.0
144.0/89.0
233.0/144.0
377.0/233.0
610.0/377.0
987.0/610.0
1597.0/987.0
2584.0/1597.0
4181.0/2584.0
6765.0/4181.0
10946.0/6765.0
17711.0/10946.0
这个数列的前20项之和为32.660263
程序分析:
利用for循环语句,if条件语句。
程序代码
import java.util.Scanner;
public class Demo04 {
private static Scanner in;
private static int digital, character, blank, other;
public static void main(String[] args) {
System.out.println("请输入一个字符串");
in = new Scanner(System.in);
String str = in.nextLine();
char[] ch = str.toCharArray();
count(ch);
}
public static void count(char[] arr) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= '0' && arr[i] <= '9') {
digital++;
} else if ((arr[i] >= 'a' && arr[i] <= 'z')
|| (arr[i] >= 'A' && arr[i] <= 'Z')) {
character++;
} else if (arr[i] == ' ') {
blank++;
} else {
other++;
}
}
System.out.println("数字个数:" + digital);
System.out.println("英文字母个数:" + character);
System.out.println("空格个数:" + blank);
System.out.println("其他字符个数:" + other);
}
}
运行结果
请输入一个字符串
123456 blog.yoodb.com _
数字个数:6
英文字母个数:12
空格个数:2
其他字符个数:3
程序分析:
用情况语句比较好,如果第一个字母一样,则判断用情况语句或if语句判断第二个字母。
程序代码
import java.util.Scanner;
public class Demo12 {
private static Scanner in;
public static void main(String[] args) {
char weekSecond;
in = new Scanner(System.in);
System.out.println("请输入星期的第一个字母:");
String letter = in.next();
if (letter.length() == 1) {
char weekFirst = letter.charAt(0);
switch (weekFirst) {
case 'm':
case 'M':
System.out.println("星期一(Monday)");
break;
case 't':
case 'T':
System.out
.print("由于星期二(Tuesday)与星期四(Thursday)均以字母T开头,故需输入第二个字母才能正确判断:");
letter = in.next();
if (letter.length() == 1) {
weekSecond = letter.charAt(0);
if (weekSecond == 'U' || weekSecond == 'u') {
System.out.println("星期二(Tuesday)");
break;
} else if (weekSecond == 'H' || weekSecond == 'h') {
System.out.println("星期四(Thursday)");
break;
} else {
System.out.println("Error!");
break;
}
} else {
System.out.println("输入错误,只能输入一个字母,程序结束!");
break;
}
case 'w':
case 'W':
System.out.println("星期三(Wednesday)");
break;
case 'f':
case 'F':
System.out.println("星期五(Friday)");
break;
case 's':
case 'S':
System.out
.print("由于星期六(Saturday)与星期日(Sunday)均以字母S开头,故需输入第二个字母才能正确判断:");
letter = in.next();
if (letter.length() == 1) {
weekSecond = letter.charAt(0);
if (weekSecond == 'A' || weekSecond == 'a') {
System.out.println("星期六(Saturday)");
break;
} else if (weekSecond == 'U' || weekSecond == 'u') {
System.out.println("星期日(Sunday)");
break;
} else {
System.out.println("Error!");
break;
}
} else {
System.out.println("输入错误,只能输入一个字母,程序结束!");
break;
}
default:
System.out.println("输入错误,不能识别的星期值第一个字母,程序结束!");
break;
}
} else {
System.out.println("输入错误,只能输入一个字母,程序结束!");
}
}
}
运行结果
请输入星期的第一个字母:
m
星期一(Monday)
程序分析:程序分析:假设有5个人,围成一圈,顺序排号,报数1、2、3、1、2,分别对应a、b、c、d、e;剩下a、b、d、e,继续报数3、1、2、3;剩下b、d,继续报数1、2,没有退出圈子的人,继续报数3、1;剩下d,最后留下来的是第4位。
程序代码如下:
package com.jingxuan.system;
import java.util.Scanner;
public class LeaveH {
private static Scanner s;
public static void main(String[] args) {
System.out.print("请输入有几个人参加:");
s = new Scanner(System.in);
int n = s.nextInt();
boolean[] arr = new boolean[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = true;
}
int leftCount = n;
int countNum = 0;
int index = 0;
while (leftCount > 1) {
if (arr[index] == true) {
countNum++;
if (countNum == 3) {
countNum = 0;
arr[index] = false;
leftCount--;
}
}
index++;
if (index == n) {
index = 0;
}
}
for (int i = 0; i < n; i++) {
if (arr[i] == true) {
System.out.println( "最后留下的是原来第" + (i+1) + "号");
}
}
}
}
运行结果如下:
请输入有几个人参加:5
最后留下的是原来第4号
冒泡排序是一种简单基础的排序算法,比较相邻的两个元素,如果前面的比后面的大,则交换两个元素;
对每个相邻的元素都进行这样的比较操作,从开始的一对到最后一对,这样最后的元素会是本次遍历完剩下最大的元素;
针对所有的元素执行上述步骤,除了已经指派出来的最大元素或序列,其中序列排在最末尾。
重复以上步骤直至排序完成。
程序分析:
1、第n行有n个数字。
2、每一行的开始和结尾数字都为1。
用二维数组表示就是a[i][0]=1; a[i][j]=1(当i==j时)。
3、第n+1行的第i个数字等于第n行的i-1个数字加上第n行的i个数字。
用二维数组表示就是 a[i+1][j]=a[i][j-1]+a[i][j]。
程序代码如下:
package com.jingxuan.system;
public class YHSJ {
public static void main(String[] args) {
int[][] arr = new int[10][];
for (int i = 0; i < arr.length; i++) {
arr[i] = new int[i + 1];
}
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
if (j == 0 || i == j) {
arr[i][j] = 1;
} else {
arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
}
}
}
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
运行结果如下:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
程序分析:在10万以内判断,先将该数加上100后再开方,再将该数加上168后再开方,如果开方后的结果满足如下条件,即是结果。请看具体分析:
程序代码如下:
package com.yoodb.util;
public class Demo03 {
public static void main(String[] args) {
for (int i = 1; i < 1000; i++) {
int m = (int) Math.sqrt((i + 100));
int n = (int) Math.sqrt((i + 100 + 168));
if (m * m == i + 100 && n * n == i + 100 + 168) {
System.out.println("这个数是" + i);
}
}
}
}
运行结果如下:
这个数是21
这个数是261
程序源码
import java.util.Scanner;
public class Tests {
public static void main(String[] args) {
int a, b, num1, num2, temp;
System.out.println("请你输入需要计算的两个数字:\n");
Scanner sc = new Scanner(System.in);
num1 = sc.nextInt();
num2 = sc.nextInt();
if (num1 < num2)/* 交换两个数,使大数放在num1上 */
{
temp = num1;
num1 = num2;
num2 = temp;
}
a = num1;
b = num2;
//辗转相除法一般指欧几里得算法
while (b != 0)/* 利用辗除法,直到b为0为止 */
{
temp = a % b;
a = b;
b = temp;
}
System.out.println("公约数" + a);
System.out.println("公倍数" + num1 * num2 / a);
}
}
输出结果
请你输入需要计算的两个数字:
65
78
公约数13
公倍数390
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。