代码随想录第三十三天复习

Posted on In

数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int search(int[] nums, int target) {
        if (target < nums[0] || target > nums[nums.length - 1]) return -1;

        int left = 0;
        int right = nums.length;

        while(left < right){
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }

        return -1;
    }
}

35 Search Insert Position

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int searchInsert(int[] nums, int target) {
        if (target < nums[0]) return 0;
        if (target > nums[nums.length - 1]) return nums.length;

        int left = 0;
        int right = nums.length;

        while (left < right){
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }

        return left;
    }
}

34 Find First and Last Position of Element in Sorted Array

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        int isFound = binarySearch(nums, target);
        if (isFound == -1) return result;
        else {
            int left = isFound;
            int right = isFound;
            while (left >= 0 && nums[left] == nums[isFound]) left--;
            while (right < nums.length && nums[right] == nums[isFound]) right++;
            result[0] = left + 1;
            result[1] = right - 1;
        }
        return result;
    }

    private int binarySearch(int[] nums, int target){
        
        if (nums.length == 0 || target < nums[0] || target > nums[nums.length - 1]) return -1;

        int left = 0;
        int right = nums.length;
        while (left < right){
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }

        return -1;
    }
}

69 Sqrt(x)

注意要用long表示整数型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        if (x == 1) return 1; 
        int left = 0;
        int right = x;

        while (left < right){
            int mid = left + ((right - left) >> 1);
            long midS = (long) mid * mid;

            if (midS == (long) x) return mid;
            else if (midS < x) left = mid + 1;
            else right = mid;
        }

        return left - 1;
        
    }
}

367 Valid Perfect Square

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isPerfectSquare(int num) {
        if (num == 0|| num == 1) return true;

        int left = 0;
        int right = num;

        while (left < right){
            int mid = left + ((right - left) >> 1);
            long midS = (long) mid * mid;
            if (midS == (long) num) return true;
            else if (midS < num) left = mid + 1;
            else right = mid;
        }

        return false;
    }
}

27 Remove Element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums == null || nums.length == 0) return 0;

        int left = 0;
        int right = nums.length - 1;

        while (left <= right){
            if (nums[left] == val) nums[left] = nums[right--];
            else left++;
        }

        return left;
    }
}

26 Remove Duplicates from Sorted Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int slowIndex = 0;
        int fastIndex = 0;
        while (fastIndex < nums.length){
            if (nums[fastIndex] == nums[slowIndex]) fastIndex++;
            else {
                slowIndex++;
                nums[slowIndex] = nums[fastIndex++];
            }
        }

        return slowIndex + 1;
    }
}

283 Move Zeroes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int slowIndex = 0;
        int fastIndex = 0;

        while (fastIndex < nums.length){
            if (nums[fastIndex] != 0){
                nums[slowIndex++] = nums[fastIndex];
            }

            fastIndex++;
        }


        while (slowIndex < nums.length){
            nums[slowIndex++] = 0;
        }
        
    }
}

844 Backspace String Compare

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean backspaceCompare(String s, String t) {
        return backspaceHelper(s).equals(backspaceHelper(t));
    }

    private String backspaceHelper(String s){
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (c != '#') sb.append(c);
            else {
                if (sb.length() >= 1) sb.deleteCharAt(sb.length() - 1);
            }
        }

        return sb.toString();
    }
}

977 Squares of a Sorted Array

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


class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];

        int left = 0;
        int right = nums.length - 1;
        int index = nums.length - 1;
        while (left <= right){
            int leftS = nums[left] * nums[left];
            int rightS = nums[right] * nums[right];

            if (leftS >= rightS){
                result[index--] = leftS;
                left++;
            } else {
                result[index--] = rightS;
                right--;
            }
        }
        return result;
    }
}

209 Minimum Size Subarray Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int minSize = Integer.MAX_VALUE; 

        while (right < nums.length){
            sum += nums[right++];
            while (sum >= target){
                minSize = Math.min(minSize, right - left);
                sum -= nums[left++];
            }
        }

        return minSize == Integer.MAX_VALUE ? 0 : minSize;
    }
}

904 Fruit Into Baskets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int totalFruit(int[] fruits) {
        int left = 0;
        int right = 0;
        int maxNum = Integer.MIN_VALUE;

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

        while (right < fruits.length){
            map.put(fruits[right], map.getOrDefault(fruits[right++], 0) + 1);
            while (map.size() > 2) {
                map.put(fruits[left], map.get(fruits[left]) - 1);
                if (map.get(fruits[left]) == 0) map.remove(fruits[left]);
                left++;
            }
            maxNum = Math.max(maxNum, right - left);
        }

        return maxNum;
    }
}

59 Spiral Matrix 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int offset = 1;
        int start = 0;
        int i = 0, j = 0;
        int loop = n / 2;
        int count = 1;

        while (loop-- > 0){
            for (j = start; j < n - offset; j++){
                result[start][j] = count++; 
            }
            for (i = start; i < n - offset; i++){
                result[i][j] = count++;
            }

            for (;j > start; j--){
                result[i][j] = count++;
            }

            for (;i > start; i--){
                result[i][j] = count++;
            }

            offset++;
            start++;
        }

        if (n % 2 == 1){
            result[start][start] = count;
        }

        return result;
        
    }
}

80 Remove Duplicates from Sorted Array II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length < 3) return nums.length;

        int slowIndex = 0;
        int fastIndex = 0;
        while (fastIndex < nums.length){
            nums[slowIndex++] = nums[fastIndex++];
            if (fastIndex < nums.length && nums[fastIndex] == nums[slowIndex - 1])
            nums[slowIndex++] = nums[fastIndex++];

            while (fastIndex< nums.length && nums[fastIndex] == nums[slowIndex - 1]) fastIndex++;
        }

        return slowIndex;

    }
}

Linked List

203 Remove Linked List Elements

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null){
            if (cur.val == val) pre.next = cur.next;
            else pre = cur;
            cur = cur.next;
        }

        return dummy.next;
    }
}

707 Design Linked List

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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 MyLinkedList {
    int size;
    ListNode head;
    public MyLinkedList() {
        this.size = 0;
        this.head = new ListNode(0);
    }
    
    public int get(int index) {
        if (index < 0 || index > size - 1) return -1;
        ListNode cur = head;
        for (int i = 0; i<= index; i++){
            cur = cur.next;
        }   
        return cur.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index < 0) index = 0;

        size++;
        ListNode pre = head;
        for (int i = 0; i < index; i++){
            pre = pre.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = pre.next;
        pre.next = newNode;
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index > size - 1) return;
        size--;
        ListNode pre = head;
        for (int i = 0; i < index; i++){
            pre = pre.next;
        }

        pre.next = pre.next.next;
    }
}

206 Reverse Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode pre = null;
        ListNode cur = head;
        ListNode temp;
        while (cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        
        return pre;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }

    private ListNode reverse(ListNode cur, ListNode pre){
        if (cur == null) return pre;

        ListNode temp = cur.next;
        cur.next = pre;

        return reverse(temp, cur);
    }
}

24 Swap Nodes in Pairs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null) return null;
        if (head != null && head.next == null) return head;
        
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        
        while (pre.next != null && pre.next.next != null){
            ListNode temp = pre.next.next.next;
            ListNode first = pre.next;
            ListNode second = pre.next.next;

            pre.next = second;
            second.next = first;
            first.next = temp;

            pre = first;
        }

        return dummy.next;
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null) return null;
        if (head != null && head.next == null) return head;

        ListNode next = head.next;
        ListNode newNode = swapPairs(head.next.next);

        next.next = head;
        head.next = newNode;

        return next;

    }
}

19 Remove Nth Node From End of List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
		
		ListNode slowIndex = dummy;
		ListNode fastIndex = dummy;
		
		for (int i = 0; i <= n; i++) fastIndex = fastIndex.next;

		while(fastIndex != null){
			fastIndex = fastIndex.next;
			slowIndex = slowIndex.next;
		}
		
		slowIndex.next = slowIndex.next.next;
		
		return dummy.next;
    }
}

160 Intersection of Two Linked Lists

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
35
36
37
38
39
40
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenHeadA = 0;
        int lenHeadB = 0;
        ListNode curA = headA;
        ListNode curB = headB;

        while (curA != null){
            lenHeadA++;
            curA = curA.next;
        }

        while (curB != null){
            lenHeadB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        if (lenHeadA > lenHeadB){
            for (int i = 0; i < lenHeadA - lenHeadB; i++){
                curA = curA.next;
            }
        } else {
            for (int i = 0; i < lenHeadB - lenHeadA; i++){
                curB = curB.next;
            }
        }

        while (curA != null){
            if (curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }

        return null;
    }
}

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 Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                ListNode node1 = head;
                ListNode node2 = slow;

                while (node1 != node2){
                    node1 = node1.next;
                    node2 = node2.next;
                }

                return node1;
            }
        }

        return null;
    }
}

哈希表

242 Valid Anagram

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] chars = new int[26];
        for (int i = 0; i < s.length(); i++){
            chars[s.charAt(i) - 'a']++;
        }

        for (int i = 0; i < t.length(); i++){
            chars[t.charAt(i) - 'a']--;
        }

        for (int i = 0; i < chars.length; i++){
            if (chars[i] != 0) return false;
        }

        return true;
    }
}

383 Ransom Note

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] chars = new int[26];

        for (int i = 0; i < magazine.length(); i++){
            chars[magazine.charAt(i) - 'a']++;
        }

        for (int i = 0; i < ransomNote.length(); i++){
            chars[ransomNote.charAt(i) - 'a']--;
        }

        for (int i = 0; i < chars.length; i++){
            if (chars[i] < 0) return false;
        }

        return true;
    }
}