从零开始，此前没有任何算法竞赛经验，没有系统刷过题
4 Likes
加油！楼主要坚持啊，暑假一起刷（
数据结构与算法，启动！
暑假？
今晚蒜了。因为刚刚突然在群里聊嗨了一直聊到现在。
良好的开始
加油捏，寒假一起刷:rofl_kissing_heart:
时间挤不出来一点
太吊了。一个 easy 也不会
做了。
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null && slow != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
}
这个有点 tricky。要求空间复杂度 O(1) ，又不让 modify linked list。于是看了下讨论区，发现真的是 tricky。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null && slow != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
while (slow != head) {
head = head.next;
slow = slow.next;
}
return head;
}
}
return null;
}
}
2 Likes
有点好笑，这个难度为 medium 的题目，答案就只有一行：
class Solution {
public boolean stoneGame(int[] piles) {
return true;
}
}
主要看证明：因为 piles.length 为偶数，所以 Alice 每次都可以选择是拿奇数列还是偶数列，而 Bob 没有选择权利。如果所有奇数 pile 的值之和大于偶数的，那 Alice 每次都拿奇数 index 的，那么 Bob 每次都只能拿偶数 index 的，所以 Alice 永远会赢。and vice versa.
1 Like
草，我 142 第一次做的太直接了，但是还好能 ac（
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode detected = head;// 要被判断是否是开始循环的结点
while (detected != null) { // 下同 141 题 判断是否有循环
ListNode slow = detected;
ListNode fast = detected;
while (fast != null && fast.next != null ) {
slow = slow.next;
fast = fast.next.next;
// 同时判断是否回到要被判断的结点
if (slow == detected || fast == detected) {
return detected;
}
if (slow == fast) {
break;
}
}
detected = detected.next;
}
return null;
}
}
然后喜提速度最慢一档。后看了讨论区的方法，服了
trade off of time and space. 为了空间有点太舍弃时间了，还不如做标记位（
感觉你这个 worst case time complexity 有 O(N^2)
1 Like
我每日一题呢 
怎么又是无脑题目
class Solution {
public String intToRoman(int num) {
StringBuilder roman = new StringBuilder();
if (num / 1000 > 0) {
roman.append("M".repeat(num / 1000));
num %= 1000;
}
if (num >= 900) {
roman.append("CM");
num -= 900;
}
if (num >= 500) {
roman.append("D");
num -= 500;
}
if (num >= 400) {
roman.append("CD");
num -= 400;
}
if (num / 100 > 0) {
roman.append("C".repeat(num / 100));
num %= 100;
}
if (num >= 90) {
roman.append("XC");
num -= 90;
}
if (num >= 50) {
roman.append("L");
num -= 50;
}
if (num >= 40) {
roman.append("XL");
num -= 40;
}
if (num / 10 > 0) {
roman.append("X".repeat(num / 10));
num %= 10;
}
if (num >= 9) {
roman.append("IX");
num -= 9;
}
if (num >= 5) {
roman.append("V");
num -= 5;
}
if (num >= 4) {
roman.append("IV");
num -= 4;
}
if (num > 0) {
roman.append("I".repeat(num));
}
return roman.toString();
}
}
当然写法可以优化
1 Like
debug 还要花钱，烂完了。
看 OI wiki 复习了一下 hash table，原来算法竞赛中常用的冲突处理方法是 separate chaining
1 Like
我太成功了，真的。彻底成功。
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
Map<Integer, Integer> m = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
if (m.containsKey(target - nums[i])) return new int[] {i, m.get(target - nums[i])};
m.put(nums[i], i);
}
return null;
}
}
1 Like