LeetCode解题报告—— Linked List Cycle II & Reverse Words in a String & Fraction to Recurring Decimal

1. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

思路：想法是利用两指针，一个每次移动一步，另一个每次移动两步，如果存在环则这两个指针一定会相遇(这里可以在纸上画一下，因为后一个指针移动比前一个指针快，当后一个指针在环中来到前一个指针的前面时只有两种情况，在它前一个或者前两个，无论那种情况都能走到一起)。但是并不知道具体会在第几圈相遇，现在到了数学分析的时候了：https://leetcode.com/problems/linked-list-cycle-ii/discuss/44793/O(n)-solution-by-using-two-pointers-without-change-anything

    ListNode *detectCycle(ListNode *head) {

    if (head == NULL || head->next == NULL) return NULL;

    ListNode* firstp = head;

    ListNode* secondp = head;

    bool isCycle = false;

    while(firstp != NULL && secondp != NULL) {

        firstp = firstp->next;

        if (secondp->next == NULL) return NULL;

        secondp = secondp->next->next;

        if (firstp == secondp) { isCycle = true; break; }

    }

    if(!isCycle) return NULL;

    firstp = head;

    while( firstp != secondp) {

        firstp = firstp->next;

        secondp = secondp->next;

    }

    return firstp;

}

2. Reverse Words in a String

Given an input string, reverse the string word by word.

Example:

Input: "the sky is blue",

Output: "blue is sky the".

Note:

A word is defined as a sequence of non-space characters.
Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
You need to reduce multiple spaces between two words to a single space in the reversed string.

String[] parts = s.trim().split("\\s+");

String out = "";

for (int i = parts.length - 1; i > 0; i--) {

    out += parts[i] + " ";

}

return out + parts[0];

注意的是上面的正则表达式的用法，\s 匹配任何不可见字符，包括空格、制表符、换页符等等。等价于[ \f\n\r\t\v]，后面的 + 表示匹配一个或多个，然后就是在java中使用正则前面要多加个反斜杠。

3. Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

Example 1:

Input: numerator = 1, denominator = 2

Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1

Output: "2"

Example 3:

Input: numerator = 2, denominator = 3

Output: "0.(6)"

思路：难点在于小数部分的判断，可以用一个map，key是当前的被除数，value是当前计算结果的数字长度，如果在计算过程中key和之前的key相等，因为除数一直不变，所以这是开始循环，那么就要在上一个key所对应的value处插入 ( 符号，然后在末尾插入 ) 符号。

public class Solution {

    public String fractionToDecimal(int numerator, int denominator) {

        if (numerator == 0) {

            return "0";

        }

        StringBuilder res = new StringBuilder();

        // "+" or "-"

        res.append(((numerator > 0) ^ (denominator > 0)) ? "-" : ""); // 判断正负，异号的情形才是负

        long num = Math.abs((long)numerator);

        long den = Math.abs((long)denominator);

        // integral part

        res.append(num / den);　　// 先求出整数部分

        num %= den;　　// 求余数

        if (num == 0) {

            return res.toString();

        }

        // fractional part

        res.append(".");

        HashMap<Long, Integer> map = new HashMap<Long, Integer>();

        map.put(num, res.length());  // 将余数作为key加入到map中

        while (num != 0) {

            num *= 10;

            res.append(num / den);  // 上面num乘10是因为这里要取小数点最后一位的后一位的除后的整数，否则num/den就一直是0

            num %= den;　　// 求余数

            if (map.containsKey(num)) { // 如果余数和某一轮的被除数一样，因为除数一直不变，那么则表明开始无限循环了

                int index = map.get(num); // 取开始发生无限循环时res的长度已确定插入 ( 符号的位置

                res.insert(index, "(");

                res.append(")");

                break;

            }

            else {

                map.put(num, res.length()); // 如果没开始无限循环，则要记录当前除后结果数字的长度，以记录插入括号的位置

            }

        }

        return res.toString();

    }

}

巴特西

LeetCode解题报告—— Linked List Cycle II & Reverse Words in a String & Fraction to Recurring Decimal

最新文章

热门文章