Jungle

Try My Best

0%

Posted on Edited on In
Symbols count in article: 9.3k Reading time ≈ 8 mins.

计算机网络自顶向下方法Character1

本文概述：

本文主要记录计算机网络自顶向下方法第一章节的知识点。
学习书籍为：计算机网络自顶向下方法
学习视频为：国立清华大学黄能富教授讲解的计算机网络自顶向下方法，需要的可以点击 这里

Read more »

Posted on Edited on In ,
Symbols count in article: 373 Reading time ≈ 1 mins.

原理图的绘制(89C51为例)

本文概述：

使用Altium Designer绘制89C51的原理图
本文以89C51原理图为例

本文使用的工具

Altium Designer 20.1.8

Read more »

Posted on Edited on In ,
Symbols count in article: 1.1k Reading time ≈ 1 mins.

PCB封装库的创建(89C51)

本文概述：

使用Altium Designer绘制89C51的PCB封装库
本文以89C51芯片为例

本文使用的工具

Altium Designer 20.1.8
学习视频：凡亿PCB

Read more »

Posted on Edited on In ,
Symbols count in article: 405 Reading time ≈ 1 mins.

原理图库的创建(89C51为例)

本文概述：

使用Altium Designer绘制89C51的原理图库
本文以89C51原理图为例

本文使用的工具

Altium Designer 20.1.8

Read more »

Posted on Edited on In ,
Symbols count in article: 244 Reading time ≈ 1 mins.

PCB工程文件的创建

本文概述：

如何使用Altium Designer建立PCB工程。

本文使用的工具

Altium Designer 20.1.8

Read more »

Posted on Edited on In ,
Symbols count in article: 405 Reading time ≈ 1 mins.

Leetcode1 Two sum

题目描述

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Read more »

Posted on Edited on In ,
Symbols count in article: 1.3k Reading time ≈ 1 mins.

Leetcode20 Valid Parentheses

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', 
determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true
Example 2:

Input: "()[]{}"
Output: true
Example 3:

Input: "(]"
Output: false
Example 4:

Input: "([)]"
Output: false
Example 5:

Input: "{[]}"
Output: true
Read more »

Posted on Edited on In ,
Symbols count in article: 823 Reading time ≈ 1 mins.

Leetcode5 Longest Palindromic Substrings

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
Given a string s, find the longest palindromic substring in s.
You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"
Read more »

Posted on Edited on In ,
Symbols count in article: 1.7k Reading time ≈ 2 mins.

LeetCode994 Rotting Oranges

题目描述

In a given grid, each cell can have one of three values:

  • the value 0 representing an empty cell;
  • the value 1 representing a fresh orange;
  • the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Read more »

Posted on Edited on In ,
Symbols count in article: 2.7k Reading time ≈ 2 mins.

Leetcode127. Ladder

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list.
Note:

<!-- more -->

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

思路

两种方法：
BFS使用队列；使用双向BFS，使用HashSet
双向BFS:
将wordlist放入HashSet中，如果最后的endword不在wordlist中，直接返回0。将startword和endword放入HashSet中，设step为0，当start 和end不为空时进入循环，当进入到循环后，step++，为保证平衡，当start的size大于end的size，交换end和star。设定一个临时的hashset。根据start里的word，每个位置替换26个字母，如果新的word在endword当中存在，返回step+1.如果wordlist没有新的word，继续循环。否则代表还没到end且wordlist中含有新的word，则将wordlist中的该元素去除（如若重复使用，长度必将增大），result中加入新的word。最后将word改回原来的值并将暂时的result作为start开启下一轮循环。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//BFS使用队列
//使用双向BFS，使用HashSet
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> wordlist= new HashSet<>();
        for(String word: wordList){
            wordlist.add(word);
        }
        if(!wordlist.contains(endWord))
            return 0;
        HashSet<String> start = new HashSet<>(); 
        HashSet<String> end = new HashSet<>(); 
        int step=0;
        start.add(beginWord);
        end.add(endWord);
        while(!start.isEmpty()&&!end.isEmpty()){
            ++step;
            if(start.size()>end.size()){//当start的大小比end大时，交换两个set以保证平衡
                HashSet<String> cur = new HashSet<>(); 
                cur = end;
                end = start;
                start = cur;
            }
            HashSet<String> result = new HashSet<>(); 
            for(String word: start){
                char[] ch = word.toCharArray();
                for(int i=0;i<beginWord.length();i++){
                    char c = ch[i];
                    for(char j='a';j<='z';j++){
                        ch[i]=j;
                        String w = new String(ch);
                        if(end.contains(w)) return step+1;
                        if(!wordlist.contains(w)) continue;
                        wordlist.remove(w);
                        result.add(w);
                    }
                    ch[i]=c;
                }
            }
            start = result;
        }
        return 0;  
    }
}