LeetCode刷题记录（简单题）
1. 两数之和 （3.7）
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
61ms(两个for循环，暴力解法)
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
}
2ms（使用hashmap）
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}
2. 两数相加 （3.8）
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 定义两个头指针，指向l1的头节点，l2的头节点
ListNode p1 = l1, p2 = l2;
// 定义一个存放结果的新的链表
ListNode dummy = new ListNode(-1);
// 定义一个头指针指向结果链表
ListNode p = dummy;
// 定义carry为进位数，newVal为每个链表同一列求和结果的单个数字
int carry = 0, newVal = 0;
while (p1 != null || p2 != null || carry > 0) {
newVal = (p1 == null ? 0: p1.val) + (p2 == null ? 0: p2.val) + carry;
carry = newVal / 10;
newVal %= 10;
p.next = new ListNode(newVal);
p1 = p1 == null? null: p1.next;
p2 = p2 == null? null: p2.next;
p = p.next;
}
return dummy.next;
}
}
1ms
3. 无重复字符的最长子串 （3.9）
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
4 ms
//每次左指针右移一位，移除set的一个字符，这一步会导致很多无用的循环。while循环发现的重复字符不一定就是Set最早添加那个，还要好多次循环才能到达，这些都是无效循环，不如直接用map记下每个字符的索引，直接进行跳转
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> map = new HashMap<>();
int max = 0, start = 0;
for (int end = 0; end < s.length(); end++) {
char ch = s.charAt(end);
if (map.containsKey(ch)){
start = Math.max(map.get(ch)+1,start);
}
max = Math.max(max,end - start + 1);
map.put(ch,end);
}
return max;
}
}
344. 反转字符串 （3.10）
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
2 ms
class Solution {
public void reverseString(char[] s) {
int len = s.length;
int size = len;
// 循环次数为数组长度的一半，只用将前一半和后一半交换就完成了
for(int i = 0;i < len/2;i++){
size--;
char tmp = s[i];
s[i] = s[size];
s[size] = tmp;
}
System.out.println(s);
}
}
21. 合并两个有序链表 （3.11）
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
（递归）
0ms
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
ListNode head = null;
if (list1.val <= list2.val){
head = list1;
head.next = mergeTwoLists(list1.next, list2);
} else {
head = list2;
head.next = mergeTwoLists(list1, list2.next);
}
return head;
}
}
94. 二叉树的中序遍历 （3.12）
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[2,1]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
（递归）0ms
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> List = new ArrayList<Integer>();
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null){
return List;
}
if(root.left!=null){
inorderTraversal(root.left);
}
List.add(root.val);
if(root.right!=null){
inorderTraversal(root.right);
}
return List;
}
}
206. 反转链表 （3.13）
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
////这道题大坑，一般来说链表的头节点是不放值的，只起了一个指向第一个节点的作用，但是这道题出题人直接就把head当成第一个节点了，只能说出题人水平不是很高
class Solution {
public ListNode reverseList(ListNode head) {
// 如果当前链表为空,或者只有一个节点,无需反转,直接返回
if(head == null || head.next == null){
return head;
}
// 定义一个辅助的指针(变量),帮助我们遍历原来的链表
ListNode cur = head;
ListNode next = null; // 指向当前节点[cur]的下一个节点
ListNode reverseHead = new ListNode(0,null);
// 遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表reverseHead的最前端
while(cur!=null){
next = cur.next;// 先暂时保存当前节点的下一个节点,因为后面需要用到
cur.next = reverseHead.next; // 将cur的下一个节点指向新的链表的最前端
reverseHead.next = cur; // 将cur连接到新的链表上
cur = next; // 让cur后移
}
// 将head.next 指向reverseHead.next,实现单链表的反转
head.next = reverseHead.next;
return head;
}
}
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur!=null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
0ms
104. 二叉树的最大深度 （3.14）
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
0ms
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return height(root);
}
public int leftHeight(TreeNode root){
if (root.left == null){
return 0;
}
return height(root.left);
}
public int rightHeight(TreeNode root){
if (root.right == null){
return 0;
}
return height(root.right);
}
public int height(TreeNode root){
return Math.max(root.left == null ? 0 : leftHeight(root), root.right == null? 0 : rightHeight(root))+1;
}
}
108. 将有序数组转换为二叉搜索树(3.14)
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
0ms
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
public TreeNode helper(int[] nums, int left, int right) {
if (left > right) {
return null;
}
// 总是选择中间位置左边的数字作为根节点
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
return root;
}
}
237. 删除链表中的节点（3.15）
请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。
题目数据保证需要删除的节点 不是末尾节点 。
示例 1：
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9
示例2：
输入：head = [1,2,3,4], node = 3
输出：[1,2,4]
示例 3：
输入：head = [0,1], node = 0
输出：[1]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
//既然不能先删除自己，那就把自己的值变成儿子，再把儿子的位置让给孙子,...,题目出得很水
node.val = node.next.val;
node.next = node.next.next;
}
}
136. 只出现一次的数字(3.15)
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
518ms
class Solution {
public int singleNumber(int[] nums) {
int temp = 0;
int count = 0;
for(int i = 0;i<nums.length;i++){
for(int j = 0;j<nums.length;j++){
if(nums[j] == nums[i]){
count++;
}
}
if(count == 1){
temp=nums[i];
}else{
count = 0;
}
}
return temp;
}
}
387. 字符串中的第一个唯一字符(3.16)
给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
示例 1：
输入: s = "leetcode"
输出: 0
示例 2:
输入: s = "loveleetcode"
输出: 2
示例 3:
输入: s = "aabb"
输出: -1
class Solution {
//直接判断第一个字符和最后一个字符的位置
public int firstUniqChar(String s) {
for(int i=0; i<s.length(); i++){
int first = s.indexOf(s.charAt(i));
int last = s.lastIndexOf(s.charAt(i));
if(first == last){
return i;
}
}
return -1;
}
}
23ms
202. 快乐数(3.16)
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
-
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
-
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
-
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入：n = 2
输出：false
0ms
class Solution {
public boolean isHappy(int n) {
int sum=n,count=0;
while(sum!=1){
if(count>8){
return false;
}
sum=add(sum);
count++;
}
return true;
}
public int add(int num){
int temp=0,sum=0;
while(num!=0){
temp=num%10;
sum+=temp*temp;
num/=10;
}
return sum;
}
}
27. 移除元素(3.17)
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
0ms
从数组第一个位置开始判断，不相等就覆盖原来数组的位置，相等的话继续判断下一个，下一个不相等的话，就把上一个相等的那个位置的元素用不相等的给覆盖了
class Solution {
public int removeElement(int[] nums, int val) {
if (nums == null || nums.length == 0)
return 0;
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[j] = nums[i];
j++;
}
}
return j;
}
}
26. 删除有序数组中的重复项(3.17)
给你一个 升序排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
0ms
一个指针留在原地，判断现在的位置与上一个位置的元素是否重复，重复的话，让另一个指针往下走，去找一个不重复的，找到了就把留在原地的指针的位置的元素给覆盖了，
class Solution {
public int removeDuplicates(int[] nums) {
//同向双指针
int i = 0;
int j = 0;
while (j < nums.length) {
if (i == 0 || nums[j] != nums[i - 1]) {
nums[i++] = nums[j++];
} else {
j++;
}
}
return i;
}
}
83. 删除排序链表中的重复元素(3.18)
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2]
输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
0ms
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
//递归
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
if (head.val == head.next.val) {
head = deleteDuplicates(head.next);
} else {
head.next = deleteDuplicates(head.next);
}
return head;
}
}
//非递归 ✔
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while(cur!=null&&cur.next !=null){
if(cur.val == cur.next.val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return head;
}
}
70. 爬楼梯（3.19）
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
0ms
class Solution {
public int climbStairs(int n) {
return fab(n);
}
public int fab(int n){
if(n==1){
return n;
}
if(n==2){
return n;
}
int i1 = 1;
int i2 = 2;
for(int i=3;i<=n;i++){
int temp = i1+i2;
i1 = i2;
i2 = temp;
}
return i2;
}
}
以下为能解决，但是超出时间限制的写法
class Solution {
public int climbStairs(int n) {
return fab(n);
}
public int fab(int n){
if(n==1){
return n;
}
if(n==2){
return n;
}
return fab(n-1) + fab(n-2);
}
}
606. 根据二叉树创建字符串（3.19）
你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例 1:
输入: 二叉树: [1,2,3,4]
1
/ \
2 3
/
4
输出: "1(2(4))(3)"
解释: 原本将是“1(2(4)())(3())”，
在你省略所有不必要的空括号对之后，
它将是“1(2(4))(3)”。
示例 2:
输入: 二叉树: [1,2,3,null,4]
1
/ \
2 3
\
4
输出: "1(2()(4))(3)"
解释: 和第一个示例相似，
除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。
7ms
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
StringBuilder sb = new StringBuilder();
public String tree2str(TreeNode root) {
if(root != null){
sb.append(root.val);
}else{
return null;
}
if(root.left != null || root.right != null){
sb.append('(');
tree2str(root.left);
sb.append(')');
if(root.right!=null){
sb.append('(');
tree2str(root.right);
sb.append(')');
}
}
return sb.toString();
}
}
9. 回文数（3.20）
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
- 例如，
121是回文，而123不是。
示例 1：
输入：x = 121
输出：true
示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
6ms
class Solution {
public boolean isPalindrome(int x) {
if(x<0){
return false;
}
String s =Integer.toString(x);
String reverse = new StringBuilder(s).reverse().toString();
if(s.equals(reverse)){
return true;
}
return false;
}
}
4ms 100%
class Solution {
public boolean isPalindrome(int x) {
if (x == 0) return true;
if (x < 0 || x % 10 == 0) return false;
int reversed = 0;
int temp = x;
while (x != 0) {
reversed = reversed * 10 + x % 10;
x /= 10;
}
return temp == reversed;
}
}
144. 二叉树的前序遍历(3.20)
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
0ms 100%
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> list = new ArrayList<Integer>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null){
return list;
}
list.add(root.val);
if(root.left == null && root.right == null){
return list;
}
if(root.left != null){
preorderTraversal(root.left);
}
if(root.right != null){
preorderTraversal(root.right);
}
return list;
}
}
145. 二叉树的后序遍历(3.21)
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
0ms 100%
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
if(root == null){
return list;
}
if(root.left != null){
postorderTraversal(root.left);
}
if(root.right != null){
postorderTraversal(root.right);
}
list.add(root.val);
return list;
}
}
110. 平衡二叉树(3.21)
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true
分析：
主要注意AVL树的概念是 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 ，是每个节点，不单单只是针对根节点
1 ms
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
if(Math.abs(leftHeight(root)-rightHeight(root))>1){
return false;
}
// 因为是每个节点都要满足，所以要递归循环下去，判断每个节点都满足才返回ture
return isBalanced(root.left) && isBalanced(root.right);
}
public int leftHeight(TreeNode root){
if (root.left == null){
return 0;
}
return height(root.left);
}
public int rightHeight(TreeNode root){
if (root.right == null){
return 0;
}
return height(root.right);
}
public int height(TreeNode root){
return Math.max(root.left == null ? 0 : height(root.left),root.right == null ? 0 : height(root.right))+1;
}
}
125. 验证回文串(3.21)
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
**说明：**本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串
示例 2:
输入: "race a car"
输出: false
解释："raceacar" 不是回文串
689 ms (一切只为了ac)
class Solution {
public boolean isPalindrome(String s) {
s = s.replaceAll("[^0-9a-zA-Z]", "");
return new StringBuilder(s).reverse().toString().equalsIgnoreCase(s);
}
}
653. 两数之和 IV - 输入 BST(3.21)
给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
示例 1：
输入: root = [5,3,6,2,4,null,7], k = 9
输出: true
示例 2：
输入: root = [5,3,6,2,4,null,7], k = 28
输出: false
思路：
因为二叉搜索树也就是二叉排序树，中序遍历出来的结果元素都是从小到大排序好的，先定义一个List存放元素的值，中序遍历后，把所有元素放到list里，两层循环判断list里的元素有没有两个相加等于k的，有就返回true，没有则false。
13 ms
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> list = new ArrayList<>();
public boolean findTarget(TreeNode root, int k) {
infixOrder(root);
for(int i = 0;i < list.size();i++){
for(int j = i+1;j < list.size();j++){
if(list.get(i)+list.get(j) == k){
return true;
}
}
}
return false;
}
// 中序遍历
public void infixOrder(TreeNode root){
if(root.left != null){
infixOrder(root.left);
}
list.add(root.val);
if (root.right != null){
infixOrder(root.right);
}
}
}
101. 对称二叉树（3.22）
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
0ms
思路：主要是得判断根节点的左子树的右子树等不等于根节点右子树的左子树，以及根节点的右子树的左子树和根节点的左子树的右子树是否相等。于是得想个办法可以同时操作到根节点的左子树和右子树，比如拿到左子树的第一个节点和右子树的第一个节点来操作，比如另起一个函数，参数为根节点的左子树和右子树即可，一开始想着在一个函数里面完成，不过这样就很难同时实现左右子树的操作判断。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null){
return true; //根节点为空，返回true
}
return dfs(root.left,root.right); //判断两棵子树是否对称
}
public boolean dfs(TreeNode l,TreeNode r){
if(l == null && r == null){
return true; //两个节点都为空
}else if(l==null||r==null){
return false; //只有一个为空
}
if(l.val != r.val){
return false;
}
//第一棵子树的左子树和第二棵子树的右子树对称，且第一棵子树的右子树和第二棵子树的左子树对称；
return dfs(l.left,r.right)&&dfs(l.right,r.left);
}
}
迭代（1ms）:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
if (node1 == null && node2 == null) {
continue;
}
if (node1 == null || node2 == null || node1.val != node2.val) {
return false;
}
queue.offer(node1.left);
queue.offer(node2.right);
queue.offer(node1.right);
queue.offer(node2.left);
}
return true;
}
}
111. 二叉树的最小深度（3.22）
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
**说明：**叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
6ms
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root==null){
return 0;
}
if(root.left!=null && root.right!=null){
return Math.min(minDepth(root.left),minDepth(root.right))+1;
}
if(root.left!=null){
return minDepth(root.left)+1;
}
if(root.right!=null){
return minDepth(root.right)+1;
}
return 1;
}
}
102. 二叉树的层序遍历（3.23）
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
0ms(递归)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
dns(root,0);
return list;
}
public void dns(TreeNode node,int lever){
if(node == null) return;
if(list.size()==lever) list.add(new ArrayList<Integer>());
list.get(lever).add(node.val); // 每一层都有一个独立的ArrayList<Integer>()，根据List<List<Integer>>的下标来获取对应层的ArrayList<Integer>()，比如0是第一层，1是第二层，2是第三层，即[[3],[9,20],[15,7]]
dns(node.left,lever+1);
dns(node.right,lever+1);
}
}
105. 从前序与中序遍历序列构造二叉树（3.23）
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
1ms(递归)(背)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int rootIndex = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < inorder.length; i++){
map.put(inorder[i],i);
}
return buildTree(map,0,preorder.length - 1,preorder);
}
//在前序遍历数组中，从前往后依次取到根节点，对应的去中序数组中确定左子树和右子树的范围，更符合人的思考方式
public TreeNode buildTree(Map<Integer,Integer> map,int left,int right,int[] preorder){
if(left <= right){
int rootVal = preorder[rootIndex];
TreeNode root = new TreeNode(rootVal);
rootIndex++;
root.left = buildTree(map,left,map.get(rootVal) - 1,preorder);
root.right = buildTree(map,map.get(rootVal) + 1,right,preorder);
return root;
}else{
return null;
}
}
}
203. 移除链表元素(3.23)
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
0ms （递归）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
//前两行增加一个header，这样避免前n个node 数据为val的情况
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode header = new ListNode(-1);
header.next = head;
ListNode cur = header; // 定义一个cur指针来辅助循环，header不动，head也不动。让cur让处理删除
while(cur.next != null){
if(cur.next.val == val ){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return header.next;
}
}
232. 用栈实现队列（3.24）
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
0ms
class MyQueue {
private Stack<Integer> a;// 输入栈
private Stack<Integer> b;// 输出栈
public MyQueue() {
a = new Stack<>();
b = new Stack<>();
}
public void push(int x) {
a.push(x);
}
public int pop() {
// 如果b栈为空，则将a栈全部弹出并压入b栈中，然后b.pop()
if(b.isEmpty()){
while(!a.isEmpty()){
b.push(a.pop());
}
}
return b.pop();
}
public int peek() {
if(b.isEmpty()){
while(!a.isEmpty()){
b.push(a.pop());
}
}
return b.peek();
}
public boolean empty() {
return a.isEmpty() && b.isEmpty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
217. 存在重复元素(3.24)
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：
输入：nums = [1,2,3,1]
输出：true
示例 2：
输入：nums = [1,2,3,4]
输出：false
示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true
744ms
class Solution {
public boolean containsDuplicate(int[] nums) {
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i]==nums[j]){
return true;
}
}
}
return false;
}
}
18ms
class Solution {
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for(int i=0;i<nums.length-1;i++){
if(nums[i] == nums[i+1]){
return true;
}
}
return false;
}
}
18ms
class Solution {
public boolean containsDuplicate(int[] nums) {
return Arrays.stream(nums).distinct().count() < nums.length
}
}
225. 用队列实现栈（3.25）
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
- void push(int x) 将元素 x 压入栈顶。
- int pop() 移除并返回栈顶元素。
- int top() 返回栈顶元素。
- boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
- 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
- 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
0ms
class MyStack {
private Queue queue1; // 输入队列
private Queue queue2; // 输出队列
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
queue1.offer(x);
while(!queue2.isEmpty()){
queue1.offer(queue2.poll());
}
Queue temp = queue1;
queue1 = queue2;
queue2 = temp;
}
public int pop() {
return (int) queue2.poll();
}
public int top() {
return (int) queue2.peek();
}
public boolean empty() {
return queue2.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
235. 二叉搜索树的最近公共祖先(3.25)
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
5ms
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
//可以利用二叉搜索树的特性
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 情况一，根节点即是祖先，大于或等于左节点，小于或等于右节点
if ((root.val - p.val)*(root.val - q.val) <= 0) {
return root;
} else if (root.val < p.val && root.val < q.val) { //情况二，根节点同时小于两个子树，说明他们的祖先在右节点，向右递归
return lowestCommonAncestor(root.right, p, q);
} else { //情况三，根节点同时大于两个子树，说明他们的祖先在左节点，向左递归
return lowestCommonAncestor(root.left, p, q);
}
}
}
226. 翻转二叉树（3.26）
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
0ms（递归）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null){
return root;
}
return invert(root);
}
public TreeNode invert(TreeNode root){
if(root == null){
return null;
}
if (root.left!=null||root.right!=null){
if(root.left==null){
invert(root.right); //递归右子树进行反转
root.left = root.right;
root.right = null;
}else if(root.right == null){
invert(root.left); //递归左子树进行反转
root.right = root.left;
root.left = null;
}else{
invert(root.right); //递归右子树进行反转
invert(root.left); //递归左子树进行反转
TreeNode temp;
temp = root.left;
root.left = root.right;
root.right = temp;
}
}
return root;
}
}
258. 各位相加（3.26）
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。
示例 1:
输入: num = 38
输出: 2
解释: 各位相加的过程为：
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
由于 2 是一位数，所以返回 2。
示例 2:
输入: num = 0
输出: 0
0ms
class Solution {
public int addDigits(int num) {
if(num / 10 == 0) return num;
int tmp = 0;
while(num > 0) {
tmp += num % 10; //第一次+个位，第二次+十位，第三次+百位
num /= 10; //第一次获取十位上的数字 第二次获取百位上的数字
}
return addDigits(tmp);
}
}
349. 两个数组的交集（3.26）
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
3ms
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<Integer>();
Set<Integer> set2 = new HashSet<Integer>();
for (int num : nums1) {
set1.add(num);
}
for (int num : nums2) {
set2.add(num);
}
return getIntersection(set1, set2);
}
public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {
if (set1.size() > set2.size()) {
return getIntersection(set2, set1);
}
Set<Integer> intersectionSet = new HashSet<Integer>();
for (int num : set1) {
if (set2.contains(num)) {
intersectionSet.add(num); // set里元素不可重复
}
}
int[] intersection = new int[intersectionSet.size()];
int index = 0;
for (int num : intersectionSet) {
intersection[index++] = num;
}
return intersection;
}
}
442. 数组中重复的数据（3.27）
给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。
示例 1：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[2,3]
示例 2：
输入：nums = [1,1,2]
输出：[1]
示例 3：
输入：nums = [1]
输出：[]
23ms
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> findDuplicates(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
Set<Integer> set = new HashSet<Integer>();
for(int i=0;i < n-1;i++){
if(nums[i] == nums[i+1]){
set.add(nums[i]);
}
}
int index = 0;
for (int num : set) {
list.add(num);
}
return list;
}
}
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> findDuplicates(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
Set<Integer> set = new HashSet<Integer>();
for(int i=0;i < n-1;i++){
if(nums[i] == nums[i+1]){
set.add(nums[i]);
}
}
// int index = 0;
// for (int num : set) {
// list.add(num);
// }
list.addAll(set);
return list;
}
}
22ms
461. 汉明距离（3.27）
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
示例 1：
输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
示例 2：
输入：x = 3, y = 1
输出：1
0ms
class Solution {
public int hammingDistance(int x, int y) {
int d = 0;
int z = x ^ y;
while (z != 0) {
z = z & (z - 1);
d++;
}
return d;
}
}
509. 斐波那契数(3.27)
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
示例 1：
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
8ms
class Solution {
public int fib(int n) {
if(n<2){
return n;
}else{
return fib(n-1)+fib(n-2);
}
}
}
面试题 08.06. 汉诺塔问题（3.28）
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; (3) 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。
示例1:
输入：A = [2, 1, 0], B = [], C = []
输出：C = [2, 1, 0]
示例2:
输入：A = [1, 0], B = [], C = []
输出：C = [1, 0]
提示:
- A中盘子的数目不大于14个。
0ms(分治法)
class Solution {
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
int num = A.size();
move(num,A,B,C);
}
public void move(int num,List<Integer> A, List<Integer> B, List<Integer> C){
// 如果只有一个盘
if (num == 1) {
C.add(A.remove(A.size()-1));
return;
} else {
// 如果我们有n >= 2情况 我们总是可以看做是两个盘 1 最下面的盘 2 上面所有的盘
// 1 先把上面的盘 a - > b 移动过程暂存到c
move(num- 1, A, C, B);
// 2 最下面的盘 a - > c
C.add(A.remove(A.size()-1));
// 3 上面的盘 b - > c 移动过程暂存到a
move(num- 1, B, A, C);
}
}
}
面试题 04.04. 检查平衡性(3.28)
实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
1ms(递归)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
boolean res;
//自己必须是平衡的
res = Math.abs(leftHeight(root)-rightHeight(root))<=1;
//左右节点必须也是平衡的
res = res && isBalanced(root.left) && isBalanced(root.right);
return res;
}
public int leftHeight(TreeNode root){
if (root.left == null){
return 0;
}
return height(root.left);
}
public int rightHeight(TreeNode root){
if (root.right == null){
return 0;
}
return height(root.right);
}
public int height(TreeNode root){
return Math.max(root.left == null ? 0 : height(root.left), root.right == null? 0 : height(root.right))+1;
}
}
100. 相同的树（3.29）
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2]
输出：false
0ms（递归）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null&&q==null){
return true;
}
if(p!=null && q!=null && p.val==q.val){
return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);
}else{
return false;
}
}
}
589. N 叉树的前序遍历(3.29)
给定一个 n 叉树的根节点 root ，返回 其节点值的 前序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[1,3,5,6,2,4]
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
0ms(递归)
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> preorder(Node root) {
if(root == null){
return list;
}
list.add(root.val);
if(root.children!=null){
for(Node node : root.children){
preorder(node);
}
}
return list;
}
}
590. N 叉树的后序遍历（3.29）
给定一个 n 叉树的根节点 root ，返回 其节点值的 后序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[5,6,3,2,4,1]
示例 2：
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
0ms(递归)
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> postorder(Node root) {
if(root == null){
return list;
}
if(root.children!=null){
for(Node node : root.children){
postorder(node);
}
}
list.add(root.val);
return list;
}
}
剑指 Offer 03. 数组中重复的数字（3.30）
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
3ms
class Solution {
public int findRepeatNumber(int[] nums) {
Arrays.sort(nums);
for(int i=0;i<nums.length-1;i++){
if(nums[i]==nums[i+1]){
return nums[i];
}
}
return -1;
}
}
//6ms
//方法2：hash表，时间O(n)，空间O(n)，不修改原数据
// public int findRepeatNumber(int[] nums) {
// HashSet<Integer> set = new HashSet<>();
// for(int num:nums){
// if(set.contains(num)) return num;
// set.add(num);
// }
// return -1;
// }
剑指 Offer 05. 替换空格(3.30)
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
0ms
class Solution {
public String replaceSpace(String s) {
return s.replace(" ","%20");
}
}
0ms
class Solution {
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < s.length(); i++){
char c = s.charAt(i);
if(c == ' ') sb.append("%20");
else sb.append(c);
}
return sb.toString();
}
}
剑指 Offer 06. 从尾到头打印链表（3.30）
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
0ms
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
ListNode node = head;
int count = 0;;
while(node != null){
++count;
node = node.next;
}
int[] nums = new int[count];
node = head;
for(int i = count-1;i>=0;i--){
nums[i] = node.val;
node = node.next;
}
return nums;
}
}
剑指 Offer 09. 用两个栈实现队列（3.30）
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
55ms
class CQueue {
Stack<Integer> stack1;
Stack<Integer> stack2;
public CQueue() {
stack1 = new Stack();
stack2 = new Stack();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
if (stack2.isEmpty()){
if(stack1.isEmpty()){
return -1;
}
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}else{
return stack2.pop();
}
}
}
/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/
剑指 Offer 10- I. 斐波那契数列（3.31）
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
0ms
class Solution {
public int fib(int n) {
if(n<2){
return n;
}
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i=2;i<=n;i++){
dp[i]=(dp[i-1]+dp[i-2])%1000000007;
}
return dp[n];
}
}
剑指 Offer 10- II. 青蛙跳台阶问题(3.31)
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
示例 3：
输入：n = 0
输出：1
提示：
0 <= n <= 100
0ms
class Solution {
public int numWays(int n) {
if(n==0){
return 1;
}
if(n==1||n==2){
return n;
}
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i=2;i<=n;i++){
dp[i]=(dp[i-1]+dp[i-2])%1000000007;
}
return dp[n];
}
}
剑指 Offer 11. 旋转数组的最小数字(3.31)
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
示例 1：
输入：numbers = [3,4,5,1,2]
输出：1
示例 2：
输入：numbers = [2,2,2,0,1]
输出：0
0ms（二分查找）
class Solution {
public int minArray(int[] numbers) {
int l = 0, r = numbers.length - 1;
while (l < r) {
int mid = (l+r)/2;
//只要右边比中间大，那右边一定是有序数组
if (numbers[r] > numbers[mid]) {
r = mid;
} else if (numbers[r] < numbers[mid]) {
l = mid + 1;
//去重
} else r--;
}
return numbers[l];
}
}
剑指 Offer 15. 二进制中1的个数(3.31)
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。
提示：
-
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
-
在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
示例 1：
输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：n = 128 (控制台输入 00000000000000000000000010000000)
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
0ms(调接口)
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
return Integer.bitCount(n);
}
}
0ms（暴力递归）
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count=0;
int flag=1;
while(flag!=0){
if((n&flag)!=0){
count++;
}
flag<<=1; // int 32位 移到最后 变为0
}
return count;
}
}
剑指 Offer 17. 打印从1到最大的n位数(4.1)
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
说明：
- 用返回一个整数列表来代替打印
- n 为正整数
1ms
class Solution {
public int[] printNumbers(int n) {
int m = (int)Math.pow(10,n); // 10的n次方，比如n=1，那么一位数的最大值为10-1,n=2，那么二位数最大值为100-1，n=3，那么三位数的最大值为1000-1;
int[] a = new int[m-1];
for(int i = 0;i<m-1;i++){
a[i] = i+1;
}
return a;
}
}
剑指 Offer 18. 删除链表的节点(4.1)
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
**注意：**此题对比原题有改动
示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明：
- 题目保证链表中节点的值互不相同
- 若使用 C 或 C++ 语言，你不需要
free或delete被删除的节点
0ms
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
// 判断头节点是否为空
if(head==null){
return head;
}
// 初始化待删除节点与其前置节点
ListNode deletedNode = head;
ListNode previousNode = null;
// 判断待删除节点是否为头节点
if(deletedNode.val==val){
return head.next;
}
// 寻找待删除节点
while(deletedNode.val!=val){
previousNode = deletedNode;
deletedNode = deletedNode.next;
}
// 通过更新指针来移除待删节点
// 待删节点的前置节点的指针指向待删除节点的后一个节点
previousNode.next = deletedNode.next;
return head;
}
}
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面(4.1)
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
提示：
0 <= nums.length <= 500000 <= nums[i] <= 10000
1ms （快排）
class Solution {
public int[] exchange(int[] nums) {
int l=0,r=nums.length-1;
while(l<r){
while(l<r&&nums[l]%2==1) l++; //左边是奇数
while(l<r&&nums[r]%2==0) r--; //右边是偶数
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
}
return nums;
}
}
剑指 Offer 22. 链表中倒数第k个节点(4.2)
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
0ms
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
if(head==null){
return null;
}
ListNode temp = head;
int count = 1;
while(temp.next!=null){
count++;
temp = temp.next;
}
int i = count - k;
while(i!=0){
i--;
head = head.next;
}
return head;
}
}
剑指 Offer 24. 反转链表(4.2)
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000
0ms
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur!=null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
剑指 Offer 25. 合并两个排序的链表(4.2)
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：
0 <= 链表长度 <= 1000
0ms(递归)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null){
return l2;
}
if(l2==null){
return l1;
}
ListNode head = null;
if(l1.val<=l2.val){
head = l1;
head.next = mergeTwoLists(l1.next,l2);
}else{
head = l2;
head.next = mergeTwoLists(l1,l2.next);
}
return head;
}
}
剑指 Offer 27. 二叉树的镜像（4.2）
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
镜像输出：
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
限制：
0 <= 节点个数 <= 1000
0ms(递归)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root==null){
return root;
}
if(root.left==null&&root.right==null){
return root;
}
TreeNode temp;
temp = root.left;
root.left = root.right;
root.right = temp;
if(root.left!=null){
mirrorTree(root.left);
}
if(root.right!=null){
mirrorTree(root.right);
}
return root;
}
}
剑指 Offer 28. 对称的二叉树（4.3）
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
限制：
0 <= 节点个数 <= 1000
0ms
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return help(root.left,root.right);
}
public boolean help(TreeNode left,TreeNode right){
if(left==null&&right==null){
return true;
}
if (left == null || right == null){
return false;
}
return left.val == right.val && help(left.left,right.right)&& help(left.right,right.left);
}
}
剑指 Offer 29. 顺时针打印矩阵(4.3)
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
限制：
0 <= matrix.length <= 1000 <= matrix[i].length <= 100
0ms
思路
其实相当于这样遍历一个矩阵
class Solution {
public int[] spiralOrder(int[][] matrix) {
int row = matrix.length;
if (row == 0) {
return new int[0];
}
int col = matrix[0].length;
int[] res = new int[row * col];
int idx = 0;
int left = 0, top = 0, right = col - 1, bottom = row - 1;
while (true) {
//从左往右走
for (int i = left; i <= right; i++) {
res[idx++] = matrix[top][i];
}
if (++top > bottom) {
break;
}
//从上往下走
for (int i = top; i <= bottom; i++) {
res[idx++] = matrix[i][right];
}
if (--right < left) {
break;
}
//从右往左走
for (int i = right; i >= left; i--) {
res[idx++] = matrix[bottom][i];
}
if (--bottom < top) {
break;
}
//从下往上走
for (int i = bottom; i >= top; i--) {
res[idx++] = matrix[i][left];
}
if (++left > right) {
break;
}
}
return res;
}
}
剑指 Offer 30. 包含min函数的栈（4.3）
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
提示：
- 各函数的调用总次数不超过 20000 次
11ms
class MinStack {
private Node head;
public MinStack() {
}
public void push(int x) {
if (head == null)
head = new Node(x, x, null);
else
head = new Node(x, Math.min(head.min, x), head);
}
public void pop() {
head = head.next;
}
public int top() {
return head.val;
}
public int min() {
return head.min;
}
private class Node {
int val;
int min;
Node next;
public Node(int val, int min, Node next) {
this.val = val;
this.min = min;
this.next = next;
}
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.min();
*/
*剑指 Offer 32 - II. 从上到下打印二叉树 II(4.4)
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
提示：
节点总数 <= 1000
0ms(递归层次遍历)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<List<Integer>> node=new ArrayList();
public List<List<Integer>> levelOrder(TreeNode root) {
help(root,0);
return node;
}
public void help(TreeNode root,int k){
if(root!=null){
if(node.size()<=k){
node.add(new ArrayList());
}
node.get(k).add(root.val);
help(root.left,k+1);
help(root.right,k+1);
}
}
}
剑指 Offer 39. 数组中出现次数超过一半的数字(4.4)
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
限制：
1 <= 数组长度 <= 50000
2ms
需要的数字出现次数多于一半 那么排序后必定在中间
class Solution {
public int majorityElement(int[] nums) {
int l = (nums.length)/2;
Arrays.sort(nums);
return nums[l];
}
}
1ms
class Solution {
public int majorityElement(int[] nums) {
// 摩尔投票法
int curNum = nums[0];
int votes = 0;
for(int num : nums){
if(num == curNum) votes++;
else votes = votes==0?0:votes-1;
if(votes == 0) {
curNum = num;
votes = 1;
}
}
return curNum;
}
}
7ms
关于Map中compute方法的使用 链接
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();// 键存放的是值，value放的是投票数
for (int i = 0; i < nums.length; i++) {
map.compute(nums[i], (k, v) -> v == null ? 1 : v + 1);
}
for (Integer k : map.keySet()) {
if (map.get(k) > nums.length / 2) {
return k;
}
}
return Integer.MIN_VALUE;
}
}
map.compute(nums[i], (k, v) -> v == null ? 1 : v + 1);
相当于
Integer curVal = map.get(nums[i]);
if (curVal == null) {
curVal = 1;
} else {
curVal += 1;
}
剑指 Offer 40. 最小的k个数(4.4)
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
限制：
0 <= k <= arr.length <= 100000 <= arr[i] <= 10000
6ms
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
Arrays.sort(arr);
return Arrays.copyOfRange(arr, 0, k);
}
}
7ms
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] vec = new int[k];
Arrays.sort(arr);
for (int i = 0; i < k; ++i) {
vec[i] = arr[i];
}
return vec;
}
}
*剑指 Offer 42. 连续子数组的最大和(4.4)
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
提示：
1 <= arr.length <= 10^5-100 <= arr[i] <= 100
1ms(动态规划)✔
class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = dp[0];
for(int i=1;i < nums.length;i++){
dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);
max = Math.max(max,dp[i]);
}
return max;
}
}
0ms(动态规划)
class Solution {
public int maxSubArray(int[] nums) {
int sum = 0;
int max = Integer.MIN_VALUE;
for (int num : nums) {
if (sum <= 0) {
sum = num;
} else {
sum += num;
}
max = Math.max(max, sum);
}
return max;
}
}
0ms(动态规划)
class Solution {
public int maxSubArray(int[] nums) {
int sum = 0;
int max = nums[0];
for(int num: nums) {
sum = Math.max(sum+num,num);
max = Math.max(sum, max);
}
return max;
}
}
剑指 Offer 50. 第一个只出现一次的字符（4.5）
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例 1:
输入：s = "abaccdeff"
输出：'b'
示例 2:
输入：s = ""
输出：' '
限制：
0 <= s 的长度 <= 50000
5ms
class Solution {
public char firstUniqChar(String s) {
//创建‘a'-'z'的字典
int[] target = new int[26];
//第一次遍历，将字符统计到字典数组
for (int i = 0; i < s.length(); i++) {
target[s.charAt(i) - 'a']++; // s.charAt(i) - 'a'的范围就在0-25之间，0-25代表就是a-z的26个字母的位置
}
//第二次遍历，从字典数组获取次数
for (int i = 0; i < s.length(); i++) {
if (target[s.charAt(i) - 'a'] == 1) return s.charAt(i);
}
return ' ';
}
}
剑指 Offer 52. 两个链表的第一个公共节点（4.5）
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
注意：
-
如果两个链表没有交点，返回 null.
-
在返回结果后，两个链表仍须保持原有的结构。
-
可假定整个链表结构中没有循环。
-
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
1ms(双指针)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null||headB==null){
return null;
}
ListNode n1 = headA;
ListNode n2 = headB;
while(n1!=n2){
n1 = n1 == null ? headB : n1.next; // 谁先到null说明它的链表较短，那么转移到另一条长的链表上多走一些路，等另一条链表跟上同步走
n2 = n2 == null ? headA : n2.next; // 谁慢到null说明它的链表较长，那么转移到另一条短的链表上多走一些路，追上另一条链表跟上同步走
}
return n1;
}
}
剑指 Offer 53 - I. 在排序数组中查找数字 I（4.5）
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
提示：
-
0 <= nums.length <= 105
-
-109 <= nums[i] <= 109
-
nums 是一个非递减数组
-
-109 <= target <= 109
0ms（for）
class Solution {
public int search(int[] nums, int target) {
int count = 0;
for(int num:nums){
if(num == target){
count++;
}
}
return count;
}
}
0ms（二分查找，只查找左边界）
class Solution {
public int search(int[] nums, int target) {
int left =0,right = nums.length-1;
int count = 0;
// 找目标的左边界
while(left<right){
int mid = (left+right)/2;
if(nums[mid]>=target)
right=mid;
if(nums[mid]<target)
left = mid+1;
}
while(left<nums.length&&nums[left++]==target) // 此时left在最左边的target的位置上，所以通过left++来计算个数
count++;
return count;
}
}
0ms（左右边界都查找）
class Solution {
public int search(int[] nums, int target) {
//二分查找
int pos;
int left = 0, right = nums.length;
//二分搜索左边界
while(left < right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
right = mid;
}else if(nums[mid] < target){
left = mid + 1;
}else if(nums[mid] > target){
right = mid;
}
}
int leftIndex = left;
//二分搜索右边界
left = 0;
right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target){
left = mid+1;
}else if(nums[mid] < target){
left = mid + 1;
}else if(nums[mid] > target){
right = mid;
}
}
int rightIndex = right;
return rightIndex - leftIndex;
}
}
剑指 Offer 53 - II. 0～n-1中缺失的数字（4.5）
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
对于有序的数组, 都应该想到用二分法搜索
0ms(遍历)
class Solution {
public int missingNumber(int[] nums) {
int l = nums.length;
for(int i=0;i<l;i++){
if(nums[i]!=i){
return i;
}
}
return l;
}
}
0ms(二分)
class Solution {
public int missingNumber(int[] nums) {
int i = 0, j = nums.length - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] == m) i = m + 1;
else j = m - 1;
}
return i;
}
}
剑指 Offer 54. 二叉搜索树的第k大节点（4.6）
给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4
限制：
- 1 ≤ k ≤ 二叉搜索树元素个数
1ms
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> List = new ArrayList<Integer>();
public int kthLargest(TreeNode root, int k) {
return List.get(List.size()-k);
}
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null){
return List;
}
if(root.left!=null){
inorderTraversal(root.left);
}
List.add(root.val);
if(root.right!=null){
inorderTraversal(root.right);
}
return List;
}
}
剑指 Offer 55 - I. 二叉树的深度（4.6）
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
提示：
节点总数 <= 10000
0ms
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return height(root);
}
public int leftHeight(TreeNode root){
if (root.left == null){
return 0;
}
return height(root.left);
}
public int rightHeight(TreeNode root){
if (root.right == null){
return 0;
}
return height(root.right);
}
public int height(TreeNode root){
return Math.max(root.left == null ? 0 : leftHeight(root), root.right == null? 0 : rightHeight(root))+1;
}
}
剑指 Offer 55 - II. 平衡二叉树（4.6）
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
限制：
0 <= 树的结点个数 <= 10000
1ms
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
boolean flag;
flag = Math.abs(leftHeight(root)-rightHeight(root))<=1;
flag = flag&&isBalanced(root.left)&&isBalanced(root.right);
return flag;
}
public int leftHeight(TreeNode root){
if (root.left == null){
return 0;
}
return height(root.left);
}
public int rightHeight(TreeNode root){
if (root.right == null){
return 0;
}
return height(root.right);
}
public int height(TreeNode root){
return Math.max(root.left == null ? 0 : leftHeight(root), root.right == null? 0 : rightHeight(root))+1;
}
}
剑指 Offer 57. 和为s的两个数字（4.7）
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2：
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
限制：
1 <= nums.length <= 10^51 <= nums[i] <= 10^6
44ms✔
class Solution {
public int[] twoSum(int[] nums, int target) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (!set.contains(target - num))
set.add(num);
else
return new int[]{num, target - num};
}
return new int[]{};
}
}
1ms（双指针）
class Solution {
public int[] twoSum(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while(i < j) {
int s = nums[i] + nums[j];
if(s < target) i++;
else if(s > target) j--;
else return new int[] { nums[i], nums[j] };
}
return new int[0];
}
}
*剑指 Offer 57 - II. 和为s的连续正数序列（4.7）
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
限制：
1 <= target <= 10^5
2ms（滑动窗口，太妙了- -）
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> list = new ArrayList<>();
//有一个区间的概念，这里的区间是(1, 2, 3, ..., target - 1)
//套滑动窗口模板，l是窗口左边界，r是窗口右边界，窗口中的值一定是连续值。
//当窗口中数字和小于target时，r右移; 大于target时，l右移; 等于target时就获得了一个解
for (int l = 1, r = 1, sum = 0; r < target; r++) {
sum += r;
while (sum > target) {
sum -= l++;
}
if (sum == target) {
int[] temp = new int[r - l + 1];
for (int i = 0; i < temp.length; i++) {
temp[i] = l + i;
}
list.add(temp);
}
}
int[][] res = new int[list.size()][];
for (int i = 0; i < res.length; i++) {
res[i] = list.get(i);
}
return res;
}
}
剑指 Offer 58 - I. 翻转单词顺序（4.8）
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
-
无空格字符构成一个单词。
-
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
-
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
1ms
class Solution {
public String reverseWords(String s) {
//将传进来的字符串以空格拆分
String[] strings = s.trim().split(" ");
StringBuilder stringBuilder = new StringBuilder();
//从尾巴开始遍历
for (int i = strings.length - 1; i >= 0; i--) {
if (strings[i].equals("")) {
continue;
}
//到头了，append然后去空格
if (i == 0) {
stringBuilder.append(strings[i].trim());
} else {
// 怕有多余的空格，去掉，再加上去
stringBuilder.append(strings[i]).append(" ");
}
}
//输出String 完事，安排！
return stringBuilder.toString();
}
}
剑指 Offer 58 - II. 左旋转字符串(4.8)
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
限制：
1 <= k < s.length <= 10000
0ms
class Solution {
public String reverseLeftWords(String s, int n) {
return s.substring(n)+s.substring(0,n);
}
}
3ms
class Solution {
public String reverseLeftWords(String s, int n) {
int len = s.length();
StringBuilder str = new StringBuilder();
for(int i =n;i<n+len;i++){
str.append(s.charAt(i%len));
}
return str.toString();
}
}
剑指 Offer 61. 扑克牌中的顺子(4.9)
从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
示例 1:
输入: [1,2,3,4,5]
输出: True
示例 2:
输入: [0,0,1,2,5]
输出: True
1ms
class Solution {
public boolean isStraight(int[] nums) {
Arrays.sort(nums);
boolean res = true;
int count = 0;
for(int i = 0;i<nums.length-1;i++){
if(nums[i]==0||nums[i+1]==0){
count++;
continue;
}
if(nums[i] == nums[i+1]){
return false;
}
if(nums[i]+1!= nums[i+1]){
if(count - Math.abs(nums[i+1]-nums[i]-1)>=0){
continue;
}
res = false;
break;
}
}
return res;
}
}
剑指 Offer 62. 圆圈中最后剩下的数字(4.9)
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3
输出: 3
示例 2：
输入: n = 10, m = 17
输出: 2
约瑟夫环问题
1042ms
class Solution {
public int lastRemaining(int n, int m) {
ArrayList<Integer> list = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
list.add(i);
}
int idx = 0;
while (n > 1) {
idx = (idx + m - 1) % n; //题目是从idx开始，是包含idx的，如果不-1就成了“idx后的第m个数”
list.remove(idx);
n--;
}
return list.get(0);
}
}
*剑指 Offer 65. 不用加减乘除做加法（4.10）
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1
输出: 2
提示：
a,b均可能是负数或 0- 结果不会溢出 32 位整数
0ms
观察发现，无进位和 与 异或运算 规律相同，进位 和 与运算 规律相同（并需左移一位）。因此，无进位和 nn 与进位 cc 的计算公式如下；
n=a⊕b 非进位和：异或运算 c=a&b<<1 进位 ：与运算+左移一位
非进位和：异或运算 进位：与运算+左移一位
class Solution {
public int add(int a, int b) {
while(b != 0) { // 当进位为 0 时跳出
int c = (a & b) << 1; // c = 进位
a ^= b; // a = 非进位和
b = c; // b = 进位
}
return a;
}
}
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先（4.10）
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
5ms
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 情况一，根节点即是祖先，大于或等于左节点，小于或等于右节点
if ((root.val - p.val)*(root.val - q.val) <= 0) {
return root;
} else if (root.val < p.val && root.val < q.val) { //情况二，根节点同时小于两个子树，说明他们的祖先在右节点，向右递归
return lowestCommonAncestor(root.right, p, q);
} else { //情况三，根节点同时大于两个子树，说明他们的祖先在左节点，向左递归
return lowestCommonAncestor(root.left, p, q);
}
}
}
*剑指 Offer 68 - II. 二叉树的最近公共祖先(4.10)
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
6ms
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
/**
* 二叉树的最近公共祖先
* 思路：
* 三种情况：
* 1、p q 一个在左子树 一个在右子树 那么当前节点即是最近公共祖先
* 2、p q 都在左子树
* 3、p q 都在右子树
* @param root
* @param p
* @param q
* @return
*left！= null 说明在当前节点的左子树找到了目标节点，这个left 可能是p 也可能是q right!=null 说明在右边 也找到了一个 ，p,q唯一的 左右都不为空说明在当前节点左右子树找到了p,q因为后序遍历自下而上，天然的当前节点就是最近的
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
if (root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
// p q 一个在左，一个在右
return root;
}
if (left != null) {
// p q 都在左子树
return left;
}
if (right != null) {
// p q 都在右子树
return right;
}
return null;
}
}
剑指 Offer II 003. 前 n 个数字二进制中 1 的个数(4.11)
给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
示例 1:
输入: n = 2
输出: [0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10
示例 2:
输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
说明 :
0 <= n <= 105
1ms
class Solution {
public int[] countBits(int n) {
// 从零开始统计,总是比给的n多出一位
int[] res = new int[n+1];
for(int index = 0 ; index < n+1 ;){
res[index] = res[index >> 1] +(index++ % 2);
}
return res;
}
}
*剑指 Offer II 002. 二进制加法(4.11)
给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "10"
输出: "101"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
提示：
- 每个字符串仅由字符
'0'或'1'组成。 1 <= a.length, b.length <= 10^4- 字符串如果不是
"0"，就都不含前导零。
1ms
class Solution {
public String addBinary(String a, String b) {
StringBuilder sb = new StringBuilder();
// 进位
int c = 0;
int i = a.length() - 1, j = b.length() - 1;
int ai = 0, bj = 0;
while(i >= 0 || j >= 0) {
ai = i < 0 ? 0 : a.charAt(i--) - '0';
bj = j < 0 ? 0 : b.charAt(j--) - '0';
// 计算当前位与进位*
sb.append(ai ^ bj ^ c);
c = (ai & bj) | ((ai ^ bj) & c);
}
if(c == 1) sb.append(c);
sb.reverse();
return sb.toString();
}
}
剑指 Offer II 006. 排序数组中两个数字之和（4.11）
给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。
假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。
示例 1：
输入：numbers = [1,2,4,6,10], target = 8
输出：[1,3]
解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[0,2]
示例 3：
输入：numbers = [-1,0], target = -1
输出：[0,1]
注意是排序数组，直接双指针即可
0ms
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left=0,right=numbers.length-1;
while(left<right) {
int sum = numbers[left] + numbers[right];
if(sum==target) {
int[] ans = new int[2];
ans[0] = left;
ans[1] = right;
return ans;
}else if(sum<target) {
++left;
}else{
--right;
}
}
return new int[0];
}
}
剑指 Offer II 001. 整数除法（4.12）
给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
注意：
- 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
- 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31−1]。本题中，如果除法结果溢出，则返回 2^31 − 1
示例 1：
输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7
示例 2：
输入：a = 7, b = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2
示例 3：
输入：a = 0, b = 1
输出：0
示例 4：
输入：a = 1, b = 1
输出：1
提示:
-231 <= a, b <= 231 - 1b != 0
2467ms
class Solution {
public int divide(int a, int b) {
if(a==0) return 0;
if(a==b) return 1;
if(a==Integer.MIN_VALUE&&b==-1) return Integer.MAX_VALUE;
int res = 0;
int flag = (a>0)^(b>0)?-1:1;
if(a>0) a=-a;// 将连个数化为同符号，便于相减
if(b>0) b=-b;// 将连个数化为同符号，便于相减
while(a<=b) {
a = a - b;
++res;
}
res = (flag==1)? res:-res;
return res;
}
}
*剑指 Offer II 012. 左右两边子数组的和相等（4.12）
给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
示例 1：
输入：nums = [1,7,3,6,5,6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等
示例 2：
输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。
示例 3：
输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
提示：
1 <= nums.length <= 104-1000 <= nums[i] <= 1000
0ms(前缀和)
先算出总和sum，再从最前面的下标开始，前缀和cur加一个下标的值，总和sum减一个下标的值，此时总和sum等于下标后面所有的值的和，即sum为后缀和，每次比较前缀和cur和后缀和sum的值，以此类推，下标不断后移，直到cur==sum。返回此时的下标即是中心下标。
class Solution {
public int pivotIndex(int[] nums) {
int sum=0,cur=0;
for(int i:nums) sum+=i;
for(int i=0;i<nums.length;i++){
sum-=nums[i];
if(cur==sum) return i;
cur+=nums[i];
}
return -1;
}
}
剑指 Offer II 018. 有效的回文（4.12）
给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。
本题中，将空字符串定义为有效的 回文串 。
示例 1:
输入: s = "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串
示例 2:
输入: s = "race a car"
输出: false
解释："raceacar" 不是回文串
提示：
1 <= s.length <= 2 * 105- 字符串
s由 ASCII 字符组成
824ms
class Solution {
public boolean isPalindrome(String s) {
String s1 = s.replaceAll("[^A-Za-z0-9]+", "");// 正则表达式，只考虑字母和数字字符，其他转为空字符串
char[] chars = s1.trim().toLowerCase().toCharArray(); // 去掉多余的空格，全部变为小写字母，转化为数组
for(int i=0,length=chars.length-1;i<=length;i++,length--){ // 从数组前缀和后缀分别开始比较
if (chars[i]!=chars[length]) return false;
}
return true;
}
}
4ms
class Solution {
public boolean isPalindrome(String s) {
StringBuilder str = new StringBuilder();
int length = s.length();
for (int i = 0; i < length; i++) {
char ch = s.charAt(i);
if (Character.isLetterOrDigit(ch)) { // 判断是否为字母或数字
str.append(Character.toLowerCase(ch)); // 是字母就转化为小写，并追加的新字符串str中
}
}
StringBuilder str_rev = new StringBuilder(str).reverse(); //反转
return str.toString().equals(str_rev.toString()); // 比较反转前后是否相等
}
}
剑指 Offer II 019. 最多删除一个字符得到回文(4.13)
给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
示例 1:
输入: s = "aba"
输出: true
示例 2:
输入: s = "abca"
输出: true
解释: 可以删除 "c" 字符 或者 "b" 字符
示例 3:
输入: s = "abc"
输出: false
提示:
1 <= s.length <= 105s由小写英文字母组成
6ms(双指针
/**
* 就是遇到一次不匹配的时候，跳过一下，左边跳过或者右边跳过。 相当于删除了一个字符
* 左边跳过 || 右边跳过
* 有一个满足回文就是回文
*/
class Solution {
public boolean validPalindrome(String s) {
int n = s.length();
int l = 0;
int r = n - 1;
while (l < r) {
if (s.charAt(l) == s.charAt(r)) {
l++;
r--;
} else {
return valid(s,l + 1,r) || valid(s,l,r - 1); // 左边跳过 || 右边跳过
}
}
return true;
}
public boolean valid(String s,int l,int r) {
while (l < r) {
if (s.charAt(l) != s.charAt(r)) {
return false;
}
l++;
r--;
}
return true;
}
}
剑指 Offer II 023. 两个链表的第一个重合节点(4.13)
给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：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 个节点。
示例 2：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
-
listA中节点数目为m -
listB中节点数目为n -
0 <= m, n <= 3 * 104 -
1 <= Node.val <= 105 -
0 <= skipA <= m -
0 <= skipB <= n -
如果
listA和listB没有交点，intersectVal为0 -
如果
listA和listB有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
1ms(双指针，短的先走完，然后指向长的链表，长的链表晚走完，然后指向短的链表，之后就会同步走)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null||headB==null){
return null;
}
ListNode n1 = headA;
ListNode n2 = headB;
while(n1!=n2){
n1=n1==null?headB:n1.next;
n2=n2==null?headA:n2.next;
}
return n1;
}
}
*剑指 Offer II 024. 反转链表（4.13）
给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
0ms
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode pre = null;
while(cur!=null){
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
*剑指 Offer II 027. 回文链表(4.13)
给定一个链表的 头节点 head **，**请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
示例 1：
输入: head = [1,2,3,3,2,1]
输出: true
示例 2：
输入: head = [1,2]
输出: false
提示：
- 链表 L 的长度范围为
[1, 105] 0 <= node.val <= 9
24ms
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
StringBuilder stringBuilder = new StringBuilder();
StringBuilder reverse = new StringBuilder();
while (head != null) {
stringBuilder.append(head.val);
reverse.append(head.val);
head = head.next;
}
reverse.reverse();
return stringBuilder.toString().equals(reverse.toString());
}
}
7ms
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<Integer>();
// 将链表的值复制到数组中
ListNode currentNode = head;
while (currentNode != null) {
vals.add(currentNode.val);
currentNode = currentNode.next;
}
// 使用双指针判断是否回文
int front = 0;
int back = vals.size() - 1;
while (front < back) {
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
}
剑指 Offer II 032. 有效的变位词(4.14)
给定两个字符串 s 和 t ，编写一个函数来判断它们是不是一组变位词（字母异位词）。
注意：若 s 和 t 中每个字符出现的次数都相同且字符顺序不完全相同，则称 s 和 t 互为变位词（字母异位词）。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
示例 3:
输入: s = "a", t = "a"
输出: false
提示:
1 <= s.length, t.length <= 5 * 104sandt仅包含小写字母
4ms
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length()!=t.length()||s.equals(t)){ // 如果长度不想通过或者两个字符串相同，返回false
return false;
}
int[] temp = new int[26]; // 下标对应1-26个字母
for(int i=0;i< s.length();i++){ // 这个时候字符串长度相同，内容不同，只需要将两个字符串中每个字母出现的个数统计到一个数组里面，第一个字符串添加字母，第二个字符串删掉字母，数组结果如果不全为0，就说明有字母的次数多余了。
temp[s.charAt(i)-'a']++;
temp[t.charAt(i)-'a']--;
}
for(int c : temp){
if(c != 0){
return false;
}
}
return true;
}
}
*剑指 Offer II 041. 滑动窗口的平均值（4.14）
给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。
实现 MovingAverage 类：
MovingAverage(int size)用窗口大小size初始化对象。- double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。
示例：
输入：
inputs = ["MovingAverage", "next", "next", "next", "next"]
inputs = [[3], [1], [10], [3], [5]]
输出：
[null, 1.0, 5.5, 4.66667, 6.0]
解释：
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // 返回 1.0 = 1 / 1
movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2
movingAverage.next(3); // 返回 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // 返回 6.0 = (10 + 3 + 5) / 3
提示：
1 <= size <= 1000-105 <= val <= 105- 最多调用
next方法104次
36ms
class MovingAverage {
int len;
double sum=0;
LinkedList<Integer> list;
/** Initialize your data structure here. */
public MovingAverage(int size) {
list = new LinkedList<>();
len = size;
}
public double next(int val) {
list.add(val);
sum+=val;
if(list.size()>len){
sum-=list.removeFirst(); // 重点
}
return sum/list.size();
}
}
/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage obj = new MovingAverage(size);
* double param_1 = obj.next(val);
*/
剑指 Offer II 042. 最近请求次数（4.15）
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请实现 RecentCounter 类：
-
RecentCounter() 初始化计数器，请求数为 0 。
-
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。
示例：
输入：
inputs = ["RecentCounter", "ping", "ping", "ping", "ping"]
inputs = [[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]
解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1); // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100); // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001); // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002); // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3
提示：
1 <= t <= 109- 保证每次对
ping调用所使用的t值都 严格递增 - 至多调用
ping方法104次
21ms
class RecentCounter {
Queue<Integer> queue;
public RecentCounter() {
queue = new LinkedList<>();
}
public int ping(int t) {
queue.offer(t);
while (queue.peek() < t - 3000) {
queue.poll();
}
return queue.size();
}
}
/**
* Your RecentCounter object will be instantiated and called as such:
* RecentCounter obj = new RecentCounter();
* int param_1 = obj.ping(t);
*/
18ms
class RecentCounter {
LinkedList<Integer> queue;
public RecentCounter() {
queue = new LinkedList<>();
}
public int ping(int t) {
queue.offer(t);
while(queue.peek() < t-3000) {
queue.poll();
}
return queue.size();
}
}
剑指 Offer II 052. 展平二叉搜索树(4.15)
给你一棵二叉搜索树，请 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
示例 1：
输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
示例 2：
输入：root = [5,1,7]
输出：[1,null,5,null,7]
提示：
- 树中节点数的取值范围是
[1, 100] 0 <= Node.val <= 1000
0ms(递归)
先中序遍历生成一个列表，根据列表重新生成树。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
ArrayList<Integer> arr;
public TreeNode increasingBST(TreeNode root) {
arr = new ArrayList<>();
inorder(root);
TreeNode res = new TreeNode(arr.get(0));
TreeNode cur = res;
for(int i = 1;i < arr.size();i++){
cur.right = new TreeNode(arr.get(i));
cur = cur.right;
}
return res;
}
public void inorder(TreeNode root){
if(root == null){
return;
}
inorder(root.left);
arr.add(root.val);
inorder(root.right);
}
}
0ms
*在中序遍历的过程中改变节点指向，生成树。
class Solution {
TreeNode res;
public TreeNode increasingBST(TreeNode root) {
TreeNode resNode=new TreeNode(-1);
res=resNode;
inorder(root);
return resNode.right;
}
public void inorder(TreeNode root){
if(root==null)
return;
inorder(root.left);
// 左孩子设为空，并将其本身作为上一个遍历到的节点的右节点
res.right=root;
root.left=null;
res=res.right;
inorder(root.right);
}
}
剑指 Offer II 056. 二叉搜索树中两个节点之和(4.16)
给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。
示例 1：
输入: root = [8,6,10,5,7,9,11], k = 12
输出: true
解释: 节点 5 和节点 7 之和等于 12
示例 2：
输入: root = [8,6,10,5,7,9,11], k = 22
输出: false
解释: 不存在两个节点值之和为 22 的节点
提示：
-
二叉树的节点个数的范围是 [1, 10^4].
-
-10^4 <= Node.val <= 10^4
-
root 为二叉搜索树
-
-10^5 <= k <= 10^5
13ms
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<Integer> list = new ArrayList<>();
public boolean findTarget(TreeNode root, int k) {
infixOrder(root);
for(int i = 0;i < list.size();i++){
for(int j = i+1;j < list.size();j++){
if(list.get(i)+list.get(j) == k){
return true;
}
}
}
return false;
}
// 中序遍历
public void infixOrder(TreeNode root){
if(root.left != null){
infixOrder(root.left);
}
list.add(root.val);
if (root.right != null){
infixOrder(root.right);
}
}
}
剑指 Offer II 059. 数据流的第 K 大数值(4.16)
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
- KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
- int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
示例：
输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]
解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8
提示：
- 1 <= k <= 104
- 0 <= nums.length <= 104
- -104 <= nums[i] <= 104
- -104 <= val <= 104
- 最多调用 add 方法 104 次
- 题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素
12ms
PriorityQueue本身就是一个小顶堆，将一些无序数据存进去，会自动排序成一个升序的数组。 可以用来寻找第k元素，即初始化一个k大小的PriorityQueue，不断将数据放进去，如果大于堆顶元素，则poll出堆顶元素，把该数据放进去，最后得到的堆顶元素就是所要求的第k个元素。
class KthLargest {
PriorityQueue<Integer> queue;
int k;
public KthLargest(int k, int[] nums) {
queue = new PriorityQueue<>();
this.k = k;
for(int num : nums){
queue.add(num);
}
while(queue.size() > k){
queue.poll();
}
}
public int add(int val) {
queue.add(val);
if(queue.size() > k){
queue.poll();
}
return queue.peek();
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/
剑指 Offer II 068. 查找插入位置(4.17)
给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
示例 4:
输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:
输入: nums = [1], target = 0
输出: 0
提示:
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums 为无重复元素的升序排列数组
- -104 <= target <= 104
0ms(二分法)
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while(left<=right){
int mid = (left+right)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid]>target){
right = mid-1;
}else if(nums[mid]<target){
left = mid+1;
}
}
return left;
}
}
剑指 Offer II 069. 山峰数组的顶部(4.17)
符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：
-
arr.length >= 3 -
存在 i（0 < i < arr.length - 1）使得：
- arr[0] < arr[1] < ... arr[i-1] < arr[i]
- arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i ，即山峰顶部。
示例 1：
输入：arr = [0,1,0]
输出：1
示例 2：
输入：arr = [1,3,5,4,2]
输出：2
示例 3：
输入：arr = [0,10,5,2]
输出：1
示例 4：
输入：arr = [3,4,5,1]
输出：2
示例 5：
输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2
提示：
3 <= arr.length <= 1040 <= arr[i] <= 106- 题目数据保证
arr是一个山脉数组
0ms(循环)
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int max = 0;
int res = 0;
for(int i=0;i<arr.length;i++){
if(arr[i]>=max){
max = arr[i];
res = i;
}
}
return res;
}
}
0ms（二分）
class Solution {
public int peakIndexInMountainArray(int[] arr) {
if (arr.length == 3) {
return 1;
}
// 肯定不是 0 和 arr.length - 1
int low = 1, high = arr.length - 2;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
return mid;
} else if (arr[mid] < arr[mid + 1]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}
剑指 Offer II 075. 数组相对排序(4.18)
给定两个数组，arr1 和 arr2，
arr2中的元素各不相同arr2中的每个元素都出现在arr1中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
提示：
- 1 <= arr1.length, arr2.length <= 1000
- 0 <= arr1[i], arr2[i] <= 1000
- arr2 中的元素 arr2[i] 各不相同
- arr2 中的每个元素 arr2[i] 都出现在 arr1 中
0ms(计数统计)
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
//统计各元素出现次数
int[] res = new int[1001];
for (int num : arr1) {
res[num]++;
}
int index = 0;
//遍历 arr2，以 arr2的顺序填arr1数组
for (int num : arr2) {
//得到 num 元素的个数，并往arr1填充
for (int i = 0; i < res[num]; i++) {
arr1[index++] = num;
}
//每一个 num元素填充完，对应res的位置值置为0
res[num] = 0;
}
//将剩下的数字按序填入arr1
for (int i = 0; i < res.length; i++) {
for (int j = 0; j < res[i]; j++) {
arr1[index++] = i;
}
}
return arr1;
}
}
剑指 Offer II 088. 爬楼梯的最少成本(4.18)
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。
请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例 1：
输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
示例 2：
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
提示：
2 <= cost.length <= 10000 <= cost[i] <= 999
0ms
class Solution {
//动规
public int minCostClimbingStairs(int[] cost) {
if(cost==null||cost.length==0){
return 0;
}
if(cost.length==1){
return cost[0];
}
//原地修改数组
for(int i=2;i<cost.length;i++){
//类似于斐波那契数列 f(n) = f(n-1) + f(n-2)
cost[i]+=Math.min(cost[i-2],cost[i-1]);
}
//到达楼顶只能是 从楼顶的前两节楼梯跳上来 或者 从楼顶的前一节楼梯爬上来
return Math.min(cost[cost.length-2],cost[cost.length-1]);
}
}
面试题 02.03. 删除中间节点(4.19)
若链表中的某个节点，既不是链表头节点，也不是链表尾节点，则称其为该链表的「中间节点」。
假定已知链表的某一个中间节点，请实现一种算法，将该节点从链表中删除。
例如，传入节点 c（位于单向链表 a->b->c->d->e->f 中），将其删除后，剩余链表为 a->b->d->e->f
示例：
输入：节点 5 （位于单向链表 4->5->1->9 中）
输出：不返回任何数据，从链表中删除传入的节点 5，使链表变为 4->1->9
0ms
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
评论