2022最新算法分析及手写代码面试解析（已拿Offer）

淡泊习惯失眠 06-29 161

前言：

此时朋友们对“c语言回文素数编程”大概比较讲究，同学们都需要知道一些“c语言回文素数编程”的相关资讯。那么小编同时在网摘上网罗了一些关于“c语言回文素数编程””的相关内容，希望看官们能喜欢，看官们一起来了解一下吧！

算法分析及手写代码

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(index<=x){       if(str[index].equals(str[x])){        num++;       }       index++;      }      //该值出现了两次，说明重复了      if(num>1){       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.length-1-i; j++) {if (arr[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()<5||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的索引为midif (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.length - 1 - i; j++) {// 挨个进行比较: 从数组的第一个元素开始, 到无序数列的最后一个if (arr[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，否则返回falsereturn 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 <= high) {mid = (low + high) / 2;if (a[mid] == e) {return mid;} else if (a[mid] > 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 < arr.length; i++) {if(arr[i] == ' '){//根据空格的位置将空格前边一个单词密续追加到str中for(int j = i - 1; j >= 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.手写9x9乘法表，冒泡排序

9x9乘法表:

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<Integer> numSet = new HashSet<Integer>();        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<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();        if(root == null)            return result;        Stack<TreeNode> stack = new Stack<TreeNode>();        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<TreeNode> store = new Stack<TreeNode>();    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程序将两个有序数组合并成一个有序数组