5.26号刷题

发表于 | 分类于 | 0 comments

第一题 287. Find the Duplicate Number

算法

这道题是非常有意思的一题，由于题目要求不能够改变Array本来的结构，相当于只是read形式的，所以另一道相似题目用的转负442 Find All Duplicates in an Array的方法就暂时用不了了。
在这道题中，我们要使用的在链表中求环的方式来进行这道题目的求解。由于题目中已经说明必定存在一个环，那么我们可以将环想象成以下样子的。

(Start)  (Circle-Entry)
 |         |
 ----->----@---->-----------
           |               |
           |               |
           ^               |
           |               |
           |-------@--<----|
                   |
              (Meet-Point)

想要求得重复的数值，我们利用两个指示点(fast, slow)，通过两部来完成整个

第一步 检验是否为环形，并得到两个点相遇的位置

我们首先获得两个指示点fast, slow。在这个Array中，每当slow走一步，fast走的总是他的两倍。这样当进入环形之后，就可以看做一个龟兔赛跑，快的兔子总会在某个点追上比较慢的乌龟，即slow == fast, 这个点我们叫相遇点(Meet-Point)。

第二步 找到进入圆环的那个点

为了找到进入圆环的点，我们需要进行一些数学推到。
令：

  • L1: 开始(Start) 到进入圆圈的点(Circle-Entry)距离
  • L2: 进入圆圈的点(Circle-Entry)到相遇点(Meet-Point)距离
  • C: 圆环周长
  • n: 当两个指示点相遇的时候，快的那个走的圈数

根据我们的定义，我们可以知道:

  • 当相遇的时候，slow走的距离为L1 + L2
  • 当相遇的时候, fast走的距离为L1 + L2 + C*n

由于我们知道，每当slow走一步，fast总是走两步的，所以
2 (L1+L2) = L1 + L2 + n C

=> L1 + L2 = n C

=> L1 = (n - 1) C + (C - L2)

当我们忽视n-1 * C的时候（走多少圈都不影响相遇点的位置(Meet-Point)）

我们得到了 L1 = C - L2
这意味着如果我们两个指针，一个从Start开始出发，另一点从相遇点（Meet-Point）开始出发，当行走相同的距离的时候(L1)。从Start开始那个点会到达圆圈起始点(Circle-Entry), 而从相遇点（Meet-Point）开始出发的那个点，也会刚好走完一整圈，到达圆圈起始点(Circle-Entry)。

这个时候我们就得到了相遇点，以下是代码具体的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class findDuplicate287 {
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0, entry = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (fast != slow);
        while (entry != slow) {
            entry = nums[entry];
            slow = nums[slow];
        }
        return entry;
    }
}

第二题 142. Linked List Cycle II

算法

方法与第一题相似, 只不过这题是在一个链表的基础上求解问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class detectCycle142 {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode fast = head, slow = head, entry = head;
        do {
            if (fast.next == null || fast.next.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
        } while (!fast.equals(slow));
        while(!slow.equals(entry)) {
            entry = entry.next;
            slow = slow.next;
        }
        return entry;
    }
}
class ListNode {
  int val;
  ListNode next;
  ListNode(int x) {
      val = x;
      next = null;
  }
}

第三题 141. Linked List Cycle

算法

更为简单，只需要判断是否有circle即可

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            head = head.next;
            if (fast.equals(head)) return true;
        }
        return false;     
    }
}

第四题 189. Rotate Array

算法

方法一

nums = [1,2,3,4,5,6,7] and k = 3

  • 首先旋转0 , length - k -1部分 [1,2,3,4] => [4,3,2,1]
  • 然后再旋转剩余部分 [5,6,7] => [7,6,5]
  • 之后旋转整个Array [4,3,2,1,7,6,5] => [5,6,7,1,2,3,4]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public class rotate189 {
        //方法2 O(n), O(1)
        public void rotate2(int[] nums, int k) {
            if (nums.length < 2 || nums ==  null) return;
            k %= nums.length;
            reverse(nums, 0, nums.length - k - 1);
            reverse(nums, nums.length - k, nums.length - 1);
            reverse(nums, 0, nums.length - 1);
        }
        public void reverse(int[] nums, int start, int end) {
            while(start < end) {
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                start++; end--;
            }
        }
    }
方法二

利用额外的存储空间进行存储

自己这个存储可以优化，实际上只需要k单位的存储空间就够了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class rotate189 {
    // 方法1 O(n), O(n)
    public void rotate(int[] nums, int k) {
        if (nums.length < 2) return;
        k = k % nums.length;
        int[] dupl = new int[nums.length];
        dupl = nums.clone();
        for (int i = 0; i < k; i++) {
            nums[i] = dupl[nums.length - k + i];
        }
        for (int i = k ; i < nums.length; i++) {
            nums[i] = dupl[i-k];
       }
    }
}

第五题 151. Reverse Words in a String

算法

方法一

将String 劈开，然后从后向前你用String Builder存储结果

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public String reverseWords(String s) {
        String[] words = s.trim().split("\\s+");
        StringBuilder result = new StringBuilder();
        for(int i = words.length - 1; i > 0; i--) {
            result.append(words[i]);
            result.append(" ");
        }
        result.append(words[0]);
        return result.toString();
    }
}

方法二

你用Arrays.asList的颠倒功能，以及String.join, 完成倒序

1
2
3
4
5
6
7
public class reverseWords151 {
    public static String reverseWords2(String s) {
        String[] words = s.trim().split("\\s+");
        Collections.reverse(Arrays.asList(words));
        return String.join(" ", words);
    }
}

学到的东西

String.join

String.join(“-“,”string”,”join”) => string-join,后面可以为一个Array

trim()

去除String头和尾的空格，防止出现异常

Collections.reverse(Arrays.asList(words));

除了reverse之外，还有sort等等很多的用法

第六题186. Reverse Words in a String II

算法

与第四题的思路相似，都是通过多次翻转，在不需要更多空间的情况下，完成整个数组的翻转。

可以先进行部分或者整体翻转，然后再进行多次翻转，看结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class reverseWords186 {
    public void reverseWords(char[] s) {
        reverse(s, 0, s.length - 1);
        int start = 0;
        for (int i = 0; i < s.length; i++) {
            if (s[i] == ' ') {
                reverse(s, start, i - 1);
                start = i + 1;
            }
        }
        reverse(s, start, s.length - 1);
    }
    public void reverse(char[] s, int start, int end) {
        while(start < end) {
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;
            start++; end--;
        }
    }
}

第七题228. Summary Ranges

算法

从头向后推进，然后看是不是满足递增1的情况，不是的话就进行输出。但是要注意最后结尾的特殊处理。时间复杂度为O(n)

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
public class summaryRanges228 {
    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<>();
        if(nums == null || nums.length == 0) return result;
        int start = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1] + 1) {
                StringBuilder temp = new StringBuilder();
                if (i - start == 1) {
                    temp.append(nums[start]);
                } else {
                    temp.append(nums[start]);
                    temp.append("->");
                    temp.append(nums[i-1]);
                }
                result.add(temp.toString());
                start = i;
            }
        }
        StringBuilder temp = new StringBuilder();
        if (nums.length - 1 == start) {
            temp.append(nums[nums.length - 1]);
        } else {
            temp.append(nums[start]);
            temp.append("->");
            temp.append(nums[nums.length - 1]);
        }
        result.add(temp.toString());
        return result;
    }
}