双非二本找实习前的准备day12

学习目标：

每天复习代码随想录上的题目2-3道算法（时间充足可以继续），背诵的八股的问题也在这里记录了

今日碎碎念：

1）科四没时间考了，等实习完回来再说咯

2）这几天在忙收拾东西和处理学校的事情，能保持记录就保持啦

3）阅读部分spring源码。

力扣刷题

算法

力扣151：151. 反转字符串中的单词

解答思路：

1）如注释

class Solution {
    /**
     * 不使用Java内置方法实现
     * <p>
     * 1.去除首尾以及中间多余空格
     * 2.反转整个字符串
     * 3.反转各个单词
     */
    public String reverseWords(String s) {
        //去除空格
        StringBuilder sb = removeSpace(s);
        //翻转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        //然后翻转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }
    //去除空格
    public StringBuilder removeSpace(String s){
        //先去除前后空格
        int start = 0;
        int end = s.length() - 1;
        while(s.charAt(start) == ' ') start++;
        while(s.charAt(end) == ' ') end--;
        StringBuilder res = new StringBuilder();
        //此时去检测中间空格
        while(start <= end){
            char c = s.charAt(start);
            if(c != ' ' || c == ' ' && s.charAt(start-1) != ' '){
                res.append(c);
            }
            start++;
        }
        return res;
    }
    //翻转整个字符串
    public void reverseString(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
    }
    //翻转各个单词
    public void reverseEachWord(StringBuilder sb) {
        //用start来标记所有单词的起始位置
        int start = 0;
        //用end来记录所有单词的结束位置
        int end = 1;
        //记录最长
        int len = sb.length();
        while(start < len){
            //分别找到每个单词的结尾，注意到最后一个单词的时候不能超长
            while(end<len && sb.charAt(end)!=' '){
                end++;
            }
            //找到结尾之后就直接传入下标调用翻转函数
            reverseString(sb,start,end-1);
            //替换start(+1 是因为要跳过空格)，end
            start = end + 1;
            end = start + 1;
        }
    }
}

力扣206：206. 反转链表

解答思路：

1）链表题的话会有些许抽象，但是我之前的做法都是，你定义的指针你得搞清楚要用来干嘛。搞清楚题目要求你的指向，以及你接下来如何改变指针指向，我觉得考虑清楚这几个会对做题有帮助

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode now = head;
        ListNode tmp = null;
        while(now != null){
            //因为我们要改变指向关系，因此得先保存下一个节点
            tmp = now.next;
            //改变now的next
            now.next = pre;
            //pre指向前一个
            pre = now;
            //改变now，是之前保存的下一个节点
            now =  tmp;
        }
        return pre;
    }
}