算法分析及手写代码
626.判断身份证:要么是15位,要么是18位,最后一位可以为字母,并写出程序提出其中年月日。要求:
写出合格的身份证的正则表达式,
^(d{15}|d{17}[dx])$
写程序提取身份证中的年月日
public class IdCard
{
private String idCard;//私有变量
public IdCard(){}//构造方法
//构造方法
public IdCard(String idCard){
this.idCard=idCard;
}
public void setIdCard(String idCard)
{
this.idCard=idCard;
}
public String getIdCard()
{
return idCard;
}
//从身份证号码中截取生日
public String getBirthday()
{
return this.getIdCard().substring(6, 14);
}
public static void main(String args[])
{
ShenFenZheng sfz = new ShenFenZheng(\"420154199908157841\");
//调用getBirthday()方法获取生日
System.out.println(\"生日:\" + sfz.getBirthday());
}
}
627.对于一个字符串,请设计一个高效算法,找到第一次重复出现的字符保证字符串中有重复的字符,字符串的长度小于等于500.
package com.bjsxt;
import java.util.ArrayList;
import java.util.List;
public class FirstRepeat {
public static void main(String[] args) {
System.out.println(findFirstRepeat(\"pmedmitjtckhxwhvpwemznhmhzhpueainchqrftkmbjlradhmjekcqzansyzkvqhwnrdgzdbzewdmxkzrscikdaugbvygntrifnolehdtrqjlasofuvzeijbmzehkxknmjekcxswqldknysfsxrqaqzp\",152));
}
//返回:y
public static char findFirstRepeat(String A, int n) {
String[] str=A.split(\"\");
for(int x=0;x<n;x++){
int index=0;
int num=0;
//对于每一个值,都需要从前开始遍历
while(index1){
char flag='x';
flag=str[x].toCharArray()[0];
return flag;
}
}
//返回该值说明已经没有重复的
return 'p';
}
}
628.写一个完整函数,实现拷贝数组
public class test {
public static void main(String[] args) {
int [] arr1 = {10,20,30,40,50};
int [] arr2 = CopyArray(arr1);
System.out.println(Arrays.toString(arr2));
}
private static int[] CopyArray(int[] arr) {
int [] arr2 = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
arr2[i] = arr[i];
}
return null;
}
}
629.写一排序算法,输入10个数字,以逗号分开,可根据参数选择升序或者降序排序,须注明是何种排序算法。
package cn.bjsxt.demo;
import java.util.Scanner;
public class SortDemo {
/**
* 给定的字符串使用,号分隔
* @param strNumber
* @return
*/
public static String [] split(String strNumber){
String [] strSplit=strNumber.split(\",\");
return strSplit;
}
/**
* 将String类型的数组转换成int类型的数组
* @param strSplit
* @return
*/
public static int [] getInt(String [] strSplit){
int arr[]=new int[strSplit.length];
for (int i = 0; i < strSplit.length; i++) {
arr[i]=Integer.parseInt(strSplit[i]);
}
return arr;
}
/**
* 冒泡排序
* @param arr
*/
public static void sort(int [] arr){
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j arr[j+1]) {
change(arr,j,j+1);
}
}
}
}
/**
* 两数交换的方法
* @param arr 数组
* @param x 数组中元素的下标
* @param y 数组中元素的下标
*/
public static void change(int [] arr,int x,int y){
int temp=arr[x];
arr[x]=arr[y];
arr[y]=temp;
}
/**
* 测试类
* @param args
*/
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
System.out.println(\"请输入一个数字串,每个数字以逗号分隔\");
String str=input.next();
//调用方法
String [] s=split(str);//使用逗号分隔
int [] arr=getInt(s);//调有获得整型数组的方法
sort(arr);//调用排序的方法
for (int i : arr) {
System.out.print(i+\"t\");
}
}
}
630.判断字符串是否是这样的组成的,第一个字母,后面可以是字母、数字、下划线、总长度为5-20。
package cn.bjsxt.demo;
import java.util.Scanner;
public class StringDemo {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
System.out.println(\"请输入一个字符串,第一个字符必须是字母:\");
String str=input.next();
if (str.length()20) {
System.out.println(\"对不起,字符串的长度必须在5-20之间!\");
}else{
char []ch=str.toCharArray();
if (Character.isLetter(ch[0])) {//判断第一个字符是否是字母
for (int i = 1; i < ch.length; i++) {
if (!Character.isLetterOrDigit(ch[i])&&ch[i]!='_') {
System.out.println("字符串不符合要求");
break;
}
}
}
}
}
}
631.已排好序的数组A,一般来说可用二分查找可以很快找到,现有一特殊数组A,它是循环递增的,如a[]={17, 19 ,20, 25, 1, 4, 7, 9},在这样的数组中找一元素,看看是否存在。请写出你的算法,必要时可写伪代码,并分析其空间,时间复杂度。
思路说明:循环递增数组有这么一个性质:以数组中间元素将循环递增数组划分为两部分,则一部分为一个严格递增数组,而另一部分为一个更小的循环递增数组。当中间元素大于首元素时,前半部分为严格递增数组,后半部分为循环递增数组;当中间元素小于首元素时,前半部分为循环递增数组;后半部分为严格递增数组。
记要检索的元素为e,数组的首元素为a[low],中间元素为a[mid],末尾元素为a[high]。则当e等于a[mid] 时,直接返回mid的值即可;当e不等于a[mid] 时:
1) a[mid] > a[low],即数组前半部分为严格递增数组,后半部分为循环递增数组时,若key小于a[mid]并且不小于a[low]时,则key落在数组前半部分;否则,key落在数组后半部分。
2) a[mid] < a[high],即数组前半部分为循环递增数组,后半部分为严格递增数组时,若key大于a[mid]并且不大于a[high]时,则key落在数组后半部分;否则,key落在数组前半部分。
这种方式的时间复杂度为:O(log(n)),空间复杂度为O(1)。
public class TestBinarySearch {
public static void main(String[] args) {
// 定义数组
int[] a = { 17, 19, 20, 21, 25, 1, 4, 7 };
// 调用改进后的二分查找法求索引
int pos = search(a, 7);
System.out.println(\"要查找的元素的索引为:\" + pos);
}
/** 改进后的二分查找法:e为要查找的元素 */
public static int search(int[] a, int e) {
int low = 0;
int high = a.length - 1;
int mid = 0;
int pos = -1; // 返回-1,表示查找失败
// 如果low < high,说明循环查找结束,直接返回-1;否则循环查找
while (low <= high) {
// mid为中间值索引
mid = (low + high) / 2;
// 如果中间值刚好是e,则查找成功,终止查找,e的索引为mid
if (a[mid] == e) {
pos = mid;
break;
}
// 如果a[low] <= a[mid],说明原数组的前半部分是严格递增的,后半部分是一个更小的循环递增数组
if (a[low] <= a[mid]) {
// 如果要查找的元素e小于a[mid]并且不小于a[low]时,则说明e落在数组前半部分
if (a[low] <= e && e < a[mid]) {
high = mid - 1;
} else {// 否则的话,需要在数组的后半部分继续查找
low = mid + 1;
}
} else {// 否则,后半部分是严格递增的,前半部分是一个更小的循环递增数组
// 如果要查找的元素e大于a[mid]并且不大于a[high]时,则说明e落在数组后半部分
if (a[mid] < e && e <= a[high]) {
low = mid + 1;
} else {// 否则的话,需要在数组的前半部分继续查找
high = mid - 1;
}
}
}
return pos;
}
}
632.请编写一个完整的程序,实现如下功能:从键盘输入数字n,程序自动计算n!并输出。(注1:n!=1*2*3…*n, 注2:请使用递归实现)
思路说明:因为n! = (n-1)! * n,所以要求n!首先要求出(n-1)!,而(n-1)! = (n-1-1)! * (n-1),以此类推,直到n = 1为止。
import java.util.Scanner;
public class TestFactorial {
public static void main(String[] args) {
System.out.print(\"请输入一个整数:\");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(n + \"的阶乘是:\" + factorial(n));
}
/**求阶乘的方法*/
public static int factorial(int n) {
if(n == 1){
return 1;
}
return factorial(n - 1) * n;
}
}
633.请用递归的方法计算斐波那契数列的同项F(n),已知F0=0,F1=1,F(n)=F(n-1)+F(n-2)(n>=2,n∈N*).
思路说明:斐波那契数列的排列是:0,1,1,2,3,5,8,13,21,34,55,89,144……,特别指出的是0不是第一项而是第0项;因为F(n)=F(n-1)+F(n-2),所以要求F(n)首先要求出F(n-1)和F(n-2),而F(n-1)=F(n-1-1)+F(n-1-2),以此类推,直到,F(2)=F(1)+F(0)为止,已知F(1) = 1,F(0) = 0。
import java.util.Scanner;
public class TestFibo {
public static void main(String[] args) {
System.out.print(\"请输要求斐波那契数列的第几项:\");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(\"斐波那契数列的第\"+ n + \"是:\" + fibo(n));
}
public static int fibo(int n) {
if(n == 0){
return 0;
} else if(n == 1){
return 1;
}
return fibo(n -1) + fibo(n - 2);
}
}
634.现在有整数数组{11,66,22,0,55,32},请任意选择一种排序算法,用Java程序实现
冒泡思路说明:
(1) 最开始将数组看做一个无序数列(个数是数组的长度)与一个有序数列(0个)的组合;
(2) 每一趟比较完后, 找到了无序数列的最大值, 将其放到有序数列中(有序数列个数+1);
(3) N个数, 比较N-1趟;
(4) 每一趟挨个进行比较:从数组的第一个元素开始, 到无序数列的最后一个为止;
(5) 如果前边一个大于后边一个, 那么交换位置;
(6) 每趟比较的次数与趟数有关;
(7) 根据每趟比较是否发生了交换判断数据是否已经有序,从而进行优化。
public class TestSort {
public static void main(String[] args) {
int[] arr = {11, 66, 22, 0, 55, 32};
// 调用排序方法
sort(arr);
// 输出排除后的数组
for (int num : arr) {
System.out.print(num + \"t\");
}
}
public static void sort(int[] arr) {
// 定义标记
boolean flag = false;
int temp;
// 排序
// 外层循环控制的是比较的趟数
for (int i = 0; i < arr.length - 1; i++) {
// 每一趟比较之前初始化, 否则会保留上一堂比较的结果
flag = false;
// 内层循环控制的是每趟比较的次数
for (int j = 0; j arr[j + 1]) {
// 交换
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
//如果发生交换,改变flag的值
flag = true;
}
}
if (!flag) {
break;
}
}
}
}
635.请根据注释,编码实现下面类的方法
// 这个类用于存取一组权限,每个权限用非负整数表示的.这组枳限存储在
// righiString属性中。如果权限N权限存在,rightString第N个字符为“1”,否则, 为空格。
class RightStore {
public String righString = \"\";
// 如果传入的权限right存在,该方法返回true.否期,为false.,
// right为传入的权限的整数值.
public boolean getRight(int right) {
return true;
}
// 该方法存储或消除传入的权限.如果value为true,存储传入的权限,
// 否则淸除该权限.
// right为传入的权限的整数值.
public void setRight(int right, boolean value) {
}
}
思路说明:我们首先要读懂这道题的意思:righString这个字符串是用来存储一系列权限的阶乘英文,并且权限的取值只有两种:有和没有;在righString中使用字符‘1’表示有权限,字符空格‘ ’表示没有权限。举个例子:如果righString的长度为3,第一位表示对订单系统是否有权限,第二位表示对人员管理系统是否有权限,第三位表示对库存系统是否有权限。而方法中的int right参数则表示的是字符串的第几位。
上边这些搞明白之后,方法的编写就简单多了。
public class RightStore {
public String righString = \"\";
public boolean getRight(int right) {
//先求得第right个字符
char ch = righString.charAt(right - 1);
//如果ch为'1',返回true,否则返回false
return ch == '1';
}
public void setRight(int right, boolean value) {
//如果value为true,存储传入的权限,否则消除权限(改为空格)
righString.replace(righString.charAt(right - 1), value ? '1' : ' ');
}
}
636.二分法查询(递归实现)
思路说明:假设在一个已经排好序的有序序列(N个元素,升序排列),首先让序列中的中间的元素与需要查找的关键字进行比较,如果相等,则查找成功,否则利用中间位置将序列分成两个子序列,如果待查找的关键字小于中间的元素,则在前一个子序列中同样的方法进一步查找,如果待查找的关键字大于中间的元素,则在后一个子序列中同样的方法进一步查找,重复以上过程一直到查找结束!
import java.util.Scanner;
public class TestBinarySearchRecursion {
public static void main(String[] args) {
int[] a = { 1, 3, 5, 7, 9, 11, 13 };
System.out.print(\"请输入要查找的元素:\");
int e = new Scanner(System.in).nextInt();
int index = binarySearch(a, 0, a.length - 1, e);
System.out.println(index != -1 ? \"元素索引为\" + index : \"没有该元素\");
}
private static int binarySearch(int[] a, int low, int high, int e) {
int mid = 0;
if (low e) {
return binarySearch(a, low, mid - 1, e);
} else {
return binarySearch(a, mid + 1, high, e);
}
}
return -1;
}
}
637.编写一段Java程序,把一句英语中的每个单词中的字母次序倒转,单词次序保持不变,例入输入为“There is a dog.”,输出结果应该是“erehT si a god.”要求不使用Java的库函数,例如String类的split,reverse方法。
函数形如:
public static String reverseWords(String input) {
String str = \"\";
return str;
}
思路说明:将字符串转化成字符数组,然后根据数组中空格的位置判断每个单词所占的索引范围,根据得到的索引将数组中的每个单词逆序后拼接到新的字符串中。
public class TestStringReverse{
public static void main(String[] args) {
String input = \"There is a dog\";
System.out.println(\"逆转后的字符串为:\" + reverseWords(input));
}
public static String reverseWords(String input) {
String str = \"\";
//将字符串转化成字符数组
char[] arr = input.toCharArray();
//index用来记录每个单词的起始索引
int index = 0;
//遍历字符数组,将空格前边的单词挨个拼接到str中
for (int i = 0; i = index; j--){
str += arr[j];
}
//单词拼接完成后,拼接一个空格
str += ' ';
//让index指向下一个单词的起始位置
index = i + 1;
}
}
//将最后一个单词拼接上
for(int i = arr.length - 1; i >= index; i--){
str += arr[i];
}
return str;
}
}
638.手写9×9乘法表,冒泡排序
9×9乘法表:
class Demo {
public static void main(String[] args) {
for(int x = 0;x <= 9; x++) {
for(int y = 1;y <= x; y++) {
System.out.print(y+"*"+x+"="+x*y+"t");
}
System.out.println();
}
}
}
冒泡排序:
public class BubbleSort{
public static void main(String[] args){
int score[] = {67, 69, 75, 87, 89, 90, 99, 100};
for (int i = 0; i < score.length -1; i++){//最多做n-1趟排序
for(int j = 0 ;j < score.length - i - 1; j++){//对当前无序区间score[0......length-i-1]进行排序(j的范围很关键,这个范围是在逐步缩小的)
if(score[j] < score[j + 1]){ //把小的值交换到后面
int temp = score[j];
score[j] = score[j + 1];
score[j + 1] = temp;
}
}
System.out.print("第" + (i + 1) + "次排序结果:");
for(int a = 0; a < score.length; a++){
System.out.print(score[a] + "t");
}
System.out.println("");
}
System.out.print("最终排序结果:");
for(int a = 0; a < score.length; a++){
System.out.print(score[a] + "t");
}
}
}
639.题目: 给定一个整数数组,找到是否该数组包含任何重复数字。你的函数应该返回true只要有任何数字 在该数组中重复出现,否则返回false。
public class Solution {
public boolean containsDuplicate(int[] nums) {
Set numSet = new HashSet();
for(int i=0;i<nums.length;i++){·
if(numSet.contains(nums[i]))
return true;
else
numSet.add(nums[i]);
}
return false;
}
}
640.给定一个数组nums, 写一个函数来移动所有0元素到数组末尾,同时维持数组中非0元素的相对顺序不变。要求不能申请额外的内存空间,并且最小化操作次数。
public void moveZeroes(int[] nums) {
int size = nums.length;
int startIndex = 0;
// 0元素开始的位置
int endIndex = 0;
// 0元素结束的位置
int currentNum;
int i= 0;
// 第一步:找到第一个0元素开始的位置
// 并将第一个0元素的游标赋值给startIndex&endIndex
while(i < size){
currentNum = nums[i];
if (currentNum == 0) {
startIndex = i;
endIndex = i;
break;
}
++i;
}
// 如果当前数组中没有找到0元素,则推出
if (nums[endIndex] != 0)
return;
// 将当前i的值加1;直接从刚才0元素位置的后一位置开始循环
++i;
while (i < size) {
currentNum = nums[i];
if (currentNum == 0){//如果当前元素等于0,则将i值赋值给endIndex
endIndex = i;
} else {
// 如果不为0
//则将当前元素赋值给nums[startIndex]
// 并将当前位置的元素赋值为0
// startIndex和endIndex都加1;
nums[startIndex] = currentNum;
nums[i] = 0;
++startIndex;
++endIndex;
}
++i;
}
}
641.给定一颗二叉树,返回节点值得先序遍历,请使用迭代(非递归)方式实现。
public class Solution {
public List preorderTraversal(TreeNode root) {
List result = new ArrayList();
if(root == null)
return result;
Stack stack = new Stack();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
if(node.right != null)
stack.push(node.right);
if(node.left != null)
stack.push(node.left);
}
return result;
}
}
642.验证一棵树是否为有效的二叉搜索树BST
public class Solution {
private static int lastVisit = Integer.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
boolean judgeLeft = isValidBST(root.left); // 先判断左子树
if(root.data >= lastVisit && judgeLeft) { // 当前节点比上次访问的数值要大
lastVisit = root.data;
} else {
return false;
}
boolean judgeRight = isValidBST(root.right); // 后判断右子树
return judgeRight;
}
}
643.从一个链表中删除节点
题目: 写一个函数用于在一个单向链表中删除一个节点(⾮非尾节点),前提是仅仅能够访问要删除的那个节点。
比如给定链表1 -> 3 -> 5 -> 7 -> 9 -> 16,给定你值为3的那个节点, 调⽤用你的函数后,链表变为
1 -> 5 -> 7 -> 9 -> 16。
/**
Definition for singly-linked list.
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
* }
*/
public class Solution {
public void deleteNode(ListNode node) {
if(node==null||node.next==null) {
System.out.println(\"节点不存在或者是尾节点\");
}else{
node.val=node.next.val;
node.next=node.next.next;
}
}
}
644.二叉搜索树BST中第Kth小的元素 题目:给定⼀个BST,写一个函数kthSmallest来找到第kth小的元素
/**
Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
* }
*/
public class Solution2 {
public int kthSmallest(TreeNode root, int k) {
Stack store = new Stack();
if (root == null) {
return -1;
}
store.push(root);
while (root.left != null) {
store.push(root.left);
root = root.left;
}
while (!store.empty()) {
TreeNode cur = store.pop();
k--;
if (k == 0) {
return cur.val;
}
if (cur.right != null) {
root = cur.right;// let cur.right be the current node
store.push(root);
while (root.left != null) {
store.push(root.left);
root = root.left;
}
}
}
return -1;
}
}
645.题目:给定含有n个整数的数组S,S中是否存在三个元素a,b,c使得a + b + c = 0? 找到所有这样的三元 组,并且结果集中不包含重复的三元组。
646.子集问题
647.迭代方法实现二叉树的先序遍历:题目: 给定一颗⼆叉树,返回节点值得先序遍历,请使用迭代(非递归)方式实现。
648.验证二叉搜索树BST:题目: 验证一棵树是否为有效的二叉搜索树BST比如,二叉树[2, 1, 3],返回true二叉树[1, 2, 3], 返回false
649.编辑距离题目: 给定两个单词word1和word2,找到最小的操作步骤使得word1转换成word2,每次操作算作一 步。你可以对单词进行以下三种操作:1)插入一个字符2)删除一个字符3)替换一个字符
650.买卖股票问题:题目: 你有一个数组,第i个元素表示第i天某个股票的价格阶乘英文,设计一个算法找到最大的利润,并且你只能最多完成两次交易。
651.[编程]任给n个整数和一个整数x。请计算n个整数中有多少对整数之和等于x。
652.[编程]请说明快速排序算法的设计思想和时间复杂度,并用高级语言写出对整数数组进行一趟快排的函数实现。
653.对于一段形如:1,-1~3,1~15×3的输入
654.有两个字符串:目标串S=“s1s2…….sn”,模式串T=”t1t2…….tm”。若存在T的每个字符一次和S中的一个连续字符序列相等,则匹配成功,返回T中第一个字符在S中的位置。否则匹配不成功,返回0。写出你的算法,要求线性时间复杂度
655.如何生成一个0-100的随机整数?
656.请编写一段Java程序将两个有序数组合并成一个有序数组
657.在最佳情况下,以下哪个时间复杂度最高(D)
658.一个数组,元素为从0到m的整数,判断其中是否有重复元素,使用java语言编写一个方法
659.某二叉树的先序遍历是12453,中序遍历是42513,那么其后序遍历是(A)
660.设一颗二叉树中有3个叶子节点,有八个度为1的节点,则该二叉树中总的节点数为()
661.给出下面的二叉树先序、中序、后序遍历的序列?
662.你知道的排序算法都哪些?用Java写一个排序系统
663.写一个二分查找(折半搜索)的算法。
664.统计一篇英文文章单词个数。
665.输入年月日,计算该日期是这一年的第几天。
666.回文素数:所谓回文数就是顺着读和倒着读一样的数(例如:11,121,1991…),回文素数就是既是回文数又是素数(只能被1和自身整除的数)的数。编程找出11~9999之间的回文素数。
667.全排列:给出五个数字12345的所有排列。
668.对于一个有N个整数元素的一维数组,找出它的子数组(数组中下标连续的元素组成的数组)之和的最大值。
669.用递归实现字符串倒转
670.输入一个正整数,将其分解为素数的乘积。
671.一个有n级的台阶,一次可以走1级、2级或3级,问走完n级台阶有多少种走法。
672.写一个算法判断一个英文单词的所有字母是否全都不同(不区分大小写)
673.有一个已经排好序的整数数组,其中存在重复元素,请将重复元素删除掉,例如,A= [1, 1, 2, 2, 3],处理之后的数组应当为A= [1, 2, 3]。
674.给一个数组,其中有一个重复元素占半数以上,找出这个元素。
675.编写一个方法求一个字符串的字节长度?
第二篇:就业实战
第三篇:热门专业学习之路
第四篇:就业之路
学习更多JAVA知识与技巧,关注与私信博主(学习)免费学习领取JAVA 课件,源码,安装包,还有最新大厂面试资料等等等
1、本站资源针对会员完全免费,站点中所有资源大部分为投稿作者付费教程,切勿轻易添加教程上除本站信息外的任何联系方式,谨防被割,如有疑问请随时联系客服。
2、本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。