为了转行程序员而努力的第三十五天-线程,队列

今天又早醒了,距离目标又近了一点点,痛苦的谈话时间几乎是过去了,剩下的就是做好收尾工作和耐心等待,虽然结果不一定跟我想象的一样,但是有一些变化也是好的。

第一次完成了一道hard的题,虽然花了很多时间,看了标准答案一次又一次,但是好歹把逻辑理清了。突然发现好像已经好几天都没有录小王子和运动了,今天补上。

今天也算是正式放春节假了,明天只需要远程接电话就可以了。趁着春节,可以好好休息一下,顺便把项目也开个头,刷的题越来越难,每天的压力越来越大,随着工作的增加,这种情况肯定会加剧,精神会越来越疲惫,要想办法解决,同时也要想办法保持一定的进度。

今日进度:
1.算是彻底结束了换岗的谈话部分,剩下的就是等通知了,也算是在年前告一段落,希望年后能有好消息,也希望可以顺利
2.坚持刷题,今天把昨天留下的练习题刷完了
3.坚持录小王子,今天太晚了,只能明天再说了
4.坚持锻炼
5.坚持记录

学习笔记:
1.Java 提供了三种创建线程方法:
通过实现 Runnable 接口;
通过继承 Thread 类本身;
通过 Callable 和 Future 创建线程。

2.创建线程的三种方式的对比

  1. 采用实现 Runnable、Callable 接口的方式创建多线程时,线程类只是实现了 Runnable 接口或 Callable 接口,还可以继承其他类。
  2. 使用继承 Thread 类的方式创建多线程时,编写简单,如果需要访问当前线程,则无需使用 Thread.currentThread() 方法,直接使用 this 即可获得当前线程。

3.线程同步:即当有一个线程在对内存进行操作时,其他线程都不可以对这个内存地址进行操作,直到该线程完成操作, 其他线程才能对该内存地址进行操作,而其他线程又处于等待状态,实现线程同步的方法有很多,临界区对象就是其中一种。

4.在多线程编程里面,一些敏感数据不允许被多个线程同时访问,此时就使用同步访问技术,保证数据在任何时刻,最多有一个线程访问,以保证数据的完整性。

5.临界区:通过对多线程的串行化来访问公共资源或一段代码,速度快,适合控制数据访问。在任意时刻只允许一个线程对共享资源进行访问,如果有多个线程试图访问公共资源,那么在有一个线程进入后,其他试图访问公共资源的线程将被挂起,并一直等到进入临界区的线程离开,临界区在被释放后,其他线程才可以抢占。它并不是核心对象,不是属于操作系统维护的,而是属于进程维护的。

6.线程同步的方法:
(1)wait():使一个线程处于等待状态,并且释放所持有的对象的lock。
(2)sleep():使一个正在运行的线程处于睡眠状态,是一个静态方法,调用此方法要捕捉 InterruptedException异常。
(3)notify():唤醒一个处于等待状态的线程,注意的是在调用此方法的时候,并不能确切的 唤醒某一个等待状态的线程,而是由JVM确定唤醒哪个线程,而且不是按优先级。
(4)notityAll ():唤醒所有处于等待状态的线程,注意并不是给所有唤醒线程一个对象的锁, 而是让它们竞争。

7.线程同步的真实意思和字面意思恰好相反。线程同步的真实意思,其实是“排队”:几个线程之间要排队,一个一个对共享资源进行操作,而不是同时进行操作。

8.127. 单词接龙
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk:
每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ,返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0 。

输入:beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出:5
解释:一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。

解题思路:创建一个addword方法,存储每个单词和他们对应的ID,创建一个addedge方法,存储每个单词和它的带*号变形单词之间的关系。使用队列来记录经过的单词,使用dis记录每一个单词到beginword的距离,最后,如果qid与endowed的ID相同,就说明到达了终点。

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

hard难度的题,确实分析和实现都比较复杂,也耗时较多,可能会先考虑跳过部分hard题,先把所有知识点刷一遍,明天继续更新。