在B不在A的数 问题陈述 一个有序数组 A，另一个无序数组 B，请打印在数组 B 中而不在数组 A 中的数。 思路分析 可遍历B中元素，然后在A中二分查找是否有相同元素存在，若存在则跳过，不存在则加入一个可变列表list。 代码实现 12345678910111213141516171819202122232425262728293031323334public class Solution{ public List<Integer> getElementsInAnotB(int[] A,int[] B) { List<Integer> list=new ArrayList<>(); for(int i=0;i<B.length;i++) { int left=0,right=A.length-1; boolean contains=false; int mid=( ...

回文链表 问题陈述 请判断一个链表是否为回文链表。 示例： 12输入: 1->2->2->1输出: true 将链表存入数组然后双指针判断 123456789101112131415161718192021class Solution { public boolean isPalindrome(ListNode head) { ListNode node1=head; int len=0; while(node1!=null){//获取链表长度 len++; node1=node1.next; } int[] array=new int[len]; int k=0; for(ListNode node=head;node!=null;node=node.next){//将链表元素存入数组 array[k++]=node.val; ...

回文子串 问题陈述 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。 123输入: "abc"输出: 3解释: 三个回文子串: "a", "b", "c". 动态规划法 状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。 状态转移方程：当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时，dp[i][j]=true，否则为false。 1、当只有一个字符时，比如a自然是一个回文串。 2、当有两个字符时，如果是相等的，比如aa，也是一个回文串。 3、当有三个及以上字符时，比如ababa这个字符记作串1，把两边的a去掉，也就是bab记作串2，可以看出只要串2是一个回文串，那么左右各多了一个a的串1必定也是回文串。所以当s[i]==s[j]时，自然要看dp[i+1][j-1]是不是一个回文串。 12345678910 ...

合并两个排序的数组 问题陈述 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中*，*使 nums1 成为一个有序数组。 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 算法实现 可使用双指针比较，由于需要合并到nums1，故需要从尾开始比较，这样不会导致覆盖。 123456789101112131415161718192021class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int i=m-1,j=n-1,k=m+n-1; while(i>=0&&j>=0){ if(nums1[i]>nums2[j]){ nums1[k--]=nums1[i]; ...

反转字符串中的元音字母 问题陈述 编写一个函数，以字符串作为输入，反转该字符串中的元音字母。 1234输入："hello"输出："holle"https://github.com/Zhi-Tu/My-Album/blob/master/photos/leetcode.pnghttps://github.com/Zhi-Tu/My-Album/blob/master/photos/const.png 思路分析 可将元音字母存入一个HashSet，双指针首尾遍历字符串，遇到元音字母则交换。 123456789101112131415161718192021private final static HashSet<Character> vowels = new HashSet<>( Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E ...

单词接龙 问题陈述 给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则： 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 说明: 如果不存在这样的转换序列，返回 0。 所有单词具有相同的长度。 所有单词只由小写字母组成。 字典中不存在重复的单词。 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。 1234567891011输入:beginWord = "hit",endWord = "cog",wordList = ["hot","dot","dog","lot","log","cog"]输出: 5解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog ...

前缀和与差分数组 前缀和问题 示例：对于一个给定的数组，寻找和为k的连续子数组。 思路实现： 对每个元素构建一个前缀和数组，然后遍历该数组所有可能的子数组判断和是否为k。 12345678910111213141516171819202122232425262728293031323334public class PrefixSum { public List<List<Integer>> subArray(int[] nums,int k){ //构建前缀和数组sum，长度为nums长度加1 int n=nums.length; int[] sum=new int[n+1]; sum[0]=0; for(int i=0;i<n;i++){ sum[i+1]=sum[i]+nums[i]; } List<List<Integer>> res=new ArrayLis ...

前k个高频元素 问题陈述 给定一个非空的整数数组，返回其中出现频率前 k 个高频元素。 算法实现 先使用哈希表统计元素及其出现频率，然后基于桶排序的思想获得频率排序，最后遍历得到前k个高频元素。 12345678910111213141516171819202122232425262728293031323334public class FrequentKElements { public List<Integer> topKFrequent(int[] nums,int k){ List<Integer> res=new ArrayList<>(); HashMap<Integer,Integer> map=new HashMap<>(); for(int num:nums){ if(!map.containsKey(num)){ map.put(num,1); ...

判断子序列 问题陈述 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。 算法实现 1234567891011//双指针遍历public boolean isSequence(String s,String t){ int i=0,j=0; while(i<s.length()&&j<t.length()){ if(!s.charAt(i)==t.charAt(j)){ j++; } i++; } return i==s.length() ...

分发饼干 问题陈述 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。 1234567891011121314151617181920//示例1输入: [1,2,3], [1,1]输出: 1解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。所以你应该输出1。//示例2输入: [1,2], [1,2,3]输出: 2解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出2. 算法实现 12345678910111213141516//贪心思想class Solution { public int findC ...