一、观察表法
【算法中级学习1】小虎去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个 每袋的包装包装不可拆分。可是小虎现在只想购买恰好n个苹果，小虎想购买尽 量少的袋数方便携带。如果不能购买恰好n个苹果，小虎将不会购买。输入一个 整数n，表示小虎想购买的个苹果，返回最小使用多少袋子。如果无论如何都不 能正好装下，返回-1
/**
* @Author: 郜宇博
* @Date: 2021/11/18 14:19
*/
public class Bag {
public static void main(String[] args) {
for (int i = 1 ;
i < 100;
i ++){
if (minBags(i) != minBag1(i)){
System.out.println(i+" no");
}
}
}/**
* 袋子分为8，6两种，想让袋子数量最少，优先选择8
* 所以先m/8得出用几个8袋子，然后计算剩余的苹果数
* 查看剩余的苹果树是否可以被6整除，如果可以总袋数就等于bag8 + bag6
* 不可以就将8袋子所用数量-1，再计算剩余苹果树然后判断bag6,
* 当bag8减到0或者剩余苹果>24时，都不用继续了（因为>24肯定优先考虑bag8）
*/
public static int minBags(int m){
if ((m & 1)!= 0){
return -1;
}
if (m == 6 || m == 8){
return 1;
}
int bag6 = -1;
int bag8 = m / 8;
int rest = m - 8 * bag8;
while (rest < 24 && bag8 >= 0){
bag6 = rest % 6 == 0 ? rest/6: -1;
if (bag6 != -1){
return bag8 + bag6;
}
bag8--;
rest = m - (bag8 * 8);
}
return -1;
}
/**
* 观察表法
*/
public static int minBag1(int m){
if ( (m & 1) != 0){
return -1;
}
if (m < 18){
switch (m){
case 6:
case 8:
return 1;
case 12:
case 14:
case 16:
return 2;
default:
return -1;
}
}
return ((m - 18) / 8) + 3;
}
}
二、滑动窗口 给定一个有序数组arr，代表数轴上从左到右有n个点arr[0]、arr[1]...arr[n－1]， 给定一个正数L，代表一根长度为L的绳子，求绳子最多能覆盖其中的几个点。
/**
* 滑动窗口，让left一直向右走
* 先让绳子起始点处于ar[0]，记为L,然后伸长绳子看能否到下一点arr[1],一直到不可以伸长为止
* 当不可以伸长的时候，更新max,L++,一直到arr末尾
*/
public static int maxCount(int []arr,int L){
int left = 0;
int count = 0;
int max = Integer.MIN_VALUE;
//int count = 0;
for (left = 0;
left < arr.length;
left++){
count = 0;
while (left+count < arr.length && arr[left+count] - arr[left] <= L){
count++;
}
//更新max
max = Math.max(count,max);
}
return max;
}
三、预处理法 牛牛有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。牛牛现在可 以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将 会被覆盖。
牛牛的目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。
牛牛想知道他最少需要涂染几个正方形。
如样例所示: s = RGRGR 我们涂染之后变成RRRGG满足要求了,涂染的个数为2,没有比这个更好的涂染方案
/**
* @Author: 郜宇博
* @Date: 2021/11/18 16:38
*/
public class Color {
public static void main(String[] args) {
System.out.println(minColorCount("RGRGR"));
}/**
* 预处理法
* 将左侧都变为R,右侧都变为G
* 因此要逐个位置从左到右尝试，如将0的左边变为R，和[0,n-1]变为G
*1的左边变为R, [1,n-1]变为G
* 而要想求最小染色数，就需要知道左边范围有多少个G,右边范围有多少个R
* 也就是[0,i]多少个G,[i,n-1]有多少个R
* 有这两个结果，就可以遍历，不断更新min = [0,i]+[i+1,n-1];
*/
public static int minColorCount(String str){
int i = 0;
char[] chars = str.toCharArray();
int [] leftG = new int[chars.length];
int [] rightR = new int[chars.length];
int min = Integer.MAX_VALUE;
leftG[0] = chars[0] == 'G'?1:0;
rightR[chars.length-1] = chars[chars.length-1] == 'R'?1:0;
//预处理
for ( i= 1;
i < leftG.length;
i++){
leftG[i] = leftG[i-1] + ((chars[i] == 'G')?1:0);
}
for (i = rightR.length-2;
i >= 0;
i--){
rightR[i] = rightR[i+1] + ((chars[i] == 'R')?1:0);
}
for (i = 0;
i < chars.length;
i++){
if (i == 0){
min = Math.min(min,leftG[chars.length-1]);
}
else if (i == chars.length-1){
min = Math.min(min,rightR[0]);
}
else {
min = Math.min(min,leftG[i]+rightR[i+1]);
}
}
return min;
}
}
四、等概率返回 给定一个函数f，可以1～5的数字等概率返回一个。请加工出1～7的数字等概率 返回一个的函数g
/**
* @Author: 郜宇博
* @Date: 2021/11/18 18:24
*/
public class RandomNum {
public static void main(String[] args) {
for (int i = 0;
i < 10;
i++){
System.out.println(getRandom7());
}
}
public static int getRandom5(){
return (int) (Math.random() * 5) + 1;
}
/**
1-7等概率相当于0-6等概率+1
二进制表示的话，需要3位二进制可以表示到0-7，
所以需要一个 方法可以等概率返回0和1，
使用三次该方法，然后拼接到一起形成十进制的数，如果最后为7，那么重新使用三次。
这样可以得到0-6等概率，再+1就是1-7
*/
public static int getRandom7(){
int random7 = 0;
do {
int random1 = getRandom01();
int random2 = getRandom01();
int random3 = getRandom01();
random7 = random1 + (random2 << 1)+(random3<<2);
}while (random7 == 7);
return random7 + 1;
}/**
* 等概率返回0 和 1
* 使用等概率返回1-5 ：12345
* 大于3返回1 ，小于3返回0等于三重新使用
*/
public static int getRandom01(){
int random01 = 0;
do {
random01 = getRandom5();
}while (random01 == 3);
return random01 > 3?1:0;
}}
五、括号匹配 题1 需要多少额外的括号，才能将字符串的括号保持正确匹配
/**
* @Author: 郜宇博
* @Date: 2021/11/19 16:13
*/
public class NeedParentheses {
public static void main(String[] args) {for (int i =0 ;
i < 20;
i++){
String s = randomParentheses(10);
if (needParentheses(s) != needParentheses1(s)){
System.out.println("no");
}
}
}
public static String randomParentheses(int m) {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0;
i < m;
i++) {
int i1 = new Random().nextInt(10);
//奇
if ((i1 & 1) != 0){
stringBuilder.append("(");
}
else {
stringBuilder.append(")");
}
}
return stringBuilder.toString();
}
public static int needParentheses1(String str) {
int leftRest = 0;
int needSolveRight = 0;
for (int i = 0;
i < str.length();
i++) {
if (str.charAt(i) == '(') {
leftRest++;
} else {
if (leftRest == 0) {
needSolveRight++;
} else {
leftRest--;
}
}
}
return leftRest + needSolveRight;
}
/**
* 设置一个count变量
* 从左向右遍历。遇到左括号++，右括号--
* 在过程中如果count <0 ，那么说明单独出现了右括号，此时需要一个左括号
* 遍历结束后，如果count >0,说明左括号多了，需要count这么多的右括号
*/
public static int needParentheses(String str){
char[] chars = str.toCharArray();
//当前状态，<0代表缺'（'
int count = 0;
//需要多少额外的括号字符
int res = 0;
for (int i = 0;
i < chars.length;
i++) {
if (chars[i] == '('){
count++;
}
//遇到右括号
else {
//count--;
//if (count < 0){
////加一个左括号
//res++;
//count = 0;
//}
if (count == 0){
res++;
}else {
count--;
}
}
}
return res+ count;
}
}
题2 括号字符串的最大深度
public static int deep(String s) {
char[] str = s.toCharArray();
int count = 0;
int max = 0;
for (int i = 0;
i < str.length;
i++) {
if (str[i] == '(') {
max = Math.max(max, ++count);
} else {
count=0;
}
}
return max;
}
六、magic集合移动 给一个包含n个整数元素的集合a，一个包含m个整数元素的集合b。 定义magic操作为，从一个集合中取出一个元素，放到另一个集合里，且操作过 后每个集合的平均值都大于操作前。 注意以下两点：
1）不可以把一个集合的元素取空，这样就没有平均值了
2）值为x的元素从集合b取出放入集合a，但集合a中已经有值为x的元素，则a的 平均值不变（因为集合元素不会重复），b的平均值可能会改变（因为x被取出 了）
问最多可以进行多少次magic操作？
/**
* @Author: 郜宇博
* @Date: 2021/11/21 20:57
*/
public class MagicOp {
public static void main(String[] args) {
int[] arr1 = { 1, 2, 5 };
int[] arr2 = { 2, 3, 4, 5, 6 };
System.out.println(magic(arr1, arr2));
}/**
* 移动元素后，保证两个集合的平均值增大
* 1.保证移动的元素，不在目标集合中
*/
public static int magic(int []arr1,int[]arr2){
double sum1=0,sum2 = 0;
int [] smallList = null;
int [] largeList = null;
double largeSum = 0;
double smallSum = 0;
for (int value : arr1) {
sum1 += value;
}
for (int value : arr2) {
sum2 += value;
}
//平均值
double avg1 = getAvg(sum1,arr1.length);
double avg2 = getAvg(sum2,arr2.length);
if ( avg1 == avg2){
return 0;
}
if (avg1 > avg2){
//为集合赋值
largeList = arr1;
smallList = arr2;
largeSum = sum1;
smallSum = sum2;
}
else {
//为集合赋值
largeList = arr2;
smallList = arr1;
largeSum = sum2;
smallSum = sum1;
}
int largeSize = largeList.length;
int smallSize = smallList.length;
int result = 0;
HashSet smallSet = new HashSet();
for (int num: smallList){
smallSet.add(num);
}
for (int num: largeList){
double cur = num;
//移动元素在平均值中间，并且目标集合中不存在该元素
if (cur > getAvg(smallSum,smallSize) && cur < getAvg(largeSum,largeSize) && !smallSet.contains(cur)){
smallSet.add(num);
largeSize--;
largeSum-=num;
smallSum+=num;
smallSize++;
result++;
}
}
return result;
}
private static double getAvg(double sum, int size) {
if (size > 0 ){
return sum/ size;
}
return -1;
}
}
七、数字转化 将给定的数转换为字符串，原则如下：1对应 a，2对应b，…..26对应z，
例如12258 可以转换为"abbeh", "aveh", "abyh", "lbeh" and "lyh"，个数为5，
编写一个函数，给出可以转换的不同字符串的个数。
/**
* @Author: 郜宇博
* @Date: 2021/11/21 21:36
*/
public class NumberConvert {
public static void main(String[] args) {
int test = 111143311;
char[] arr = String.valueOf(test).toCharArray();
System.out.println(convertDP(arr));
}
public static int convert(char []arr,int index){
if (index == arr.length){
return 1;
}
if (arr[index] == '0'){
return 0;
}
//当前索引位作为一个字母
int res = convert(arr,index+1);
//两个索引位组合为字母 规则0-26
if ( (index +1) < arr.length
&&
((arr[index]-'0')*10 + (arr[index+1]-'0') < 27 )
){
res += convert(arr,index+2);
}
return res;
}
public static int convertDP(char[] arr){
int[] dp = new int[arr.length+1];
dp[arr.length] = 1;
dp[arr.length-1] = arr[arr.length-1] == '0'?0:1;
for (int i = arr.length-2;
i >=0;
i--){
if (arr[i] == '0'){
dp[i] = 0;
}
else {
dp[i] = dp[i+1];
if ((arr[i] -'0') *10 + (arr[i+1]-'0')<27 ){
dp[i] += dp[i+2];
}
}
}
return dp[0];
}
}
八、栈内排序 请编写一个程序，对一个栈里的整型数据，按升序进行排序（即排序前，栈里 的数据是无序的，排序后最大元素位于栈顶），要求最多只能使用一个额外的
栈存放临时数据，但不得将元素复制到别的数据结构中。
public static void sortWithStack(Stack stack){
Stack help = new Stack();
help.add(stack.pop());
//将栈内元素加入辅助栈中
while (! stack.isEmpty()){
int pop = stack.pop();
while (!help.isEmpty() && pop > help.peek()){
stack.add(help.pop());
}
//保证辅助栈的底部是大元素
help.add(pop);
}
//放回stack
while (!help.isEmpty()){
stack.add(help.pop());
}
while (!stack.isEmpty()){
System.out.print(stack.pop()+" ");
}
}
九、二叉树权值 二叉树每个结点都有一个int型权值，给定一棵二叉树，要求计算出从根结点到 叶结点的所有路径中，权值和最大的值为多少。
package day12;
/**
* @Author: 郜宇博
* @Date: 2021/11/21 22:17
*/
public class TreeSum {
public static void main(String[] args) {
Node head = new Node(4);
head.left = new Node(1);
head.left.right = new Node(5);
head.right = new Node(-7);
head.right.left = new Node(3);
System.out.println(getMax(head));
}
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int val) {
value = https://www.it610.com/article/val;
}
}
public static int getMax(Node node){
if (node == null){
return 0;
}
//叶节点
if (node.left == node && node.right == null){
return node.value;
}
//左、右节点权值
int rightSum = getMax(node.right);
int leftSum = getMax(node.left);
return Math.max(rightSum,leftSum) + node.value;
}
}
