深度学习算法算法中级学习1

观察表法、滑动窗口、预处理法、栈内排序、括号匹配等一、观察表法小虎去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装包装不可拆分。可是小虎现在只想购买恰好n个苹果，小虎想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小虎将不会购买。输入一个整数n，表示小虎想购买的个苹果，返回最小使用多少袋子。如果无论如何都不能正好装下，返回-1
【深度学习算法算法中级学习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++;}//更新maxmax = 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<Integer> 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-26if ( (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<Integer> stack){Stack<Integer> help = new Stack<Integer>();help.add(stack.pop());//将栈内元素加入辅助栈中while (! stack.isEmpty()){int pop = stack.pop();while (!help.isEmpty() && pop > help.peek()){stack.add(help.pop());}//保证辅助栈的底部是大元素help.add(pop);}//放回stackwhile (!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://tazarkount.com/read/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;}}

深度学习算法 算法中级学习1

深度学习算法算法中级学习1