虾皮秋招笔试三道编程题（2021-09-06）

淡淡的烟草味﹌ 2022-09-10 10:11 179阅读 0赞

> 通知：\**虾皮*、**华为**最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在微信公众号【TechGuide】了，私信公众号回复【虾皮】或者【华为】即可获得最实时、最详细的笔试题解啦！

### 文章目录 ###

*  第一道：字符串的全排列（100%）
 *   *  题目描述
     *  参考代码：
 *  第二道： 括号匹配（100%）
 *   *  题目描述
     *  参考代码
     *   *  Java版本
         *  CPP版本
 *  第三道：布尔运算（100%）
 *   *  题目描述
     *  参考代码
     *   *  Java版本

# 第一道：字符串的全排列（100%） #

## 题目描述 ##

给定一个字符串，输出这个字符串中所有字符的排列组合，参考剑指offer 38原题

**输入描述：**

"abc"

**输出描述：**

["abc","acb","bac","bca","cba","cab"]

## 参考代码： ##

ArrayList<String> ans=new ArrayList<>();
        public String[] permutation(String s) { 
            //判断一些特殊情况 否则只有90
            if(s==null||s.length()==0){ 
                return new String[0];
            }
            if(s.length()==1)
                return new String[]{ s};
            // write code here
            char[] ch=s.toCharArray();
            dfs(ch,0,"");
            return ans.toArray(new String[ans.size()]);
        }
    
        private void dfs(char[] ch, int cur,String s) { 
            if(cur==ch.length){ 
                ans.add(s);
                return;
            }
            for(int i=cur;i<ch.length;i++){ 
                swap(ch,cur,i);
                dfs(ch,cur+1,s+ch[cur]);
                swap(ch,cur,i);
            }
        }
        private void swap(char[] ch,int i,int j){ 
            char tmp=ch[i];
            ch[i]=ch[j];
            ch[j]=tmp;
        }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

# 第二道： 括号匹配（100%） #

## 题目描述 ##

给定一个只由0（假）、1（真）、&（逻辑与）、|（逻辑或）、^（异或）五种字符组成的字符串express，再给定一个布尔值desired。返回express能有多少种组合方式，可以达到desired的结果。

**输入描述：**

express="1^0|0|1"，
    desired=false

**输出描述**

**解释:**  
只有1 ^ ((0|0)|1) 和 1^(0|(0|1)) 的组合可以得到 false，返回2。

## 参考代码 ##

1）这个问题是一个“加括号”问题，和矩阵连乘的计算过程类似，但是要比后者复杂很多。

2）问题的难点在于找出“状态”和“递推式”，因为状态不是唯一的，是和输入的desired有关系。

3）但是我们可以确定的是，只有两种状态，那就是表达式为真的数目和表达式为假的数目，令t\[i\]\[j\]为从 i 到 j 表达式为真的数目，f\[i\]\[j\]为表达式为假的数目。

4）初始状态：i==j，如果express\[j\]==1，那么t\[j\]\[j\]=1;f\[j\]\[j\]=0;如果express\[j\]==0，t\[j\]\[j\]=0;f\[j\]\[j\]=1。

递推状态：i！=j，t[i][j]和f[i][j]的计算之间有依赖的关系，而且和具体的运算符也有关系，拿“|”（或运算）来举例，真=真*真+真*假+假*真，假=假*假（或运算法则），也就是t[i][j]=t[i][k]*t[k+2][j]+t[i][k]*f[k+2][j]+f[i][j]*t[k+2][j]，其中i<=k<j,k+=2。

5）这个题目的思路和纸牌博弈问题类似，都是两个状态，而且互相对立，互相依赖。

### Java版本 ###

public long GetNumOfExpress(String express, boolean desired) { 
            // write code here
    
            if (express==null || express.length()==0 || !isValid(express.toCharArray())){ 
                return 0;
            }
            char[] str = express.toCharArray();
            int len = str.length;
            long[][] dpTrue = new long[len][len];
            long[][] dpFalse = new long[len][len];
            if (str[0]=='0'){ 
                dpTrue[0][0] = 0;
                dpFalse[0][0] = 1;
            }
            else { 
                dpTrue[0][0] = 1;
                dpFalse[0][0] = 0;
            }
    
            // 区间dp
            for (int j=0;j<len;j+=2){ 
                if (str[j]=='0'){ 
                    dpTrue[j][j] = 0;
                    dpFalse[j][j] = 1;
                }
                else { 
                    dpTrue[j][j] = 1;
                    dpFalse[j][j] = 0;
                }
                for (int i=j-2;i>=0;i-=2){ 
                    for (int k=i+1;k<j;k+=2){ 
                        if (str[k]=='&'){ 
                            dpTrue[i][j] += dpTrue[i][k-1]*dpTrue[k+1][j];
                            dpFalse[i][j]+= dpTrue[i][k-1]*dpFalse[k+1][j]+dpFalse[i][k-1]*dpTrue[k+1][j]+dpFalse[i][k-1]*dpFalse[k+1][j];
                        }
                        else if (str[k]=='|'){ 
                            dpTrue[i][j] += dpTrue[i][k-1]*dpTrue[k+1][j] + dpTrue[i][k-1]*dpFalse[k+1][j] + dpFalse[i][k-1]*dpTrue[k+1][j];
                            dpFalse[i][j] += dpFalse[i][k-1]*dpFalse[k+1][j];
                        }
                        else { 
                            dpTrue[i][j] += dpTrue[i][k-1]*dpFalse[k+1][j] + dpFalse[i][k-1]*dpTrue[k+1][j];
                            dpFalse[i][j] += dpTrue[i][k-1]*dpTrue[k+1][j] + dpFalse[i][k-1]*dpFalse[k+1][j];
                        }
                    }
                }
            }
            if (desired)
                return dpTrue[0][len-1];
            else
                return dpFalse[0][len-1];
        }
    
        private boolean isValid(char[] str){ 
            boolean flag = true;
            for (char c:str){ 
                if (flag){ 
                    if (c!='0' && c!='1')
                        return false;
                    flag = false;
                }
                else { 
                    if (c!='|' && c!='&' && c!='^')
                        return false;
                    flag = true;
                }
            }
            if (flag)
                return false;
            return true;
        }
        // 关注TechGuide！ 大厂笔经面经闪电速递！

### CPP版本 ###

#include<iostream>
    #include<vector>
    #include<string>
     
    using namespace std;
    int getResult(string, string);
    int main() { 
    	string str,desired;
    	cin >> str >> desired;
    	cout << getResult(str, desired) << endl;
    }
    int getResult(string str, string desired) { 
    	int len = str.length();
    	//判断字符串是否有效
    	if (len % 2 == 0)
    		return -1;
    	int i, j, k;
    	vector<vector<int>> t(len, vector<int>(len)), f(len, vector<int>(len));//t[i][j]代表从str[i]到str[j]值为true的个数，f[i][j]代表为false的数目
    	for (j = 0; j < len; j += 2) { 
    		if (str[j] == '1') { 
    			t[j][j] = 1;
    			f[j][j] = 0;
    		}
    		else if (str[j] == '0') { 
    			t[j][j] = 0;
    			f[j][j] = 1;
    		}
    		else return -1;
    		cout << j << "行 " << j << "列 真:" << t[j][j] << " 假： " << f[j][j] << endl;
    		for (i = j - 2; i >= 0; i -= 2) { //计算的顺序是先计算列，再从下向上
    			for (k = i; k < j; k += 2) { //k从i遍历到j，类似于矩阵连乘，这个是一个累加
    				//cout << "K的值：" << k << endl;
    				switch (str[k + 1]) { 
    				case '|':t[i][j] += t[i][k] * (t[k + 2][j] + f[k + 2][j]) + f[i][k] * t[k + 2][j];
    					f[i][j] += f[i][k] * f[k + 2][j];
    					break;//如果是或，那么只要两边有任意一个真，那么结果就是真；用乘法的原因是假设左边有m种组合，右边有n种组合，那么总的组合方案数目就是m*n种
    				case '&':t[i][j] += t[i][k] * t[k + 2][j];
    					f[i][j] += f[i][k] * (t[k + 2][j] + f[k + 2][j]) + t[i][k] * f[k + 2][j];
    					break;
    				case '^':t[i][j] += t[i][k] * f[k + 2][j] + f[i][k] * t[k + 2][j];
    					f[i][j] += t[i][k] * t[k + 2][j] + f[i][k] * f[k + 2][j];
    					break;
    				default: return -1;
    				}
    			}//end for k
    			cout << i << "行 " << j << "列 真:" << t[i][j] << " 假： " << f[i][j] << endl;
    		}//end for i
    	}//end for j
    	return desired == "false" ? f[0][len - 1] : t[0][len - 1];
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

# 第三道：布尔运算（100%） #

## 题目描述 ##

给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成。实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。【参考力扣 面试题08.14】

**输入描述：**

s = "1^0|0|1", result = 0

**输出描述：**

**解释:**  
两种可能的括号方法是

1^(0|(0|1))
    1^((0|0)|1)

## 参考代码 ##

### Java版本 ###

class Solution { 
        public int countEval(String s, int result) { 
            int n = s.length();
            int[][][] dp = new int[n][n][2];
            // dp[i][j][0] 表示从i到j的子串运算结果为0的可能的方法数
            for(int i = 0; i < n; i += 2){ // 子串长度为 1 时的结果
                dp[i][i][0] = s.charAt(i) == '0' ? 1:0;
                dp[i][i][1] = s.charAt(i) == '1' ? 1:0;
            }
            for(int len = 3; len <= n; len += 2){ // len表示每一段的长度,只有len是奇数才是符合要求的，即有n个数字的话必有n-1个运算符
                for(int i = 0; i+len <= n; i += 2){ // i表示起始坐标，数字只在偶数位
                    int j = i + len -1;// j 表示终止坐标,则j < n, 即 i+len-1 < n 即, i+len <= n
                    for(int k = i+1; k < j; k += 2){ 
                        switch(s.charAt(k)){ 
                            case '&':
                                dp[i][j][0] += dp[i][k-1][0]*dp[k+1][j][0];// 0 & 0 = 0
                                dp[i][j][0] += dp[i][k-1][1]*dp[k+1][j][0];// 1 & 0 = 0
                                dp[i][j][0] += dp[i][k-1][0]*dp[k+1][j][1];// 0 & 1 = 0
                                dp[i][j][1] += dp[i][k-1][1]*dp[k+1][j][1];// 1 & 1 = 1
                                break;
                            case '|':
                                dp[i][j][0] += dp[i][k-1][0]*dp[k+1][j][0];// 0 | 0 = 0
                                dp[i][j][1] += dp[i][k-1][1]*dp[k+1][j][0];// 1 | 0 = 1
                                dp[i][j][1] += dp[i][k-1][0]*dp[k+1][j][1];// 0 | 1 = 1
                                dp[i][j][1] += dp[i][k-1][1]*dp[k+1][j][1];// 1 | 1 = 1
                                break;
                            case '^':
                                dp[i][j][0] += dp[i][k-1][0]*dp[k+1][j][0];// 0 ^ 0 = 0
                                dp[i][j][1] += dp[i][k-1][1]*dp[k+1][j][0];// 1 ^ 0 = 1
                                dp[i][j][1] += dp[i][k-1][0]*dp[k+1][j][1];// 0 ^ 1 = 1
                                dp[i][j][0] += dp[i][k-1][1]*dp[k+1][j][1];// 1 ^ 1 = 0
                                break;
                        }
                    }
                }
            }
            return dp[0][n-1][result];
        }
    }

> 恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。