I woke up early today and was a little closer to my goal. The painful conversation time was almost over. All that remained was to finish the work and wait patiently. Although the result was not necessarily the same as I imagined, some changes were also good.
I finished a hard question for the first time. Although I spent a lot of time and looked at the standard answer again and again, I managed to clarify the logic somehow. I suddenly found that I haven't recorded the little prince and sports for several days. I'll make it up today.
Today is also the official Spring Festival holiday. Tomorrow, you only need to answer the phone remotely. Take advantage of the Spring Festival, you can have a good rest and start the project by the way. The problems are getting more and more difficult and the pressure is increasing every day. With the increase of work, this situation will certainly intensify and the spirit will become more and more tired. We should find ways to solve it and maintain a certain progress at the same time.
Today's progress:
1. It's the end of the job change conversation. The rest is waiting for the notice. It's also an end before the year. I hope there will be good news and smooth progress after the year
2. Continue to brush the exercises and finish the exercises left yesterday today
3. Insist on recording the little prince. It's too late today. We can only talk about it tomorrow
4. Keep exercising
5. Keep records
Study notes:
1.Java provides three methods to create threads:
Through the implementation of Runnable interface;
By inheriting the Thread class itself;
Create threads through Callable and Future.
2. Comparison of three ways to create threads
- When multithreading is created by implementing Runnable and Callable interfaces, the thread class only implements the Runnable interface or Callable interface, and can also inherit other classes.
- When creating a multithread by inheriting the Thread class, it is easy to write. If you need to access the current Thread, you don't need to use Thread The currentthread() method can directly use this to obtain the current Thread.
3. Thread synchronization: that is, when a thread is operating on the memory, other threads cannot operate on the memory address. Until the thread completes the operation, other threads can operate on the memory address, while other threads are in the waiting state. There are many methods to realize thread synchronization, and the critical area object is one of them.
4. In multithreaded programming, some sensitive data are not allowed to be accessed by multiple threads at the same time. At this time, synchronous access technology is used to ensure that at most one thread can access the data at any time to ensure the integrity of the data.
5. Critical area: access to common resources or a piece of code through multi-threaded serialization, which is fast and suitable for controlling data access. At any time, only one thread is allowed to access shared resources. If multiple threads attempt to access public resources, after one thread enters, other threads attempting to access public resources will be suspended and wait until the thread entering the critical area leaves. After the critical area is released, other threads can seize it. It is not a core object. It is not maintained by the operating system, but by the process.
6. Method of thread synchronization:
(1)wait(): put a thread in a waiting state and release the lock of the held object.
(2)sleep(): it is a static method to make a running thread sleep. Call this method to catch the InterruptedException exception.
(3)notify(): wake up a thread in a waiting state. Note that when this method is called, it cannot wake up a thread in a waiting state exactly, but the JVM determines which thread to wake up, not by priority.
(4)notityAll(): wake up all the waiting threads. Note that instead of giving all the waking threads an object lock, let them compete.
7. The real meaning of thread synchronization is just the opposite of the literal meaning. The real meaning of thread synchronization is actually "queuing": several threads have to queue up to operate on shared resources one by one, rather than at the same time.
8.127. Word Chain
The conversion sequence from the words beginWord and endWord in the dictionary wordList is a sequence formed according to the following specifications: beginWord - > S1 - > S2 - >... - > SK:
Each pair of adjacent words is only one letter short.
For 1 < = I < = k, each si is in the wordList. Note that beginWord does not need to be in the wordList.
sk == endWord
Give you two words beginWord and endWord and a dictionary wordList to return the number of words in the shortest conversion sequence from beginWord to endWord. If there is no such conversion sequence, 0 is returned.
Input: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
Output: 5
Explanation: a shortest conversion sequence is "hit" - > "hot" - > "dot" - > "dog" - > "cog", which returns its len gt h of 5.
Solution idea: create an addword method to store each word and their corresponding ID, and create an addedge method to store the relationship between each word and its deformed word with * sign. Use the queue to record the passing words, and use dis to record the distance from each word to beginword. Finally, if the ID of qid is the same as that of endowed, it means that the end point has been reached.
class Solution {
Map<String, Integer> wordId = new HashMap<String, Integer>();
List<List<Integer>> edge = new ArrayList<List<Integer>>();
int wordNum = 0;
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
for(String word : wordList){
addEdge(word);
}
addEdge(beginWord);
if(!wordId.containsKey(endWord)){
return 0;
}
int[] dis = new int[wordNum];
Arrays.fill(dis, Integer.MAX_VALUE);
int beginId = wordId.get(beginWord);
int endId = wordId.get(endWord);
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(beginId);
dis[beginId] = 0;
while(!queue.isEmpty()){
int qId = queue.poll();
if(qId == endId){
return dis[qId] / 2 + 1;
}
for(int e : edge.get(qId)){
if(dis[e] == Integer.MAX_VALUE){
dis[e] = dis[qId] + 1;
queue.offer(e);
}
}
}
return 0;
}
public void addEdge(String word){
addWord(word);
int wordLen = word.length();
char[] wordCl = word.toCharArray();
int id1 = wordId.get(word);
for(int i=0; i<wordLen; i++){
char tmp = wordCl[i];
wordCl[i] = '*';
String nw = String.valueOf(wordCl);
addWord(nw);
int id2 = wordId.get(nw);
List<Integer> list1 = edge.get(id1);
list1.add(id2);
List<Integer> list2 = edge.get(id2);
list2.add(id1);
wordCl[i] = tmp;
}
}
public void addWord(String word){
if(!wordId.containsKey(word)){
wordId.put(word, wordNum);
wordNum ++;
}
edge.add(new ArrayList<Integer>());
}
}
The analysis and implementation of hard difficult questions are indeed complex and time-consuming. You may consider skipping some hard questions first, brush all the knowledge points first, and continue to update tomorrow.