数组链表哈希表

字数统计: 4k字   |   阅读时长: 21分

数组

移除元素

https://leetcode-cn.com/problems/remove-element/

  • 暴力法
    图片

找到目标值后，后面的元素依次向前移动，覆盖掉目标值

1
2
3
4
5
6
7
8
9
10
11
12
13
public int removeElement(int[] nums, int val) {
    int length = nums.length;
    for (int i=0; i<length; i++) {
        if (nums[i] == val) {
            for (int j=i+1; j<length; j++) {
                nums[j-1] = nums[j];
            }
            i--; // 后面的元素向前移动了，i要回退一位
            length--;
        }
    }
    return length;
}
  • 快慢指针法
    快指针把不是目标值的元素移动到慢指针位置

图片

1
2
3
4
5
6
7
8
9
10
public int removeElement(int[] nums, int val) {
    int length = nums.length;
    int slow = 0;
    for (int fast=0; fast<length; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

长度最小的子数组

https://leetcode-cn.com/problems/minimum-size-subarray-sum/

  • 暴力法
    遍历所有窗口的时候，不是生成某长度的窗口，让窗口移动，这样需要重复计算这个窗口里面数字的和。而是按照不同的起点分类，每个起点遍历不同长度的窗口，这样可以利用已经计算出的结果，也可以遍历完所有窗口。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int minSubArrayLen(int target, int[] nums) {
    int minLength = Integer.MAX_VALUE;
    for (int i=0; i<nums.length; i++) {
        int sum = 0;
        for (int j=i; j<nums.length; j++) {
            sum += nums[j];
            if (sum >= target) {
                if (j-i+1 < minLength) {
                    minLength = j - i + 1;
                }
                break;
            }
        }
    }
    if (minLength < Integer.MAX_VALUE) {
        return minLength;
    } else {
        return 0;
    }
}
  • 滑动窗口
    滑动窗口是双指针的一种，sum>=target 收缩 sum<target 扩大
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
public int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int right = 0;
    int sum = nums[0];
    int minLength = Integer.MAX_VALUE;
    while (right < nums.length) {
        if (sum >= target) {
            minLength = Math.min(minLength, right-left+1);
            if (left==right) {
                right++;
                if (right < nums.length) {
                    sum += nums[right];
                }
            }
            sum -= nums[left];
            left++;
        } else {
            right++;
            if (right < nums.length) {
                sum += nums[right];
            }
        }
    }
    if (minLength < Integer.MAX_VALUE) {
        return minLength;
    } else {
        return 0;
    }
}
  • 滑动窗口优化
    核心思想还是sum >= target 左侧收缩 sum<target 右侧扩大

不过使用了双重循环，外循环负责移动右侧，内循环赋值移动左侧

当left 与 right 重合时，sum的值为0，while循环停止，nums不会取到right右侧的值，right不会越界，所以left也不会越界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int minSubArrayLen(int target, int[] nums) {
    int length = Integer.MAX_VALUE;
    int sum = 0;
    int left = 0;
    for (int right=0; right<nums.length; right++) {
        sum += nums[right];
        while (sum >= target) {
            int tempLength = right - left + 1;
            length = tempLength < length ? tempLength : length;
            sum -= nums[left++];
        }
    }
    return length == Integer.MAX_VALUE ? 0 : length;
}

螺旋矩阵Ⅱ

https://leetcode.cn/problems/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
private int counter = 1;
public int[][] generateMatrix(int n) {
    int[][] matrix = new int[n][n];
    this.fillMatrix(matrix, 0, n-1, 0, n-1);
    return matrix;
}

private void fillMatrix(int[][] matrix, int startRow, int endRow, int startCol, int endCol) {
    // 递归终止条件，必须有，这个与回溯不一样，不能靠for结束递归，因为递归在for外面
    if (startRow > endRow || startCol > endCol) {
        return;
    }
    // 打印第一行
    for (int j=startCol; j<=endCol; j++) {
        matrix[startRow][j] = this.counter++;
    }
    // 打印最后一列
    for (int i=startRow+1; i<=endRow; i++) {
        matrix[i][endCol] = this.counter++;
    }
    // 打印最后一行，由于这是方阵，不会出现只有一行的情况，不用加限制条件
    // startRow ！= endRow，只有一行没有这个限制条件，会重复遍历第一行
    for (int j=endCol-1; j>=startCol; j--) {
        matrix[endRow][j] = this.counter++;
    }
    // 打印最后一列，由于这是方阵，不会出现只有一列的情况，不用加限制条件
    // startCol ！= endCol，只有一列没有这个限制条件，会重复遍历最后一列
    for (int i=endRow-1; i>=startRow+1; i--) {
        matrix[i][startCol] = this.counter++;
    }
    fillMatrix(matrix, startRow+1, endRow-1, startCol+1, endCol-1);
}

螺旋矩阵

https://leetcode.cn/problems/spiral-matrix/

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
private List<Integer> result = new LinkedList<>();
public List<Integer> spiralOrder(int[][] matrix) {
    int rows = matrix.length;
    int cols =matrix[0].length;
    this.helper(matrix, 0, rows-1, 0, cols-1);
    return this.result;
}

private void helper(int[][] matrix, int startRow, int endRow, int startCol, int endCol) {
    if (startRow > endRow || startCol > endCol) {
        return;
    }

    for (int j=startCol; j<=endCol; j++) {
        this.result.add(matrix[startRow][j]);
    }
    for (int i=startRow+1; i<=endRow; i++) {
        this.result.add(matrix[i][endCol]);
    }
    for (int j=endCol-1; j>=startRow && startRow!=endRow; j--) {
        this.result.add(matrix[endRow][j]);
    }
    for (int i=endRow-1; i>=startRow+1 && startCol!=endCol; i--) {
        this.result.add(matrix[i][startCol]);
    }

    helper(matrix, startRow+1, endRow-1, startCol+1, endCol-1);
}

链表

删除链表中的元素

https://leetcode.cn/problems/remove-linked-list-elements/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode removeElements(ListNode head, int val) {
    ListNode virtualHead = new ListNode(-1);
    virtualHead.next = head;
    ListNode previous = virtualHead;
    ListNode current = head;
    while (current != null) {
        // 删除current节点时，current移动到下一个，但是previous不用移动
        // 因为最新current节点的上一个节点仍然没有变
        if (current.val == val) {
            previous.next = current.next;
            current = current.next;
        } else {
        // 没有删除节点时，current与previous都需要移动
            previous = previous.next;
            current = current.next;
        }
    }
    return virtualHead.next;
}

设计链表

https://leetcode.cn/problems/design-linked-list/

定义内部节点类

判断索引是否有效 index >=size index < 0无效

找到index位置节点

current设置为虚拟节点，当index等于0时，current要移动到头节点，所以for要写成

// 模仿对数组的遍历，i相当于数组的下标

for (int i=0; i<=index; i++) {

current = current.next;

}

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class MyLinkedList {
    private class ListNode{
        public int val;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    private ListNode virtualHead;
    private int size;
    public MyLinkedList() {
        this.virtualHead = new ListNode(-1);
    }
    
    public int get(int index) {
        if (index >= this.size || index < 0) {
            return -1;
        }
        ListNode current = this.virtualHead;
        for (int i=0; i<=index; i++) {
            current = current.next;
        }
        return current.val;
    }
    
    public void addAtHead(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = this.virtualHead.next;
        this.virtualHead.next = newNode;
        this.size++;
    }
    
    public void addAtTail(int val) {
        ListNode current = this.virtualHead;
        for (int i=0; i<this.size; i++) {
            current = current.next;
        }
        ListNode newNode = new ListNode(val);
        current.next = newNode;
        this.size++;
    }
    
    public void addAtIndex(int index, int val) {
        if (index > this.size || index < 0) {
            return;
        }
        ListNode current = this.virtualHead;
        for (int i=0; i<index; i++) {
            current = current.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = current.next;
        current.next = newNode;
        this.size++;
    }
    
    public void deleteAtIndex(int index) {
        if (index >= this.size || index < 0) {
            return;
        }
        ListNode current = this.virtualHead;
        for (int i=0; i<index; i++) {
            current = current.next;
        }
        current.next = current.next.next;
        this.size--;
    }

    public void printList() {
        ListNode current = this.virtualHead.next;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

反转链表

https://leetcode.cn/problems/reverse-linked-list/

图片

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode previous = null;
        ListNode current = head;
        while (current != null) {
            // 提前保存下一个节点
            ListNode next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }
        return previous;
    }

两两交换节点

https://leetcode.cn/problems/swap-nodes-in-pairs/

图片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode();
    dummy.next = head;
    ListNode current = dummy;
    while (current.next != null && current.next.next != null) {
        // 保存第1个节点，current节点next指向第2个节点
        ListNode temp1 = current.next;
        current.next = current.next.next;

        // 保存第3个节点，第2个节点next指向第1个节点
        ListNode temp3 = current.next.next;
        current.next.next = temp1;

        // 第1个节点，指向第3个节点
        temp1.next = temp3;

        current = current.next.next;
    }
    return dummy.next;
}

链表相交

https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

移动到相同长度的位置

图片

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
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int lengthA = this.getLength(headA);
    int lengthB = this.getLength(headB);
    if (lengthA >= lengthB) {
        headA = this.getNode(headA, lengthA - lengthB);
    } else {
        headB = this.getNode(headB, lengthB - lengthA);
    }
    while (headA != headB) {
        headA = headA.next;
        headB = headB.next;
    }
    return headA;
}

private int getLength(ListNode head) {
    int length = 0;
    while (head != null) {
        length++;
        head = head.next;
    }
    return length;
}

private ListNode getNode(ListNode head ,int index) {
    for (int i=0; i<index; i++) {
        head = head.next;
    }
    return head;
}

环形链表

https://leetcode.cn/problems/linked-list-cycle-ii/

  • 集合
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (!set.add(head)) {
                return head;
            }
            head = head.next;
        }
        ListNode result = null;
        return result;
    }
  • 数学
    图片

图片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode detectCycle(ListNode head) {
   ListNode slow = head;
   ListNode fast = head;
   // 一直不为null，表示有环
   while (fast != null && fast.next != null) {
       fast = fast.next.next;
       slow = slow.next;
       // 相遇
       if (slow == fast) {
           ListNode index1 = fast;
           ListNode index2 = head;
           while (index1 != index2) {
               index1 = index1.next;
               index2 = index2.next;
           }
           return index1;
       }
   }
   return null;
}

哈希表

字母异位词

https://leetcode.cn/problems/valid-anagram/

数组其实就是一种简单的哈希表，key是index，value是元素的值

小写字母，26个，新建长度26的数组

记录s每个字母的数量++

记录t每个字母的数量–

如果nums有非零元素，说明有数量不一样的字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isAnagram(String s, String t) {
    
    int[] nums = new int[26];
    for (int i=0; i<s.length(); i++) {
        nums[s.charAt(i) - 'a']++;
    }
    for (int i=0; i<t.length(); i++) {
        nums[t.charAt(i) - 'a']--;
    }
    for (int value : nums) {
        if (value != 0) {
            return false;
        }
    }
    return true;
}

交集

https://leetcode.cn/problems/intersection-of-two-arrays/

set1 去重nums1

set1中contains nums2中的元素

就就加入set2

set2变成数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set1 = new HashSet<>();
    Set<Integer> set2 = new HashSet<>();

    for (int value : nums1) {
        set1.add(value);
    }
    for (int value : nums2) {
        if (set1.contains(value)) {
            set2.add(value);
        }
    }
    int[] result = new int[set2.size()];
    int i=0;
    for (int value : set2) {
        result[i++] = value;
    } 
    return result;
}

快乐数

https://leetcode.cn/problems/happy-number/

利用好题目给的条件，会循环的，只要找到一个相同的，就开始死循环了，平方和永远无法变成1，直接return false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean isHappy(int n) {
    Set<Integer> set = new HashSet<>();
    do {
        n = this.getSum(n);
        if (!set.add(n)) {
            return false;
        }
    } while (n != 1);
    return true;
}

private int getSum(int n) {
    int sum = 0;
    while (n != 0) {
        int digit = n % 10;
        sum += digit * digit;
        n = n / 10;
    }
    return sum;
}

两数之和

https://leetcode.cn/problems/two-sum/

  • 暴力
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for (int i=0; i<nums.length; i++) {
            for (int j=0; j<nums.length; j++) {
                if (j == i) {
                    continue;
                }
                if (nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return result;
    }
  • map
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        // map key=nums[i] value=i
        Map<Integer, Integer> map = new HashMap<>();
        for (int i=0; i<nums.length; i++) {
            int another = target - nums[i];
            if (map.containsKey(another)) {
                result[0] = map.get(another);
                result[1] = i;
                return result;
            } else {
                // 找不到后才加入，防止another与当前nums[i]重复
                map.put(nums[i], i);
            }
        }
        return result;
    }

四数相加

https://leetcode.cn/problems/4sum-ii/

  • 回溯 超时x
    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
    private int[] nums1;
    private int[] nums2;
    private int[] nums3;
    private int[] nums4;
    private int result;
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        this.nums3 = nums3;
        this.nums4 = nums4;
        this.backtrack(0, 0);
        return this.result;
    }

    private void backtrack(int depth, int sum) {
        if (depth == 4) {
            if (sum == 0) {
                this.result++;
            }
            return;
        }

        for (int i=0; i<this.nums1.length; i++) {
            backtrack(depth + 1, sum + this.getNums(depth)[i]);
        }
    }

    private int[] getNums(int depth) {
        if (depth == 0) {
            return nums1;
        } else if (depth == 1) {
            return nums2;
        } else if (depth == 2) {
            return nums3;
        } else {
            return nums4;
        }
    }
  • 四层循环暴力 超时x
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int result = 0;
        int n = nums1.length;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                for (int k=0; k<n; k++) {
                    for (int l=0; l<n; l++) {
                        if (nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) {
                            result++;
                        }
                    }
                }
            }
        }
        return result;
    }
  • 使用map
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int a : nums1) {
            for (int b : nums2) {
                int temp = a + b;
                map.put(temp, map.getOrDefault(temp, 0) + 1);
            }
        }
        int result = 0;
        for (int c : nums3) {
            for (int d : nums4) {
                // a + b == 0 - c - d时，a b和当前c d组合都满足条件，情况数就是a+b的次数
                result += map.getOrDefault(0 - c - d, 0);
            }
        }
        return result;
    }

三数之和

https://leetcode.cn/problems/3sum/

  • 双指针
    图片

如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

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
public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    for (int i=0; i<nums.length; i++) {
        // 如果最小的元素大于0，无法找到和为0，直接返回result
        if (nums[0] > 0) {
            return result;
        }
        if (i > 0 && nums[i] == nums[i-1]) {
            continue;
        }
        int left = i + 1;
        int right = nums.length - 1;
        while (left < right) {
            // 值大就收缩right，right左移
            int sum = nums[i] + nums[left] + nums[right];
            if (sum > 0) {
                right--;
                // 去重直到nums[right]与后面的元素不想等
                while (left < right && nums[right] == nums[right+1]) {
                    right--;
                }
            }
            // 值小就收缩left，left右移
            else if (sum < 0) {
                left++;
                // 去重
                while (left < right && nums[left] == nums[left-1]) {
                    left++;
                }
            }
            // 找到值后，保存，left与right都要收缩，只收缩一个，肯定不满足条件
            else {
                List<Integer> temp = new ArrayList<>();
                temp.add(nums[i]);
                temp.add(nums[left]);
                temp.add(nums[right]);
                result.add(temp);
                left++;
                right--;
                // 去重，已经保存过一次nums[left]了，不能再用了，换下一个值
                while (left < right && nums[left] == nums[left-1]) {
                    left++;
                }
                // 去重，已经保存过一次nums[right]了，找下一个值
                while (left < right && nums[right] == nums[right+1]) {
                    right--;
                }
            }
        }
    }
    return result;
}
  • 回溯 超时
    回溯也是一种暴力搜索，很容易超时，只不过比for循环复杂一些，但是本质还是暴力搜索
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
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> threeSum(int[] nums) {
    if (nums.length <= 2) {
        return this.result;
    }
    boolean[] used = new boolean[nums.length];
    Arrays.sort(nums);
    this.backtrack(nums, 0, used);
    return this.result;
}

private void backtrack(int[] nums, int startIndex, boolean[] used) {
    if (this.path.size() == 3) {
        int sum = this.getSum(this.path);
        if (sum == 0) {
            this.result.add(new ArrayList(this.path));
        }
        return;
    }

    for (int i=startIndex; i<nums.length; i++) {
        if (i > 0 && !used[i-1] && nums[i-1]==nums[i]) {
            continue;
        }
        used[i] = true;
        this.path.add(nums[i]);
        backtrack(nums, i+1, used);
        used[i] = false;
        this.path.remove(this.path.size()-1);
    }
}

private int getSum(List<Integer> path) {
    int sum = 0;
    for (Integer value : path) {
        sum += value;
    }
    return sum;
}

四数之和

https://leetcode.cn/problems/4sum/

  • 回溯 勉强过
    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
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums.length <= 3) {
            return this.result;
        }
        boolean[] used = new boolean[nums.length];
        
        Arrays.sort(nums);
        this.backtrack(nums, 0, used, target);
        return this.result;
    }

    private void backtrack(int[] nums, int startIndex, boolean[] used, int target) {
        if (this.path.size() == 4) {
            if (target == 0) {
                this.result.add(new ArrayList(this.path));
            }
            return;
        }

        for (int i=startIndex; i<nums.length; i++) {
            if (i > 0 && !used[i-1] && nums[i-1]==nums[i]) {
                continue;
            }
            used[i] = true;
            this.path.add(nums[i]);
            backtrack(nums, i+1, used, target - nums[i]);
            used[i] = false;
            this.path.remove(this.path.size()-1);
        }
    }
  • 双指针
    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
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
       
        for (int i=0; i<nums.length; i++) {
           if (i > 0 && nums[i] == nums[i - 1]) {
               continue;
           }
           for (int j = i + 1; j < nums.length; j++) {
               // 注意去重方式，不能是紧挨上一层循环的元素，相当于回溯遍历去重方式，
               // 能和上一层元素相同，但是本层不能使用重复的
               if (j > i + 1 && nums[j] == nums[j - 1]) {
                   continue;
               }
               int left = j + 1;
               int right = nums.length - 1;
               while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                       // 和上一个值重复了，sum值仍然是一样的，直接循环到不一样的
                       while (left < right && nums[right] == nums[right + 1]) {
                           right--;
                       }
                   } else if (sum < target) {
                       left++;
                       while (left < right && nums[left] == nums[left - 1]) {
                           left++;
                       }
                   } else {
                       result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                       left++;
                       right--;
                       while (left < right && nums[left] == nums[left - 1]) {
                           left++;
                       }
                       while (left < right && nums[right] == nums[right + 1]) {
                           right--;
                       }
                   }
               }
           }
        }
        return result；
    }

赎金信

https://leetcode.cn/problems/ransom-note/

  • 数组哈希表
    记录magazine各个字符的数量

在ransomNote中，减去使用的字符，如果出现负数，说明magazine字符不够用，false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean canConstruct(String ransomNote, String magazine) {
    final int CHAR_NUM = 26;
    int[] nums = new int[CHAR_NUM];
    for (int i = 0; i < magazine.length(); i++) {
        nums[magazine.charAt(i) - 'a']++;
    }
    for (int i = 0; i < ransomNote.length(); i++) {
        nums[ransomNote.charAt(i) - 'a']--;
    }

    for (int value : nums) {
        if (value < 0 ) {
            return false;
        }
    }
    return true;
}

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

北科大计算机在读<br><br>爱好编程<br><br>热爱技术<br><br>喜欢折腾