#yyds干货盘点# LeetCode刷题集201 - 210

2021年11月24日 阅读数:3
这篇文章主要向大家介绍#yyds干货盘点# LeetCode刷题集201 - 210,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

博主私藏的LeetCode刷题集合
有些较难的问题都有思路和注释算法

201. 数字范围按位与

给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内全部数字的按位与(包含 m, n 两端点)。数组

示例 1: markdown

输入: [5,7]
输出: 4
示例 2:app

输入: [0,1]
输出: 0ide

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        while (m < n) n &= n - 1;
        return n;
    }
}

202. 快乐数

编写一个算法来判断一个数是否是“快乐数”。学习

一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每一个位置上的数字的平方和,而后重复这个过程直到这个数变为 1,也多是无限循环但始终变不到 1。若是能够变为 1,那么这个数就是快乐数。ui

示例: 指针

输入: 19
输出: true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1code

PS:

这题能够用快慢指针的思想去作,有点相似于检测是否为环形链表那道题
若是给定的数字最后会一直循环重复,那么快的指针(值)必定会追上慢的指针(值),也就是
二者必定会相等。若是没有循环重复,那么最后快慢指针也会相等,且都等于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 具备相同的长度。

PS:
用两个字符数组,互相判断

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 进行拓扑排序 - 一个关于Coursera的精彩视频教程(21分钟),介绍拓扑排序的基本概念。
拓扑排序也能够经过 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 构成的。
保证全部输入均为非空字符串。

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) 时间复杂度的解法。

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;
    }
}