1.计算字符串的编辑距离【动态规划编程题】

import java.util.Scanner;
import  java.io.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String args[])  throws Exception{BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String str1 ;while((str1=reader.readLine())!=null){String str2 = reader.readLine();System.out.println(getDistance(str1,str2));}}public  static int getDistance(String str1, String str2) {char[] ch1 = str1.toCharArray();char[] ch2 =  str2.toCharArray();int len1  = ch1.length;int  len2  = ch2.length;//定义一个矩阵int[][] dist = new  int[len1 + 1][len2 + 1];//初始状态 F(i,0) = i F(0,j) = jfor (int i = 0; i <= len1; ++i) {dist[i][0] = i;}for (int j = 0; j <= len2; ++j) {dist[0][j] = j;}for (int i = 1; i <= len1; ++i) {for (int j = 1; j <= len2; ++j) {//F[i,j] = min(F(i-j,j)+1,F(i,j-1)+1,F(i-1,j-1)+(ch1[i]==ch2[j]?0:1))//          插入           删除                替换dist[i][j] = Math.min(dist[i - 1][j] + 1, dist[i][j - 1] + 1);//在和替换比较if (ch1[i - 1] == ch2[j - 1]) {dist[i][j] = Math.min(dist[i ][j], dist[i - 1][j - 1]);} else {dist[i][j] = Math.min(dist[i ][j], dist[i - 1][j - 1]+1);}}}return dist[len1][len2];}
}

2.微信红包

import java.util.*;public class Gift {public int getValue(int[] gifts, int n) {// write code hereint mid = gifts.length / 2;int count = 0;for (int i = 0; i < gifts.length; i++) {if (gifts[i] == gifts[mid]) {count++;}}if (count > mid) {return gifts[mid];}return 0 ;}
}

3.找出字符串中第一个只出现一次的字符

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);String str = in.nextLine();int[] arr = new int[str.length()];for(int i=0;iarr[i]= count(str,str.charAt(i));}for(int j =0;jif(arr[j]==1){System.out.println(str.charAt(j));break;}if(none(arr)==-1){System.out.println(-1);break;}}}public  static int none(int[] arr){int count = 0;for(int i= 0;iif(arr[i]!=1){count++;}}if(count==arr.length){return -1;}return 0;}public  static int count(String str,char ch){int count = 0;for(int i =0;iif(str.charAt(i)==ch){count++;}}return count;}
}

4.小易的升级之路

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextInt()) { // 注意 while 处理多个 caseint n = in.nextInt();int c = in.nextInt();int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = in.nextInt();}for (int i = 0; i < n; i++) {if (arr[i] <= c) {c += arr[i];} else {c += zdgy(c, arr[i]);}}System.out.println(c);}}public static int zdgy(int c, int arr) {for (int i = c; i > 0; i--) {if (arr % i == 0 && c % i == 0) {return i;}}return 0 ;}
}

4.数据结构中具有记忆功能的是【栈】

下列数据结构具有记忆功能的是? C
A. 队列 B. 循环队列 C. 栈 D. 顺序表
记忆功能比如, 浏览器的回退功能,文本编辑器的撤销功能,都属于记忆功能
栈的LIFO特性,A函数调用B函数,B函数调用C函数,然后最后一层一层返回,这也具有记忆功能

5.递归程序的优化一般为 【尾递归优化】

对递归程序的优化的一般的手段为(A)A. 尾递归优化       B. 循环优化        C. 堆栈优化            D. 停止值优化比如快速排序和归并排序,在递归的终止条件是 l 是区间最左侧,r 是区间最右侧//终止条件(l >= r){return ;}//在递归终止条件处进行优化//当区间个数较小时,采用插入排序来优化(r - l <= 15)  --->  采用插入排序所以这种对递归的优化一般都是 尾递归优化

6.时间复杂度的判断

A 红黑树插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(logn)
B B+树插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(logn)
C Hash表插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(n)
D 排序链表插入操作的平均时间复杂度为O(n)，最坏时间复杂度为O(n)

由图可知，Hash表插入操作的平均时间复杂度为O(1)，最坏时间复杂度为O(1)

7.为提高散列（Hash）表的查找效率，可以采取的正确措施是（II,III ）

Ⅰ．增大装填（载）因子
Ⅱ．设计冲突（碰撞）少的散列函数
Ⅲ．处理冲突（碰撞）时避免产生聚集（堆积）现象

散列表的查找效率取决于：散列函数、处理冲突的方法和装填因子。 冲突的产生概率与装填因子成正比，故错。
采取合适的冲突处理方法可以避免聚集现象，也提高查找效率。