哈希表
1. 有效的字母异位词
https://leetcode.cn/problems/valid-anagram/description/
数组，set,map
java
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] cnt = new int[26];
for (int i = 0; i < s.length(); i++) {
cnt[s.charAt(i) - 'a']++;
}
for (int i = 0; i < t.length(); i++) {
cnt[t.charAt(i) - 'a']--;
if (cnt[t.charAt(i) - 'a'] < 0) {
return false;
}
}
return true;
}2.两个数组的交集
https://leetcode.cn/problems/intersection-of-two-arrays/
java
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums1.length; i++) {
set.add(nums1[i]);
}
Set<Integer> set2 = new HashSet<>();
for (int i = 0; i < nums2.length; i++) {
if (set.contains(nums2[i])) {
set2.add(nums2[i]);
}
}
int[] result = new int[set2.size()];
int i = 0;
for (Integer integer : set2) {
result[i++] = integer;
}
return result;
}3.2数之和
https://leetcode.cn/problems/two-sum/description/
java
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[0];
}暴力解法也没有超时
java
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[]{};
}四数相加
java
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
int sum = nums1[i] + nums2[j];
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
}
int count = 0;
for (int i = 0; i < nums3.length; i++) {
for (int j = 0; j < nums4.length; j++) {
int sum = nums3[i] + nums4[j];
if (map.containsKey(-sum)) {
count += map.get(-sum);
}
}
}
return count;
}三数
java
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
if (nums.length < 3) {
return res;
}
// 这里确定i
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
// 这里确定left right。
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
left++;
} else if (sum > 0) {
right--;
} else {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 跳过重复的left这里是为了去重
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
}
}
}
return res;
}
}字母异味词分组
https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked
java
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = String.valueOf(chars);
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(str);
}
return new ArrayList<>(map.values());
}字符串
反转字符串
https://leetcode.cn/problems/reverse-string-ii/description/
java
public String reverseStr(String s, int k) {
char[] c = s.toCharArray();
for (int i = 0; i < c.length; i += 2 * k) {
if (i + k < c.length) {
reverse(c, i, i + k - 1);
continue;
}
reverse(c, i, c.length - 1);
}
return new String(c);
}
public void reverse(char[] c, int start, int end) {
while (start < end) {
char temp = c[start];
c[start] = c[end];
c[end] = temp;
start++;
end--;
}
}反转字符串单词
https://leetcode.cn/problems/reverse-words-in-a-string/
java
class Solution {
public String reverseWords(String s) {
char[] ch = s.toCharArray();
// 第一步将整个字符串反转
reverse(ch, 0, ch.length - 1);
// 第二部去除多余的空格，首先去除首部空字符串，然后使用快慢指针收集
int start = 0;
// 去除首部空格
while (start < ch.length && ch[start] == ' ') {
start++;
}
int slow = start;
for (int fast = start; fast < ch.length; fast++) {
// 当前字符不是空格时，将当前字符复制给slow位置
if (fast == start || ch[fast] != ' ' || ch[fast - 1] != ' ') {
ch[slow++] = ch[fast];
}
}
// 去除尾部空格
if (ch[slow - 1] == ' ') {
slow--;
}
// System.out.println(new String(ch));
// 反转每个单词
int left = start;
// System.out.println("开始位置" + start);
for (int i = start; i < slow; i++) {
if (ch[i] == ' ') {
reverse(ch, left, i - 1);
left = i + 1;
continue;
}
if (i == slow - 1) {
reverse(ch, left, i);
}
}
// System.out.println(new String(ch));
// System.out.println("结束位置" + slow);
return new String(ch, start, slow - start);
}
public void reverse(char[] ch, int start, int end) {
while (start < end) {
char temp = ch[start];
ch[start] = ch[end];
ch[end] = temp;
start++;
end--;
}
}
}重复的子字符串
https://leetcode.cn/problems/repeated-substring-pattern/description/
java
public boolean repeatedSubstringPattern(String s) {
// 移动匹配
int n = s.length();
char[] ch = s.toCharArray();
char[] tmp = new char[2 * n];
for (int i = 0; i < n; i++) {
tmp[i] = ch[i];
tmp[i + n] = ch[i];
}
String tmpStr = new String(tmp);
return tmpStr.substring(1, tmpStr.length() - 1).contains(s);
// for (int i = 1; i <= n / 2; ++i) {
// if (n % i == 0) {
// String substring = s.substring(0, i);
// boolean match = true;
// for (int j = i; j < n; j += i) {
// if (!s.substring(j, j + i).equals(substring)) {
// match = false;
// break;
// }
// }
// if (match) {
// return true;
// }
// }
// }
}最长连续序列
这里需要注意，第二次遍历的时候，只能遍历Set集合
java
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) {
return 0;
}
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int res = 0;
for (int num : set) {
if (!set.contains(num - 1)) {
int count = 1;
int temp = num;
while (set.contains(temp + 1)) {
count++;
temp++;
}
res = Math.max(res, count);
}
}
return res;
}
}最长公共子序列
java
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 如果2个字符串相等，那么就加1
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// 如果不想等的情况下。
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}双指针
移动零
java
class Solution {
public void moveZeroes(int[] nums) {
int left = 0;
int temp = 0;
for (int i = 0; i < nums.length; i++) {
// 开始寻找非0元素
if (nums[i] != 0) {
// 将非0元素放到左边
temp = nums[i];
nums[i] = nums[left];
nums[left] = temp;
left++;
}
}
}
}