许愿腾讯二面！

import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.HashMap; import java.util.ArrayList; public class Main { static boolean[] visited; // 标记节点是否已经被访问 static int[] weight; // 节点权值 static int[] childNum; // 存储以节点i为根的树...

这道题实际上是求环形数组的连续子数组的最大和。 我们先不要去管数组是环形的情况，利用动态规划求解连续子数组的最大和以及最小和。(1) 不考虑环形得到的最大值：题中允许寿司首尾相连的环形数组情况，因此常规求得的连续子数组的最大和就是我们排除这种情况之外的所有情况中的最大和。(2) 只考虑环形得到的最大值：而对于首尾相连的情况，我们可以这样考虑，如果常规求得的连续子数组的和达到了最小，那么总和减去这个最小值就等于首尾相连情况的最大值了。因此最大的美味值就是(1)和(2)两种情况中大的那个。 接下来说下连续子数组的最大和：状态定义：dp[i]为以i结尾的连续子数组的最大和状态转移方程：dp[i]...

先记一下 打家劫舍的进阶 排成一排的房子 排成一圈的房子 排成二叉树的房子 不变的是不能偷相邻的房子。自顶向下是打劫了第0家开始，自底向上是打劫了第n-1家开始的。动态规划第一步是先确定状态和选择。选择就是 抢或不抢状态就是 房子的索引如果采用自顶向下递归法，就会存在重叠子问题，但是可以用备忘录来进行优化。 也可以采用自底向上递推的方式来解题，在这基础上可以降维，降低空间复杂度。 第二题的题解： int rob(int[] nums){ int n = nums.length; if(n == 1) return nums[0]; return Math.max(...

还是有点难的，但抓住重点 pre节点 + 迭代 class Solution { public void flatten(TreeNode root) { while(root != null){ if(root.left == null){ root = root.right; }else{ //先找到左子树最右的节点 TreeNode pre = root.left; while(pre !=...

贪心算法 + 前缀和 class Solution { public int findMaxLength(int[] nums) { int len = nums.length; if(len <= 1){ return 0; } //前缀和 int count = 0; //进行更新的 int maxLen = 0; //哈希表记录前缀和对应的索引 HashMap<Integer, Integer>...

拓扑排序是专门应用于有向图的算法，可用BFS和DFS的写法来实现。这里只用BFS。需要有个表记录每个节点的后驱节点以及数组来记录每个节点的入度数（前面有几个节点）。还需要有个队列来保证得到的都是先上的课程。 class Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { if(numCourses <= 0) return new int[0]; //记录每个节点的后驱节点们 HashSet<Intege...

插入排序就是默认左边第一个是已排序好的状态，然后在剩下的数中依次拿出来进行插入操作。 class Solution { public ListNode insertionSortList(ListNode head) { if(head == null || head.next == null) return head; ListNode start = head; //已排序子链表头 ListNode end = head; //已排序子链表尾 ListNode p = end.next; w...

参考了题解区的大佬题解： class Solution extends SolBase { public int rand10() { int num = (rand7() - 1) * 7 + rand7(); while(num > 40){ num = (rand7() - 1) * 7 + rand7(); } //进行了优化 return 1 + num % 10; } }就是记住 如果用小的数去随机生成大的数，利用公式：(randn() - 1) * n ...

这道题有思路，但是是很简单的暴力解题思路。感觉写起来太麻烦了，就考虑有什么数据结构能来帮助我减少遍历的次数，想了哈希表，链表...就是没想到用小根堆。学到了学到了~~以下是评论区第一的大佬题解： import java.io.*; import java.util.*; public class Main{ public static void main(String[] agrs) throws IOException{ BufferedReader reader = new BufferedReader(new InputStreamReader(System.in...

import java.io.*; public class Main{ //每个节点选择对应的开销 static int[][][] mem; static int[] weight; static int n; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt...

我好菜

就是等差数列求和，推出a1 = 2N-i(i-1) / 2i即可。i就是大等于L的长度。a1是第一项。 import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int L = sc.nextInt(); boolean flag = false; for(int i = L; i...

栈排序 重点在push操作 class SortedStack { Stack<Integer> stackMin; Stack<Integer> stack; public SortedStack() { stackMin = new Stack<>(); stack = new Stack<>(); } public void push(int val) { //放入栈中前，将最小的弹出，并放在辅助栈中 while(!stack....