摘要：示例输入输出示例输入输出说明输出结果中的每个元素一定是唯一的。示例输入输出示例输入输出说明输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。在完成所有重复项删除操作后返回最终的字符串。
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"输出: true示例 2:
输入: s = "rat", t = "car"输出: false提示:
1 <= s.length, t.length <= 5 * 104s 和 t 仅包含小写字母数组是一种最简单的哈希表，因为两个字符串只包含小写字母所以我们可以设置一个长度为26的数组，0-25分别对应a-z出现的次数，最后再遍历一次数组如果出现了不为1的元素就表明两个字符串不是有效的字母异位词
class Solution { public boolean isAnagram(String s, String t) { int[] result = new int[26]; for(int i = 0; i < s.length(); i++) { result[s.charAt(i) - "a"]++; } for(int j = 0; j < t.length(); j++) { result[t.charAt(j) - "a"]--; } for(int k = 0; k < 26; k++) { if(result[k] != 0) { return false; } } return true; }}O(n)
O(1)
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]输出：[2]示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出：[9,4]说明：
这道题是虚假的求交集，即只是求出元素并不要求元素的个数所以我们可以声明两个set集合，然后将两个set集合中包含的元素加入到结果数组中
也可以使用排序双指针求解这里就不做演示了
class Solution { public int[] intersection(int[] nums1, int[] nums2) { HashSet<Integer> set = new HashSet<>(); HashSet<Integer> set0 = new HashSet<>(); int i = 0; for(int item : nums1) { set.add(item); } for(int item : nums2) { if(set.contains(item)) set0.add(item); } int[] result = new int[set0.size()]; for(int item : set0) { result[i] = item; i++; } return result; }}O(n)
O(n)
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]输出：[2,2]示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出：[4,9]说明：
真正的求交集，和上一题一样也是两种思路，排序双指针的会简单一些
排序双指针
class Solution { public int[] intersect(int[] nums1, int[] nums2) { //将数组排序 Arrays.sort(nums1); Arrays.sort(nums2); //定义双指针分别指向两个数组的头部 int a = 0, b = 0; //定义结果集 int[] result = new int[Math.min(nums1.length,nums2.length)]; //定义遍历结果集指针 int k = 0; while(a < nums1.length && b < nums2.length) { if(nums1[a] == nums2[b]) { //第一种情况：如果两数相等就将数字加入到结果集中并让两个指针同时移动 result[k++] = nums1[a]; a++; b++; } else if(nums1[a] > nums2[b]) { //第二种情况：如果第一个数组的值大于第二个数组那么就让值小的数组的指针前移 b++; } else { //第三种情况：如果第二个数组的值大于第一个数组那么就让值小的数组的指针前移 a++; } } return Arrays.copyOfRange(result, 0, k); }}时间复杂度
O(n)
空间复杂度
O(n)
两个map模拟并集
class Solution { public int[] intersect(int[] nums1, int[] nums2) { //存储第一数组的元素和个数的key和value HashMap map0 = new HashMap<>(); //存储第二个数组的元素和个数的key和value HashMap map1 = new HashMap<>(); //存储并集 HashMap temp = new HashMap<>(); //将第一数组的元素和对应的元素存储到map中 for(int i = 0; i < nums1.length; i++) { if(map0.containsKey(nums1[i])) { map0.replace(nums1[i], map0.get(nums1[i]) + 1); } else { map0.put(nums1[i], 1); } } //将第二数组的元素和对应的元素存储到map中 for(int j = 0; j < nums2.length; j++) { if(map1.containsKey(nums2[j])) { map1.replace(nums2[j], map1.get(nums2[j]) + 1); } else { map1.put(nums2[j], 1); } } //模拟并集的过程，将两个数组的相同元素作为key并将元素个数的最小值作为value存储到result结集合中 for(int index : map0.keySet()) { if(map1.containsKey(index)) { temp.put(index,Math.min(map0.get(index), map1.get(index))); } } //定义数组长度 int length = 0; //将并集的长度求出来 //具体做法为将result集合中所有的value求和 for(int index : temp.values()) { length += index; } //定义返回数组 int[] result = new int[length]; /** * k 用来遍历数组 * e 限制每个key的value循环 */ int k = 0, e = 0; for(int index : temp.keySet()) { e = 0; while(e < temp.get(index)) { result[k++] = index; e++; } } return result; }} 时间复杂度
O(n)
空间复杂度
O(n)
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
如果 n 是快乐数就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19输出：true解释：12 + 92 = 8282 + 22 = 6862 + 82 = 10012 + 02 + 02 = 1示例 2：
输入：n = 2输出：false提示：
1 <= n <= 231 - 1将数通过%10分离个位数再通过/10移除个位数并让其他位数顺位减一，将分离完的个位数依次平方求和然后储存到set集合中，循环这个过程，如果平方和和set中的元素重复那么这个数就不是快乐数
class Solution { public boolean isHappy(int n) { //定义哈希set存储每次sum的值如果添加sum的时候sum重复了那就返回false HashSet set = new HashSet<>(); int sum = n; //如果sum不为1 while(sum != 1) { if(set.contains(sum)){ return false; }else{ set.add(sum); } sum = 0; while(n != 0) { sum += Math.pow(n % 10, 2); n /= 10; } n = sum; } return true; }} O(logn)
O(logn)
给定一个整数数组 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]示例 3：
输入：nums = [3,3], target = 6输出：[0,1]提示：
这道题求解思路很多，暴力硬A的，二分查找，也可以使用哈希表来求得
使用目标数字减去数组的值如果map中存在那么就返回这两个值如果map中不存在那么就将这个数组元素和数组下标存入map中
class Solution { public int[] twoSum(int[] nums, int target) { int[] result = new int[2]; if(nums == null || nums.length == 0) { return result; } HashMap<Integer,Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++) { int temp = target - nums[i]; if(map.containsKey(temp)) { result[0] = i; result[1] = map.get(temp); return result; } map.put(nums[i], i); } return result; }}O(n)
O(n)
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]输出：2解释：两个元组如下：1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 02. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]输出：1提示：
因为题解的最后是需要得到能够构成0的个数，所以我们可以将前两个数组的元素之和求出同时统计出现的次数记录到map中，然后再统计剩余元素的和，在map中寻找后两个元素相加求和的相反数如果能找到就记录出现的次数
class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { Map<Integer, Integer> map = new HashMap<>(); int temp; int res = 0; //统计两个数组中的元素之和，同时统计出现的次数，放入map for (int i : nums1) { for (int j : nums2) { temp = i + j; if (map.containsKey(temp)) { map.put(temp, map.get(temp) + 1); } else { map.put(temp, 1); } } } //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数 for (int i : nums3) { for (int j : nums4) { temp = i + j; if (map.containsKey(0 - temp)) { res += map.get(0 - temp); } } } return res; }}O(n^2)
O(n)
为了不在赎金信中暴露字迹，从杂志上搜索各个需要的字母，组成单词来表达意思。
给你一个赎金信 (ransomNote) 字符串和一个杂志(magazine)字符串，判断 ransomNote 能不能由 magazines 里面的字符构成。
如果可以构成，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b"输出：false示例 2：
输入：ransomNote = "aa", magazine = "ab"输出：false示例 3：
输入：ransomNote = "aa", magazine = "aab"输出：true提示：
因为只需要magazine中的字符在ransomNote中出现的次数一致就可以了，所以我们用数组来记录赎金信中的字母及其个数，然后将杂志中的元素进行比对
class Solution { public boolean canConstruct(String ransomNote, String magazine) { int[] result = new int[26]; for(int i = 0; i < ransomNote.length(); i++) { // 遍历赎金信并记录次数 result[ransomNote.charAt(i) - "a"]++; } for(int j = 0; j < magazine.length(); j++) { // 将杂志中的字符串和赎金信中的做比对 if(result[magazine.charAt(j) - "a"] != 0) result[magazine.charAt(j) - "a"]--; } for(int i = 0; i < 26; i++) { if(result[i] != 0) return false; } return true; }}O(n + m)
O(1)
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]示例 2：
输入：nums = []输出：[]示例 3：
输入：nums = [0]输出：[]排序双指针，首先确认第一个元素，如果第一个元素大于0就没有后续的必要了，因为不可以包含重复的三元组所以还涉及到了去重的操作，再确认好第一个元素之后，剩下两个元素的值也很好确认可以使用双指针来分别指向末尾和第一个元素后一位的元素
class Solution { public List<List<Integer>> threeSum(int[] nums) { //定义结果集LinkedList相比于ArrayList添加和删除效率比较高 List> result = new LinkedList>(); //如果数组长度小于3就不需要进行后续操作了直接返回空的结果集即可 if(nums.length < 3) { return result; } //我们采用排序双指针的方法方便去重的操作 Arrays.sort(nums); for(int i = 0; i < nums.length; i++) { //因为数组已经排过序了如果第一个值是正数后面就没必要比较了 if(nums[i] > 0) break; //如果从数组第二个值开始，当前元素和前一个元素相同那么直接跳过本次循环 if(i > 0 && nums[i - 1] == nums[i]) continue; //a > b > c 由于第一个元素的确认我们把他看作常数对待那么 满足函数 a(常数) + b(未知量) = -c(未知量) 形状有点像 y = -x int left = i + 1; int right = nums.length - 1; while(left < right) { // temp = a + b + c if(nums[left] + nums[right] == -nums[i]) { result.add(new LinkedList(Arrays.asList(nums[i], nums[left], nums[right]))); left++; right--; //去重操作 while(left < right && nums[left] == nums[left - 1]) left++; while(left < right && nums[right] == nums[right + 1]) right--; } else if(nums[left] + nums[right] > -nums[i]) { right--; } else if(nums[left] + nums[right] < -nums[i]) { left++; } } } return result; }} O(n^2)
O(n)
这道题和15题核心思路基本一致
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { //创建结果集 List> result = new LinkedList>(); if(nums.length < 4) { return result; } //排序双指针 Arrays.sort(nums); for(int i = 0; i < nums.length - 3; i++) { //去重 if(i > 0 && nums[i - 1] == nums[i]) { continue; } for(int j = i + 1; j < nums.length - 2; j++) { //去重 if(j > i + 1 && nums[j - 1] == nums[j]) { continue; } int left = j + 1; int right = nums.length - 1; int temp = target - nums[i] - nums[j]; while(left < right) { int sum = nums[left] + nums[right]; if(sum == temp) { result.add(new LinkedList(Arrays.asList(nums[i], nums[j], nums[left], nums[right]))); left++; right--; //去重 while(left < right && nums[left] == nums[left - 1]) left++; while(left < right && nums[right] == nums[right + 1]) right--; } else if(sum < temp) { left++; } else { right--; } } } } return result; }} 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
模拟题仔细就可以了
class MyQueue { //定义两个栈 Stack stack0 = null; Stack stack1 = null; //初始化两个栈 public MyQueue() { stack0 = new Stack<>(); stack1 = new Stack<>(); } //如果栈1不为空那就先将栈1的元素全部出栈添加到栈0然后向栈0中添加新元素 public void push(int x) { if(stack1.size() != 0) { while(stack1.size() != 0) { stack0.push(stack1.pop()); } } stack0.push(x); } //如果栈0中包含元素那么就将所有元素出栈并添加到栈1中移除并返回栈1的栈顶元素 public int pop() { if(stack0.size() != 0) { while(stack0.size() != 0) { stack1.push(stack0.pop()); } } return stack1.pop(); } //如果栈0中包含元素那么就将所有元素出栈并添加到栈1中返回栈1的栈顶元素 public int peek() { if(stack0.size() != 0) { while(stack0.size() != 0) { stack1.push(stack0.pop()); } } return stack1.peek(); } //查看栈0和栈1中是否含有元素 public boolean empty() { return stack1.isEmpty() && stack0.isEmpty(); }} 模拟题我是使用一个队列实现的
class MyStack { List<Integer> list0 = null; //初始化队列 public MyStack() { list0 = new LinkedList(); } public void push(int x) { list0.add(x); } public int pop() { return list0.remove(list0.size() - 1); } public int top() { return list0.get(list0.size() - 1); } public boolean empty() { return list0.isEmpty(); }} 栈很适合用来做匹配消除，遍历整个字符串，如果栈中元素不为空并且栈顶元素和对应的右括号匹配就弹出栈
class Solution { public boolean isValid(String s) { //定义一个栈 Stack stack = new Stack<>(); for(int i = 0; i < s.length(); i++) { if(!stack.isEmpty() && stack.peek() == isType(s.charAt(i))) { stack.pop(); continue; } stack.push(s.charAt(i)); } return stack.isEmpty(); } public char isType(char c) { char flag = "/0"; if(c == ")") { flag = "("; }else if(c == "]") { flag = "["; }else if(c == "}") { flag = "{"; } return flag; }} O(n)
O(n)
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
输入："abbaca"输出："ca"解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。/** * 第一种思路，用栈来实现 * 依次将字符串的字符入栈如果两两相当，那么就消除 */class Solution { public String removeDuplicates(String s) { LinkedList<Character> queue = new LinkedList<>(); char temp; for(int i = 0; i < s.length(); i++) { temp = s.charAt(i); // 如果栈为空或者栈顶元素不等于temp就入栈，否则就出栈 if(queue.isEmpty() || queue.peek() != temp) { queue.push(temp); } else { queue.pop(); } } // 剩余的元素就是最终字符串,但是由于栈的结构所以得出来的字符串是反的需要换一下 String result = ""; while(!queue.isEmpty()) { result += queue.pop(); } result = new StringBuffer(result).reverse().toString(); return result; }}/** * 第二种思路，字符串模拟栈 */class Solution { public String removeDuplicates(String s) { StringBuffer buffer = new StringBuffer(); char temp; // 记录buffer的长度，为什么是-1？ // 之所以是-1是因为第一个元素是默认添加的，它的索引值为0，此时为了能够判断第二次循环条件， // l模仿指向栈顶 int l = -1; for(int i = 0; i < s.length(); i++) { temp = s.charAt(i); // 如果此时字符串的尾部元素和temp相同那么就把字符串尾部删除,为了添加第一个元素所以需要设置temp >= 0 if(l >= 0 && temp == buffer.charAt(l)) { buffer.deleteCharAt(l); l--; } else { buffer.append(temp); l++; } } return buffer.toString(); }}/** * 第三种思路，双指针法,直接使用现有字符串使用双指针覆盖重复的元素 */class Solution { public String removeDuplicates(String s) { char[] c = s.toCharArray(); int slow = 0; for(int fast = 0; fast < s.length(); fast++) { c[slow] = c[fast]; // 如果slow指向的元素和slow-1所指向的元素相等那么就让slow指针后移，下次循环直接就覆盖掉了 if(slow > 0 && c[slow] == c[slow - 1]) { slow--; } else { slow++; } } return new String(c,0,slow); }}根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
示例 1：
输入：tokens = ["2","1","+","3","*"]输出：9解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9示例 2：
输入：tokens = ["4","13","5","/","+"]输出：6解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6求解逆波兰表达式，如果是数字直接入栈，如果是操作符，从栈中取出两个元素进行操作后再压入栈
class Solution { public int evalRPN(String[] tokens) { //定义一个栈便于存储运算数字 Stack<Integer> stack = new Stack<Integer>(); //因为遍历到+ - * /需要出栈两个字符计算后入栈所以设置两个变量 int a = 0; int b = 0; for(int i = 0; i < tokens.length; i++) { if ("+".equals(tokens[i])) { a = stack.pop(); b = stack.pop(); stack.push(b + a); } else if ("-".equals(tokens[i])) { a = stack.pop(); b = stack.pop(); stack.push(b - a); } else if ("*".equals(tokens[i]))
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/124497.html
摘要：此专栏文章是对力扣上算法题目各种方法的总结和归纳整理出最重要的思路和知识重点并以思维导图形式呈现当然也会加上我对导图的详解目的是为了更方便快捷的记忆和回忆算法重点不用每次都重复看题解毕竟算法不是做了一遍就能完全记住的所 ...
摘要：图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。因此使用一个数组代表每个节点的入度，若入度为就是叶子节点。 题目地址：https://leetcode-cn.com/probl...题目描述： 对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小...
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
此专栏文章是对力扣上算法题目各种方法的总结和归纳, 整理出最重要的思路和知识重点并以思维导图形式呈现, 当然也会加上我对导图的详解. 目的是为了更方便快捷的记忆和回忆算法重点(不用每次都重复看题解), 毕竟算法不是做了一遍就能完全记住的. 所以本文适合已经知道解题思路和方法, 想进一步加强理解和记忆的朋友, 并不适合第一次接触此题的朋友(可以根据题号先去力扣看看官方题解, 然后再看本文内容). 关...
阅读 1106·2021-11-23 09:51
阅读 1073·2021-10-18 13:31
阅读 2965·2021-09-22 16:06
阅读 4255·2021-09-10 11:19
阅读 2195·2019-08-29 17:04
阅读 424·2019-08-29 10:55
阅读 2471·2019-08-26 16:37
阅读 3368·2019-08-26 13:29
