某班级考试成绩按非严格递增顺序记录于整数数组 scores,请返回目标成绩 target 的出现次数。
示例 1:
输入: scores = [2, 2, 3, 4, 4, 4, 5, 6, 6, 8], target = 4
输出: 3
示例 2:
输入: scores = [1, 2, 3, 5, 7, 9], target = 6
输出: 0
LeetCode链接
对于排序数组,首先想到的就是二分法,通过不断二分查找到相同数字的第一个出现位置和最后出现位置,则可计算出出现次数;
public static int countTarget(int[] scores, int target) {
if (scores == null || scores.length == 0) {
return 0;
}
int lo = 0;
int hi = scores.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (scores[mid] < target) {
lo = mid + 1;
} else if (scores[mid] > target) {
hi = mid - 1;
} else {
//找出左右边界值
if (scores[lo] != target) {
lo++;
} else if (scores[hi] != target) {
hi--;
} else {
break;
}
}
}
return hi - lo + 1;
}
m*n 的二维数组 plants 记录了园林景观的植物排布情况,具有以下特性:
每行中,每棵植物的右侧相邻植物不矮于该植物;
每列中,每棵植物的下侧相邻植物不矮于该植物。
请判断 plants 中是否存在目标高度值 target。
示例 1:
输入:plants = [[2,3,6,8],[4,5,8,9],[5,9,10,12]], target = 8
输出:true
示例 2:
输入:plants = [[1,3,5],[2,5,7]], target = 4
输出:false
选择右上方元素作为参考值与目标值进行比较,则可能出现以下几种情况:
public boolean findTargetIn2DPlants(int[][] plants, int target) {
if (plants == null || plants.length == 0 ) {
return false;
}
int row = 0;
int col = plants[0].length - 1;
while (row < plants.length && col >= 0) {
if (plants[row][col] == target) {
return true;
} else if (plants[row][col] > target) {
col--;
} else {
row++;
}
}
return false;
}
已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到:
若旋转 4 次,则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次,则可以得到 [0,1,4,4,5,6,7]
注意,数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须尽可能减少整个过程的操作步骤。
LeetCode链接
利用排序数组的性质,采用二分查找,通过计算mid下标元素与最后一个元素下标对比,则存在如下三种情况:
public int findMin(int[] nums) {
if(nums == null || nums.length == 0){
return Integer.MIN_VALUE;
}
int l = 0;
int r = nums.length - 1;
while(l < r){ //退出循环条件为两者相等时
int mid = l + (r- l )/2;
if(nums[mid] > nums[r]){
//说明最小值位于后半段
l = mid + 1;
}else if(nums[mid] < nums[r]){
//说明最小值位于前半段
r = mid;
} else {
//向前移动r
r--;
}
}
return nums[l];
}
某店铺将用于组成套餐的商品记作字符串 goods,其中 goods[i] 表示对应商品。请返回该套餐内所含商品的 全部排列方式 。
返回结果 无顺序要求,但不能含有重复的元素。
示例 1:
输入:goods = “agew”
输出:[“aegw”,“aewg”,“agew”,“agwe”,“aweg”,“awge”,“eagw”,“eawg”,“egaw”,“egwa”,“ewag”,“ewga”,“gaew”,“gawe”,“geaw”,“gewa”,“gwae”,“gwea”,“waeg”,“wage”,“weag”,“wega”,“wgae”,“wgea”]
采用回溯法思想
回溯法
public static String[] goodsOrder(String goods) {
if (goods == null || goods.length() == 0) {
return null;
}
Set<String> res = new HashSet<>();
goodsOrder(goods.toCharArray(), "", new boolean[goods.length()] , res);
return res.toArray(new String[res.size()]);
}
private static void goodsOrder(char[] chars, String temp, boolean[] isVisited, Set<String> res) {
if (temp.length() == chars.length) {
res.add(temp);
return;
}
for (int i = 0; i < chars.length; i++) {
if (isVisited[i]) {
continue;
}
isVisited[i] = true;
goodsOrder(chars, temp + chars[i], isVisited, res);
isVisited[i] = false;
}
}
给你一个整数 n ,请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …] 中找出并返回第 n 位上的数字。
示例 1:
输入:n = 3
输出:3
示例 2:
输入:n = 11
输出:0
解释:第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … 里是 0 ,它是 10 的一部分。
LeetCode链接
我们可以发现如下规律
数据范围 | 位数[digit] | 起始数字[start] | 总长度[count] |
---|---|---|---|
1 - 9 | 1 | 1 | start * 9 * digit = 9 |
10 - 99 | 2 | 10 | start * 9 * digit = 180 |
100 - 999 | 3 | 100 | start * 9 * digit = 2700 |
那我们可以根据入参位数不断缩小查找范围,计算出落到的具体数字,从而找出n位上的数字;
public int findNthDigit(int n) {
if(n < 10 ){
return n;
}
int digit = 1; // 1-9范围内 位数对应为1
long start = 1; // 1-9范围内 开始值对应为1
long count = 9; // 1-9范围内 一共有9个数
while (n > count) { //不断缩小查找范围
n -= count;
start = start * 10;
digit++;
count = digit * start * 9;
}
long num = start + (n - 1) / digit; // 2.计算得到具体对应的值
int i = (n - 1) % digit; //计算对应的下标
return Long.toString(num).charAt(i) - '0'; // 3.得到具体的值
}