给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。
如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：
0 <= i < j < n，且lower <= nums[i] + nums[j] <= upper
示例 1：
输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6
输出：6
解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。
|
示例 2：
输入：nums = [1,7,9,2,5], lower = 11, upper = 11
输出：1
解释：只有单个公平数对：(2,3) 。
|
提示：
1 <= nums.length <= 105nums.length == n-109 <= nums[i] <= 109-109 <= lower <= upper <= 109
C++
class Solution {
public:
long long countFairPairs(vector<int>& nums, int lower, int upper) {
long long res = 0;
sort(nums.begin(), nums.end());
for (auto it = nums.begin(); it != nums.end(); ++it) {
int minNum = lower - *it;
int maxNum = upper - *it;
auto x = lower_bound(it + 1, nums.end(), minNum);
auto y = upper_bound(it + 1, nums.end(), maxNum);
res += y - x;
}
return res;
}
};
|
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
- 例如：
"0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
|
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
|
示例 3：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
|
提示：
1 <= s.length <= 20s 仅由数字组成
C++
class Solution {
public:
vector<string> res;
string str = "";
void backtracking(string s, int idx, int cnt){
if(cnt == 4 || idx == s.size() ){
if(cnt == 4 && idx ==s.size())
res.push_back(str.substr(0,str.size()-1));
return;
}
for(int i = 1; i <= 3; i ++){
if(s[idx] == '0' && i > 1) return;
if(i == 3 && s.substr(idx,i) > "255") return;
if(idx + i > s.size()) return;
str += s.substr(idx,i);
str += ".";
backtracking(s, idx + i, cnt + 1);
str = str.substr(0, str.size() - 1 - i);
}
}
vector<string> restoreIpAddresses(string s) {
backtracking(s,0, 0);
return res;
}
};
|
给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- 交错 是
s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
注意：a + b 意味着字符串 a 和 b 连接。
示例 1：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true
|
示例 2：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false
|
示例 3：
输入：s1 = "", s2 = "", s3 = ""
输出：true
|
提示：
0 <= s1.length, s2.length <= 1000 <= s3.length <= 200s1、s2、和 s3 都由小写英文字母组成
进阶：您能否仅使用 O(s2.length) 额外的内存空间来解决它?
C++
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size()) return false;
return dfs(s1, s2, s3, 0 , 0 , 0);
}
bool dfs(string s1, string s2, string s3 , int i, int j, int k){
int len1 = s1.size(), len2 = s2.size(), len3 = s3.size();
while(k < len3){
if(s3[k] == s1[i] && s3[k] == s2[j] && i < len1 && j < len2){
return dfs(s1,s2,s3,i + 1,j,k + 1)
|| dfs(s1,s2,s3,i,j + 1,k + 1);
}
else if(s3[k] == s1[i] && i < len1){
i ++;
k ++;
}
else if(s3[k] == s2[j] && j < len2){
j ++;
k ++;
}
else return false;
}
return true;
}
};
|
给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。
例如：
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
|
示例 1：
输入：columnNumber = 1
输出："A"
|
示例 2：
输入：columnNumber = 28
输出："AB"
|
示例 3：
输入：columnNumber = 701
输出："ZY"
|
示例 4：
输入：columnNumber = 2147483647
输出："FXSHRXW"
|
提示：
1 <= columnNumber <= 231 - 1
C++
class Solution {
public:
string convertToTitle(int columnNumber) {
string res;
while(columnNumber > 0){
--columnNumber;
res += columnNumber % 26 + 'A';
columnNumber /= 26;
}
reverse(res.begin(), res.end());
return res;
}
};
|