852. Peak index of mountain range array; 162. Look for peaks; 165. Compare the version number; 166. Fraction to decimal; 171. Excel table column serial number; 172. Zero after factorial

We call array A that meets the following attributes Mountains:


    A.length >= 3
There is 0 < I < a.length - 1 such that a [0] < a [1] < A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]


Given an array determined as mountains, return any that satisfies a [0] < a [1] < A[i-1] < A[i] > A[i+1] > ... > The value of I of a [a.length - 1].

 

Example 1:

Input: [0,1,0]
Output: 1


Example 2:

Input: [0,2,1,0]
Output: 1

 

Tips:


    3 <= A.length <= 10000
    0 <= A[i] <= 10^6
A is the mountain range as defined above


 

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        int le = 1, ri = A.size() - 2;
        while (le <= ri) {
            int mid = le + ((ri - le) >> 1);
            if (A[mid] > A[mid - 1] && A[mid] > A[mid + 1]) return mid;
            else if (A[mid] <= A[mid - 1]) ri = mid - 1;
            else le = mid + 1;
        }
        return -1;
    }
};

The peak element refers to the element whose value is greater than the left and right adjacent values.

Given an input array nums, where nums[i] ≠ nums[i+1], find the peak element and return its index.

The array may contain multiple peaks. In this case, just return the location of any peak.

You can assume nums[-1] = nums[n] = - ∞.

Example 1:

Input: num = [1,2,3,1]
Output: 2
Explanation: 3 is the peak element, and your function should return its index 2.

Example 2:

Input: num = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: your function can return index 1, and its peak element is 2;
Or return index 5, whose peak element is 6.


explain:

Your solution should be O(logN) time complexity.

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if (nums.size() == 1) return 0;                     // Except in this case, there can be no mid_ le,mid_ The situation of RI crossing the boundary at the same time exists
        int le = 0, ri = nums.size() - 1, pos = -1;
        while (le <= ri) {
            int mid = le + ((ri - le) >> 1);
            int mid_le = mid - 1, mid_ri = mid + 1;
            if (mid_le != -1 && mid_ri != nums.size()) {    // Normal condition: Top / increase / decrease / bottom
                if (nums[mid] > nums[mid_le] && nums[mid] > nums[mid_ri]) {
                    return mid;
                } else if (nums[mid] < nums[mid_ri]) {
                    le = mid_ri;
                } else {
                    ri = mid_le;
                }
            } else if (mid_le == -1) {                      // mid_ Le - > mid: required
                if (nums[mid] > nums[mid_ri]) return mid;
                else le = mid_ri;
            } else {                                        // mid -> mid_ RI: necessary reduction
                if (nums[mid] > nums[mid_le]) return mid;
                else ri = mid_le;
            }            
        }
        return -1;
    }
};

Compare the two version numbers version1 and version2.
If Version1 > version2 returns 1, if Version1 < version2 returns - 1, in addition to 0.

You can assume that the version string is not empty and contains only numbers and Character.

 . Characters do not represent decimal points, but are used to separate sequences of numbers.

For example, 2.5 is not "two and a half", nor "half to three", but the fifth minor version in the second edition.

You can assume that the default revision number for each level of the version number is 0. For example, the revision numbers of the first level (large version) and the second level (small version) of version 3.4 are 3 and 4 respectively. The revision numbers of the third and fourth levels are 0.
 

Example 1:

Input: version1 = "0.1", version2 = "1.1"
Output: - 1

Example 2:

Input: version1 = "1.0.1", version2 = "1"
Output: 1

Example 3:

Input: version1 = "7.5.2.4", version2 = "7.5.3"
Output: - 1

Example 4:

Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: leading zeros are ignored, "01" and "001" represent the same number "1".

Example 5:

Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: version1 has no level 3 revision number, which means that its level 3 revision number defaults to "0".

 

Tips:


The version string consists of a dot (.) Composed of separated numeric strings. This numeric string may have leading zeros.
The version string does not start or end with a point, and there will not be two consecutive points.

class Solution {
public:
    int compareVersion(string version1, string version2) {
        stringstream ss1(version1), ss2(version2);
        string s1, s2;
        while (true) {
            auto &b1 = getline(ss1, s1, '.');   // Must reference
            auto &b2 = getline(ss2, s2, '.');   // Cannot be bool, because istream & getline (istream & is, string & STR, char delim);
            if (!b1 && !b2) {
                return 0;
            } else if (!b1) {
                if (stoi(s2)) return -1;
            } else if (!b2) {
                if (stoi(s1)) return 1;
            } else {
                auto int_s1 = stoi(s1), int_s2 = stoi(s2);
                if (int_s1 == int_s2) continue;
                else if (int_s1 > int_s2) return 1;
                else return -1;
            }
        }
    }
};

Given two integers representing the numerator and denominator of the fraction, return the decimal in the form of string.

If the decimal part is a circular decimal, enclose the circular part in parentheses.

Example 1:

Input: numerator = 1, denominator = 2
Output: "0.5"


Example 2:

Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

Input: numerator = 2, denominator = 3
Output: "0. (6)"

class Solution {
public:
	string fractionToDecimal(int numerator, int denominator) {	// If the remainder of the decimal part repeats twice, it means that the decimal is a circular decimal
		if (denominator == 0) return "";						
		if (numerator == 0) return "0";							
		string result;
		long long num = static_cast<long long>(numerator);      // Convert to longlong to prevent overflow
		long long denom = static_cast<long long>(denominator);
		if ((num>0) ^ (denom>0))result.push_back('-');          // Deal with positive and negative signs, one positive and one negative sign      
		num = llabs(num); denom = llabs(denom);					  
		result.append(to_string(num / denom));					// Processing integer parts      
																// Processing decimal parts
		num %= denom;											
		if (num == 0)return result;								
		result.push_back('.');									
		int index = result.size() - 1;							
		unordered_map<int, int> record;							// map is used to record the subscript of the repetition number, and then insert '(' in front of the repetition number
		while (num&&record.count(num) == 0) {					// Decimal part: the remainder is not 0 and there are no duplicate digits in the remainder
			record[num] = ++index;
			num *= 10;											// The remainder is expanded by 10 times, and then the quotient is obtained. The operation method is the same as that on the draft book
			result += to_string(num / denom);
			num %= denom;
		}
		if (record.count(num) == 1) {							// In case of cyclic remainder, we directly add '(' in front of the repeating number and ')' at the end of the string
			result.insert(record[num], "(");
			result.push_back(')');
		}
		return result;
	}
};

Given the column name in an Excel table, return its corresponding column sequence number.

For example,

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 
    ...


Example 1:

Input: "A"
Output: 1


Example 2:

Input: "AB"
Output: 28


Example 3:

Input: "ZY"
Output: 701

class Solution {
public:
    int titleToNumber(string s) {
        int res = 0;
        for (auto &i: s) {
            res = 26*res + static_cast<int>(i - 'A' + 1);
        }
        return res;
    }
};

Given an integer n, return n! The number of zeros in the mantissa of the result.

Example 1:

Input: 3
Output: 0
Explanation: 3= 6. There is no zero in the mantissa.

Example 2:

Input: 5
Output: 1
Explanation: 5= 120, there is a zero in the mantissa

Note: the time complexity of your algorithm should be O(log n).

class Solution {
public:
    int trailingZeroes(int n) {
        int res = 0;
        while (n >= 5) {
            res += n / 5;
            n /= 5;
        }
        return res; // return n/5+n/25+n/125+n/625+n/3125+n/15625+n/78125+n/390625+n/1953125+n/9765625+n/48828125+n/244140625+n/1220703125;
    }
};

 

Tags: leetcode

Posted by suaji on Sun, 22 May 2022 10:56:47 +0300