统计所有小于非负整数 n 的质数的数量。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
埃氏筛法：要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
class Solution {
public int countPrimes(int n) {
boolean[] isPrim = new boolean[n];
Arrays.fill(isPrim, true);
for(int i = 2; i * i < n; i++) {
if (isPrim[i]) {
for (int j = i * i; j < n; j += i) {
isPrim[j] = false;
}
}
}
int ans = 0;
for (int i = 2;i < n; i++) {
if (isPrim[i]) {
ans++;
}
}
return ans;
}
}
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode temp = null;
while (cur != null) {
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
给定两个字符串 s 和 *t*，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 *t* ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
示例 1:
输入：s = "egg", t = "add"
输出：true
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> st = new HashMap<>();
Map<Character, Character> ts = new HashMap<>();
int len = s.length();
for (int i = 0; i < len; i++) {
char x = s.charAt(i);
char y = t.charAt(i);
if ((st.containsKey(x) && st.get(x) != y) || (ts.containsKey(y) && ts.get(y) != x))
return false;
st.put(x, y);
ts.put(y, x);
}
return true;
}
}
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int ans = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length; i ++) {
int start = i + 1;
int end = nums.length - 1;
while(start < end) {
int sum = nums[i] + nums[start] + nums[end];
if (Math.abs(target - sum) < Math.abs(target - ans)) {
ans = sum;
}
if (sum > target) {
end--;
}
else if (sum < target) {
start++;
}
else
return ans;
}
}
return ans;
}