Today I have done Length of Longest Fibonacci Subsequence and leetcode's May LeetCoding Challenge with cpp.

Length of Longest Fibonacci Subsequence

Description

A sequence X1, X2, ..., Xn is Fibonacci-like if:

• n >= 3
• Xi + Xi+1 = Xi+2 for all i + 2 <= n

Given a strictly increasing array arr of positive integers forming a sequence, return the length of the longest Fibonacci-like subsequence of arr. If one does not exist, return 0.

A subsequence is derived from another sequence arr by deleting any number of elements (including none) from arr, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].

Example 1:

Input: arr = [1,2,3,4,5,6,7,8]
Output: 5
Explanation: The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

Input: arr = [1,3,7,11,12,14,18]
Output: 3
Explanation: The longest subsequence that is fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].

Constraints:

• 3 <= arr.length <= 1000
• 1 <= arr[i] < arr[i + 1] <= 109

Solution

I thought there was a non-square-time-complexity solution... but no

class Solution {
public:
  int lenLongestFibSubseq(vector<int>& arr) {
    unordered_map<int, unordered_map<int, int>> mp;
    unordered_set<int> has;
    int len = arr.size();
    int answer = 0;
    for(auto i : arr) has.insert(i);
    for(int i = 2; i < len; ++i) {
      for(int j = i - 1; j >= 0 && arr[j] * 2 > arr[i]; --j) {
        int gt = arr[i];
        int lt = arr[j];
        int diff = gt - lt;
        if(has.count(diff)) {
          mp[gt][lt] = mp[lt][diff] + 1;
          answer = max(mp[gt][lt], answer);
        }
      }
    }
    return answer ? answer + 2 : 0;
  }
};

May LeetCoding Challenge 25

Description

Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Constraints:

• 1 <= tokens.length <= 104
• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Solution

class Solution {
public:
  string toLowerCase(string s) {
    for(auto &c : s) c = tolower(c);
    return s;
  }
};