leetcode每日一题

算法苦手

零矩阵

来源： https://leetcode-cn.com/problems/zero-matrix-lcci/

想法：

遍历矩阵，使用两个数组来记录矩阵中哪些行和列需要变为0，然后根据第一遍遍历完矩阵得出的数组，第二遍遍历矩阵，将需要改为0的元素修改。

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] rows = new boolean[m];
        boolean[] cols = new boolean[n];
        for (int i = 0 ; i < m ; i++) {
            for (int j = 0 ; j < n ; j++) {
                if (matrix[i][j] == 0) {
                    rows[i] = true;
                    cols[j] = true;
                }
            }
        }
        for (int i = 0 ; i < m ; i++) {
            for (int j = 0 ; j < n ; j++) {
                if (rows[i] || cols[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

时间复杂度： O(mn)

空间复杂度： O(m + n)

优化：

可将矩阵的第一行和第一列作为记录需要修改为0的行和列的数据，额外使用两个标记变量来记录第一行和第一列是否需要修改为0即可。

时间复杂度： O(mn)

空间复杂度： O(1)

字符串轮转

来源： https://leetcode-cn.com/problems/string-rotation-lcci/

想法：

遍历字符串S1，以当前字符为分界点，判断S1分成的前后两个字符串与S2分成的两个字符串是否相同。

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (s1.equals("") && s2.equals("")) return true;
        if (s1.length() != s2.length()) return false;
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        int n = 0;
        while(true) {
            while (n < c1.length && c1[n] != c2[0]) n++;
            if (n == c1.length) return false;
            else {
                int m = 0;
                while (m + n < c1.length && c1[m + n] == c2[m]) m++;
                if (m + n  == c1.length) {
                    int k = 0;
                int tmp = c2.length - n;
                    while (tmp + k < c2.length && c1[k] == c2[k + tmp]) k++;
                    if (k + tmp == c2.length) return true;
                    else n++;
                }else n++;
            }
        }
    }
}

时间复杂度： O(n²)

空间复杂度： O(n)

优化：

若将 $S_1$ 分成的两个子串视为 $L$ 和 $R$ , 可并凑字符串 $S_2 + S_2$ , 所得到的字符串即为 $L + R + L + R = L + S_1 + R$ ，则只需判断 $S_1$ 是否是 $S_2 + S_2$ 的子串即可。

时间复杂度： O(n) (KMP)

空间复杂度： O(n)

移除重复节点

来源： https://leetcode-cn.com/problems/remove-duplicate-node-lcci/

想法：

遍历链表途中，用哈希集合存储该节点的值是否出现过，出现过将节点移出即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        HashSet<Integer> nums = new HashSet<>();
        if (head == null) return head;
        nums.add(head.val);
        ListNode pos = head;
        while (pos.next != null) {
            ListNode cur = pos.next;
            if (nums.add(cur.val)) {
                pos = pos.next;
            } else {
                pos.next = pos.next.next;
            }
        }
        pos.next = null;
        return head;
    }
}

时间复杂度： O(n)

空间复杂度： O(n)

返回倒数第k个节点

来源： https://leetcode-cn.com/problems/kth-node-from-end-of-list-lcci/

想法：

使用两个指针，保持两个指针相隔的节点数为k，第一个指针到达链表尾部时，第二个指针即为倒数第k个节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthToLast(ListNode head, int k) {
        ListNode p1 = head;
        ListNode p2 = head;
        int cnt = 0;
        while (cnt < k) {
            p1 = p1.next;
            cnt++;
        }
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2.val;
    }
}

时间复杂度： O(n)

空间复杂度： O(1)

分割链表

来源： https://leetcode-cn.com/problems/partition-list-lcci/

想法：

维护两个链表，一个为小于 x 的节点，一个为大于等于 x 的节点，在遍历完原始链表后，将两个链表连接起来即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) return head;
        ListNode p1 = null;
        ListNode p2 = null;
        ListNode p1_head = null;
        ListNode p2_head = null;
        while(head != null) {
            if (head.val < x) {
                if (p1_head == null) p1_head = head;
                else p1.next = head;
                p1 = head;
            }else {
                if (p2_head == null) p2_head = head;
                else p2.next = head;
                p2 = head;
            }
            head = head.next;
        }
        if (p2 != null) p2.next = null;
        if (p1 == null) return p2_head;
        p1.next = p2_head;
        return p1_head;
    }
}

时间复杂度： O(n)

空间复杂度： O(1)

链表求和

来源： https://leetcode-cn.com/problems/sum-lists-lcci/

想法：

按照竖式计算的方法，遍历两个链表，将处理完进位的结果连接成一个新的链表即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0);
        ListNode head = res;
        boolean sign = false;
        while (l1 != null || l2 != null || sign) {
            int tmp;
            if (l1 == null && l2 == null) tmp = 0;
            else if (l2 == null) tmp = l1.val;
            else if (l1 == null) tmp = l2.val;
            else tmp = l1.val + l2.val;

            if (sign) tmp++;
            if (tmp >= 10) {
                sign = true;
                res.next = new ListNode(tmp - 10);
            }else {
                sign = false;
                res.next = new ListNode(tmp);
            }
            res = res.next;
            if (l1 != null)l1 = l1.next;
            if (l2 != null)l2 = l2.next;
        }
        return head.next;
    }
}

时间复杂度： O(n)

空间复杂度： O(n)

回文链表

来源： https://leetcode-cn.com/problems/palindrome-linked-list-lcci/

想法：

简单的想法即通过遍历链表，将结果存储在数组中，然后判断是否为回文即可。

时间复杂度： O(n)

空间复杂度： O(n)

另一个想法就是找到回文的中心点，以此中心点将链表分为两个子链表，然后将前面一半的链表逆转，最后从这两个子链表的头开始遍历比较，如果元素都相同即为回文链表，如果找不到这样的中心点或者遍历比较时出现元素不同，即不为回文链表。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        if (head.next.next == null) return head.val == head.next.val;
        ListNode p1 = head;
        ListNode p2 = head.next;
        ListNode p3 = head.next.next;
        if (p1.val == p3.val && p3.next == null) return true;
        while (p3 != null && p1.val != p2.val && p1.val != p3.val) {
            ListNode tmp = p1;
            p1 = p2;
            p2 = p2.next;
            if (tmp == head) tmp.next = null;
            p1.next = tmp;
            p3 = p3.next;
        }
        if (p3 == null) return false;
        if (p1.val == p3.val) {
            while (p1 != null && p3 != null) {
                if (p1.val != p3.val) return false;
                p1 = p1.next;
                p3 = p3.next;
            }
            if (p1 != p3) return false;
        }
        else{
            while (p1 != null && p2 != null) {
                if (p1.val != p2.val) return false;
                p1 = p1.next;
                p2 = p2.next;
            }
            if (p1 != p2) return false;
        }
        return true;
    }
}

时间复杂度： O(n)

空间复杂度： O(1)

链表相交

来源： https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/

想法：

将两链表的公共部分长度设为c，若设置一个指针在遍历完链表a后遍历链表b，则在到达公共部分时，总共经过(a + b - c) 个节点，同理设置一个指针在遍历完链表b后遍历链表a，则在到达公共部分时，总共也经过(b + a - c) 个节点。

此时有两种情况：

1. 若两链表有公共部分，则两指针都指向公共部分的首节点。 2. 若两链表没有公共部分，则两指针都指向null。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }
}

时间复杂度： O(m + n)

空间复杂度： O(1)

PREVIOUSC++ Primer Plus Chapter2

NEXTC++ Primer Plus Chapter3