数字在升序数组中出现的次数_牛客题霸_牛客网
package 查询算法;
import org.junit.Test;
import java.util.HashMap;
/**
* @Classname JZ53数字在升序数组中出现的次数
* @Description TODO
* @Date 2022/2/3 13:59
* @Created by xjl
*/
public class JZ53数字在升序数组中出现的次数 {
public int GetNumberOfK(int[] array, int k) {
HashMap map = new HashMap();
for (int i : array) {
if (!map.containsKey(i)) {
map.put(i, 1);
} else {
map.put(i, map.get(i) + 1);
}
}
return map.get(k);
}
public int GetNumberOfK2(int[] array, int k) {
int count = 0;
for (int i : array) {
if (i == k) {
count++;
}
}
return count;
}
/**
* @description 二分法 看见有序，肯定就是二分查找了，算法比较简单，不多说，值得一提的是，不要拘泥于递归，要会循环写法。
* @param: array
* @param: k
* @date: 2022/2/3 14:08
* @return: int
* @author: xjl
*/
public int GetNumberOfK3(int[] array, int k) {
int length = array.length;
if (length == 0) {
return 0;
}
int firstK = getFirstK(array, k, 0, length - 1);
int lastK = getLastK(array, k, 0, length - 1);
if (firstK != -1 && lastK != -1) {
return lastK - firstK + 1;
}
return 0;
}
private int getFirstK(int[] array, int k, int start, int end) {
if (start > end) {
return -1;
}
int mid = (start + end) >> 1;//做云运算就是除以2
if (array[mid] > k) {
return getFirstK(array, k, start, mid - 1);
} else if (array[mid] < k) {
return getFirstK(array, k, mid + 1, end);
} else if (mid - 1 >= 0 && array[mid - 1] == k) {
return getFirstK(array, k, start, mid - 1);
} else {
return mid;
}
}
//循环写法
private int getLastK(int[] array, int k, int start, int end) {
int length = array.length;
int mid = (start + end) >> 1;
while (start k) {
end = mid - 1;
} else if (array[mid] < k) {
start = mid + 1;
} else if (mid + 1 < length && array[mid + 1] == k) {
start = mid + 1;
} else {
return mid;
}
mid = (start + end) >> 1;
}
return -1;
}
@Test
public void test() {
int[] array = {1, 2, 3, 3, 3, 3, 4, 5};
int k = 3;
int i = GetNumberOfK2(array, k);
System.out.println(i);
}
}
二维数组中的查找_牛客题霸_牛客网
package 查询算法;
/**
* @Classname JZ4二维数组的中查找
* @Description TODO
* @Date 2022/2/3 16:12
* @Created by xjl
*/
public class JZ4二维数组的中查找 {
/**
* @description 可以采用差分到每一个数组上 进行二分法
* @param: target
* @param: array
* @date: 2022/2/3 16:40
* @return: boolean
* @author: xjl
*/
public boolean Find(int target, int[][] array) {
// 判断数组是否为空
int len = array.length;
int row = array[0].length;
if (len == 0 || row == 0) {
return false;
}
for (int[] arr : array) {
if (findtarget(arr, target)) {
return true;
}
}
return false;
}
/**
* @description 每一个数数组采用二分法
* @param: arr
* @param: target
* @date: 2022/2/3 16:34
* @return: boolean
* @author: xjl
*/
private boolean findtarget(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left > 1;
if (arr[mid] == target) {
return true;
} else if (target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return false;
}
/**
* @description 也是可以直接暴力的方式
* 也可以采用：
* 由于行列递增，可以得出：
* a.在一列中的某个数字，其上的数字都比它小
* b.在一行中的某个数字，其右的数字都比它大
* 搜索流程：
* a.首先从数组左下角搜索.
* b.如果当前数字大于target,那么查找往上移一位,如果当前数字小于target,那么查找往右移一位。
* c.查找到target,返回true; 如果越界，返回false;
* @param: target
* @param: array
* @date: 2022/2/3 16:40
* @return: boolean
* @author: xjl
*/
public boolean Find2(int target, int[][] array) {
// 判断数组是否为空
int len = array.length;//行
int wide = array[0].length;//列
if (len == 0 || wide == 0) {
return false;
}
int left = 0;
int down = len - 1;
while (left < wide && down >= 0) {
int temp = array[down][left];
if (temp == target) {
return true;
} else if (target > temp) {
left++;
} else {
down--;
}
}
return false;
}
/**
* @description 解题思路： 利用数组行列递增特性。
* 主要思路：一维的二分查找可以舍弃一半的查找范围，二维的二分可以舍弃左上部分或者右下部分1/4的查找范围。
* @param: target
* @param: array
* @date: 2022/2/3 16:54
* @return: boolean
* @author: xjl
*/
public boolean Find3(int target, int[][] array) {
// 判断数组是否为空
int len = array.length;//行
int wide = array[0].length;//列
if (len == 0 || wide == 0) {
return false;
}
return double_binary(array, 0, array.length, 0, array[0].length, target);
}
private boolean double_binary(int[][] arr, int x1, int x2, int y1, int y2, int target) {
if (x1 == x2 || y1 == y2) return false;
int xmid = (x1 + x2) >> 1, ymid = (y1 + y2) >> 1;
int num = arr[xmid][ymid];
if (num == target) return true;
if (num > target) {
if (double_binary(arr, x1, xmid, y1, y2, target)) return true;
if (double_binary(arr, xmid, x2, y1, ymid, target)) return true;
} else {
if (double_binary(arr, xmid + 1, x2, y1, y2, target)) return true;
if (double_binary(arr, x1, xmid + 1, ymid + 1, y2, target)) return true;
}
return false;
}
}
旋转数组的最小数字_牛客题霸_牛客网
package 查询算法;
import org.junit.Test;
/**
* @Classname JZ11旋转数组的最小数字
* @Description TODO
* @Date 2022/2/3 17:05
* @Created by xjl
*/
public class JZ11旋转数组的最小数字 {
/**
* @description 可以采用的是遍历的思想 复杂度还是o(n)
* @param: array
* @date: 2022/2/3 17:06
* @return: int
* @author: xjl
*/
public int minNumberInarray(int[] array) {
int min = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
min = Math.min(min, array[i]);
break;
}
}
return min;
}
/**
* @description 空间复杂度：O(1)，时间复杂度：O(logn)
* 这种二分查找难就难在，arr[mid]跟谁比.
* 我们的目的是：当进行一次比较时，一定能够确定答案在mid的某一侧。一次比较为 arr[mid]跟谁比的问题。
* 一般的比较原则有：
*
* 如果有目标值target，那么直接让arr[mid] 和 target 比较即可。
* 如果没有目标值，一般可以考虑 端点
*
* 这里我们把target 看作是右端点，来进行分析，那就要分析以下三种情况，看是否可以达到上述的目标。
*
* 情况1，arr[mid] > target：4 5 6 1 2 3
* arr[mid] 为 6， target为右端点 3， arr[mid] > target, 说明[first ... mid] 都是 >= target 的，因为原始数组是非递减，所以可以确定答案为 [mid+1...last]区间,所以 first = mid + 1
* 情况2，arr[mid] < target:5 6 1 2 3 4
* arr[mid] 为 1， target为右端点 4， arr[mid] < target, 说明答案肯定不在[mid+1...last]，但是arr[mid] 有可能是答案,所以答案在[first, mid]区间，所以last = mid;
* 情况3，arr[mid] == target:
* 如果是 1 0 1 1 1， arr[mid] = target = 1, 显然答案在左边
* 如果是 1 1 1 0 1, arr[mid] = target = 1, 显然答案在右边
* 所以这种情况，不能确定答案在左边还是右边，那么就让last = last - 1;慢慢缩少区间，同时也不会错过答案。
* @param: array
* @date: 2022/2/3 17:16
* @return: int
* @author: xjl
*/
public int minNumberInarray2(int[] array) {
if (array.length == 0) return 0;
int first = 0;
int last = array.length - 1;
while (first < last) { // 最后剩下一个元素，即为答案
if (array[first] < array[last]) { // 提前退出
return array[first];
}
int mid = (first + last) >> 1;
if (array[mid] > array[last]) { // 情况1
first = mid + 1;
} else if (array[mid] < array[last]) { //情况2
last = mid;
} else { // 情况3
--last;
}
}
return array[first];
}
public int minNumberInarray3(int[] array) {
if (array.length == 0) {
return 0;
}
int left = 0;
int right = array.length - 1;
while (left < right) {
if (array[left] < array[right]) {
return array[left];
}
int mid = (left + right) >> 1;
if (array[mid] > array[right]) {
left=mid+1;
} else if (array[mid] < array[right]) {
right=mid;
} else {
--right;
}
}
return array[left];
}
@Test
public void test() {
int[] array = {3, 100, 200, 3};
int i = minNumberInarray(array);
System.out.println(i);
}
}
字符串的排列_牛客题霸_牛客网
字符串的排列_牛客题霸_牛客网
package 查询算法;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
/**
* @Classname JZ38字符串的排列
* @Description TODO
* @Date 2022/2/3 18:00
* @Created by xjl
*/
public class JZ38字符串的排列 {
public ArrayList Permutation(String str) {
ArrayList list = new ArrayList();
if (str != null && str.length() > 0) {
dfs(str.toCharArray(), 0, list);
Collections.sort(list);
}
return list;
}
private void dfs(char[] chars, int i, ArrayList list) {
if (i == chars.length - 1) {
list.add(String.valueOf(chars));
} else {
Set charSet = new HashSet();
for (int j = i; j < chars.length; ++j) {
if (j == i || !charSet.contains(chars[j])) {
charSet.add(chars[j]);
swap(chars, i, j);
dfs(chars, i + 1, list);
swap(chars, j, i);
}
}
}
}
private void swap(char[] cs, int i, int j) {
char temp = cs[i];
cs[i] = cs[j];
cs[j] = temp;
}
public ArrayList Permutation2(String str) {
ArrayList list = new ArrayList();
if (str.length() == 0) {
return list;
}
boolean[] vis = new boolean[str.length()];
StringBuilder sb=new StringBuilder();
dfs1(str, 0, sb, list, vis);
//去重复
ArrayList ans=new ArrayList(new HashSet(list));
return ans;
}
private void dfs1(String str, int index, StringBuilder sb, ArrayList list, boolean[] vis) {
if (index == str.length()) {
list.add(sb.toString());
return;
}
for (int i = 0; i < str.length(); i++) {
if (!vis[i]) {
vis[i]=true;
sb.append(str.charAt(i));
dfs1(str,index+1,sb,list,vis);
sb.deleteCharAt(sb.length()-1);
vis[i]=false;
}
}
}
@Test
public void test(){
ArrayList list = Permutation2("aab");
for (String s:list){
System.out.print(s+" ");
}
}
}
数字序列中某一位的数字_牛客题霸_牛客网
解题思路
思路：数学
先观察数字规律
小于10，1~9，9个数字，9位
小于100，10~99，90个数字，180位
小于1000，100~999，900个数字，2700位
各个区间的下限上限是[0,10),[10, 100),[100,1000)...位数是1，2，3...
从第1个区间的上限开始进行比较，如果大于上限，将上下限*10，将n=n-(上限-下限)*位数 直至找到n所在的区间
找到区间后，n/位数 找到所在的数字，然后n%位数，找到数字的第几位数字
public int findNthDigit (int n) {
int digitCont = 1;//位数
int start=1;//区间下限
long count=9l;//区间位数
while(n > count){
n-=count;
digitCont+=1;
start*=10;
count=Integer.toUnsignedLong(start*digitCont*9);
}
//num表示n所在的数字
int num = (n-1) / digitCont + start;
String s=num+"";
//r表示n所在数字中的位置
int r = (n-1)%digitCont;
return Integer.parseInt(s.substring(r,r+1));
}
