Google软件工程实习生，2019年秋季–北美 _实习生

1.考虑N个顶点的二叉树, 使得节点k的子代为2 * k和2 * k + 1。顶点1是树的根, 每个节点都有一个与之关联的整数值。
通过写下来自连续节点的值, 这样的树可以表示为N个整数的数组。
该树可以表示为数组[-1、7、0、7, -8]。
如果该节点与根x-1之间的最短路径长度为该节点, 则称该节点处于x级别。因此, 根在1级, 根的子级在2级, 依此类推。
你的任务是找到最小的级别数x, 以使级别x的所有节点的总和最大。
示例：给定数组A, 使得：A [0] =-1, A [1] = 7, A [2] = 0, A [3] = 7, A [4] =-8。该函数应返回2。

Input : [-1, 7, 0, 7, -8] Output : 2

#include < iostream> using namespace std; int solution( int a[], int n) { int max = -1; int temp = 0; for ( int i = 0; i < n; i = i + 2) { if (i == 0) temp = a[i]; else temp = a[i] + a[i - 1]; if (temp> max) max = i; } return max; }int main() { int a[4]; a[0] = -1, a[1] = 7, a[2] = 0, a[3] = 7, a[4] = -8; int size = 4; cout < < solution(a, size); }

【Google软件工程实习生，2019年秋季–北美】2.假设你有一个特殊的键盘, 其中所有键都位于一行中。键盘上字符的布局由长度为26的字符串S1表示。S1的索引从0到25。最初, 你的手指在索引0处。要键入一个字符, 必须将手指移至键盘的索引处。所需的字符。将手指从索引i移到索引j所需的时间是| j-i |, 其中||表示绝对值。
编写一个函数solution(), 给定一个描述键盘布局的字符串S1和一个字符串S2, 该函数返回一个整数, 该整数表示键入字符串S2所花费的时间。
例子：
S1 = abcdefghijklmnopqrstuvwxyz
S2 = cba

Input : S1 = abcdefghijklmnopqrstuvwxyz, S2 = cba Output : 4

#include < bits/stdc++.h> using namespace std; int solution(string& s1, string& s2) { map< char , int> dict; for ( int i = 0; i < 26; i++) { dict[s1[i]] = i; } int ans = 0; int prev = 0; for ( int i = 0; i < s2.length(); i++) { ans = ans + abs (dict[s2[i]] - prev); prev = dict[s2[i]]; } return ans; }int main() { string s1 = "abcdefghijklmnopqrstuvwxyz" ; string s2 = "cba" ; cout < < solution(s1, s2); }