...

https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/ 题面实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。 示例 1: 输入: haystack = “hello”, needle = “ll” 输出: 2 示例 2: 输入: haystack = “aaaaa”, needle = “bba” 输出: -1 说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。 思路 KMP，时间O(n+m)，空间O(m)KMP经典例题。 实现① 前缀表不减一C++ 1234567891011121314151617 ...

https://leetcode.cn/problems/reverse-words-in-a-string/ 题面给定一个字符串，逐个翻转字符串中的每个单词。 示例 1：输入: “the sky is blue”输出: “blue is sky the” 示例 2：输入: “ hello world! “输出: “world! hello”解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 示例 3：输入: “a good example”输出: “example good a”解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。 思路 时间O(n)，空间O(1)或O(n)用split这题就太简单，所以要求不要使用辅助空间，空间复杂度为O(1)。 解题思路如下： 移除多余空格 将整个字符串反转 将每个单词反转 解法①不使用Java内置方法。 去除首尾以及中间多余空格 反转整个字符串 反转各个单词 1234567891011121314151617181920212223242526272829303132333435363 ...

https://leetcode.cn/problems/reverse-string-ii/ 题面给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。 如果剩余字符少于 k 个，则将剩余字符全部反转。 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。 示例: 输入: s = “abcdefg”, k = 2输出: “bacdfeg” 解法①123456789101112131415161718192021public String reverseStr(String s, int k) { StringBuffer res = new StringBuffer(); int length = s.length(); int start = 0; while (start < length) { // 找到 k 处和 2k 处 StringBuffer temp = new Stri ...

https://leetcode.cn/problems/reverse-string/ 题面编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。 示例 1：输入：[“h”,”e”,”l”,”l”,”o”]输出：[“o”,”l”,”l”,”e”,”h”] 示例 2：输入：[“H”,”a”,”n”,”n”,”a”,”h”]输出：[“h”,”a”,”n”,”n”,”a”,”H”] 思路 双指针，时间O(n)，空间O(1)1234567891011121314151617181920public void reverseString(char[] s) { int l = 0; int r = s.length - 1; while (l < r) { // 常规swap写法 char tmp = s[l]; ...

https://leetcode.cn/problems/4sum/ 题面题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。 注意： 答案中不可以包含重复的四元组。 示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ] 思路 双指针 ，时间O(n^3)有个已经踩过坑的细节需要注意！ 不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。 思路和三数之和没太大区别，都是双指针，在三数之和的 ...

https://leetcode.cn/problems/3sum/ 题面给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。 注意： 答案中不可以包含重复的三元组。 示例： 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ] 思路① 双指针，时间O(n^2)，空间O(1)12345678910111213141516171819202122232425262728293031323334public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); // 找出 a + b + c = 0 // ...

https://leetcode.cn/problems/ransom-note/ 题面给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。 (题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。) 注意： 你可以假设两个字符串均只含有小写字母。 canConstruct(“a”, “b”) -> falsecanConstruct(“aa”, “ab”) -> falsecanConstruct(“aa”, “aab”) -> true 分析本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成，但是这里需要注意两点。 第一点“为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。 第二点 “你可以假设两个字符串均只含有小写字母。” ...

https://leetcode.cn/problems/4sum-ii/ 题面给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。 为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。 例如: 输入: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] 输出: 2 解释: 两个元组如下: (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0 思路：哈希，时间O(n ...

https://leetcode.cn/problems/two-sum/ 题面给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 思路① 暴力，时间O(n^2)，空间O(n^2)思路② 哈希，map，时间O(n)，空间O(n)想清楚map的key和value分别用来存什么——key存数字，value存下标。 12345678910111213141516public int[] twoSum(int[] sums, int target) { int[] res = new int[2]; if (nums == null || nums.length == 0) return res; ...

https://leetcode.cn/problems/happy-number/ 题面编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。 如果 n 是快乐数就返回 True ；不是，则返回 False 。 示例： 输入：19输出：true解释：1^2 + 9^2 = 828^2 + 2^2 = 686^2 + 8^2 = 1001^2 + 0^2 + 0^2 = 1 思路：哈希，时间O(log n)，空间O(log n)题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！（当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。） 还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。 123456789101112131415161718public boolean i ...