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.

A 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。

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。

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:

• S1 = "0"
• S2 = "011"
• S3 = "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。

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。

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。