您现在的位置是:首页 > 正文

测试开发工程师面试总结(二)——算法篇

2024-02-01 00:53:04阅读 1

算法也属于常见面试内容之一,但基本不会超过《剑指offer》的范围,在此附上一篇简书上整理的内容:
第二版java解法
常见的面试题包括以下几类:字符串操作,文件输入输出流及统计,矩阵操作,单例模式等。

1.针对字符串的操作:如字符串反转、字符串去重、含有左右括号的字符串匹配。

含有左右括号的字符串匹配的题目及代码如下:

给定一个字符串,其中的字符只包含三种括号:花括号{ }、中括号[ ]、圆括号( ),即它仅由 “( ) [ ] { }” 这六个字符组成。设计算法,判断该字符串是否有效,即字符串中括号是否匹配。括号匹配要求括号必须以正确的顺序配对,如 “{ [ ] ( ) }” 或 “[ ( { } [ ] ) ]” 等为正确的格式,而 “[ ( ] )” 或 “{ [ ( ) }” 或 “( { } ] )” 均为不正确的格式。

/**
 * 栈的先入后出,非常适合作为括号匹配的对象 思路:将所有的左括号类型入栈,出现一个匹配的右括号即出栈
 * 如果最后栈为空则完全匹配;如果最后栈非空则不匹配
 */
public class MatchString {

       public static boolean isMatchStr(String s){
              if(s==null || s.length()<1) return false;
              Stack<Character> stack=new Stack<>();
              char c;
              boolean flag=true;
              int cnt=0;
              for(int i=0;i<s.length();i++){
                     c=s.charAt(i);
//              入栈规则
              if(c=='(' || c=='[' || c=='{'){
                     stack.push(c);
                     cnt++;
                     continue;
              }
//              过滤非括号的无关字符串
            if(c!='(' && c!='[' && c!='{' && c!=')' && c!=']' && c!='}') continue;
//              出栈规则
              if(stack.isEmpty()||!isMatch(c,stack.peek())) return false;
              if (!stack.isEmpty() && isMatch(c, stack.peek())) {
                            stack.pop();
                            cnt++;
                            continue;
                     }

              }
              if(!stack.isEmpty()) return false;
              return flag;
       }

       private static boolean isMatch(char right, char left) {
              if(right==')')
                     return left=='(';
              if(right==']')
                     return left=='[';
              if(right=='}')
                     return left=='{';
              return false;
       }

       public static void main(String[] args) {
              String s1="({{123}})";
              String s2="}}}}}{{{{";
              String s3="((111111({{}}})))";
              System.out.println(isMatchStr(s1));
              System.out.println(isMatchStr(s2));
              System.out.println(isMatchStr(s3));

       }
}

字符串反转在剑指offer上也能找到类似的题目,反转单词顺序:

输入一个英文句子,翻转单词顺序,单词内字符不翻转,标点符号和普通字母一样处理。例如输入输入“I am a student.”,则输出“student. a am I”。

/**
 * 先对所有字符串进行反转,之后按照空格分隔开,再对单个单词进行反转。
 */
public class ReverseWordsInSentence {

       public static String reverseStr(String str){
              if(str==null || str.length()<=1) return str;
              Stack<Character> stack=new Stack<>();

              StringBuffer stringBuffer=new StringBuffer();
              for(int i=0;i<str.length();i++){
                      stack.push(str.charAt(i));

              }
              for(int i=0;i<str.length();i++){
                      stringBuffer.append(stack.pop());
              }
              System.out.println(stringBuffer.toString());
              String[] strings=stringBuffer.toString().split(" ");
              stringBuffer.setLength(0); 
              for(int i=0;i<strings.length;i++){
                     stringBuffer.append(reverseWord(strings[i]));
                     stringBuffer.append(" ");
              }
              return stringBuffer.toString();

       }
       public static String reverseWord(String s){
              StringBuffer stringBuffer=new StringBuffer();
              if(s==null || s.length()<=1) return s;
              Stack<Character> stack=new Stack<>();
              for(int i=0;i<s.length();i++){
                     stack.push(s.charAt(i));
              }
              while(!stack.isEmpty()){
                     stringBuffer.append(stack.pop());
              }
              return stringBuffer.toString();
       }

       public static void main(String[] args) {
              String str="I am a student.";
              System.out.println(reverseStr(str));
       }
}

查找字符串重复问题因为会用到哈希也常被放在面试中。

找出给定字符串中第一个不重复的字母。例如:abcccaddd,第一个不重复的字母是b。

public class FirstNotRepeatingChar {
       public static char firstNotRepeatChar(String str){
//              256个字母
              char temp=str.charAt(0);
              int[] hashTimes=new int[256];
              for(int i=0;i<str.length();i++){
                     hashTimes[str.charAt(i)]++;
              }
              for (int i=0;i<str.length();i++){
                     if(hashTimes[str.charAt(i)]==1)
                            return str.charAt(i);
              }
              return '\77';
       }

       public static void main(String[] args) {
              System.out.println(firstNotRepeatChar("aaaaaaaaaaaaaa"));

       }
}
2. 文件输入流考察:文件读入并统计某个字符的值。
3. 矩阵(二维数组)考察:矩阵的的顺时针打印、顺时针90度等。
4. 递归考察:其实递归是很容易考察到的一个点,我因为这块薄弱挂掉了某厂。把两个典型的递归的方法在这里写一下,希望大家也能有所启发。递归重要的点一定是去找结束条件以及对应的返回值,多做几个题目就熟练了。

1.求1的阶乘到n的阶乘的和。

public class GetSumFactorial {
       public static long getAddFactorial(long n){
              if(n<=0) return -1;
              long sum=0,start=1,end=n;
              long mid;
              while (start<=end){
                     sum+=getSingleFactorial(end);
                     end--;

              }
              return sum;
       }

       private static long getSingleFactorial(long i) {
              if(i<1) return -1;
              if(i==1) return 1;
              return getSingleFactorial(i-1)*i;
       }


       public static void main(String[] args) {
              System.out.println(getAddFactorial(4));
              // 异常值 如果n比较大的时候,递归消耗内存就会导致程序启动报栈溢出异常,这个时候可以通过设置jvm的参数-Xss512k来解决这个问题 (如果主动考虑到这个 可以作为面试中的加分项哦)       System.out.println(getAddFactorial(100000));

       }
}

2.给一个有序排列的整数数组a[n],整数数组有且仅有一个值缺失,求当前缺失的值。例子 a[10]={0,1,2,3,5,6,7,8,9,10},返回缺失的值为4.
其中,方法一和方法二都是递归的思路,只不过方法一是用了二分法求和的递归思路,方法二是利用数组的特点进行递归,递归仍然使用二分的思想。

public class QueryLackedInt {
       //       方法一:根据数组特性即可求出缺失的值
       public static int getNum1(int[] data) {
              if (data == null || data.length == 0) return -1;
              if (data[0] != 0) return 0;
              int len = data.length;
              int sum1 = getSum(data, 0, len - 1);
              int sum2 = (len + 1) * (data[0] + data[len - 1]) / 2;
              return sum2 - sum1;
       }

       public static int getSum(int[] data, int low, int high) {
              if (data == null || data.length == 0) return -1;
              if (low == high) {
                     return data[low];
              } else {
                     int mi = (low + high) >> 1;
                     return getSum(data, low, mi) + getSum(data, mi + 1, high);
              }
       }

       //       方法二:使用两个指针进行递归
       public static int getNum2(int[] data) {
              if (data == null || data.length == 0) return -1;
              if (data.length >= 1 && data[0] != 0) return 0;
              return getRecursion(data, 0, data.length-1);
       }

       private static int getRecursion(int[] data, int left, int right) {
              int mid = (left + right) / 2;
              if (right == left && data[left] != left) return left;
              if (data[mid] == mid) {
                    return getRecursion(data, mid+1, right);
              } else {
                  return   getRecursion(data, left, mid);
              }
       }

       public static void main(String[] args) {
              int[] a = {0, 1, 2, 3, 4, 5, 6, 7,  9, 10, 11, 12,13, 14, 15};
              int[] b = null;
              int[] c = {1, 2};
              System.out.println(getNum1(a));
              System.out.println(getNum1(b));
              System.out.println(getNum1(c));
              System.out.println(getNum2(a));
              System.out.println(getNum2(b));
              System.out.println(getNum2(c));


       }
}
5. 常见的排序算法,冒泡、选择、快速、归并、堆排序等算法要会,而且时间复杂度和空间复杂度的分析要会。
6. 单例模式:但凡要考察并发的使用,一般会要求写单例模式,注意懒汉模式、饿汉模式;线程安全、线程不安全的单例模式;以及双重校验,单例模式最好的实现是枚举实现,举出枚举实现的例子并且讲出原理。
7. 考察二叉树、红黑树等。

网站文章

  • 适合 Go 新手学习的开源项目——在 GitHub 学编程

    适合 Go 新手学习的开源项目——在 GitHub 学编程

    作者:HelloGitHub-小鱼干&amp;卤蛋 故事要从 2007 年说起。因为受够了 C++ 煎熬的 Google 首席软件工程师 Rob Pike 召集 Robert Griesemer 和 ...

    2024-02-01 00:52:57
  • 怎么制作gif动态图 QQ动态表情包怎么制作

    怎么制作gif动态图 QQ动态表情包怎么制作

    在平时的聊天中经常会使用到GIF动图,不仅仅可以缓解气氛,还很有趣,那这些动态图是如何制作的呢?没有想象的那么难,今天来看看怎么制作的吧! 1、先准备好素材,要制作什么样的动图,可以是图片也可以是...

    2024-02-01 00:52:50
  • 系统架构设计专业技能 · 系统工程与系统性能

    系统架构设计专业技能 · 系统工程与系统性能

    系统工程的生命周期阶段包括。

    2024-02-01 00:52:42
  • java 接口bean_详解Spring中接口的bean是如何注入的

    java 接口bean_详解Spring中接口的bean是如何注入的

    java 接口bean_详解Spring中接口的bean是如何注入的

    2024-02-01 00:52:14
  • Tomcat的使用

    Tomcat的使用

    Tomcat下载tomcat官网:http://tomcat.apache.org安装直接将下载的tomcat压缩包解压即可*注意:此处建议不要安装在有空格或中文目录下卸载直接将解压的文件删除即可目录解析(apache开源项目通用结构)bin 可执行文件conf 配置文件lib 依赖j...

    2024-02-01 00:52:06
  • P4145 上帝造题的七分钟2 / 花神游历各国 (线段树区间开方)

    题目链接:点击这里 题目大意: 给定一个长度为 nnn 的序列 a1,a2,...,ana_1,a_2,...,a_na1,a2,...,an ,对序列进行区间开方和区间查询 题目分析: 因为 1≤a...

    2024-02-01 00:51:59
  • 使用标准输出流(system.out)和打印流 (PrintWriter)来读取txt文件

    在电脑某盘根目录下放一个文本文件.里面写一首诗(内容随意发挥).把诗的内容输出到控制台. 要求: 1.使用标准输出流(system.out)来做。 2.使用打印流; (PrintWriter)来做。 import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.FileReade

    2024-02-01 00:51:29
  • js:输出指定范围内所有自幂数

    4.输出指定范围内所有自幂数

    2024-02-01 00:51:21
  • 解决计算机不能登陆银行网银、邮箱、支付宝、淘宝等问题

    <br />  解决计算机不能登陆银行网银、邮箱、支付宝、淘宝等问题,本人使用了网上多个版本,以下操作才是王道,其余的诸如,重新启动“shell。dll”等,均不能解决,而且降低电脑的安全性。<br /> <br />  开始-运行-输入regsvr32 jscript.dll-确定,然后注册regsvr32 vbscript.dll。

    2024-02-01 00:51:13
  • 移植net-snmp到GSC3280

    移植net-snmp到GSC32801. 概念SNMP 是专门设计用于在 IP 网络管理网络节点(服务器、工作站、路由器、交换机及 HUBS 等)的一种标准协议,它是一种应用层协议。 SNMP 使网络管理员能够管理网络效能,发现并解决网络问题以及规划网络增长。通过 SNMP 接收随机消息(及事件报告)网络管理系统获知网络出现问题。SNMP 管理的网络有三个主要组成部分:管理的设备、代理...

    2024-02-01 00:50:43