Category Archives: LeetCode

LeetCode Maximum Length of Subarray With Positive Product

1567. Maximum Length of Subarray With Positive Product

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return the maximum length of a subarray with positive product.

Example 1:

Input: nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.

Example 2:

Input: nums = [0,1,-2,-3,-4]
Output: 3
Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.
Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.

Example 3:

Input: nums = [-1,-2,-3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].

Example 4:

Input: nums = [-1,2]
Output: 1

Example 5:

Input: nums = [1,2,3,5,-6,4,0,10]
Output: 4

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

给一个数组,包含正数、负数和0,问最长连乘结果为正的长度是多少。

本题与LeetCode Maximum Product Subarray类似,要注意负负得正的情况。首先是传统DP好理解方法:设置dp_pos和dp_neg两个数组,分别表示遍历到i时,当前的最长连乘为正的长度和最长连乘为负的长度。则对于第i个位置,如果nums[i]是正数,则dp_pos直接+1;对于dp_neg,如果前一刻已经是连乘为负,即dp_neg[i-1]>0,则在前一刻基础上再乘以nums[i]还是负,所以负数长度可变长,即dp_neg+1;如果前一刻没有连乘为负,则增加一个正数也不会使连乘为负的长度增加,所以dp_neg=0。类似的可以讨论num[i]为负数的情况。如果nums[i]==0,则dp_pos和dp_neg都重置为0。

完整代码如下:

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp_pos(n, 0), dp_neg(n, 0);
        if(nums[0] > 0) dp_pos[0] = 1;
        else if(nums[0] < 0) dp_neg[0] = 1;
        int ans = dp_pos[0];
        for(int i = 1; i < n; ++i) {
            if(nums[i] > 0) {
                dp_pos[i] = dp_pos[i - 1] + 1;
                dp_neg[i] = dp_neg[i - 1] > 0 ? dp_neg[i - 1] + 1 : 0;
            } else if(nums[i] < 0) {
                dp_pos[i] = dp_neg[i - 1] > 0 ? dp_neg[i - 1] + 1 : 0;
                dp_neg[i] = dp_pos[i - 1] + 1;
            }
            ans = max(ans, dp_pos[i]);
        }
        return ans;
    }
};

本代码提交AC,用时268MS。

因为DP只用到上一刻的状态,所以不用数组存储也可以,节省内存版本如下,不过需要注意tmp=pos_len保存上一刻的pos_len状态。

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        int pos_len = 0, neg_len = 0;
        if(nums[0] > 0) pos_len = 1;
        else if(nums[0] < 0) neg_len = 1;
        int ans = pos_len;
        for(int i = 1; i < n; ++i) {
            if(nums[i] > 0) {
                ++pos_len;
                neg_len = neg_len > 0 ? neg_len + 1 : 0;
            } else if(nums[i] < 0) {
                int tmp = pos_len;
                pos_len = neg_len > 0 ? neg_len + 1 : 0;
                neg_len = tmp + 1;
            } else if(nums[i] == 0) {
                pos_len = neg_len = 0;
            }
            ans = max(ans, pos_len);
        }
        return ans;
    }
};

本代码提交AC,用时368MS。

LeetCode Detect Pattern of Length M Repeated K or More Times

5499. Detect Pattern of Length M Repeated K or More Times

Given an array of positive integers arr,  find a pattern of length m that is repeated k or more times.

pattern is a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple times consecutively without overlapping. A pattern is defined by its length and the number of repetitions.

Return true if there exists a pattern of length m that is repeated k or more times, otherwise return false.

Example 1:

Input: arr = [1,2,4,4,4,4], m = 1, k = 3
Output: true
Explanation: The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.

Example 2:

Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
Output: true
Explanation: The pattern (1,2) of length 2 is repeated 2 consecutive times. Another valid pattern (2,1) is also repeated 2 times.

Example 3:

Input: arr = [1,2,1,2,1,3], m = 2, k = 3
Output: false
Explanation: The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.

Example 4:

Input: arr = [1,2,3,1,2], m = 2, k = 2
Output: false
Explanation: Notice that the pattern (1,2) exists twice but not consecutively, so it doesn't count.

Example 5:

Input: arr = [2,2,2,2], m = 2, k = 3
Output: false
Explanation: The only pattern of length 2 is (2,2) however it's repeated only twice. Notice that we do not count overlapping repetitions.

Constraints:

  • 2 <= arr.length <= 100
  • 1 <= arr[i] <= 100
  • 1 <= m <= 100
  • 2 <= k <= 100

给定一个数组,为是否存在长度为m的子数组,这个子数组重复了至少k词。

观察数据范围,数据量很小,直接暴力求解,代码如下:

class Solution {
public:
    bool containsPattern(vector<int>& arr, int m, int k) {
        int n = arr.size();
        if(m * k > n) return false;
        for(int i = 0; i < n; ++i) {
            int rep = 0;
            for(int j = i; j < n; j += m) {
                bool good = true;
                for(int u = 0; u < m; ++u) {
                    if(u + j >= n || arr[u + j] != arr[i + u]) {
                        good = false;
                        break;
                    }
                }
                if(!good) break;
                else ++rep;
            }
            if(rep >= k) return true;
        }
        return false;
    }
};

本代码提交AC,用时4MS。

LeetCode K Closest Points to Origin

973. K Closest Points to Origin

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)

Note:

  1. 1 <= K <= points.length <= 10000
  2. -10000 < points[i][0] < 10000
  3. -10000 < points[i][1] < 10000

给定二维平面上的若干个点,求距离原点最近的K个点。

看总结: https://leetcode-cn.com/problems/k-closest-points-to-origin/solution/cyu-yan-san-chong-jie-fa-han-zong-jie-by-gan-cui-j/

事实上,诸如此类的,要在一个数组中寻找第K大的数(或者第K小的数),前K大的数,前K小的数,一般来说的方法有:

1.先排序(快排)时间复杂度为nlogn
2.建堆,堆的大小为K,建立大根堆或者小根堆,时间复杂度为nlogK(如果要求出前K个较大的,那么就建立小根堆,一旦比堆顶大,那么就入堆);
3.结合快速排序划分的方法,不断减小问题的规模

对于这一题,采用解法3,即快排划分的思路。采用标准快排思路,每次选区间最右边的元素作为pivot,然后划分,看看划分后的pivot位置和K的大小关系,递归在左右区间进行划分。完整代码如下:

class Solution {
private:
	vector<int> origin;

	int CalDist(vector<int> &p1, vector<int> &p2) {
		return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
	}

	void MySwap(vector<vector<int>>& points, int u, int v) {
		swap(points[u][0], points[v][0]);
		swap(points[u][1], points[v][1]);
	}

	void Work(vector<vector<int>>& points, int l, int r, int K) {
		if (l >= r) return;

		int pivot = r;
		int pdist = CalDist(points[pivot], origin);
		int i = l;
		for (int j = l; j < r; ++j) {
			int idist = CalDist(points[j], origin);
			if (idist < pdist) {
				MySwap(points, i++, j);
			}
		}
		MySwap(points, i, pivot);

		if (K == i)return;
		else if (K < i)Work(points, l, i - 1, K);
		else Work(points, i + 1, r, K);
	}
public:
	vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
		origin = { 0, 0 }; // 求与该点距离最近的top-k个点,本题中该点是原点

		for (int i = 0; i < points.size(); ++i) {
			printf("x=%d,y=%d,dist=%d\n", points[i][0], points[i][1], CalDist(points[i], origin));
		}

		Work(points, 0, points.size() - 1, K - 1);

		vector<vector<int>> ans;
		for (int i = 0; i < K; ++i) ans.push_back(points[i]);
		return ans;
	}
};

本代码提交AC,用时612MS。

LeetCode Maximum Sum Circular Subarray

918. Maximum Sum Circular Subarray

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array.  (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once.  (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Example 1:

Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

Example 2:

Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3:

Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Example 4:

Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5:

Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1

Note:

  1. -30000 <= A[i] <= 30000
  2. 1 <= A.length <= 30000

给定一个循环数组,即数组的最后一个和数字第一个连起来了。求循环数组的最大连续子数组和。

LeetCode Maximum Subarray的升级版,即数组首尾相连了。我一开始想到的解法是,既然数组首尾相连了,那就2*n次dp即可,即把原数组复制一遍,接到原数组后面,形成2*n长的数组,然后照样跑原来的DP算法。这个解法是不对的,比如如果数组是[1,2,3,4]这种全是正数,则跑2n遍之后,ans会一直max更新,导致最后的ans是1+…+4+1+…4,即数组加了两遍,每个数重复加了。另外对于数组[5,-3,5]这种,也会完整数组加两遍。

正确解法是,分两种情况,第一种情况是最大子串和没有跨越首尾,则使用常规DP即可求解。第二种情况是,最大子串和跨越了首尾,则可以把问题转化为求原数组的最小连续子串和,然后用数组总和减去最小连续子串和,就能得到跨越首尾的最大连续子串和。在求解第二种情况时,需要注意如果最小连续子串和是整个数组的情况,比如数组都是负数[-1,-2,-3],则求到的最小连续子串和是整个数组[-1,-2,-3],用数组总和一减变成了空集和为0,但最大连续子串和至少需要1个元素,对于这种情况,丢弃case2的解。

完整代码如下:

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int n = A.size();
        vector<int> dp(n, 0);
        
        // 最大连续子串
        dp[0] = A[0];
        int ans1 = A[0], sum = A[0];
        for(int i = 1; i < n; ++i) {
            dp[i] = max(dp[i - 1], 0) + A[i];
            ans1 = max(ans1, dp[i]);
            
            sum += A[i];
        }
        
        // 最小连续子串
        fill(dp.begin(), dp.end(), 0);
        dp[0] = A[0];
        int ans2 = A[0];
        for(int i = 1; i < n; ++i) {
            dp[i] = min(dp[i - 1], 0) + A[i];
            ans2 = min(ans2, dp[i]);
        }
        
        if(ans2 == sum) ans2 = INT_MIN; // 注意最小连续子串和不能是全长数组
        else ans2 = sum - ans2;
        
        return max(ans1, ans2);
    }
};

本代码提交AC,用时252MS。

LeetCode Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).

Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

Example 3:

Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3

Example 4:

Input: nums = [0,0,0], target = 0
Output: 3

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 0 <= target <= 10^6

给定一个数组,问数组中最多有多少个不overlap的子数组,它们的和等于target。

常规DP方法,假设dp[i]表示[0,…,i]能找到的最多的子串数目,则对于nums[i+1],如果从i+1往前,求累加和,如果累加到j的地方,累加和[j,…,i]等于target,则dp[i+1]=dp[j-1]+1。

这种思路的代码如下,需要注意for循环需要满足dp[j]==dp[i],如果dp[j]<dp[i],说明j已经回退到上一个累加和等于target的区间,已经有overlap了,需要终止。

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> dp(n + 1, 0);
        for(int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1];
            int sum = 0;
            for(int j = i; j > 0 && dp[j] == dp[i]; --j) {
                sum += nums[j - 1];
                if(sum == target) dp[i] = max(dp[i], dp[j - 1] + 1);
            }
        }
        return dp[n];
    }
};

上述代码的时间复杂度为O(n^2),在最后几个大数据集上TLE。

参考评论区,用一个hash记录某个前缀和出现的最新下标,对于任意一个数nums[i],看看prefix_sum-target是否在之前记录的前缀和中(查hash即可),如果在,假设对应下标为j,则说明[j,…,i]之间的累加和等于target,找到一个。不过为了保证不overlap,需要保证下标j不能回退到上一个合法的累加和区间内,每次找到一个合法区间后,用right_most记录其右边界,下次只需要用j和right_most比较大小即可。

完整代码如下:

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int n = nums.size();
        unordered_map<int, int> hash;
        hash[0] = -1;
        int prefix_sum = 0, right_most = -1;
        int ans = 0;
        for(int i = 0; i < n; ++i) {
            prefix_sum += nums[i];
            int supplement = prefix_sum - target;
            if(hash.find(supplement) != hash.end()) {
                int left = hash[supplement];
                if(left >= right_most) {
                    ++ans;
                    right_most = i;
                }
            }
            hash[prefix_sum] = i;
        }
        return ans;
    }
};

本代码提交AC,用时392MS。

LeetCode Find Kth Bit in Nth Binary String

5484. Find Kth Bit in Nth Binary String

Given two positive integers n and k, the binary string  Sn is formed as follows:

  • S1 = "0"
  • Si = Si-1 + "1" + reverse(invert(Si-1)) for i > 1

Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).

For example, the first 4 strings in the above sequence are:

  • S= "0"
  • S= "011"
  • S= "0111001"
  • S4 = "011100110110001"

Return the kth bit in Sn. It is guaranteed that k is valid for the given n.

Example 1:

Input: n = 3, k = 1
Output: "0"
Explanation: S3 is "0111001". The first bit is "0".

Example 2:

Input: n = 4, k = 11
Output: "1"
Explanation: S4 is "011100110110001". The 11th bit is "1".

Example 3:

Input: n = 1, k = 1
Output: "0"

Example 4:

Input: n = 2, k = 3
Output: "1"

Constraints:

  • 1 <= n <= 20
  • 1 <= k <= 2n - 1

简单题,直接字符串模拟操作即可,完整代码如下:

class Solution {
private:
	string InvertStr(string &s) {
		string ans = "";
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == '0')ans.push_back('1');
			else ans.push_back('0');
		}
		return ans;
	}
public:
	char findKthBit(int n, int k) {
		string s = "0";
		for (int i = 2; i <= n; ++i) {
			string inv_str = InvertStr(s);
			reverse(inv_str.begin(), inv_str.end());
			s = s + "1" + inv_str;
		}
		return s[k - 1];
	}
};

本代码提交AC。

LeetCode Make The String Great

5483. Make The String Great

Given a string s of lower and upper case English letters.

A good string is a string which doesn’t have two adjacent characters s[i] and s[i + 1] where:

  • 0 <= i <= s.length - 2
  • s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.

To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.

Return the string after making it good. The answer is guaranteed to be unique under the given constraints.

Notice that an empty string is also good.

Example 1:

Input: s = "leEeetcode"
Output: "leetcode"
Explanation: In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode" to be reduced to "leetcode".

Example 2:

Input: s = "abBAcC"
Output: ""
Explanation: We have many possible scenarios, and all lead to the same answer. For example:
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

Example 3:

Input: s = "s"
Output: "s"

Constraints:

  • 1 <= s.length <= 100
  • s contains only lower and upper case English letters.

给定一个字符串,如果相邻两个字符是同一字母的大小写形式,则需要删除这两个字母,问最终的字符串形式是什么。

简单题,使用栈,完整代码如下:

class Solution {
public:
    string makeGood(string s) {
        stack<char> stk;
        for(int i = 0; i < s.size(); ++i) {
            if(!stk.empty() && abs(stk.top() - s[i]) == 32) {
                stk.pop();
            } else {
                stk.push(s[i]);
            }
        }
        string ans="";
        while(!stk.empty()) {
            ans = string(1, stk.top()) + ans;
            stk.pop();
        }
        return ans;
    }
};

本代码提交AC。

LeetCode Coin Change 2

518. Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10] 
Output: 1

Note:

You can assume that

  • 0 <= amount <= 5000
  • 1 <= coin <= 5000
  • the number of coins is less than 500
  • the answer is guaranteed to fit into signed 32-bit integer

给定一堆不同面值的硬币,问凑齐amount块钱,有多少种不同的凑齐方案。

LeetCode Coin Change类似,也用动态规划。假设dp[i][j]表示用前i硬币,凑齐j块钱的方案数。则有两种情况,一是不用第i类硬币,有dp[i-1][j]种情况;二是用第i类硬币,则还需要凑齐j-coins[i]块钱,因为每类硬币无穷个,所以还是用前i类硬币凑齐j-coins[i]块钱,即有dp[i][j-coins[i]]种情况。两种情况数相加即可。完整代码如下:LeetCode Coin Change与

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        if(amount == 0) return 1;
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
        for(int i = 0; i <= n; ++i) dp[i][0] = 1;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= amount; ++j) {
                dp[i][j] = dp[i - 1][j];
                if(j >= coins[i - 1]) dp[i][j] += dp[i][j - coins[i - 1]];
            }
        }
        return dp[n][amount];
    }
};

本代码提交AC,用时60MS。

LeetCode Number of Good Leaf Nodes Pairs

5474. Number of Good Leaf Nodes Pairs

Given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

Example 2:

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.

Example 3:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].

Example 4:

Input: root = [100], distance = 1
Output: 0

Example 5:

Input: root = [1,1,1], distance = 2
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [1, 2^10].
  • Each node’s value is between [1, 100].
  • 1 <= distance <= 10

这一题第一眼看上去还是有难度的,后来观察数据量,发现总节点数才1024,则叶子节点数会更少,所以首先尝试了暴力方法。

暴力方法分为两个阶段,第一阶段是找到所有的叶子节点,第二阶段是求任意两个叶子节点的最短距离。

第一阶段在递归查找所有叶子节点时,保留了从根到该叶子的路径,以便后续求任意两个叶子的距离。第二阶段求距离时,思路比较简单,比如第一个样例,节点4的路径是1-2-4,节点3的路径是1-3,则两条路径都从根节点开始,看看两者的最长的公共前缀,直到找到它们的最后一个公共节点,相当于它们的最近公共祖先,然后假设最近公共祖先为两个叶子的子树的根节点,算两个叶子的高度,高度相加就是它们的最短距离。完整代码如下:

class Solution {
private:
	void CollectLeaves(TreeNode *root, unordered_map<TreeNode*, vector<TreeNode*>> &all_paths, vector<TreeNode*> &one_path) {
		if (root == NULL)return;
		one_path.push_back(root);
		if (root->left == NULL && root->right == NULL) {
			all_paths[root] = one_path;
		}
		else {
			CollectLeaves(root->left, all_paths, one_path);
			CollectLeaves(root->right, all_paths, one_path);
		}
		one_path.pop_back();
	}
	int CalDist(vector<TreeNode*> &path1, vector<TreeNode*> &path2) {
		int m = path1.size(), n = path2.size();
		int i = 0;
		while (i < m&&i < n) {
			if (path1[i] != path2[i])break;
			++i;
		}
		return (m - i) + (n - i);
	}

public:
	int countPairs(TreeNode* root, int distance) {
		unordered_map<TreeNode*, vector<TreeNode*>> all_paths;
		vector<TreeNode*> one_path;
		CollectLeaves(root, all_paths, one_path);
		vector<TreeNode*> leaves;
		for (unordered_map<TreeNode*, vector<TreeNode*>>::iterator it = all_paths.begin(); it != all_paths.end(); ++it) {
			leaves.push_back(it->first);
		}

		int ans = 0;
		for (int i = 0; i < leaves.size(); ++i) {
			for (int j = i + 1; j < leaves.size(); ++j) {
				int d = CalDist(all_paths[leaves[i]], all_paths[leaves[j]]);
				if (d <= distance)++ans;
			}
		}

		return ans;
	}
};

本代码提交AC。

LeetCode Bulb Switcher IV

5473. Bulb Switcher IV

There is a room with n bulbs, numbered from 0 to n-1, arranged in a row from left to right. Initially all the bulbs are turned off.

Your task is to obtain the configuration represented by target where target[i] is ‘1’ if the i-th bulb is turned on and is ‘0’ if it is turned off.

You have a switch to flip the state of the bulb, a flip operation is defined as follows:

  • Choose any bulb (index i) of your current configuration.
  • Flip each bulb from index i to n-1.

When any bulb is flipped it means that if it is 0 it changes to 1 and if it is 1 it changes to 0.

Return the minimum number of flips required to form target.

Example 1:

Input: target = "10111"
Output: 3
Explanation: Initial configuration "00000".
flip from the third bulb:  "00000" -> "00111"
flip from the first bulb:  "00111" -> "11000"
flip from the second bulb:  "11000" -> "10111"
We need at least 3 flip operations to form target.

Example 2:

Input: target = "101"
Output: 3
Explanation: "000" -> "111" -> "100" -> "101".

Example 3:

Input: target = "00000"
Output: 0

Example 4:

Input: target = "001011101"
Output: 5

Constraints:

  • 1 <= target.length <= 10^5
  • target[i] == '0' or target[i] == '1'

给一排灯泡,初始时都是灭的,每次可以选第i个灯泡,然后把第i个到最后的所有灯泡的状态翻转。问最少需要多少次操作才能得到目标状态序列。

很有意思的题,观察数据发现数据规模在1e5,数据量比较大,估计只有O(n)算法能过。接着,观察样例,不要被样例的解答给迷惑了。比如第一个例子10111,除了样例的解法,还可以谈心的做,序列变化如下:

0. 00000
1. 11111
2. 10000
3. 10111

即每次从左往右,把第一个不符合target状态的灯及往后的灯都flip,这种方法已经是最优的了。所以对于任意一个灯泡,它至少被翻转的次数就是它前面有多少种连续不同状态的灯泡。比如对于10111的后三个111,它前面有1和0,因为最原始是00,要变成10,则在满足第一个灯泡时有个0->1的翻转,导致第2个灯泡也变了;第二个灯泡也要flip一次;等到111时,它需要翻转的次数就是前面10共有2种特异状态。

所以问题转换为求字符串中有多少个连续相同状态的片段,所有片段数就是需要翻转的次数。另外要注意如果开头是0的话,则开头可以少翻转一次。代码如下:

class Solution {
public:
	int minFlips(string target) {
		int n = target.size();
		int ans = 0;
		int  i = 0;
		while (i < n) {
			int j = i + 1;
			while (j < n&&target[j] == target[i])++j;
			++ans;
			i = j;
		}
		if (target[0] == '0')return ans - 1;
		else return ans;
	}
};

本代码提交AC。