- 给定一个无序数组arr，返回如果排序之后，相邻数之间的最大差值
{3,1,7,9}，如果排序后{1,3,7,9}，相邻数之间的最大差值来自3和7，返回4
要求：不能真的进行排序，并且要求在时间复杂度O(N)内解决
public class MaxDifference {
public static int maxDifference(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
int len = arr.length;
// 先求出数组中的最大值和最小值
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
min = Math.min(min,arr[i]);
max = Math.max(max,arr[i]);
}
if(min == max){
// 说明差值为0
return 0;
}
// 准备数组长度加1个桶,桶中值存储这个桶的最大值，最小值，还有是否为空桶，
// 因为只有三个参数，所以可以用三个数组分别表示桶的三个变量
boolean[] isEmptyBucket = new boolean[len+1];
int[] maxNum = new int[len+1];
int[] minNum = new int[len+1];
for (int i = 0; i < len; i++) {
int index = getIndex(arr[i],len,max,min);
maxNum[index] = !isEmptyBucket[index] ? arr[i] : Math.max(maxNum[index],arr[i]);
minNum[index] = !isEmptyBucket[index] ? arr[i] : Math.min(minNum[index],arr[i]);
isEmptyBucket[index] = true;
}
// 遍历桶，求出相邻桶中的最大差值
int res = Integer.MIN_VALUE;
int pre = maxNum[0];
int cur = 0;
for (int i = 1; i < len + 1; i++) {
if(isEmptyBucket[i]){
cur = minNum[i];
res = Math.max(res,cur-pre);
pre = maxNum[i];
}
}
return res;
}
// 根据数字大小，和桶的大小，最大值和最小值确定元素属于桶的哪个下标
private static int getIndex(int num,int len,int max,int min){
return (int) ((num - min) * len / (max - min));
}
}
- 假设所有字符都是小写字母. 长字符串是str
arr是去重的单词表, 每个单词都不是空字符串且可以使用任意次
使用arr中的单词有多少种拼接str的方式，返回方法数.
/**
* 假设所有字符都是小写字母. 长字符串是str
* arr是去重的单词表, 每个单词都不是空字符串且可以使用任意次
* 使用arr中的单词有多少种拼接str的方式，返回方法数.
*/
public class WaysNum {
public static int waysNum(String str,String[] arr){
if(str == null || "".equals(str)){
return 0;
}
Set<String> set = new HashSet<>(Arrays.asList(arr));
return process(str,set,0);
}
// 从index位置开始在单词表中找有多少种拼接方式返回
private static int process(String str, Set<String> set, int index){
// 如果已经来到str.length()位置，说明前面都是有效的匹配获得一种拼接方式
if(index == str.length()){
return 1;
}
int ways = 0;
// 没有到最后字符,从index 位置开始，以index开头，枚举每一个前缀串是否匹配单词表
for (int end = index;end < str.length();end++){
String pre = str.substring(index,end+1);
if(set.contains(pre)){
// 这个前缀匹配上了，求后续
ways += process(str,set, end+1);
}
}
return ways;
}
// dp
public static int dp(String str,String[] arr){
if(str == null || "".equals(str)){
return 0;
}
Set<String> set = new HashSet<>(Arrays.asList(arr));
int[] dp = new int[str.length()+1];
dp[str.length()] = 1;
// 没有到最后字符,从index 位置开始，以index开头，枚举每一个前缀串是否匹配单词表
for (int i = str.length()-1; i >= 0; i--) {
int ways = 0;
for (int end = i;end < str.length();end++){
// 这里比对不可忽略导致整个复杂为O(n^3)
String pre = str.substring(i,end+1);
if(set.contains(pre)){
// 这个前缀匹配上了，求后续
ways += dp[end+1];
}
}
dp[i] = ways;
}
return dp[0];
}
// 利用前缀树加速查询，并且可以提前结束后续不能匹配的前缀（前缀树中路径已经没有了，那么这个前缀的后续都不可在匹配上了）
public static int preFixWithDp(String str,String[] arr){
if(str == null || "".equals(str)){
return 0;
}
Node root = new Node();
// 构建前缀树
buildPreFix(root,arr);
int[] dp = new int[str.length()+1];
dp[str.length()] = 1;
char[] c = str.toCharArray();
for (int i = str.length()-1; i >= 0; i--) {
int ways = 0;
Node cur = root;
for (int end = i;end < str.length();end++){
int path = c[end] - 'a';
if(cur.nexts[path] == null){
// 后续以i这个开头的都不用试了
break;
}
ways += cur.nexts[path].end == true ?dp[end+1] : 0 ;
cur = cur.nexts[path];
}
dp[i] = ways;
}
return dp[0];
}
private static void buildPreFix(Node node,String[] arr){
for (String s : arr){
Node cur = node;
char[] c = s.toCharArray();
for (int i = 0; i < c.length; i++) {
// 有路复用，无路新建
int path = c[i] - 'a';
if(cur.nexts[path] == null){
cur.nexts[path] = new Node();
}
cur = cur.nexts[path];
}
cur.end = true;
}
}
static class Node{
boolean end;
Node[] nexts;
public Node(){
// 题中说了只有小写字母
this.nexts = new Node[26];
}
}
}
- 给定一棵二叉树的头节点head，和一个数K
路径的定义:
可以从任何一个点开始，但是只能往下走，往下可以走到任何节点停止
返回路径累加和为K的所有路径中，最长的路径最多有几个节点？
/**
* 给定一棵二叉树的头节点head，和一个数K
* 路径的定义:
* 可以从任何一个点开始，但是只能往下走，往下可以走到任何节点停止
* 返回路径累加和为K的所有路径中，最长的路径最多有几个节点？
*/
public class MaxPathWithNode {
private static int nodeNum = 0;
public static int maxPathWithNode(Node head,int k){
if(head == null){
return 0;
}
// 此题可以用数组中求最长子数组和等于K的子数组长度的方法来求解。
HashMap<Integer,Integer> map = new HashMap<>();
// 一开始规定0这个累加和在-1的位置
map.put(0,-1);
process(head,0,0,k,map);
return nodeNum;
}
// cur 当前来到的节点，level,当前来到的层数，preSum 来到当前节点之前已经形成的累加和，map 记录某个累加和出现的层数
// 层数从0开始，也就是根节点处于第0层
private static void process(Node cur, int level,int preSum, int k, HashMap<Integer,Integer>map){
if(cur == null){
return;
}
// 来到当前节点所形成的累加和
int curNum = cur.value + preSum;
// curNum-k 在map中出现过吗？
if(map.containsKey(curNum - k)){
// 如果出现过那么就可以确定找到了一个前缀和为k的链
nodeNum = Math.max(nodeNum,level - map.get(curNum - k));
}
if(!map.containsKey(curNum)){
map.put(curNum,level);
}
// 左树去求一个答案
process(cur.left,level+1,curNum,k,map);
// 右树求一个答案
process(cur.right,level+1,curNum,k,map);
// 深度优先遍历，还原现场
if(map.get(curNum) == level){
map.remove(curNum);
}
}
static class Node{
int value;
Node left;
Node right;
public Node(int value){
this.value = value;
}
}
}
- 给定一个数组arr，已知除了一种数只出现1次之外，剩下所有的数都出现了k次，如何使用O(1)的额外空间，找到这个数。
/**
* 给定一个数组arr，已知除了一种数只出现1次之外，剩下所有的数都
* 出现了k次，如何使用O(1)的额外空间，找到这个数。
*/
public class FindOneNum {
public static int findOneNum(int[] arr,int k){
if(arr == null || arr.length == 0){
return 0;
}
// 思路，利用k进行来求解,32为二进制可以表示int类型的所有数，那么k进制要表示一个int
// 类型数，其实不需要32位，我们统一用一个32大小的数组来表示k进制
int[] kArr = new int[32];
// 把数组中的每一个数表示成k仅仅只放入kArr中，每个位置一次累加
// 让后对数组中每一个位置取模，值填入对应位置
for (int i = 0; i < arr.length; i++) {
numToK(kArr,arr[i],k);
}
// kArr中剩余的数一定是那个只出现了一次的数，把他转化为十进制
return kToDecimal(kArr,k);
}
private static int kToDecimal(int[] kArr,int k){
int res = 0;
for (int i = kArr.length-1; i >= 0 ; i--) {
// 逆序 高位 -> 低位
res = res*k + kArr[i];
}
return res;
}
// 填kArr
private static void numToK(int[] kArr,int num,int k){
int[] decimalToK = getDecimalToK(num, k);
// 把当前这个数的k进制加入到kArr中，本来是所有数都加完以后再取模的，
// 现在我们加一个数就取模是一样的，放置溢出
for (int i = 0; i < kArr.length; i++) {
// 如果真有一个数被出现k次，那么某个位置一定加了k次，对k取模一定是0
// 低位 -> 高位
kArr[i] = (kArr[i] + decimalToK[i]) % k;
}
}
// 十进制到k进制
private static int[] getDecimalToK(int num,int k){
int [] res = new int[32];
int index = 0;
while (num != 0){
res[index++] = num % k;
num /= k;
}
return res;
}
}
- 1.给定一个数组arr，如果有某个数出现次数超过了数组长度的一半，打印这个数，如果没有不打印。
2.给定一个数组arr和整数k，arr长度为N，如果有某些数出现次数超过了N/K，打印这些数，如果没有不打印。
/**
* 给定一个数组arr，如果有某个数出现次数超过了数组长度的一半，打印这个数，如果没有不打印
*
* 给定一个数组arr和整数k，arr长度为N，如果有某些数出现次数超过了N/K，打印这些数，如果没有不打印
*/
public class PrintMoreThanHalfNum {
// 第一问
public static void printMoreThanHalfNum(int[] arr){
if(arr == null || arr.length == 0){
System.out.println("No such number!");
}
// 当前遍历到的血量不为0的标志(数)
int flag = 0;
// 当前标志数的血量
int hp = 0;
// 每次删除不想同的两个数的逻辑
for (int i = 0; i < arr.length; i++) {
if(hp == 0){
flag = arr[i];
hp ++;
}else if(flag != arr[i]){
hp --;
}else {
hp ++;
}
}
if(hp == 0){
// 相当于全部删除完毕，没有这样的数
System.out.println("No such number!");
return;
}
// 可能存在这样的数flag
int count = 0;
for (int i = 0; i < arr.length; i++) {
count += arr[i] == flag ? 1 : 0;
}
if(count > (arr.length / 2)){
System.out.println(flag);
}else{
System.out.println("No such number!");
}
}
// 第二问
public static void printMoreThanHalfNum2(int[] arr,int k){
if(arr == null || arr.length == 0){
System.out.println("No such number!");
}
// 同理 n/2 时 最多有一个 n/3 时最多有两个 ...n/k时 最多有 k-1个
// 同时删除k个数，看最后剩下的那几个符合要求
// k : 对应的数字，v : 该数字对应的血量
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if(map.containsKey(arr[i])){
map.put(arr[i],map.get(arr[i])+1);
}else if(map.size() < k-1){
map.put(arr[i],1);
}else {
Set<Integer> keys = map.keySet();
for (Integer key : keys){
if(map.get(key) == 1){
map.remove(key);
}else{
map.put(key,map.get(key)-1);
}
}
}
}
if(map.size() == 0){
System.out.println("No such number!");
}
Set<Integer> keys = map.keySet();
for (Integer key : keys) {
if(map.get(key) > (arr.length / k)){
System.out.print(key + " ");
}
}
}
}
