装饰公司怎么做微网站,如何搭建网站,c 做网站 知乎,wordpress设置关键字字母板上的路径
题目描述
我们从一块字母板上的位置 (0, 0) 出发#xff0c;该坐标对应的字符为 board[0][0]。
在本题里#xff0c;字母板为board [“abcde”, “fghij”, “klmno”, “pqrst”, “uvwxy”, “z”]#xff0c;如下所示。 我们可以按下面的指令规则行动…字母板上的路径
题目描述
我们从一块字母板上的位置 (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 100target 仅含有小写英文字母。
思路
模拟题但是有些细节需要注意因为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) 。 提示
1nums.length1051 nums.length 10^51nums.length105nums.lengthnnums.length nnums.lengthn−109nums[i]109-10^9 nums[i] 10^9−109nums[i]109−109lowerupper109-10^9 lower upper 10^9−109lowerupper109
思路
被这个0 i j n坑了一大把一直没想到其实位置不影响结果每个数都会被作为nums[i]与nums[j]遍历两次。所以根本不影响。可以直接排序然后使用二分控制算法时间复杂度在O(nlog2nnlog_2nnlog2n)。看n的范围只能使用O(nlog2n)的算法。nlog_2n)的算法。nlog2n)的算法。看到区间查询就想使用数组数组或者线段树但这个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;}
}
