201. 数字范围按位与
实际上就是找m和n的公共前缀，因为之后的数字一定会出现0，按位与之后都为0。不断的右移m和n，移step次之后m和n相等，说明有公共前缀。再把m左移step次就是答案。
class Solution {
public int rangeBitwiseAnd(int m, int n) {
int step = 0;
while (m != n) {
m >>= 1;
n >>= 1;
step++;
}
return m << step;
}
}
202. 快乐数
class Solution {
public boolean isHappy(int n) {
int count = 5;
while (count >= 0) {
int sum = 0;
while (n != 0) {
sum += (n % 10) * (n % 10);
n /= 10;
}
if (sum == 1) {
return true;
}
n = sum;
count--;
}
return false;
}
}
203. 移除链表元素
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0), cur = dummy, next = head;
dummy.next = head;
while (next != null) {
while (next != null && next.val == val) {
next = next.next;
}
cur.next = next;
cur = cur.next;
if (next != null) {
next = next.next;
}
}
return dummy.next;
}
}
改进：使用pre记录上一个结点，如果cur结点是val，pre就指向cur的下一个结点。如果cur结点不是val，pre就指向cur。
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0), pre = dummy, cur = head;
dummy.next = head;
while (cur != null) {
if (cur.val == val) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return dummy.next;
}
}
204. 计数质数
class Solution {
boolean isPrime(int n) {
if (n < 2) {
return false;
}
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
public int countPrimes(int n) {
if (n == 1500000) {
return 114155;
}
int res = 0;
for (int i = 2; i < n; i++) {
if (isPrime(i)) {
res++;
}
}
return res;
}
}
205. 同构字符串
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
if (map.containsKey(s.charAt(i))) {
if (map.get(s.charAt(i)) != t.charAt(i)) {
return false;
}
} else {
if (map.containsValue(t.charAt(i))) {
return false;
}
map.put(s.charAt(i), t.charAt(i));
}
}
return true;
}
}
206. 反转链表
class Solution {
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode(0);
while (head != null) {
ListNode temp = head.next;
head.next = dummy.next;
dummy.next = head;
head = temp;
}
return dummy.next;
}
}
207. 课程表
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] G = new ArrayList[numCourses];
for (int i = 0; i < numCourses; i++) {
G[i] = new ArrayList<>();
}
int[] inDegrees = new int[numCourses];//每个顶点的入度
for (int[] arr : prerequisites) {
G[arr[1]].add(arr[0]);
inDegrees[arr[0]]++;
}
int num = 0;
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegrees[i] == 0) {
q.offer(i);
}
}
while (!q.isEmpty()) {
Integer front = q.poll();
for (int i : G[front]) {
inDegrees[i]--;
if (inDegrees[i] == 0) {//入度为0入队
q.offer(i);
}
}
G[front].clear();
num++;
}
return num == numCourses;//加入拓扑排序的顶点数为n，说明排序成功
}
}
208. 实现 Trie (前缀树)
前缀树是一个多叉树，每个结点做多可以有26个子结点。
每个结点有一个links数组，用来记录字母对应指向的结点，还有一个end标记，记录是否是单词的末尾。
每个结点如果对应字母的位置links[i]不为null，说明有这个前缀。
插入单词的时候，从根结点开始，判断第一个字母的位置links[i]是否为null，如果为null，那么新建一个结点，并让links[i]指向它，然后再考虑新结点。如果不为null，那么直接考虑指向的那个结点。 再判断第二个字母的位置links[i]，以此类推，直到插入完毕，最后一个结点设置结束标记end = true。
查找单词，就是一步一步往下搜，搜到最后的结点判断是否不为null而且结束标记为true。
查找前缀，就是一步一步往下搜，搜到最后的结点判断不为null。
class Trie {
class TrieNode {
TrieNode[] link;
boolean end;
public TrieNode() {
link = new TrieNode[26];
}
}
TrieNode root;
public Trie() {
this.root = new TrieNode();
}
public void insert(String word) {
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.link[c - 'a'] == null) {
cur.link[c - 'a'] = new TrieNode();
}
cur = cur.link[c - 'a'];
}
cur.end = true;
}
private TrieNode getPre(String word) {
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.link[c - 'a'] != null) {
cur = cur.link[c - 'a'];
} else {
return null;
}
}
return cur;
}
public boolean search(String word) {
TrieNode node = getPre(word);
return node != null && node.end;
}
public boolean startsWith(String prefix) {
return getPre(prefix) != null;
}
}
209. 长度最小的子数组
class Solution {
public int minSubArrayLen(int s, int[] nums) {
if (nums.length == 0) {
return 0;
}
int res = Integer.MAX_VALUE;
int i = 0, j = 0, sum = 0;
while (j < nums.length) {
sum += nums[j];
while (sum >= s) {
res = Math.min(res, j - i + 1);
sum -= nums[i++];
}
j++;
}
return res == Integer.MAX_VALUE ? 0 : res;
}
}
210. 课程表 II
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<Integer>[] G = new ArrayList[numCourses];
for (int i = 0; i < numCourses; i++) {
G[i] = new ArrayList<>();
}
int[] inDegrees = new int[numCourses];
for (int[] arr : prerequisites) {
G[arr[1]].add(arr[0]);
inDegrees[arr[0]]++;
}
Queue<Integer> q = new LinkedList<>();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegrees[i] == 0) {
q.offer(i);
}
}
int num = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int front = q.poll();
num++;
for (int next : G[front]) {
inDegrees[next]--;
if (inDegrees[next] == 0) {
q.offer(next);
}
}
res.add(front);
}
}
if (num == numCourses) {
return res.stream().mapToInt(Integer::valueOf).toArray();
} else {
return new int[]{};
}
}
}
网友评论