牛客.判断是不是平衡二叉树
public static boolean IsBalanced_Solution (TreeNode pRoot) { return dfs(pRoot)!=-1; //如果是-1，表示他不是平衡二叉树 } public static int dfs(TreeNode root){ if(root==null) return 0; //当返回值不是-1的时候，返回的是树的高度 int left=dfs(root.left); if(left==-1) return -1;//剪枝,他用处理，就是他肯定不是平衡二叉树了，就直接不用看了，实际上没啥大用 int right=dfs(root.right); //假如这两个值不是-1，那么这两个值里面存储的是数的高度 if(right==-1)return -1;//剪枝 return Math.abs(left-right)<=1?Math.max(left,right)+1:-1; //是平衡二叉树，则返回左树和右树最大值+1 }
好写，不好想，不好理解
牛客.最大子矩阵
如何枚举出所有的子矩阵
所以枚举的时候，只需要枚举四个斜对角即可。
初始化我们的前缀和
这种用边表示的我不是很懂，所以我画了个图方便大家感受
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int m = scanner.nextInt(); int[][]a = new int[m + 1][m + 1]; for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { a[i][j] = scanner.nextInt(); } } int [][]dp = new int[m + 1][m + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + a[i - 1][j - 1]; } } int ret = -128; for (int i = 1; i <= m; i++) { for (int j = 1; j <= m; j++) { for (int x2 = i; x2 <= m; x2++) { for (int y2 = j; y2 <= m; y2++) { ret = Math.max(ret, dp[x2][y2] - dp[x2][j - 1] - dp[i - 1][y2] + dp[i - 1][j - 1]); } } } } System.out.println(ret); } }
假设染色体有10个，那么我们需要染红5个，才会相同，换句话说只需要选择长度为字符串一半即可
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); scanner.nextLine(); String b=scanner.nextLine(); char[]t=b.toCharArray(); int white0=0; int white1=0; for(int i=0;i<t.length;i++){ if(t[i]=='0'){ white0++;}else white1++; } int count=0; int left=0; int right=0; int half=n/2; int red0=0; int red1=0; while (right<n-1){ if(t[right]=='0'){ red0++; }else{ red1++;} while(right-left+1>half){ if(t[left]=='0'){ red0--; }else{ red1--;} left++; } if(right-left+1==half){ if(red0==white0/2&&red1==white1/2) count+=2; } right++; } System.out.println(count); } }
两个数组的交集
这个题好久之前做过，但是有点忘了，我最开始想的是排序，后来一看上面写着哈希，但是我哈希又不咋熟，突然想起来模拟哈希。模拟哈希，我开始又在想他是一个数字类型的hash,但是存了半天，又发现他有重复的数字，我不能两个加起来看是不是2 啥的，后来看题解，发现仅仅需要把哈希模拟成一个boolean类型，那么这样如何处理重复， 首先把1号全部设置为true,这样1号没有重复，然后去处理2号，看2号，如果也是要填到这个位置，那么就标记为true,然后我们再去想，处理重复问题，把当前放进去的位置，设置为false.
public ArrayList<Integer> intersection (ArrayList<Integer> nums1, ArrayList<Integer> nums2) { ArrayList<Integer> m = new ArrayList<Integer>(); boolean []hash = new boolean[1001]; for (int i = 0; i < nums1.size(); i++) { hash[nums1.get(i)] = true; } for (int i = 0; i < nums2.size(); i++) { if (hash[nums2.get(i)] == true) { m.add(nums2.get(i)); hash[nums2.get(i)] = false; } } return m; // write code here } }
牛客.数组中两个字符串的最小距离
思路:就是我们在遍历的过程中，我们使用两个变量，存储（我们判断好，哪个是相等的之后，我们要找距离这个位置最近的另一个变量，所以我们设置prev1是第一个,prev第二个
然后我们当找到第一个的时候，看看前面有没有另一个，如果有，那么就去更新，假如没有那么就去更新当前的prev1
Scanner scanner = new Scanner(System.in); int a = scanner.nextInt(); String b = scanner.next(); String c = scanner.next(); String[] t = new String[a]; scanner.nextLine(); for (int i = 0; i < a; i++) { t[i] = scanner.nextLine(); } int prev1 = -1; int prev2 = -1; int count = 0x3f3f3f3f; for (int i = 0; i < a; i++) { if (b.equals(t[i]) == true) { if (prev2 != -1) { count = Math.min(Math.abs(i - prev2), count); } prev1 = i; } else if (c.equals(t[i]) == true) { if (prev1 != -1) { count = Math.min(Math.abs(i - prev1), count); } prev2 = i; } } if (count == 0x3f3f3f3f) System.out.println(-1);else{ System.out.println(count);} }
