goMars的学习随记

反转链表1.题目反转一个单链表。 示例： 给定二叉树 [3,9,20,null,null,15,7]， 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 2.分析这题的目的就是把两节点之间的指向反转 所以可以用双指针一个pre 一个cur ，让cur.next指向pre，再把双指针依次往后挪最后返回即可。 3.代码12345678910111213141516171819202122232425/** * 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 ...

二叉树的最大深度1.题目给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例： 给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。 2.分析遍历二叉树，先遍历左支再遍历右支，然后比较得出最大深度 3.代码12345678910111213141516171819202122232425/** * 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, Tre ...

翻转二叉树1.题目翻转一棵二叉树。 示例： 输入： 4 / \ 2 7 / \ / \ 1 3 6 9 输出： 4 / 7 2 / \ / 9 6 3 1 2.分析使用深度遍历即可,左右子字点互换即可。 3.代码12345678910111213141516171819202122232425262728/** * 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) { * ...

合并二叉树1.题目给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。 示例 1: 输入: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7输出:合并后的树: 3 / 4 5 / \ \ 5 4 7 2.分析使用深度遍历即可,可以new一个根节点也可以直接使用t1返回.显然直接使用t1效率更高和内存消耗更低 3.代码12 ...

子集1.题目给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1： 12输入：nums = [1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2： 12输入：nums = [0]输出：[[],[0]] 2.分析 使用回溯法，进行子集枚举。(排列组合子集都可以用到) 3.代码123456789101112131415161718class Solution { List<List<Integer>> ans = new ArrayList<>(); List<Integer> temp = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { dfs(0,nums); r ...

最大子序和1.题目给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例 1： 123输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 示例 2： 12输入：nums = [1]输出：1 示例 3： 12输入：nums = [0]输出：0 2.分析 使用动态规划,我们边遍历数组边算出当前的最大和，然后再比较之前的最大和得出最终的最大和 3.代码123456789101112131415class Solution { public int maxSubArray(int[] nums) { int[] dp = new int[nums.length]; //dp记录当前最大和 dp[0] = nums[0]; int ans = nums[0]; for (int i = 1; i < nums.length; i ...

删除字符串中的所有相邻重复项1.题目给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。 在 S 上反复执行重复项删除操作，直到无法继续删除。 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。 示例： 1234输入："abbaca"输出："ca"解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。 2.分析这题和有效括号类似，可以利用栈先进后出的特性来存储每个字符并判断得出最后结果 3.代码123456789101112131415161718class Solution { public String removeDuplicates(String S) { StringBuffer ...

只出现一次的数字1.题目给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 示例 1: 12输入: [2,2,1]输出: 1 示例 2: 12输入: [4,1,2,1,2]输出: 4 2.分析 我个人第一时间想到的是先排序再遍历看哪个是单出来的 (时间复杂度太高了) 还有一种是使用hashmap计数然后判断 官方给出的解法 使用异或 (数组中各数异或 最后只会得到不相同的一个) 3.代码 解法1： 1234567891011121314class Solution { public int singleNumber(int[] nums) { int len = nums.length; int ans=0; if(len==1){ ans = nums[0]; }else{ Arrays.sort(nums); boolean flag = fals ...

爬楼梯1.题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 2.分析经典的动态规划题目 我们用 f(x)f(x) 表示爬到第 xx 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出式子：f(x)=f(x−1)+f(x−2) 3.代码1234567891011121314151617class Solution { public int climbStairs(int n) { if(n<=1){ return n; } int ans=2; int pre1=1; int pre2=2; for (int i = 3; i <= n; i++) { ans=pre1+pre2; pre1=pre2; pre2=ans; } ...

移动零1.题目给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例: 12输入: [0,1,0,3,12]输出: [1,3,12,0,0] 2.分析先遍历数组，再遍历的过程中，若该数为0则用count记录次数，若不为0，则将该数放在 i - count 位上并该位变为0，直到遍历完成。 3.代码1234567891011121314151617class Solution { public void moveZeroes(int[] nums) { int len = nums.length,count=0; for (int i = 0; i < len; i++) { if(nums[i]==0){ count++; continue; }else if(i==0||count==0){ continue; ...