690. Employee Importance ---------E

You have a data structure of employee information, including the employee's unique ID, importance value, and direct subordinates' IDs.

You are given an array of employees employees where:

• employees[i].id is the ID of the ith employee.
• employees[i].importance is the importance value of the ith employee.
• employees[i].subordinates is a list of the IDs of the direct subordinates of the ith employee.

Given an integer id that represents an employee's ID, return the total importance value of this employee and all their direct and indirect subordinates.

 

Example 1:

Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
Output: 11
Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3.
They both have an importance value of 3.
Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.

Example 2:

Input: employees = [[1,2,[5]],[5,-3,[]]], id = 5
Output: -3
Explanation: Employee 5 has an importance value of -3 and has no direct subordinates.
Thus, the total importance value of employee 5 is -3.

 

Constraints:

• 1 <= employees.length <= 2000
• 1 <= employees[i].id <= 2000
• All employees[i].id are unique.
• -100 <= employees[i].importance <= 100
• One employee has at most one direct leader and may have several subordinates.
• The IDs in employees[i].subordinates are valid IDs.

A:

-------------------就是用HashMap ---------记得map[E->id] = E;  而不是map[E->id] = E->importance -------------

直接用递归

/*

// Definition for Employee.

class Employee {

public:

int id;

int importance;

vector<int> subordinates;

};

*/

class Solution {

public:

int getImportance(vector<Employee*> employees, int id) {

unordered_map<int, Employee*> M;

for (auto e : employees) {

M[e->id] = e;

}

int res = 0;

dfs(M, res, id);

return res;

}

private:

void dfs(unordered_map<int, Employee*>& M, int& res, int id) {

res += M[id]->importance;

for (auto idx : M[id]->subordinates) {

dfs(M, res, idx);

}

}

};

---------------- 尝试不用递归，用queue来保存刚发现的，待检查的。

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/
class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, Employee*> M;
        for (auto e : employees) {
            M[e->id] = e;
        }
        int res = 0;
        queue<int> Q;
        Q.push(id);
        while (not Q.empty()) {
            auto idx = Q.front();
            Q.pop();
            res += M[idx]->importance;
            for (auto v : M[idx]->subordinates)
                Q.push(v);
        }
        return res;
    }
};

学到了，

哎， map.find(curID)->second->importance

记得是 ->second

748. Shortest Completing Word -----------E

Q:

Find the minimum length word from a given dictionary words, which has all the letters from the string licensePlate. Such a word is said to complete the given string licensePlate

Here, for letters we ignore case. For example, "P" on the licensePlate still matches "p" on the word.

It is guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array.

The license plate might have the same letter occurring multiple times. For example, given a licensePlate of "PP", the word "pair" does not complete the licensePlate, but the word "supper" does.

Example 1:

Input: licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
Output: "steps"
Explanation: The smallest length word that contains the letters "S", "P", "S", and "T".
Note that the answer is not "step", because the letter "s" must occur in the word twice.
Also note that we ignored case for the purposes of comparing whether a letter exists in the word.

Example 2:

Input: licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
Output: "pest"
Explanation: There are 3 smallest length words that contains the letters "s".
We return the one that occurred first.

Note:

1. licensePlate will be a string with length in range [1, 7].
2. licensePlate will contain digits, spaces, or letters (uppercase or lowercase).
3. words will have a length in the range [10, 1000].
4. Every words[i] will consist of lowercase letters, and have length in range [1, 15].

A:

class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        vector<int> A(26,0);
        for(char ch:licensePlate)
            if(isalpha(ch))
                A[tolower(ch)-'a']+=1;
        string res=licensePlate+"aaaaaaaaaaaaaaaaa";
        for(auto str:words){
            vector<int> B(26,0);
            for(char ch:str)
                B[tolower(ch)-'a']+=1;
            bool found = true;
            for(int i =0;i<26;++i)
                if(B[i]<A[i])
                    found = false;
            if(found && res.length() > str.length())
                res = str;
        }
        return res;
    }
};

733. Flood Fill ------------E

Q:

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, "flood fill" the image.

To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

At the end, return the modified image.

Example 1:

Input: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: 
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected 
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.

Note:

The length of image and image[0] will be in the range [1, 50].

The given starting pixel will satisfy 0 <= sr < image.length and 0 <= sc < image[0].length.

The value of each color in image[i][j] and newColor will be an integer in [0, 65535].

A:

就是DFS。  下面的是基于queue的dfs

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc,
                                  int newColor) {
        int m = image.size(), n = image[0].size();
        vector<vector<int>> res(m, vector<int>(n, -1));
        queue<vector<int>> Q;
        int val = image[sr][sc];
        Q.push({sr, sc});
        vector<vector<int>> V{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        while (!Q.empty()) {
            auto curPos = Q.front();
            int rr = curPos[0], cc = curPos[1];
            Q.pop();
            res[rr][cc] = newColor;
            for (auto off : V) {
                int dr = rr + off[0], dc = cc + off[1];
                if (dr >= 0 && dr < m && dc >= 0 && dc < n &&
                    image[dr][dc] == val && res[dr][dc] == -1) {
                    Q.push({dr, dc});
                }
            }
        }
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (res[i][j] == -1)
                    res[i][j] = image[i][j];
        return res;
    }
};

递归的dfs

class Solution {

public:

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc,

int color) {

int ori = image[sr][sc];

if (ori == color) {

return image;

}

dfs(image, sr, sc, ori, color);

return image;

}

private:

void dfs(vector<vector<int>>& image, int sr, int sc, const int ORI,

int color) {

int m = image.size(), n = image[0].size();

int ori = image[sr][sc];

image[sr][sc] = color;

if (sr - 1 >= 0 && image[sr - 1][sc] == ORI)

dfs(image, sr - 1, sc, ORI, color);

if (sr + 1 < m && image[sr + 1][sc] == ORI)

dfs(image, sr + 1, sc, ORI, color);

if (sc - 1 >= 0 && image[sr][sc - 1] == ORI)

dfs(image, sr, sc - 1, ORI, color);

if(sc+1 <n && image[sr][sc+1] == ORI )

dfs(image, sr, sc + 1, ORI, color);

}

};

771. Jewels and Stones -------E

Q:

You're given strings J representing the types of stones that are jewels, and S representing the stones you have.  Each character in S is a type of stone you have.  You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note:

• S and J will consist of letters and have length at most 50.
• The characters in J are distinct.

A:

class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int res = 0;
        for(char ch : S)
        {
            for(char j : J)
                if(ch == j)
                    res++;
        }
        return res;
    }
};

766. Toeplitz Matrix --------- E

Q:

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.
 

Example 1:

Input:
matrix = [
  [1,2,3,4],
  [5,1,2,3],
  [9,5,1,2]
]
Output: True
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

Example 2:

Input:
matrix = [
  [1,2],
  [2,2]
]
Output: False
Explanation:
The diagonal "[1, 2]" has different elements.

Note:

1. matrix will be a 2D array of integers.
2. matrix will have a number of rows and columns in range [1, 20].
3. matrix[i][j] will be integers in range [0, 99].

Follow up:

1. What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
2. What if the matrix is so large that you can only load up a partial row into the memory at once?

A:

一格格斜杠对比呗。没什么fancy 的

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size(); // no need to check boundary, since already
        int r = 0, c = n-1;
        while(r<m){
            int val = matrix[r][c];
            int rr = r, cc = c;
            while(rr <m && cc <n) // when valid
            {
                if(matrix[rr++][cc++] != val)
                    return false;
            }
            if(c>0)
            {
                c--;
            }else{
                r++;
            }
        }
        return true;
    }
};

720. Longest Word in Dictionary ------------E

Q:

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

Example 1:

Input: 
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation: 
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input: 
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation: 
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

Note:

All the strings in the input will only contain lowercase letters.

The length of words will be in the range [1, 1000].

The length of words[i] will be in the range [1, 30].

A:

class Solution {
public:
    string longestWord(vector<string>& words) {
        unordered_set<string> set(words.begin(), words.end());
        string res = "";
        vector<string> preLayer;
        preLayer.push_back(res);
        while(preLayer.size()>0){
            res = preLayer[0];
            vector<string> curLayer;
            for(auto str:preLayer){
                for(char ch = 'a'; ch<='z'; ++ch){
                    string ss = str+ch;
                    if(set.find(ss) != set.end()){
                        curLayer.push_back(ss);
                    }
                }
            }
            preLayer = curLayer;
        }
        return res;
    }
};

错误在：

2个for loop 次序颠倒了。 哎， 肏

762. Prime Number of Set Bits in Binary Representation ---------E

Q:

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Input: L = 6, R = 10
Output: 4
Explanation:
6 -> 110 (2 set bits, 2 is prime)
7 -> 111 (3 set bits, 3 is prime)
9 -> 1001 (2 set bits , 2 is prime)
10->1010 (2 set bits , 2 is prime)

Example 2:

Input: L = 10, R = 15
Output: 5
Explanation:
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)

Note:

1. L, R will be integers L <= R in the range [1, 10^6].
2. R - L will be at most 10000.

A:

class Solution {
public:
    int countPrimeSetBits(int L, int R) {
        unordered_set<int> S{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
        int res = 0;
        for(int k = L; k<=R; ++k)
        {
            if( S.find(getDigit(k)) != S.end())
                ++res;
        }
        return res;
    }
private:
    int getDigit(int k){
        int nDigit = 0;
        while(k != 0)
        {
            ++nDigit;
            k = k & (k-1);
        }
        return nDigit;
    }
};