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);
}

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);
}