58同城笔试：后端开发编程题

1.找出二维字符数组里行字符数组所共有的字符

例子：
输入：{{“you”,“are”,“pig”,“dog”},{“is”,“as”,“you”,“are”},{“kik”,“you”,“are”,“aoa”}}
输出：{“you”,“are”}

class Solution {
public:
	/**
	 *
	 * @param values string字符串二维数组
	 * @param valuesRowLen int values数组行数
	 * @param valuesColLen int* values数组列数
	 * @return string字符串vector
	 */
	vector<string> findCommonString(string** values, int valuesRowLen, int* valuesColLen) {
		// write code here
		vector<string> ans;
		unordered_map<string, int> m;
		for (int i = 0; i < valuesRowLen; ++i) {
			for (int j = 0; j < *valuesColLen; ++j) {
				++m[values[i][j]];
			}
		}
		for (int j = 0; j < *valuesColLen; ++j) {
			if (m[values[0][j]] == valuesRowLen)
				ans.push_back(values[0][j]);
		}
		return ans;
	}
};

只AC了60，提示段错误，但是不知道哪会出现，忘热心老哥解答下。

2.给一个数，它加上a是完全平方数，加上b也是完全平方数，这个数是多少？

输入：a=100, b=200
输出：476

class Solution {
public:
	/**
	 *
	 * @param a int整型
	 * @param b int整型
	 * @return int整型
	 */
	int question(int a, int b) {
		// write code here
		long long ans = 0;
		while (!isValid(ans, a) || !isValid(ans, b))
			++ans;
		return ans;
	}

	bool isValid(long long ans, int a) {
		long long val = ans + a;
		int pre = 0, last = val / 2;
		while (pre <= last) {
			int mid = (pre + last) / 2;
			if (pow(mid, 2) == val)
				return true;
			if (pow(mid, 2) > val)
				last = mid - 1;
			else
				pre = mid + 1;
		}
		return false;
	}
};

第一眼就想到了二分暴力搜寻，竟然直接过了…

3.破译密码，给一个数，其中的数位可以翻译成“a-z”，对应每一位“0~25”，问有几种翻译方式。

输入：112
输出：3：1,1,2 11,2 1,12

class Solution {
public:
	/**
	 * 翻译组合数
	 * @param num int整型 数字加密报文
	 * @return int整型
	 */
	int translateNum(int num) {
		// write code here
		string strNum = to_string(num);
		int n = strNum.size();
		vector<int> dp(n+1);
		dp[0] = 1;
		dp[1] = 1;
		for (int i = 2; i <= n; ++i) {
			dp[i] = dp[i - 1] + isValid(strNum, i - 2)*dp[i - 2];
		}
		return dp[n];
	}

	int isValid(string &str, int i) {
		string ans = str.substr(i, 2);
		int res = stoi(ans);
		if (res >= 10 && res <= 25)
			return 1;
		return 0;
	}
};

当时直接dp数组存，也直接过了，所以没优化了。