这是我参与11月更文挑战的第25天，活动详情查看：2021最后一次更文挑战
LeetCode习题集
有些题可能直接略过了，整理一下之前刷leetcode
201. 数字范围按位与
给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
示例 1:
输入: [5,7]
输出: 4
示例 2:
输入: [0,1]
输出: 0
class Solution {
public int rangeBitwiseAnd(int m, int n) {
//位运算
while (m < n) n &= n - 1;
return n;
}
}
复制代码202. 快乐数
编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
示例:
输入: 19
输出: true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
这题可以用快慢指针的思想去做，有点类似于检测是否为环形链表那道题
如果给定的数字最后会一直循环重复，那么快的指针（值）一定会追上慢的指针（值），也就是
两者一定会相等。如果没有循环重复，那么最后快慢指针也会相等，且都等于1。
复制代码class Solution {
public boolean isHappy(int n) {
int fast=n;
int slow=n;
do{
slow=squareSum(slow);
fast=squareSum(fast);
fast=squareSum(fast);
}while(slow!=fast);
if(fast==1)
return true;
else return false;
}
private int squareSum(int m){
int squaresum=0;
while(m!=0){
squaresum+=(m%10)*(m%10);
m/=10;
}
return squaresum;
}
}
复制代码203. 移除链表元素
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode header = new ListNode(-1);
header.next = head;
ListNode cur = header;
while(cur.next != null){
//检测到如果下一个结点值相等的话，就把下一个结点直接跳过，当前结点的下一个指向下下个结点
if(cur.next.val == val ){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return header.next;
}
}
复制代码204. 计数质数
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
欧拉晒，在找到的素数的基础上，凡是素数的倍数，肯定都不是素数，把不是素数的直接标记，
能省去很多的重复计算
复制代码class Solution {
public int countPrimes(int n) {
if (n < 2)
return 0;
boolean[] isPrime = new boolean[n];
Arrays.fill(isPrime, true);
for (int i = 2; i <= Math.sqrt(n); i++) {
if (isPrime[i]) {
for (int j = 2 * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
int count = -2;
for (boolean bool : isPrime) {
if (bool)
++count;
}
return count;
}
}
复制代码205. 同构字符串
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
示例 1:
输入: s = "egg", t = "add"
输出: true
示例 2:
输入: s = "foo", t = "bar"
输出: false
示例 3:
输入: s = "paper", t = "title"
输出: true
说明:
你可以假设 s 和 t 具有相同的长度。
用两个字符数组，互相判断
然后接下来建造相对应的字符匹配
把t字符放到相对应s字符为下标的地方
把s字符放到相对应t字符为下标的地方
如果有一个字符匹配的不存在，并且还匹配上面规定的存放位置，那么肯定就不是同构
复制代码class Solution {
public boolean isIsomorphic(String s, String t) {
char[] s2t = new char[127];
char[] t2s = new char[127];
char[] S = s.toCharArray();
char[] T = t.toCharArray();
int len = s.length();
for (int i = 0;i < len;i ++){
if (s2t[S[i]] != '\0' || t2s[T[i]] != '\0'){
if (s2t[S[i]] != T[i]) return false;
}else {
s2t[S[i]] = T[i];
t2s[T[i]] = S[i];
}
}
return true;
}
}
复制代码206. 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null; //前指针节点
ListNode curr = head; //当前指针节点
//每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移
while (curr != null) {
ListNode nextTemp = curr.next; //临时节点，暂存当前节点的下一节点，用于后移
curr.next = prev; //将当前节点指向它前面的节点
prev = curr; //前指针后移
curr = nextTemp; //当前指针后移
}
return prev;
}
}
复制代码207. 课程表
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
说明:
输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
这个问题相当于查找一个循环是否存在于有向图中。
如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序
拓扑排序 也可以通过 BFS 完成。
复制代码class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int len = prerequisites.length;
if(len==0) return true;
Stack stack = new Stack();
//存放各课程的入度
int[] count = new int[numCourses];
for(int i=0;i<len;i++)
count[prerequisites[i][1]]++;
//将入度为0的课程入栈
for(int i=0;i<numCourses;i++)
if(count[i]==0)
stack.push(i);
int m,result=0;
//只要栈不空就循环
while(!stack.isEmpty()){
//每从栈顶取出一个课程，结果集加1
m=(int) stack.pop();
result++;
//将与m课程连接的顶点入度减1，并判断其入度是否为0，若为0则入栈
for(int i=0;i<len;i++)
if(prerequisites[i][0]==m){
count[prerequisites[i][1]]--;
if(count[prerequisites[i][1]]==0)
stack.push(prerequisites[i][1]);
}
}
//比较结果集与课程数目是否相等
return result==numCourses;
}
}
复制代码208. 实现 Trie (前缀树)
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
复制代码说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。
前缀树，每个一结点都对应着二十六个子节点
相类似于Huffman树，不过这里的路径就是字符串
如果存在字符串，对应结点的值就是true
插入的时候就疯狂创建树，如果没有对应的结点，就创建结点，然后接着指向创建的结点，一直到字符串都能存放，然后把isWord改成true
匹配的时候，只要前缀中有一个结点不存在，那么就返回false，找到对应结点，然后返回此节点的isWorld，看此节点是否有单词
匹配前缀也是，同上，如果前缀都在直接返回true
复制代码class Trie {
class Node {
boolean isWord;
Node[] next = new Node[26];
}
Node root = new Node();
/** Initialize your data structure here. */
public Trie() {
}
/** Inserts a word into the trie. */
public void insert(String word) {
Node p = root;
for(char ch : word.toCharArray()) {
if(p.next[ch - 'a'] == null)
p.next[ch - 'a'] = new Node();
p = p.next[ch - 'a'];
}
p.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Node p = root;
for(char ch : word.toCharArray()) {
if(p.next[ch - 'a'] == null)
return false;
p = p.next[ch - 'a'];
}
return p.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
Node p = root;
for(char ch : prefix.toCharArray()) {
if(p.next[ch - 'a'] == null)
return false;
p = p.next[ch - 'a'];
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
复制代码209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
滑动窗口
双指针，右指针一直向后找，
一直到sum大于s了，就记录一下当前长度，看看是不是最小的那个
此时大于s了，就可以左指针右移了，接着右指针右移找下一个能>s的子数组
复制代码class Solution {
public int minSubArrayLen(int s, int[] nums) {
int i = 0;
int sum = 0;
int len = 0;
for (int j = 0; j < nums.length; j++) {
sum += nums[j];
while (sum >= s) {
len = len == 0 ? j - i + 1 : Math.min(len, j - i + 1);
sum -= nums[i++];
}
}
return len;
}
}
复制代码210. 课程表 II
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例 1:
输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2:
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
说明:
输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
提示:
这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<Integer> results = new ArrayList<>();
int[] degree = new int[numCourses];
List<List<Integer>> edges = new ArrayList(numCourses);
// 初始化
for (int i = 0; i < numCourses; i++) {
edges.add(new ArrayList<Integer>());
}
for (int i = 0; i < prerequisites.length; i++) {
//把有前提的课程放进去，存在入度的
degree[prerequisites[i][0]]++;
//当前的有入读的那个列表，添加上次课程
edges.get(prerequisites[i][1]).add(prerequisites[i][0]);
}
Queue<Integer> queue = new LinkedList<>();
int count = 0;
// 把入度为0的点放入队列中
for (int i = 0; i < numCourses; i++) {
if (degree[i] == 0) {
queue.add(i);
}
}
while (!queue.isEmpty()) {
int course = queue.poll();
//最后的结果先添加不需要条件的课程
results.add(course);
//每次添加一个课程，就++，看最后是不是把所有课程都添加进去了
count++;
for (Integer c : edges.get(course)) {
//循环当前这个课程开头的，就是以当前课程为前提的课
//以当前课程为前提的课程--
degree[c]--;
//如果当前课程为前提的课没有了，那么我就可以++此课程
if (degree[c] == 0) {
queue.add(c);
}
}
}
// 判断是否有拓扑排序
if (count != numCourses) {
return new int[0];
}
int[] res = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
res[i] = results.get(i);
}
return res;
}
}
复制代码
近期评论