goMars的学习随记

翻转二叉树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; ...

有效的括号1.题目给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 2.分析这题括号的匹配刚好契合数据结构栈先进后出的特性。。所以就当输入为左括号时就入栈，当为右括号时就弹出栈顶元素进行匹配，匹配成功则继续，失败则直接返回false，这里有两个需要注意的地方就是当字符串长度为1时就肯定没效直接返回false，还有当循环结束了栈里面还有字符那说明也没用相应的匹配也返回false; 3.代码1234567891011121314151617181920212223242526272829303132333435363738394041class Solution { public boolean isValid(String s) { Stack<Character> stack = ...

找到所有数组中消失的数字1.题目给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。 找到所有在 [1, n] 范围之间没有出现在数组中的数字。 您能在不使用额外空间且时间复杂度为*O(n)*的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。 2.分析这题要求找出1到n数租缺少了哪一个，就开一个大小为n的数组，然后遍历nums把每个元素以坐标存在新开的数组中，最后统计看那个坐标的元素为0则就少哪个数。 3.代码12345678910111213141516class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { ArrayList<Integer> ans = new ArrayList<>(); int len = nums.length; int[] count = new int[len+1]; ...