字母板上的路径

题目描述

我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。

在本题里，字母板为board = [“abcde”, “fghij”, “klmno”, “pqrst”, “uvwxy”, “z”]，如下所示。

我们可以按下面的指令规则行动：

如果方格存在，‘U’ 意味着将我们的位置上移一行；
如果方格存在，‘D’ 意味着将我们的位置下移一行；
如果方格存在，‘L’ 意味着将我们的位置左移一列；
如果方格存在，‘R’ 意味着将我们的位置右移一列；
‘!’ 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。
（注意，字母板上只存在有字母的位置。）

返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。

样例

样例输入

target = “leet”
target = “code”

样例输出

“DDR!UURRR!!DDD!”
“RR!DDRR!UUL!R!”

提示

• 1 <= target.length <= 100
• target 仅含有小写英文字母。

思路

模拟题，但是有些细节需要注意，因为Z的特殊性，L的优先级要大于D, U的优先级需要大于R。

代码实现

class Solution {public String alphabetBoardPath(String target) {String ans = "";int i = 0, j = 0;char[] arr = target.toCharArray();for(char ch : arr){int row = (ch - 'a') / 5 , col = (ch - 'a') % 5;while(col < j){j--;ans += "L";}while(row > i){i++;ans += "D";}while(row < i){i--;ans += "U";}while(col > j){j++;ans += 'R';}ans += "!";}return ans;}
}

统计公平数对的数目

题目描述

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

• 0 <= i < j < n，且
• lower <= nums[i] + nums[j] <= upper

样例

样例输入

nums = [0,1,7,4,4,5], lower = 3, upper = 6
nums = [1,7,9,2,5], lower = 11, upper = 11

样例输出

6
解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。

1
解释：只有单个公平数对：(2,3) 。

提示

• $1<=nums.length<=10^5$
• $nums.length==n$
• $-10^9<=nums[i]<=10^9$
• $-10^9<=lower<=upper<=10^9$

思路

被这个0 <= i < j < n坑了一大把，一直没想到其实位置不影响结果，每个数都会被作为nums[i]与nums[j]遍历两次。所以根本不影响。可以直接排序，然后使用二分控制算法时间复杂度在O($nlo{g}_{2}n$)。看n的范围，只能使用O($nlo{g}_{2}n)的算法。$（看到区间查询，就想使用数组数组或者线段树，但这个nums[i] 范围一下子就给我树状数组整超内存了）

代码实现

class Solution {public long countFairPairs(int[] nums, int lower, int upper) {Arrays.sort(nums);long ans = 0;for(int i = 1; i < nums.length; i++){ans += Math.max(0, upper_bound(nums, upper-nums[i], 0, i-1) - lower_bound(nums, lower-nums[i], 0, i-1) + 1);}return ans;}private int upper_bound(int[] nums, int target, int l, int r){while(l <= r){int mid = (l + r) / 2;if(nums[mid] > target) r = mid - 1;else l = mid + 1;}return r;}private int lower_bound(int[] nums, int target, int l, int r){while(l <= r){int mid = (l + r + 1) / 2;if(nums[mid] < target) l = mid + 1; else r = mid - 1;}return l;}
}