面试资料

最大子数组和给你一个整数数组 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 = [5,4,-1,7,8]输出：23 提示： 1 <= nums.length <= 105 -104 <= nums[i] <= 104 使用动态规划，f[i]表示以i结尾的最大连续子数组和 显然f[i]=max(f[i-1]+nums[i],nums[i])。因为f[i]必须要以i做结尾，所以必须包含nums[i]，f[i]就是f[i-1]+nums[i]和nums[i]中较大的那一个 12345678910111213class Solution { public int maxSubArray(int[] nums) { ...

滑动窗口的最大值给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1： 1234567891011输入：nums = [1,3,-1,-3,5,3,6,7], k = 3输出：[3,3,5,5,6,7]解释：滑动窗口的位置 最大值--------------- -----[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 示例 2： 12输入：nums = [1], k = 1输出：[1] 提示： 1 <= nums.length & ...

和为K的子数组给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。 示例 1： 12输入：nums = [1,1,1], k = 2输出：2 示例 2： 12输入：nums = [1,2,3], k = 3输出：2 提示： 1 <= nums.length <= 2 * 104 -1000 <= nums[i] <= 1000 -107 <= k <= 107 使用哈希表存储每个前缀和出现的次数 如果[j,i]这段区间和为k:sum[i]-sum[j-1]==k -> sum[i]-k==sum[j-1] 。 使用哈希表记录每个前缀和出现的次数，由于sum[j-1]先加入的哈希表，如果之后遍历到i，发现sum[i]-k也在哈希表中说明，[j,i]这段区间和为k.也就是当哈希表中存在sum[i]-k时就找到了满足条件的区间。 1234567891011121314class Solution { public int subarraySum ...

找到字符串中所有得到字母异位词给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 示例 1: 12345输入: s = "cbaebabacd", p = "abc"输出: [0,6]解释:起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。 示例 2: 123456输入: s = "abab", p = "ab"输出: [0,1,2]解释:起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。 提示: 1 ...

移动零给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 请注意 ，必须在不复制数组的情况下原地对数组进行操作。 示例 1: 12输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0] 示例 2: 12输入: nums = [0]输出: [0] 提示: 1 <= nums.length <= 104 -231 <= nums[i] <= 231 - 1 进阶：你能尽量减少完成的操作次数吗？ 设置两个指针i和j,i从头开始遍历数组，如果nums[j]==0,j就应该停在这个位置，直到nums[i]!=0,此时把nums[i]覆盖nums[j],并且j前进一个位置，nums[i]的值改为0. 12345678910111213141516class Solution { public void moveZeroes(int[] nums) { // 0 1 0 3 12 for(int i =0,j=0;i<nums.length ...

最长连续序列给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1： 123输入：nums = [100,4,200,1,3,2]输出：4解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 示例 2： 12输入：nums = [0,3,7,2,5,8,4,6,0,1]输出：9 提示： 0 <= nums.length <= 105 -109 <= nums[i] <= 109 第一次的做法是用一个哈希数组，<nums[i],出现次数>，问题就转化为了求数组的最长连续子序列长度。 没有注意nums[i]会有负数，所以错误.就算把nums[i]全部映射为正数，也会爆内存。 1234567891011121314151617181920212223class Solution { public int longestConsecutive(int[] nums) { int m ...

字母异位词分组给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 12输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]输出: [["bat"],["nat","tan"],["ate","eat","tea"]] 示例 2: 12输入: strs = [""]输出: [[""]] 示例 3: 12输入: strs = ["a"]输出: [["a"]] 提示： 1 <= strs.length <= 104 0 <= strs[i].length <= 100 strs[i] 仅包含小 ...

赎金信给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以，返回 true ；否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。 示例 1： 12输入：ransomNote = "a", magazine = "b"输出：false 示例 2： 12输入：ransomNote = "aa", magazine = "ab"输出：false 示例 3： 12输入：ransomNote = "aa", magazine = "aab"输出：true 提示： 1 <= ransomNote.length, magazine.length <= 105 ransomNote 和 magazine 由小写英文字母组成 这题很像上一道有效字母的异位词。 使用哈希表记录ransomNote中每个字母出现的次数 遍历ma ...

两数之和给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。 你可以按任意顺序返回答案。 示例 1： 123输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 示例 2： 12输入：nums = [3,2,4], target = 6输出：[1,2] 示例 3： 12输入：nums = [3,3], target = 6输出：[0,1] 提示： 2 <= nums.length <= 104 -109 <= nums[i] <= 109 -109 <= target <= 109 只会存在一个有效答案 问题的关键是如何快速找到j，使得，nums[i]==target-nums[j]. 使用哈希表，数组值作为k,对应下标作为v。遍历数组： 如果nums[i]作为下标在 ...

快乐数编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为： 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1，那么这个数就是快乐数。 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。 示例 1： 1234567输入：n = 19输出：true解释：12 + 92 = 8282 + 22 = 6862 + 82 = 10012 + 02 + 02 = 1 示例 2： 12输入：n = 2输出：false 提示： 1 <= n <= 231 - 1 这道题有两种情况： 是快乐数，经过一系列计算后n=1,返回真 不是快乐数，n会在几个数中循环，就像一个环形链表 第二种情况的证明过程很复杂，用到了不知道是极限还是无穷级数，没仔细看。总之挺复杂。但这道题的标签是简单。 12345678910111213141516171819202122232425262728class Solution { pu ...