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。

LeetCode Shuffle String

5472. Shuffle String

Given a string s and an integer array indices of the same length.

The string s will be shuffled such that the character at the ith position moves to indices[i] in the shuffled string.

Return the shuffled string.

Example 1:

Input: s = "codeleet", indices = [4,5,6,7,0,2,1,3]
Output: "leetcode"
Explanation: As shown, "codeleet" becomes "leetcode" after shuffling.

Example 2:

Input: s = "abc", indices = [0,1,2]
Output: "abc"
Explanation: After shuffling, each character remains in its position.

Example 3:

Input: s = "aiohn", indices = [3,1,4,2,0]
Output: "nihao"

Example 4:

Input: s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]
Output: "arigatou"

Example 5:

Input: s = "art", indices = [1,0,2]
Output: "rat"

Constraints:

  • s.length == indices.length == n
  • 1 <= n <= 100
  • s contains only lower-case English letters.
  • 0 <= indices[i] < n
  • All values of indices are unique (i.e. indices is a permutation of the integers from 0 to n - 1).

给定一个字符串,根据给定规则进行shuffle,直接照做。代码如下:

class Solution {
public:
	string restoreString(string s, vector<int>& indices) {
		int n = s.size();
		string ans = s;
		for (int i = 0; i < n; ++i)ans[indices[i]] = s[i];
		return ans;
	}
};

本代码提交AC。

LeetCode Minimum Window Substring

76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

  • If there is no such window in S that covers all characters in T, return the empty string "".
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

给两个字符串S和T,问S中是否存在一个子串,包括T中的所有字符,如果存在,输出最短的那个子串。

hard题,用双指针+滑动窗口。核心思想是找到滑动窗口[i,j),首先++j,加入右边界的字符;然后检查[i,j)是否能覆盖t;再然后++i,丢掉左边界的字符。

首先设置一个required数组,存储t中每个字符出现的次数,表示滑动窗口[i,j)需要覆盖的每个字符的次数。found表示需要找到的字符总数,如果found==t.size()表示滑动窗口能覆盖t。

首先检查右边界j,如果s[j]在t中,则++found。然后看看found==n?,如果是,则检查左边界,如果左边界s[i]在t中,则i++之后要–found。在窗口滑动过程中记录窗口最小长度。完整代码如下:

class Solution {
public:
	string minWindow(string s, string t) {
		int m = s.size(), n = t.size();
		vector<int> required(128, 0);
		for (int i = 0; i < n; ++i) {
			++required[t[i]];
		}

		int min_len = m + 1, start_id = 0, found = 0;
		int i = 0, j = 0;
		while (j < m) {
			--required[s[j]];
			if (required[s[j]] >= 0) { // s[j]在t中
				++found;
			}
			++j;

			while (found == n) {
				int cur_len = j - i;
				if (cur_len < min_len) {
					min_len = cur_len;
					start_id = i;
				}
				++required[s[i]];
				if (required[s[i]] > 0) --found;
				++i;
			}
		}
		if (min_len == m + 1) return "";
		else return s.substr(start_id, min_len);
	}
};

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

今晚字节跳动三面,面试官问了一个此题的变种,即只给定了字符串s,要找s的一个子串,使得该子串能覆盖s中所有特异的字符,且子串越短越好。可以把面试问题转换为这个问题,即先遍历s,把s中的特异字符拼成一个字符串t,然后调用本题的解法。

LeetCode Number of Nodes in the Sub-Tree With the Same Label

5465. Number of Nodes in the Sub-Tree With the Same Label

Given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [ai, bi], which means there is an edge between nodes ai and bi in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the ith node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

Example 2:

Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.

Example 3:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]

Example 4:

Input: n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa"
Output: [1,2,1,1,2,1]

Example 5:

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
Output: [6,5,4,1,3,2,1]

Constraints:

  • 1 <= n <= 10^5
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • labels.length == n
  • labels is consisting of only of lower-case English letters.

给定一棵多叉树(无向图),有n个顶点n-1条边。每个顶点上标了一个字母,问对于每个顶点,在它的子树中,与其字母相同的点有多少个。

每个节点维护一个26长的数组,记录该子树包含所有字母的频数。然后DFS,记录每个节点的这个数组,父节点的数组的值要累加上其直接孩子的这个数组的值。最后查表得到结果。代码如下:

class Solution {
private:
	void DFS(int parid, int curid, vector<vector<int>> &children_string, unordered_map<int, vector<int>> &graph, const string &labels) {
		int mylabel = labels[curid] - 'a';
		++children_string[curid][mylabel];

		for (int i = 0; i < graph[curid].size(); ++i) {
			int childid = graph[curid][i];
			if (childid == parid)continue;
			DFS(curid, childid, children_string, graph, labels);
			for (int j = 0; j < 26; ++j) {
				children_string[curid][j] += children_string[childid][j];
			}
		}
	}
public:
	vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
		unordered_map<int, vector<int>> graph;
		for (int i = 0; i < edges.size(); ++i) {
			graph[edges[i][0]].push_back(edges[i][1]);
			graph[edges[i][1]].push_back(edges[i][0]);
		}
		vector<vector<int>> children_string(n, vector<int>(26, 0));
		
		DFS(-1, 0, children_string, graph, labels);

		vector<int> ans;
		for (int i = 0; i < n; ++i) {
			int mylabel = labels[i] - 'a';
			ans.push_back(children_string[i][mylabel]);
		}
		return ans;
	}
};

本代码提交AC。

LeetCode Water Bottles

5464. Water Bottles

Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Return the maximum number of water bottles you can drink.

Example 1:

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

Example 2:

Input: numBottles = 15, numExchange = 4
Output: 19
Explanation: You can exchange 4 empty bottles to get 1 full water bottle. 
Number of water bottles you can drink: 15 + 3 + 1 = 19.

Example 3:

Input: numBottles = 5, numExchange = 5
Output: 6

Example 4:

Input: numBottles = 2, numExchange = 3
Output: 2

Constraints:

  • 1 <= numBottles <= 100
  • 2 <= numExchange <= 100

很贴近生活的一个题。初始有n瓶满饮料,喝完之后,可以每m个空瓶子换一瓶新饮料,问最终能喝多少瓶饮料。

直接模拟,代码如下:

class Solution {
public:
	int numWaterBottles(int numBottles, int numExchange) {
		int full = numBottles, empty = 0, div = numExchange;
		int ans = 0;
		while (full + empty >= div) {
			ans += full;
			empty += full;
			full = empty / div;
			empty = empty % div;
		}
		return ans + full;
	}
};

本代码提交AC。

LeetCode Number of Substrings With Only 1s

1513. Number of Substrings With Only 1s

Given a binary string s (a string consisting only of ‘0’ and ‘1’s).

Return the number of substrings with all characters 1’s.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: s = "0110111"
Output: 9
Explanation: There are 9 substring in total with only 1's characters.
"1" -> 5 times.
"11" -> 3 times.
"111" -> 1 time.

Example 2:

Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.

Example 3:

Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.

Example 4:

Input: s = "000"
Output: 0

Constraints:

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

给定一个字符串,问有多少个连续为1的子串。

简单题,先找出最长连续的1,假设长度为n,则这个n长的串能形成(n+1)n/2个1的子串,累加所有这样的子串和即可。代码如下:

const long long kMOD = 1e9 + 7;

class Solution {
	long long CalAccSum(long long l) {
		return (l %kMOD)* ((l + 1) % kMOD) / 2;
	}
public:
	int numSub(string s) {

		long long ans = 0;
		int i = 0, j = 0, n = s.size();
		while (i < n) {
			while (i < n&&s[i] == '0')++i;
			if (i >= n)break;
			j = i + 1;
			while (j < n&&s[j] == '1')++j;
			int m = j - i;
			ans += CalAccSum(m) % kMOD;
			i = j;
		}
		return ans % kMOD;
	}
};

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