面试资料

有效的字母异位词给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词 。 示例 1: 12输入: s = "anagram", t = "nagaram"输出: true 示例 2: 12输入: s = "rat", t = "car"输出: false 提示: 1 <= s.length, t.length <= 5 * 104 s 和 t 仅包含小写字母 123456789101112131415class Solution { public boolean isAnagram(String s, String t) { if(s.length()!=t.length()) return false; int[] table = new int[26]; for(int i=0;i<s.length();i++){ table[s.charAt(i ...

环形链表II给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 不允许修改 链表。 示例 1： 123输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。 提示： 链表中节点的数目范围在范围 [0, 104] 内 -105 <= Node.val <= 105 pos 的值为 -1 或者链表中的一个有效索引 容易想到的方法是哈希表。使用双指针优化 找到相遇点后，从相遇点和起点同时出发一个指针，第一个相遇的点就是环的起点。 123456789101112131415161718192021222324252627282930/** * De ...

链表相交给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。 图示两个链表在节点 c1 开始相交： 题目数据 保证 整个链式结构中不存在环。 注意，函数返回结果后，链表必须 保持其原始结构 。 示例 1： 12345输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3输出：Intersected at '8'解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 求出两个链表的长度之差，长的一条移动到和短的一条同样的位置，遍历整条链表并比较是否相等 1234567891011121314151617181920212223242526272829303132333435363 ...

删除链表的倒数第N个结点给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 示例 1： 12输入：head = [1,2,3,4,5], n = 2输出：[1,2,3,5] 示例 2： 12输入：head = [1], n = 1输出：[] 示例 3： 12输入：head = [1,2], n = 1输出：[1] 提示： 链表中结点的数目为 sz 1 <= sz <= 30 0 <= Node.val <= 100 1 <= n <= sz 进阶：你能尝试使用一趟扫描实现吗？ 经典双指针。 1234567891011121314151617181920212223242526272829/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { t ...

两两交换链表中的节点给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。 示例 1： 12输入：head = [1,2,3,4]输出：[2,1,4,3] 示例 2： 12输入：head = []输出：[] 示例 3： 12输入：head = [1]输出：[1] 提示： 链表中节点的数目在范围 [0, 100] 内 0 <= Node.val <= 100 这个题一定要给节点编号，要不太容易晕了。 其实很简单，就是当前节点对后面两个节点进行操作，三个节点互换位置 创建一个头节点n0,后面的两个节点分别表示为n1和n2,为了和上图对应。 为了不丢失2后面的链表，所以第一步操作是n1连接后边的：n1.next = n2.next 第二步，n2连接n1,n2.next = n1 第三步，n0.next = n2 最后头结点n0向后移动两个位置 1234567891011121314151617181920212223242526/** * Definition for singly-lin ...

反转链表给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 示例 1： 12输入：head = [1,2,3,4,5]输出：[5,4,3,2,1] 示例 2： 12输入：head = [1,2]输出：[2,1] 示例 3： 12输入：head = []输出：[] 提示： 链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000 看到链表要有一个虚空的意识，也就是除了链表的结点，其余都是null。 要反转链表，首先想到头插法可以反转，也就是新建一个头结点，遍历链表把链表头插到这个头结点上。 头结点的初始值可以设为null 1234567891011121314151617181920212223/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int va ...

设计链表你可以选择使用单链表或者双链表，设计并实现自己的链表。 单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。 如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。 实现 MyLinkedList 类： MyLinkedList() 初始化 MyLinkedList 对象。 int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。 void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。 void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。 void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 ...

螺旋矩阵 II给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1： 12输入：n = 3输出：[[1,2,3],[8,9,4],[7,6,5]] 示例 2： 12输入：n = 1输出：[[1]] 提示： 1 <= n <= 20 经典模拟题。做过好多遍了，每次写都忘。 定义两个数组，模拟移动方向 12345int[] dx = {0,1,0,-1};int[] dy = {1,0,-1,0};int d = 0;//d从0到3分别代表向右下上左四个方向移动//改变方向的条件是撞墙或者已经填好数 123456789101112131415161718192021class Solution { public int[][] generateMatrix(int n) { int[] dx = {0,1,0,-1}; int[] dy = {1,0, ...

二分查找给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 示例 1: 123输入: nums = [-1,0,3,5,9,12], target = 9输出: 4解释: 9 出现在 nums 中并且下标为 4 示例 2: 123输入: nums = [-1,0,3,5,9,12], target = 2输出: -1解释: 2 不存在 nums 中因此返回 -1 提示： 你可以假设 nums 中的所有元素是不重复的。 n 将在 [1, 10000]之间。 nums 的每个元素都将在 [-9999, 9999]之间。 二分查找模板题。 写法一 1234567891011121314class Solution { public int search(int[] nums, int target) { int l=0,r=nums.length-1; while(l<r){ ...

有序数组的平方给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。 示例 1： 1234输入：nums = [-4,-1,0,3,10]输出：[0,1,9,16,100]解释：平方后，数组变为 [16,1,0,9,100]排序后，数组变为 [0,1,9,16,100] 示例 2： 12输入：nums = [-7,-3,2,3,11]输出：[4,9,9,49,121] 提示： 1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums 已按 非递减顺序 排序 进阶： 请你设计时间复杂度为 O(n) 的算法解决本问题 最简单的做法直接计算平方后排序 123456789class Solution { public int[] sortedSquares(int[] nums) { for(int i=0;i<nums.length;i++){ nums[i]=nums[i ...