1331. Rank Transform of an Array (easy)

Q:

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

• Rank is an integer starting from 1.
• The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
• Rank should be as small as possible.

Example 1:

Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

Example 2:

Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.

Example 3:

Input: arr = [37,12,28,9,100,56,80,5,12]
Output: [5,3,4,2,8,6,7,1,3]

Constraints:

• 0 <= arr.length <= 105
• -109 <= arr[i] <= 109

A:

搞一个priority_queue, 复杂类型，然后从小到大取就行了。

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        struct A
        { 
            int val, index;
            A(int v, int i):val(v), index(i){};
        };
        struct compareA
        {
            bool operator()(A const& p1, A const& p2)
            {
                if(p1.val == p2.val)
                {
                    return p1.index > p2.index;
                }
                return p1.val > p2.val;
            }
        };
        vector<int> res(arr.size());
        priority_queue<A, vector<A>, compareA> Q;
        for(int i =0; i<arr.size(); ++i)
        {
            Q.push(A(arr[i],i));
        }
        int curRank = 0, preVal = 0;
        while(!Q.empty())
        {
            A p = Q.top();
            Q.pop();
            if(curRank == 0 || preVal != p.val)
            {
                curRank++;
                preVal = p.val;
            }
            res[p.index] = curRank;
        }        
        return res;
    }
};

another way is to copy arr, and sort it, then remove duplicate, then map their index as rank.


Learned：
1:  priority_queue,  默认的，p1 < p2, 会导致max queue.  如果用min queue, 需要 >
2:  how to create Struct, and apply the Compare operator(),
3: Q.top(),   Q.pop() 需要分开声明

1337. The K Weakest Rows in a Matrix

Q

Given a m * n matrix mat of ones (representing soldiers) and zeros (representing civilians), return the indexes of the k weakest rows in the matrix ordered from the weakest to the strongest.

A row i is weaker than row j, if the number of soldiers in row i is less than the number of soldiers in row j, or they have the same number of soldiers but i is less than j. Soldiers are always stand in the frontier of a row, that is, always ones may appear first and then zeros.

Example 1:

Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers for each row is: 
row 0 -> 2 
row 1 -> 4 
row 2 -> 1 
row 3 -> 2 
row 4 -> 5 
Rows ordered from the weakest to the strongest are [2,0,3,1,4]

Example 2:

Input: mat = 
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 
k = 2
Output: [0,2]
Explanation: 
The number of soldiers for each row is: 
row 0 -> 1 
row 1 -> 4 
row 2 -> 1 
row 3 -> 1 
Rows ordered from the weakest to the strongest are [0,2,3,1]

Constraints:

• m == mat.length
• n == mat[i].length
• 2 <= n, m <= 100
• 1 <= k <= m
• matrix[i][j] is either 0 or 1.

A

// vertical traversal

class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {        
        set<int> ss;// vertical traversal
        vector<int> res;
        // check by finding 0 vertically
        for(int j=0; j<mat[0].size() && res.size()<k; ++j )
        {
            for(int i=0; i< mat.size() && res.size() < k; ++i)
            {
                if(mat[i][j] ==0 &&  ss.find(i) == ss.end() )
                {
                    ss.insert(i);
                    res.push_back(i);
                }
            }
        }
        // now that all zeros have been found, but still not enough
        for(int i=0;i<mat.size() && (res.size() < k); ++i)
       {
            if(ss.find(i) ==ss.end()) // all 0 have been found
            {
                res.push_back(i);
            }
       }        
        return res;
    }
};

1342. Number of Steps to Reduce a Number to Zero (Easy)

Q

Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

Example 1:

Input: num = 14
Output: 6
Explanation: 
Step 1) 14 is even; divide by 2 and obtain 7. 
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3. 
Step 4) 3 is odd; subtract 1 and obtain 2. 
Step 5) 2 is even; divide by 2 and obtain 1. 
Step 6) 1 is odd; subtract 1 and obtain 0.

Example 2:

Input: num = 8
Output: 4
Explanation: 
Step 1) 8 is even; divide by 2 and obtain 4. 
Step 2) 4 is even; divide by 2 and obtain 2. 
Step 3) 2 is even; divide by 2 and obtain 1. 
Step 4) 1 is odd; subtract 1 and obtain 0.

Example 3:

Input: num = 123
Output: 12

Constraints:

• 0 <= num <= 10^6

A:

if( (num & 1) ==0)

和 if (num &1 ==0)

结果是不一样的。操，我是个SB

--------直接计算---------------------

class Solution {
public:
    int numberOfSteps (int num) {
        int res = 0;
        while(num > 0)
        {
            if( (num & 1) ==0)
            {
                num = num>>1;
            }else
            {
                num = num-1;
            }
            res ++;
        }
        return res;
    }
};

*****************计算1 的数量，和最高的 1 的位数*****************

1346. Check If N and Its Double Exist (Easy)

Q

Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M).

More formally check if there exists two indices i and j such that :

• i != j
• 0 <= i, j < arr.length
• arr[i] == 2 * arr[j]

Example 1:

Input: arr = [10,2,5,3]
Output: true
Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.

Example 2:

Input: arr = [7,1,14,11]
Output: true
Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.

Example 3:

Input: arr = [3,1,7,11]
Output: false
Explanation: In this case does not exist N and M, such that N = 2 * M.

Constraints:

• 2 <= arr.length <= 500
• -10^3 <= arr[i] <= 10^3

A:
忘记 0 的特殊情况了。

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        std::set<int> s;
        int count0 = 0;
        for(int a : arr)
        {
            if (a==0)            
                count0 +=1;
            else
                s.insert(a);
        }
        if (count0>=2)
            return true;
        for(int a:arr)
        {
            if(s.find(a+a) != s.end())
            {
                return true;
            }
        }
        return false;
    }
};

1351. Count Negative Numbers in a Sorted Matrix

Below is the top 7 difference between C++ Reference vs Pointer

Q

Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise. 

Return the number of negative numbers in grid.

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

Example 2:

Input: grid = [[3,2],[1,0]]
Output: 0

Example 3:

Input: grid = [[1,-1],[-1,-1]]
Output: 3

Example 4:

Input: grid = [[-1]]
Output: 1

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

A:

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        if ( grid.size()==0 || grid[0].size() == 0)
            return 0;
        return helper(grid,0,0,grid.size(),grid[0].size());
    }
private:
    int helper(vector<vector<int>>& grid, int X1, int Y1, const int m, const int n) {
        if (X1>=m ||  Y1>=n )
        {
            return 0;
        }
        if (grid[X1][Y1]< 0)
        {
            return (m-X1) * (n-Y1);
        }
        int res = 0;
        // linear search a row
        vector<int> & row = grid[X1];
        for (int j = Y1+1; j<n; ++j )
        {
            if(row[j]<0)
            {
                res += n-j;
                break;
            }
        }
            
        // linear search a column
        for (int i = X1+1; i<m; ++i)
        {
            if(grid[i][Y1]<0)
            {
                res += m -i;
                break;
            }
        }
        #
        res +=helper(grid, X1+1, Y1+1, m, n);
        return res;
    }
};

1115. Print FooBar Alternately

Q:

Suppose you are given the following code:

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }

  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

The same instance of FooBar will be passed to two different threads. Thread A will call foo() while thread B will call bar(). Modify the given program to output "foobar" n times.

Example 1:

Input: n = 1
Output: "foobar"
Explanation: There are two threads being fired asynchronously. One of them calls foo(), while the other calls bar(). "foobar" is being output 1 time.

Example 2:

Input: n = 2
Output: "foobarfoobar"
Explanation: "foobar" is being output 2 times.

A:

class FooBar {
private:
    int n;
    mutex m1;
    mutex m2;
    
public:
    FooBar(int n) {
        this->n = n;
        m1.unlock();
        m2.lock();
    }

    void foo(function<void()> printFoo) {
        
        for (int i = 0; i < n; i++) {
            m1.lock();            
            // printFoo() outputs "foo". Do not change or remove this line.
            printFoo();
            m2.unlock();
        }
    }

    void bar(function<void()> printBar) {
        
        for (int i = 0; i < n; i++) {
            
            m2.lock(); 
            
            // printBar() outputs "bar". Do not change or remove this line.
            printBar();
                        
            m1.unlock();
        }
    }
};

1114. Print in Order

Q:

Suppose we have a class:

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

The same instance of Foo will be passed to three different threads. Thread A will call first(), thread B will call second(), and thread C will call third(). Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().

Example 1:

Input: [1,2,3]
Output: "firstsecondthird"
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.

Example 2:

Input: [1,3,2]
Output: "firstsecondthird"
Explanation: The input [1,3,2] means thread A calls first(), thread B calls third(), and thread C calls second(). "firstsecondthird" is the correct output.

Note:

We do not know how the threads will be scheduled in the operating system, even though the numbers in the input seems to imply the ordering. The input format you see is mainly to ensure our tests' comprehensiveness.

A:

************use simple while loop *********

class Foo {
public:
    bool isFirst, isSecond;
    Foo() {
        isFirst = false;
        isSecond = false;
        
    }

    void first(function<void()> printFirst) {
        
        // printFirst() outputs "first". Do not change or remove this line.
        printFirst();
        isFirst = true;
    }

    void second(function<void()> printSecond) {
        while(!isFirst)
        {
            
        }
        // printSecond() outputs "second". Do not change or remove this line.
        printSecond();
        isSecond = true;
    }

    void third(function<void()> printThird) {
        while(!isSecond)
        {
            
        }
        // printThird() outputs "third". Do not change or remove this line.
        printThird();
    }
};

***********   use two  mutex ************

class Foo {
public:
    
    Foo() {
        m1.lock();
        m2.lock();        
    }

    void first(function<void()> printFirst) {
        
        // printFirst() outputs "first". Do not change or remove this line.
        printFirst();
        m1.unlock();
    }

    void second(function<void()> printSecond) {
        m1.lock();
        // printSecond() outputs "second". Do not change or remove this line.
        printSecond();
        m2.unlock();
    }

    void third(function<void()> printThird) {        
        m2.lock();
        // printThird() outputs "third". Do not change or remove this line.
        printThird();
        
    }
private:
    mutex m1;
    mutex m2;
};