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

Q:

You are given a data structure of employee information, which includes the employee's unique id, their importance value and their direct subordinates' id.

For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.

Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all their subordinates.

Example 1:

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

 

Note:

1. One employee has at most one direct leader and may have several subordinates.
2. The maximum number of employees won't exceed 2000.

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*> map; // id to importance
        for(auto E: employees)
            map[E->id] = E;
        
        unordered_set<int> FoundSet;
        vector<int> V{id};
        int res =0;
        while(! V.empty()){
            int curID = V.back();
            V.pop_back();
            FoundSet.insert(curID);
            res += map.find(curID)->second->importance;
            for(auto tt:  map.find(curID)->second->subordinates){
                V.push_back(tt);
            }
        }
        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];
        vector<int> tmp{sr,sc};
        Q.push(tmp);
        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){
                    vector<int> tmp2{dr,dc};
                    Q.push(tmp2);
                }
            }
        }
        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;
    }
};

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

747. Largest Number At Least Twice of Others ---E

Q:

In a given integer array nums, there is always exactly one largest element.

Find whether the largest element in the array is at least twice as much as every other number in the array.

If it is, return the index of the largest element, otherwise return -1.

Example 1:

Input: nums = [3, 6, 1, 0]
Output: 1
Explanation: 6 is the largest integer, and for every other number in the array x,
6 is more than twice as big as x.  The index of value 6 is 1, so we return 1.

 

Example 2:

Input: nums = [1, 2, 3, 4]
Output: -1
Explanation: 4 isn't at least as big as twice the value of 3, so we return -1.

 

Note:

1. nums will have a length in the range [1, 50].
2. Every nums[i] will be an integer in the range [0, 99].

A:

class Solution {
public:
    int dominantIndex(vector<int>& nums) {
        int maxVal = *max_element(nums.begin(), nums.end());
        for(auto k : nums)
        {
            if(k != maxVal && maxVal < 2*k)
                return -1;
        }
        for(int i =0;i<nums.size(); ++i)
            if(nums[i] == maxVal)
                return i;
        return 0;
    }
};

744. Find Smallest Letter Greater Than Target -----------E

Q:

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

Letters also wrap around. For example, if the target is target = 'z' and letters = ['a', 'b'], the answer is 'a'.

Examples:

Input:
letters = ["c", "f", "j"]
target = "a"
Output: "c"

Input:
letters = ["c", "f", "j"]
target = "c"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "d"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "g"
Output: "j"

Input:
letters = ["c", "f", "j"]
target = "j"
Output: "c"

Input:
letters = ["c", "f", "j"]
target = "k"
Output: "c"

Note:

1. letters has a length in range [2, 10000].
2. letters consists of lowercase letters, and contains at least 2 unique letters.
3. target is a lowercase letter.

A:

一开始没有弄明白什么是wrap around. 下面这个，没有用上 list of sorted characters

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        char largerRes ='A';
        char smallerRes = 'A';
        for(auto ch:letters)
        {
            if(ch>target){
                if( isupper(largerRes) || ch < largerRes )
                {
                    largerRes = ch;
                }
            }else if(ch<target){
                if( isupper(smallerRes) || ch < smallerRes )
                {
                    smallerRes = ch;
                }
            }
        }
        return isupper(largerRes)?smallerRes:largerRes;
    }
};

-----------------------利用了sorted List---

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        for(auto ch:letters)
            if(ch > target)
                return ch;
        return letters[0];
    }
};

728. Self Dividing Numbers ----E

Q:

A self-dividing number is a number that is divisible by every digit it contains.

For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.

Also, a self-dividing number is not allowed to contain the digit zero.

Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.

Example 1:

Input: 
left = 1, right = 22
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

Note:

The boundaries of each input argument are 1 <= left <= right <= 10000.

A:

就是一个个数呗。没啥好办法

class Solution {
public:
    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> res;
        for(int i = left; i<= right; ++i){
            if(isSelf(i))
                res.push_back(i);
        }
        return res;
    }
private:
    bool isSelf(int v){
        int origV = v;
        while(v>0)
        {
            int r = v%10;
            v = v/10;
            if(r == 0 || origV % r != 0)
                return false;
        }
        return true;
    }
};

697. Degree of an Array ----E

Q:

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

 

Example 1:

Input: nums = [1,2,2,3,1]
Output: 2
Explanation: 
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.

Example 2:

Input: nums = [1,2,2,3,1,4,2]
Output: 6
Explanation: 
The degree is 3 because the element 2 is repeated 3 times.
So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.

 

Constraints:

• nums.length will be between 1 and 50,000.
• nums[i] will be an integer between 0 and 49,999.

A:

用一个map 来计算出degree来， 再用左右 index runner来跟着计算刚达到的degree

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        int degree = 0;
        unordered_map<int,int> map; // count of 
        for(auto k : nums){
            map[k] +=1;
            degree = max(degree, map[k]);
        }
        
        map.clear();
        int res = nums.size();
        int begin = 0;
        for(int end = 0;end<nums.size(); ++end)
        {
            int k = nums[end];
            map[k] += 1;
            if(map[k] == degree)
            {
                //loop till not equal
                while(nums[begin] != k)
                {
                    map[nums[begin]] -= 1;
                    ++begin;
                }
                res = min(res, end-begin+1);
                ++begin;
                map[k] -= 1;
            }
        }
        return res;
    }
};