1.两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
题解
解法一：
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
}
// 官方题解
// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。解法二：
public class Solution {
public static void main(String[] args) {
int[] Sample = {2, 7, 11, 15};
System.out.println(Arrays.toString(twoSum(Sample, 9)));
}
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> Temp = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int temp = target - nums[i];
if (Temp.containsKey(temp)) {
return new int[] {i, Temp.get(temp)};
} else {
Temp.put(nums[i], i);
}
}
return null;
}
}评价
LeeCode 中少有的靠暴力就能破解的题，但他的优化仍有一些难度。
知识点总结
[HashMap].containsKey(Object value)
HashMap 检测存在函数
2.两数相加
// @algorithm @lc id=2 lang=java
// @title add-two-numbers
package _2_Add_Two_Numbers;
import algm.*;
// @test([2,4,3],[5,6,4])=[7,0,8]
// @test([0],[0])=[0]
// @test([9,9,9,9,9,9,9],[9,9,9,9])=[8,9,9,9,0,0,0,1]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int temp = 0, result = 0;
ListNode lNode = new ListNode();
ListNode tNode = lNode;
while (l1 != null || l2 != null || temp != 0) {
// 置空
result = temp;
if (l1 != null) {
// 加入值1
result += l1.val;
l1 = l1.next;
}
if (l2 != null) {
// 加入值2
result += l2.val;
l2 = l2.next;
}
if (result >= 10) {
//进位判断
temp = 1;
result -= 10;
} else {
temp = 0;
}
//输出
tNode.next = new ListNode(result, null);
tNode = tNode.next;
}
return lNode.next;
}
}202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
示例：输入：19 输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1题解
解法一：
public class Solution {
public static void main(String[] args) {
System.out.println(isHappy(19));
}
public static boolean isHappy(int n) {
Set<Integer> appear = new HashSet<>();
while (n != 1 && !appear.contains(n)) {
appear.add(n);
n = getNext(n);
}
return n == 1;
}
private static int getNext(int n) {
int res = 0;
while (n > 0) {
int temp = n % 10;
res += temp * temp;
n = n / 10;
}
return res;
}
}评价
使用 HashSet 实现存储唯一值
知识点总结
Set<Integer> appear = new HashSet<>();
242.有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true 示例 2: 输入: s = “rat”, t = “car” 输出: false
说明: 你可以假设字符串只包含小写字母。
题解
解法一：
public class Solution {
public static void main(String[] args) {
String s = "anagram";
String t = "nagaram";
System.out.println(isAnagram(s, t));
}
public static boolean isAnagram(String s, String t) {
//定义新数组储存各字母的出现次数
int[] Sign = new int[26];
//统计s中出现
for (char a : s.toCharArray()) {
Sign[a - 'a']++;
}
//统计t中出现
for (char a : t.toCharArray()) {
Sign[a - 'a']--;
}
//判断s和t是否为字母异位词
for (int flag : Sign) {
if (flag != 0) {
return false;
}
}
return true;
}
}解法二：
import java.lang.reflect.Array;
import java.util.*;
public class Solution2 {
public static void main(String[] args) {
String s = "anagram";
String t = "nagaram";
System.out.println(isAnagram(s, t));
}
public static boolean isAnagram(String s, String t) {
//定义新数组储存各字母的出现次数
ArrayList Sign = new ArrayList(Arrays.asList(s.split("")));
//统计t中出现
for (String c : t.split("")) {
if (!Sign.remove(c)) {
return false;
}
}
//判断s和t是否为字母异位词
return Sign.size() == 0;
}
}评价
该题使用了 [String].toCharArray() 、Arrays.asList() 、[List].size() 、[String].split() 和 [List].remove() 方法和基本的算法逻辑
知识点总结
[String].toCharArray()
public char[] toCharArray() {
// Cannot use Arrays.copyOf because of class initialization order issues
char result[] = new char[value.length];
System.arraycopy(value, 0, result, 0, value.length);
return result;
}Arrays.asList()
[List].size()
[String].split()
[List].remove()
349. 两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2] 示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4]
说明：
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
题解
解法一：
import java.util.*;
public class Solution {
public static void main(String[] args) {
int[] nums1 = {1,2,2,1};
int[] nums2 = {2,2};
System.out.println(Arrays.toString(intersection(nums1, nums2)));
}
public static int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Set<Integer> temp = new HashSet<>();
for (int i : nums1) {
set.add(i);
}
for (int i : nums2) {
if (set.contains(i)) {
temp.add(i);
}
}
int[] res = new int[temp.size()];
int index = 0;
for (Integer i : temp) {
res[index++] = i;
}
return res;
}
}解法二：
import java.util.*;
public class Solution2 {
public static void main(String[] args) {
int[] nums1 = {1,2,2,1};
int[] nums2 = {2,2};
System.out.println(Arrays.toString(intersection(nums1, nums2)));
}
public static int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Set<Integer> temp = new HashSet<>();
for (int i : nums1) {
set.add(i);
}
for (int i : nums2) {
if (set.contains(i)) {
temp.add(i);
}
}
return temp.stream().mapToInt(x -> x).toArray();
}
}评价
该题使用了 stream()、mapToInt() 方法、Set 数据结构和基本的算法逻辑
知识点总结
stream()
mapToInt()
383.赎金信
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
注意：
你可以假设两个字符串均只含有小写字母。
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true题解
解法一：
public class Solution {
public static void main(String[] args) {
String a = "a";
String b = "b";
System.out.println(canConstruct(a, b));
}
public static boolean canConstruct(String ransomNote, String magazine) {
int[] Flag = new int[26];
int temp;
for (int i = 0; i < magazine.length(); i++) {
temp = magazine.charAt(i) - 'a';
Flag[temp]++;
}
for (int i = 0; i < ransomNote.length(); i++) {
temp = ransomNote.charAt(i) - 'a';
if (Flag[temp] > 0) {
Flag[temp]--;
} else {
return false;
}
}
return true;
}
}评价
与 字母异位词 类似，但要注意字母不能复用
454.四数相加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
*解释: 两个元组如下:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0题解
解法一：
public class Solution {
public static void main(String[] args) {
int[] a = {1, 2};
int[] b = {-1, -2};
int[] c = {-1, 2};
int[] d = {0, 2};
System.out.println(fourSumCount(a, b, c, d));
}
public static int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int Result = 0;
Map<Integer, Integer> temp = new HashMap<>();
for (int i : nums1) {
for (int j : nums2) {
if (temp.containsKey(i + j)) {
temp.put(i + j, temp.get(i + j) + 1);
} else {
temp.put(i + j, 1);
}
}
}
for (int i : nums3) {
for (int j : nums4) {
if (temp.containsKey(-i - j)) {
Result += temp.get(-i - j);
}
}
}
return Result;
}
}解法二：
// 参考题解
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int res = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int a : nums1) for (int b : nums2) map.compute(a + b, (k, v) -> v == null ? 1 : v + 1);
for (int c : nums3) for (int d : nums4) res += map.getOrDefault(-c - d, 0);
return res;
}
}评价
增强了对哈希表的理解
知识点总结
Lambda表达式
lambda 表达式的语法格式如下：
(parameters) -> expression
或
(parameters) -> {
statements;
}[HashMap].compute(K key, BiFunction remappingFunction
key- 键remappingFunction- 重新映射函数，用于重新计算值
