2018年7月

给定一个保存员工信息的数据结构,它包含了员工唯一的id,重要度 和 直系下属的id。

比如,员工1是员工2的领导,员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]],员工2的数据结构是[2, 10, [3]],员工3的数据结构是[3, 5, []]。注意虽然员工3也是员工1的一个下属,但是由于并不是直系下属,因此没有体现在员工1的数据结构中。

现在输入一个公司的所有员工信息,以及单个员工id,返回这个员工和他所有下属的重要度之和。

示例 1:

输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
输出: 11
解释:
员工1自身的重要度是5,他有两个直系下属2和3,而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11。
注意:

一个员工最多有一个直系领导,但是可以有多个直系下属
员工数量不超过2000。

解题关键在于:用递归实现找到当前id用for循环递归调用本身寻找相应的sub然后相加返回

/*
// Employee info
class Employee {
public:
    // It's the unique ID of each node.
    // unique id of this employee
    int id;
    // the importance value of this employee
    int importance;
    // the id of direct subordinates
    vector<int> subordinates;
};
*/
class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        for(auto v:employees){
            if(v->id == id){
                int ret = v->importance;
                for(auto s:v->subordinates){
                    ret+= this->getImportance(employees,s);
                }
                return ret;
            }
        }
    }
};

给定平面上 n 对不同的点,“回旋镖” 是由点表示的元组 (i, j, k) ,其中 i 和 j 之间的距离和 i 和 k 之间的距离相等(需要考虑元组的顺序)。

找到所有回旋镖的数量。你可以假设 n 最大为 500,所有点的坐标在闭区间 [-10000, 10000] 中。

示例:

输入:
[[0,0],[1,0],[2,0]]

输出:
2

解释:
两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

class Solution {
private:
    inline int distance(pair<int, int>& a, pair<int, int>& b){
        int x = a.first - b.first;
        int y = a.second- b.second;
        return x*x + y*y;
    }
    inline int count(int n){
        return n*(n-1);
    }
    
public:
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int n = points.size();
        int dis[n][n] = {0};
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                dis[i][j] = dis[j][i] = distance(points[i], points[j]);
            }
        }
        
        int ans = 0;
        for(int i = 0; i < n; i++){
            sort(dis[i], dis[i]+n);
            int cnt = 1;
            for(int j = 0; j < n-1; j++){
                if(dis[i][j] == dis[i][j+1]){
                    cnt++;
                }else{
                    ans += count(cnt);
                    cnt = 1;
                }
            }
            ans += count(cnt);
        }
        return ans;
    }
};

#include <iostream>
#include <vector>
using namespace std;

struct MaxSubArrayInfo{
    int left;
    int right;
    int sum;
};

MaxSubArrayInfo* FindMaxSubArray(vector<int> A,int low,int mid,int high){
    int left_sum = -INT_MAX;
    int sum = 0;
    int max_left = 0;
    for(int i = mid ;i<low;i--){
        sum += A[i];
        if(sum > left_sum){
            left_sum = sum;
            max_left = i;
        }
    }
    int right_sum = -INT_MAX;
    int max_right = 0;
    sum = 0;
    for(int j = mid+1;j<high;j++){
        sum = sum+A[j];
        if(sum > right_sum){
            right_sum = sum;
            max_right = j;
        }
    }
    return new MaxSubArrayInfo{
        max_left,
        max_right,
        left_sum+right_sum
    };
};

MaxSubArrayInfo* FindMaximumSubArray(vector<int> A,int low,int high){
    if(high == low){ //只有一个元素
        return new MaxSubArrayInfo{
            low,
            high,
            A[low]
        };
    }else{
        int mid = (low+high)/2;
        MaxSubArrayInfo*left = FindMaximumSubArray(A,low,mid);
        MaxSubArrayInfo*right = FindMaximumSubArray(A,mid+1,high);
        MaxSubArrayInfo*cross = FindMaxSubArray(A,low,mid,high);
        if(left->sum >= right->sum && left->sum >= cross->sum){
            return new MaxSubArrayInfo{
                left->left,
                left->right,
                left->sum
            };
        }else if(right->sum >= left->sum && right->sum >= cross->sum){
            return new MaxSubArrayInfo{
                right->left,
                right->right,
                right->sum
            };
        }else{
            return new MaxSubArrayInfo{
                cross->left,
                cross->right,
                cross->sum
            };
        }
    }
}

三个步骤:
1.分解 把问题分解成若干个子问题
2.解决 子问题分别解决
3.合并 解决之后进行合并

递归情况: 当子问题足够大时需要递归求解
基本情况:当子问题变得足够小的时候不再需要递归。

三种求解递归式的方法:
代入法
递归树法
主方法

编写一个算法来判断一个数是不是“快乐数”。

一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。如果可以变为 1,那么这个数就是快乐数。

示例:

输入: 19
输出: true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
解题关键在于维护一个set来判断每次的n之前是否存在过来防止无限循环!

class Solution {
public:
    bool isHappy(int n) {
        set<int> arr;
        while(n != 1 && arr.find(n) == arr.end()){
            arr.insert(n);
            int sum = 0;
            while(n){
                sum += pow(n%10,2);
                n /= 10;
            }
            n = sum;
        }
        return n == 1;
    }
};