从入门到入土

1. 翻转二叉树 法一：递归 左子树 = 翻转后的左子树 右子树 = 翻转后的右子树 左子树和右子树交换位置 12345678910public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } TreeNode right = invertTree(root.right); TreeNode left = invertTree(root.left); root.left = right; root.right = left; return root;} 法二：迭代 这个方法的思路就是，我们需要交换树中所有节点的左孩子和右孩子。因此可以创一个队列来存储所有左孩子和右孩子还没有被交换过的节点。开始的时候，只有根节点在这个队列里面。只要这个队列不空，就一直从队列中出队节点，然后互换这个节点的左右孩子节点，接着再把孩子节点入队到队列，对于其中的空节点不需要加入队列。最终队列一定会 ...

1. 同构字符串 思路一：调用 api遍历字符串 s 和字符串 t 中的每一个元素，如果每个元素第一次出现的位置都相同，则两个字符串为同构字符串（不推荐） 12345678class Solution { public boolean isIsomorphic(String s, String t) { for (int i = 0; i < s.length(); i++) { if (s.indexOf(s.charAt(i)) != t.indexOf(t.charAt(i))) return false; } return true; }} 思路二：HashMap 建立映射关系两个字符串同构的含义就是字符串 s 可以唯一的映射到 t ，同时 t 也可以唯一的映射到 s 使用 HashMap，存入两个字符串中相映射的元素 12345678910111213141516171819egg 和 add 同构，就意味着下边的映射成立e -& ...

1. 判断子序列 我的思路：双指针建立两个指针 i，j，分别指向 s 和 t 当 s.charAt(i) == t.charAt(j) 时，两个指针均向后移动一位 否则，只将 j 后移一位 循环结束后，如果 i 等于 s 的长度，说明指针遍历过整个字符串 s，均找到 t 中与之相等的字母，故返回 true 123456789101112131415class Solution { public boolean isSubsequence(String s, String t) { int i = 0, j = 0; while (i < s.length() && j < t.length()) { if (s.charAt(i) == t.charAt(j)) { i++; j++; } else { j++; ...

1. 颠倒二进制位 解法一：调用 api使用 Integer 现成的 api 翻转二进制位 123456public class Solution { // you need treat n as an unsigned value public int reverseBits(int n) { return Integer.reverse(n); }} 不推荐这种做法，但是我们可以深究一步，看看 Integer.reverse() 方法究竟是怎样实现的 12345678910// Integer 源码public static int reverse(int i) { // HD, Figure 7-1 i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555; i = (i & 0x33333333) << 2 | (i >>> 2) & 0x3 ...

1. 组合两个表 解题思路 因为表 Address 中的 personId 是表 Person 的外关键字，所以我们可以连接这两个表来获取一个人的地址信息。 考虑到可能不是每个人都有地址信息，我们应该使用 outer join 而不是默认的 inner join。 作者：LeetCode链接：https://leetcode-cn.com/problems/combine-two-tables/solution/zu-he-liang-ge-biao-by-leetcode/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 1234select p.FirstName, p.LastName, a.City, a. Statefrom Person pleft join Address aon p.PersonId = a.PersonId; 2. 第二高的薪水 解题方法一：使用子查询和 LIMIT 子句 将不同的薪资按降序排序，然后使用 LIMIT 子句获得第二高的薪资。 然而，如果没有这样的第二最高工资，这个解决 ...

1. 相交链表 思路一：暴力求解对 headA 中的每一个节点，遍历 headB 中的每一个节点判断是否与其相等。 时间复杂度：O (mn) 空间复杂度：O (1) 思路二：借助哈希表将 headA 中的节点存入一个 HashSet 中，如果 headB 中有节点在 HashSet 中，则说明该节点为交叉点 时间复杂度：O (m + n) 空间复杂度：O (m) 思路三：浪漫双指针法创建两个指针分别指向 headA 、 headB，两个指针分别向前走，若相同则返回当前节点，若为空则指向另一条链表的头 初看很难理解，但是细想就会发现很简单很巧妙 A和B两个链表长度可能不同，但是 A+B 和 B+A 的长度是相同的，所以遍历 A+B 和遍历 B+A 一定是同时结束。 如果A, B相交的话A和B有一段尾巴是相同的，所以两个遍历的指针一定会同时到达交点 如果A,B不相交的话两个指针就会同时到达 A+B（B+A）的尾节点 1234567891011121314151617public class Solution { public ListNode get ...

1. 两个数组的交集 II 思路一： 使用 HashMap 将 nums1 中的元素加入到 map 中并统计所有数字出现的次数 遍历 nums2，若 nums2 中的元素在 map 中有，则将该元素加入到结果集中并且将 map 中该元素出现的次数减一 返回结果集 12345678910111213141516171819202122232425262728class Solution { public int[] intersect(int[] nums1, int[] nums2) { // 提高效率，遍历较小的数组，将其元素加入到 map 中 if (nums1.length > nums2.length) { return intersect(nums2,nums1); } Map<Integer, Integer> map = new HashMap<>(); for (int num: nums1)
...

前言寒假刚刚过去，暑假正式开始！ 开始刷 LeetCode 的第一天，计划每天两小时，从简单题开始，到刷完为止（刷不完就一直刷~~~） 1. 一维数组的动态和2. 拥有最多糖果的孩子3. 重新排列数组 我的思路： 引入一个空数组用于存放结果，使用两个指针分别指向原数组和新数组 指向原数组的指针每次加2，指向新数组的指针每次加1 我的代码：12345678910class Solution { public int[] shuffle(int[] nums, int n) { int[] res = new int[nums.length]; for(int i = 0, j = 0; j < n; i = i + 2, j++){ res[i] = nums[j]; res[i + 1] = nums[j + n]; } return res; }} 执行结果： 时间复杂度为 O(n) ，然而只击败26 ...

非连续内存分配优点 一个程序的物理地址是非连续的 更好的内存利用和管理 允许共享代码与数据 支持动态加载和动态链接 潜在问题 如何建立虚拟地址与物理地址之间的转换 软件方案 硬件方案 分段 分页 分段程序的分段地址空间 将逻辑地址空间分成各个块 如下图，需要一种运行机制，来使逻辑地址空间与物理地址空间之间有对应的关联 分段寻址方案 两种实现方案： 段寄存器 + 地址寄存器：将段号和段内偏移分开放置 单地址实现方案：将段号和段内偏移放在一起 分页 现在CPU主要使用分页方式 分页地址空间 与分段方式相似，同样拥有页号和偏移 不同之处在于分段中段的大小可变，而分页中页的大小固定的 帧（frame）和页（page）： 划分物理内存至固定大小的帧：大小是2的幂次方 划分逻辑地址空间至相同大小的页：大小也是2的幂次方 依据逻辑地址的页号到页表中查询出物理地址的帧号 建立方案转化逻辑地址为物理地址（pages to frames） 页的寻址方案 页表概述 页表其实就是一个大数 ...

功能目标 功能：当缺页中断发生，需要调入新的页面而内存已满时，选择当中哪个物理页面被置换。 目标：尽可能减少页面的换进换出次数。 页面锁定：将相关的页（必须常驻操作系统的关键部分）放在内存里面，确保操作系统随时能够正常工作 6.1 最优页面置换算法基本思路（如果能预知将来）根据将来什么时候访问，将距离再次使用间隔时间最长的页作为被置换的页面（不太实际，无法预知未来） 可用作其他算法的性能评价依据。 实例 6.2 先进先出算法（FIFO）基本思路选择在内存中驻留时间最长的页面并淘汰之。 系统维护着一个链表，记录了所有位于内存中的逻辑页面，链表首页驻留时间最长，尾部最短，发生缺页中断时，链表首页先淘汰，在链表尾部加入新的页面。 特点性能较差，调出的页面有可能是经常要访问的页面，并且有可能出现 Belady现象（后面讲），很少单独使用。 实例 6.3 最近最久未使用（LRU）基本思路当一个缺页中断发生时，选择最久未使用的那个页面并淘汰之。 根据过去推测将来。（过去使用的较少，推测将来使用的也会很少） 特点：LRU算法需要记录各个页面使用的先后顺序，开销比较大 两种可能的实现方式 ...