• 搞搞算法 1

    https://github.com/labuladong/fucking-algorithm

    双指针

    力扣26 删除有序数组中的重复项

    https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

    1. class Solution {
    2.     public int removeDuplicates(int[] nums) {
    3.         if(nums.length < 2){
    4.             return nums.length;
    5.         }
    6.         // 定义快慢双指针
    7.         int fast = 1;
    8.         int slow = 0;
    9.         while(fast < nums.length){
    10.             if(nums[slow] != nums[fast]){
    11.                 slow++;
    12.                 nums[slow] = nums[fast];
    13.             }
    14.             fast++;
    15.         }
    16.         return slow + 1;
    17.     }
    18. }

    力扣27 移除元素

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

    1. class Solution {
    2.     public int removeElement(int[] nums, int val) {
    3.         // 定义快慢双指针
    4.         int fast = 0;
    5.         int slow = 0;
    6.         while (fast < nums.length) {
    7.             if (nums[fast] != val) {
    8.                 nums[slow] = nums[fast];
    9.                 slow++;
    10.             }
    11.             fast++;
    12.         }
    13.         return slow;
    14.     }
    15. }

    力扣167 两数之和 II

    https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/

    1. class Solution {
    2.     public int[] twoSum(int[] numbers, int target) {
    3.         // 定义对撞双指针
    4.         int left = 0;
    5.         int right = numbers.length - 1;
    6.         while(left < right){
    7.             if(numbers[left] + numbers[right] == target){
    8.                 return new int[] {left + 1, right + 1};
    9.             }
    10.             if(numbers[left] + numbers[right] < target){
    11.                 left++;
    12.             }
    13.             if(numbers[left] + numbers[right] > target){
    14.                 right--;
    15.             }
    16.         }
    17.         return new int[]{-1, -1};
    18.     }
    19. }

    力扣344 反转字符串

    https://leetcode.cn/problems/reverse-string/

    1. class Solution {
    2.     public void reverseString(char[] s) {
    3.         // 定义对撞双指针
    4.         int left = 0;
    5.         int right = s.length - 1;
    6.         char c;
    7.         while(left < right){
    8.             c = s[left];
    9.             s[left] = s[right];
    10.             s[right] = c;
    11.             left++;
    12.             right--;
    13.         }
    14.     }
    15. }

    力扣5 最长回文子串

    https://leetcode.cn/problems/longest-palindromic-substring/

    1. class Solution {
    2.     /**
    3.      * 主方法
    4.      */
    5.     public String longestPalindrome(String s) {
    6.         String res = "";
    7.         // 遍历字符串s
    8.         for(int i = 0; i < s.length(); i++){
    9.             String str1 = getPalindrome(s, i, i);
    10.             String str2 = getPalindrome(s, i, i + 1);
    11.             String str = str1.length() > str2.length() ? str1 : str2;
    12.             res = str.length() > res.length() ? str : res;
    13.         }
    14.         return res;
    15.     }
    16.  
    17.     /**
    18.      * 获得以某两点为中心的最长子回文串
    19.      */
    20.     public String getPalindrome(String s, int left, int right){
    21.         while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
    22.             // 离心双指针
    23.             left--;
    24.             right++;
    25.         }
    26.         return s.substring(left + 1, right);
    27.     }
    28. }

    双指针-链表

    力扣21 合并两个有序链表

    https://leetcode.cn/problems/merge-two-sorted-lists/

    1. class Solution {
    2.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    3.         // 双指针list1、list2
    4.         if(list1 == null){
    5.             return list2;
    6.         }
    7.         if(list2 == null){
    8.             return list1;
    9.         }
    10.         // 定义虚拟头结点
    11.         ListNode dummy = new ListNode();
    12.         ListNode current = dummy;
    13.         // 推进
    14.         while(list1 != null && list2 != null){
    15.             if(list1.val <= list2.val){
    16.                 current.next = list1;
    17.                 list1 = list1.next;
    18.             } else{
    19.                 current.next = list2;
    20.                 list2 = list2.next;
    21.             }
    22.             current = current.next;
    23.         }
    24.         // 处理剩余结点
    25.         if(list1 != null){
    26.             current.next = list1;
    27.         }
    28.         if(list2 != null){
    29.             current.next = list2;
    30.         }
    31.         return dummy.next;
    32.     }
    33. }

    力扣86 分隔链表

    https://leetcode.cn/problems/partition-list/

    1. class Solution {
    2.     public ListNode partition(ListNode head, int x) {
    3.         if (head == null) {
    4.             return head;
    5.         }
    6.         // 定义虚拟头结点
    7.         ListNode dummy1 = new ListNode(-1, head);
    8.         ListNode dummy2 = new ListNode(-1, head);
    9.         // 定义双指针
    10.         ListNode p1 = dummy1;
    11.         ListNode p2 = dummy2;
    12.         while(head != null){
    13.             if(head.val < x){
    14.                 p1.next = head;
    15.                 p1 = head;
    16.                 p2.next = null;
    17.             } else{
    18.                 p2.next = head;
    19.                 p2 = head;
    20.                 p1.next = null;
    21.             }
    22.             head = head.next;
    23.         }
    24.         // 连接两个链表
    25.         p1.next = dummy2.next;
    26.         return dummy1.next;
    27.     }
    28. }

    力扣19 删除链表的倒数第n个结点

    https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

    1. class Solution {
    2.     public ListNode removeNthFromEnd(ListNode head, int n) {
    3.         // 定义虚拟头结点
    4.         ListNode dummy = new ListNode(-1, head);
    5.         // 定义双指针
    6.         ListNode p1 = dummy;
    7.         ListNode p2 = dummy;
    8.         // p3是p2的前一个结点
    9.         ListNode p3 = null;
    10.         // p1先行
    11.         for(int i = 0; i < n; i++){
    12.             p1 = p1.next;
    13.         }
    14.         // p1、p2、p3同时推进
    15.         while(p1 != null){
    16.             if(p3 == null){
    17.                 p3 = p2;
    18.             } else{
    19.                 p3 = p3.next;
    20.             }
    21.             p1 = p1.next;
    22.             p2 = p2.next;
    23.         }
    24.         // 删除p2结点
    25.         p3.next = p2.next;
    26.         return dummy.next;
    27.     }
    28. }

    力扣876 链表的中间结点

    https://leetcode.cn/problems/middle-of-the-linked-list/

    1. class Solution {
    2.     public ListNode middleNode(ListNode head) {
    3.         // 定义虚拟头结点
    4.         ListNode dummy = new ListNode(-1, head);
    5.         // 定义快慢双指针
    6.         ListNode p1 = dummy;
    7.         ListNode p2 = dummy;
    8.         while(p1 != null){
    9.             p1 = p1.next;
    10.             p2 = p2.next;
    11.             if(p1 == null || p1.next == null){
    12.                 return p2;
    13.             }
    14.             p1 = p1.next;
    15.         }
    16.         return null;
    17.     }
    18. }

    力扣141 环形链表

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

    1. class Solution {
    2.     public boolean hasCycle(ListNode head) {
    3.         if(head == null || head.next == null){
    4.             return false;
    5.         }
    6.         // 定义快慢双指针
    7.         ListNode p1 = head;
    8.         ListNode p2 = head;
    9.         while(p1 != null && p1.next != null){
    10.             p1 = p1.next.next;
    11.             p2 = p2.next;
    12.             if(p1 == p2){
    13.                 return true;
    14.             }
    15.         }
    16.         return false;
    17.     }
    18. }

    力扣160 相交链表

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

    1. class Solution {
    2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    3.         // 定义双指针
    4.         ListNode p1 = headA;
    5.         ListNode p2 = headB;
    6.         while(p1 != p2){
    7.          if(p1 == null){
    8.                 p1 = headB;
    9.             } else{
    10.                 p1 = p1.next;
    11.             }
    12.             if(p2 == null){
    13.                 p2 = headA;
    14.             } else{
    15.                 p2 = p2.next;
    16.             }
    17.         }
    18.         return p1;
    19.     }
    20. }

    递归

    力扣206 反转链表

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

    1. class Solution {
    2.     public ListNode reverseList(ListNode head) {
    3.         // base case
    4.         if(head == null || head.next == null){
    5.             return head;
    6.         }
    7.         // 前序位置(无操作)
    8.         // 递归
    9.         ListNode last = reverseList(head.next);
    10.         // 后序位置
    11.         head.next.next = head;
    12.         head.next = null;
    13.         return last;
    14.     }
    15. }

    力扣92 反转链表 II

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

    1. class Solution {
    2.     ListNode mark = null;
    3.  
    4.     /**
    5.      * 主方法
    6.      */
    7.     public ListNode reverseBetween(ListNode head, int left, int right) {
    8.         if (left == 1) {
    9.             return reverseN(head, right);
    10.         }
    11.         head.next = reverseBetween(head.next, left - 1, right - 1);
    12.         return head;
    13.     }
    14.  
    15.     /**
    16.      * 反转链表的前n个结点
    17.      */
    18.     ListNode reverseN(ListNode head, int n) {
    19.         if (n == 1) {
    20.             mark = head.next;
    21.             return head;
    22.         }
    23.         ListNode last = reverseN(head.next, n - 1);
    24.         head.next.next = head;
    25.         head.next = mark;
    26.         return last;
    27.     }
    28. }

    力扣234 回文链表

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

    1. class Solution {
    2.     ListNode left;
    3.  
    4.     /**
    5.      * 主方法
    6.      */
    7.     public boolean isPalindrome(ListNode head) {
    8.         left = head;
    9.         return work(left);
    10.     }
    11.  
    12.     /**
    13.   * 判断是否是回文链表
    14.      */
    15.     public boolean work(ListNode current){
    16.         if(current == null){
    17.             return true;
    18.         }
    19.         boolean res = work(current.next);
    20.         res = res && (left.val == current.val);
    21.         left = left.next;
    22.         return res;
    23.     }
    24. }

    滑动窗口

    1. // 滑动窗口算法框架
    2. void slidingWindow(string s) {
    3.     unordered_map<char, int> window;
    4.     
    5.     int left = 0, right = 0;
    6.     while (right < s.size()) {
    7.         // c是将移入窗口的字符
    8.         char c = s[right];
    9.         // 增大窗口
    10.         right++;
    11.         // 进行窗口内数据的一系列更新
    12.         ...
    13.  
    14.         /*** debug 输出的位置 ***/
    15.         printf("window: [%d, %d)\n", left, right);
    16.         /********************/
    17.         
    18.         // 判断左侧窗口是否要收缩
    19.         while (window needs shrink) {
    20.             // d 是将移出窗口的字符
    21.             char d = s[left];
    22.             // 缩小窗口
    23.             left++;
    24.             // 进行窗口内数据的一系列更新
    25.             ...
    26.         }
    27.     }
    28. }

    力扣76 最小覆盖子串

    https://leetcode.cn/problems/minimum-window-substring/

    1. class Solution {
    2.     public String minWindow(String s, String t) {
    3.         // 字符串转数组
    4.         char[] sArr = s.toCharArray();
    5.         char[] tArr = t.toCharArray();
    6.         // 子串
    7.         Map need = new HashMap();
    8.         for(char c : tArr){
    9.             need.put(c, need.getOrDefault(c, 0) + 1);
    10.         }
    11.         // 窗口
    12.         Map window = new HashMap();
    13.         int left = 0;
    14.         int right = 0;
    15.         // 匹配度
    16.         int valid = 0;
    17.         // 记录结果
    18.         int start = 0;
    19.         int len = Integer.MAX_VALUE;
    20.         // 窗口滑动
    21.         while(right < sArr.length){
    22.             // 右指针前进, 扩大窗口
    23.             char c = sArr[right];
    24.             right++;
    25.             if(need.containsKey(c)){
    26.                 window.put(c, window.getOrDefault(c, 0) + 1);
    27.                 if(window.getOrDefault(c, 0).equals(need.getOrDefault(c, 0))){
    28.                     valid++;
    29.                 }
    30.             }
    31.             // 窗口完全覆盖子串
    32.             while(valid == need.size()){
    33.                 // 记录当前窗口
    34.                 if(right - left < len){
    35.                     start = left;
    36.                     len = right - left;
    37.                 }
    38.                 // 左指针前进, 缩小窗口
    39.                 char d = sArr[left];
    40.                 left++;
    41.                 if(need.containsKey(d)){
    42.                     if(window.getOrDefault(d, 0).equals(need.getOrDefault(d, 0))){
    43.                         valid--;
    44.                     }
    45.                     window.put(d, window.getOrDefault(d, 0) - 1);
    46.                 }
    47.             }
    48.         }
    49.         return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    50.     }
    51. }

    力扣567 字符串的排列

    https://leetcode.cn/problems/permutation-in-string/

    1. class Solution {
    2.     public boolean checkInclusion(String s1, String s2) {
    3.         // 字符串转数组
    4.         char[] s1Arr = s1.toCharArray();
    5.         char[] s2Arr = s2.toCharArray();
    6.         // 子串
    7.         Map need = new HashMap();
    8.         for(char c : s1Arr){
    9.             need.put(c, need.getOrDefault(c, 0) + 1);
    10.         }
    11.         // 窗口
    12.         Map window = new HashMap();
    13.         int left = 0;
    14.         int right = 0;
    15.         // 匹配度
    16.         int valid = 0;
    17.         // 窗口滑动
    18.         while(right < s2Arr.length){
    19.             // 右指针前进, 扩大窗口
    20.             char c = s2Arr[right];
    21.             right++;
    22.             if(need.containsKey(c)){
    23.                 window.put(c, window.getOrDefault(c, 0) + 1);
    24.                 if(window.getOrDefault(c, 0) <= need.getOrDefault(c, 0)){
    25.                     valid++;
    26.                 }
    27.             }
    28.             // 窗口大小不能超过s1的长度
    29.             while(right - left >= s1Arr.length){
    30.                 // 匹配成功
    31.                 if(valid == s1Arr.length){
    32.                     return true;
    33.                 }
    34.                 // 左指针前进, 缩小窗口
    35.                 char d = s2Arr[left];
    36.                 left++;
    37.                 if(need.containsKey(d)){
    38.                     if(window.getOrDefault(d, 0) <= need.getOrDefault(d, 0)){
    39.                         valid--;
    40.                     }
    41.                     window.put(d, window.getOrDefault(d, 0) - 1);
    42.                 }
    43.             }
    44.         }
    45.         return false;
    46.     }
    47. }

    力扣438 找到字符串中素有字母异位词

    https://leetcode.cn/problems/find-all-anagrams-in-a-string/

    1. class Solution {
    2.     public List findAnagrams(String s, String p) {
    3.         // 字符串转数组
    4.         char[] sArr = s.toCharArray();
    5.         char[] pArr = p.toCharArray();
    6.         // 子串
    7.         Map need = new HashMap();
    8.         for(char c : pArr){
    9.             need.put(c, need.getOrDefault(c, 0) + 1);
    10.         }
    11.         // 窗口
    12.         Map window = new HashMap();
    13.         int left = 0;
    14.         int right = 0;
    15.         // 匹配度
    16.         int valid = 0;
    17.         // 记录结果
    18.         List res = new ArrayList();
    19.         // 窗口滑动
    20.         while(right < sArr.length){
    21.             // 右指针前进, 扩大窗口
    22.             char c = sArr[right];
    23.             right++;
    24.             if(need.containsKey(c)){
    25.                 window.put(c, window.getOrDefault(c, 0) + 1);
    26.                 if(window.getOrDefault(c, 0) <= need.getOrDefault(c, 0)){
    27.                     valid++;
    28.                 }
    29.             }
    30.             // 窗口大小不能超过p的长度
    31.             while(right - left >= pArr.length){
    32.                 // 匹配成功
    33.                 if(valid == pArr.length){
    34.                     res.add(left);
    35.                 }
    36.                 // 左指针前进, 缩小窗口
    37.                 char d = sArr[left];
    38.                 left++;
    39.                 if(need.containsKey(d)){
    40.                     if(window.getOrDefault(d, 0) <= need.getOrDefault(d, 0)){
    41.                         valid--;
    42.                     }
    43.                     window.put(d, window.getOrDefault(d, 0) - 1);
    44.                 }
    45.             }
    46.         }
    47.         return res;
    48.     }
    49. }

    力扣3 无重复字符的最长子串

    https://leetcode.cn/problems/longest-substring-without-repeating-characters/

    1. class Solution {
    2.     public int lengthOfLongestSubstring(String s) {
    3.         // 字符串转数组
    4.         char[] sArr = s.toCharArray();
    5.         // 窗口
    6.         Map window = new HashMap();
    7.         int left = 0;
    8.         int right = 0;
    9.         // 记录结果
    10.         int len = 0;
    11.         // 窗口滑动
    12.         while(right < sArr.length){
    13.             // 右指针前进, 扩大窗口
    14.             char c = sArr[right];
    15.             right++;
    16.             window.put(c, window.getOrDefault(c, 0) + 1);
    17.             // 窗口中不能包含重复元素
    18.             while(window.getOrDefault(c, 0) > 1){
    19.                 // 左指针前进, 缩小窗口
    20.                 char d = sArr[left];
    21.                 left++;
    22.                 window.put(d, window.getOrDefault(d, 0) - 1);
    23.             }
    24.             // 更新结果
    25.             if(right - left > len){
    26.                 len = right - left;
    27.             }
    28.         }
    29.         return len;
    30.     }
    31. }

    力扣187 重复的DNA序列

    https://leetcode.cn/problems/repeated-dna-sequences/

    1. class Solution {
    2.     public List findRepeatedDnaSequences(String s) {
    3.         // 字符串转数组
    4.         char[] sArr = s.toCharArray();
    5.         // char数组转int数组
    6.         int[] nums = new int[sArr.length];
    7.         for(int i = 0; i < nums.length; i++){
    8.             switch(sArr[i]){
    9.                 case 'A':
    10.                     nums[i] = 0;
    11.                     break;
    12.                 case 'G':
    13.                     nums[i] = 1;
    14.                     break;
    15.                 case 'C':
    16.                     nums[i] = 2;
    17.                     break;
    18.                 case 'T':
    19.                     nums[i] = 3;
    20.                     break;
    21.             }
    22.         }
    23.         // 窗口位数、进制、最高位代表的值
    24.         int L = 10;
    25.         int R = 4;
    26.         int RL = (int) Math.pow(R, L - 1);
    27.         // 窗口hash
    28.         int windowHash = 0;
    29.         // 记录结果
    30.         Set seen = new HashSet();
    31.         Set res = new HashSet();
    32.         // 窗口滑动
    33.         int left = 0;
    34.         int right = 0;
    35.         while(right < nums.length){
    36.             // 计算窗口hash
    37.             windowHash = windowHash * R + nums[right];
    38.             right++;
    39.             // 窗口大小为定值L
    40.             if(right - left == L){
    41.                 if(seen.contains(windowHash)){
    42.                     res.add(s.substring(left, right));
    43.                 } else{
    44.                     seen.add(windowHash);
    45.                 }
    46.                 windowHash = windowHash - nums[left] * RL;
    47.                 left++;
    48.             }
    49.         }
    50.         return new LinkedList(res);
    51.     }
    52. }

    二分搜索

    1. int binarySearch(int[] nums, int target) {
    2.     int left = 0, right = ...;
    3.  
    4.     while(...) {
    5.         int mid = left + (right - left) / 2;
    6.         if (nums[mid] == target) {
    7.             ...
    8.         } else if (nums[mid] < target) {
    9.             left = ...
    10.         } else if (nums[mid] > target) {
    11.             right = ...
    12.         }
    13.     }
    14.     return ...;
    15. }

    左边界和右边界

    如图，target=5的情况下，搜索左侧边界得到的值为6，搜索右侧边界得到的值为4。

    力扣704 二分查找

    https://leetcode.cn/problems/binary-search/

    1. class Solution {
    2.     public int search(int[] nums, int target) {
    3.         int left = 0;
    4.         int right = nums.length - 1;
    5.         // 二分查找
    6.         while(left <= right){
    7.             int mid = left + (right - left) / 2;
    8.             if(nums[mid] == target){
    9.                 return mid;
    10.             } else if(nums[mid] > target){
    11.                 right = mid - 1;
    12.             } else if(nums[left] < target){
    13.                 left = mid + 1;
    14.             }
    15.         }
    16.         return -1;
    17.     }
    18. }

    力扣34 在排序数组中查找元素的第一个和最后一个位置

    https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

    1. class Solution {
    2.     public int[] searchRange(int[] nums, int target) {
    3.         if(nums.length == 0){
    4.             return new int[]{-1, -1};
    5.         }
    6.         // 查找范围: [0, nums.length - 1]
    7.         int left = 0;
    8.         int right = nums.length - 1;
    9.         // 终止条件: left == right + 1
    10.         while(left <= right){
    11.             int mid = left + (right - left) / 2;
    12.             if(nums[mid] == target){
    13.                 right = mid - 1;
    14.             } else if(nums[mid] > target){
    15.                 right = mid - 1;
    16.             } else if(nums[mid] < target){
    17.                 left = mid + 1;
    18.             }
    19.         }
    20.         int pl = (left != nums.length && nums[left] == target) ? left : -1;
    21.         left = 0;
    22.         right = nums.length - 1;
    23.         while(left <= right){
    24.             int mid = left + (right - left) / 2;
    25.             if(nums[mid] == target){
    26.                 left = mid + 1;
    27.             } else if(nums[mid] > target){
    28.                 right = mid - 1;
    29.             } else if(nums[mid] < target){
    30.                 left = mid + 1;
    31.             }
    32.         }
    33.         int pr = (right != -1 && nums[right] == target) ? right : -1;
    34.         return new int[]{pl, pr};
    35.     }
    36. }

    力扣875 爱吃香蕉的珂珂

    https://leetcode.cn/problems/koko-eating-bananas/

    力扣1011 在D天内送达包裹的能力

    https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/

    力扣410 分割数组的最大值

    https://leetcode.cn/problems/split-array-largest-sum/ 

    前缀和数组

    力扣303 区域和检索 - 数组不可变

    https://leetcode.cn/problems/range-sum-query-immutable/

    1. class NumArray {
    2.     private int[] preNums;
    3.  
    4.     /**
    5.      * 构造方法
    6.      */
    7.     public NumArray(int[] nums) {
    8.         preNums = new int[nums.length + 1];
    9.         preNums[0] = 0;
    10.         // 构建前缀和数组
    11.         for(int i = 1; i < preNums.length; i++){
    12.             preNums[i] = preNums[i - 1] + nums[i - 1];
    13.         }
    14.     }
    15.  
    16.     /**
    17.      * 获取区域内元素总和
    18.      */
    19.     public int sumRange(int left, int right) {
    20.         return preNums[right + 1] - preNums[left];
    21.     }
    22. }

    力扣304 二位区域和检索

    https://leetcode.cn/problems/range-sum-query-2d-immutable/

    1. class NumMatrix {
    2.     private int[][] preSum;
    3.  
    4.     /**
    5.      * 构造方法
    6.      */
    7.     public NumMatrix(int[][] matrix) {
    8.         int m = matrix.length;
    9.         int n = matrix[0].length;
    10.         // 构建二维前缀和数组
    11.         preSum = new int[m + 1][n + 1];
    12.         for(int i = 1; i <= m; i++){
    13.             for(int j = 1; j <= n; j++){
    14.                 preSum[i][j] = matrix[i - 1][j - 1] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1];
    15.             }
    16.         }
    17.     }
    18.  
    19.     /**
    20.      * 获取子矩阵元素总和
    21.      */
    22.     public int sumRegion(int row1, int col1, int row2, int col2) {
    23.         return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1] - preSum[row2 + 1][col1] + preSum[row1][col1];
    24.     }
    25. }

    力扣528 按权重随机选择

    https://leetcode.cn/problems/random-pick-with-weight/

    1. class Solution {
    2.     private int[] preSums;
    3.     private Random rand = new Random();
    4.  
    5.     /**
    6.      * 构造方法
    7.      */
    8.     public Solution(int[] w) {
    9.         // 定义前缀和数组
    10.         preSums = new int[w.length + 1];
    11.         preSums[0] = 0;
    12.         for(int i = 1; i < preSums.length; i++){
    13.             preSums[i] = preSums[i - 1] + w[i - 1];
    14.         }
    15.     }
    16.  
    17.     /**
    18.      * 按权重随机选择
    19.      */
    20.     public int pickIndex() {
    21.         // 随机数生成范围: [1, preSums[preSums.length - 1]]
    22.         int target = rand.nextInt(preSums[preSums.length - 1]) + 1;
    23.         int left = 0;
    24.         int right = preSums.length - 1;
    25.         // 二分查找 左边界
    26.         while(left <= right){
    27.             int mid = left + (right - left) / 2;
    28.             if(preSums[mid] == target){
    29.                 right = mid - 1;
    30.             } else if(preSums[mid] > target){
    31.                 right = mid - 1;
    32.             } else if(preSums[mid] < target){
    33.                 left = mid + 1;
    34.             }
    35.         }
    36.         return left - 1;
    37.     }
    38. }

    差分数组

    力扣1109 航班预订统计

    https://leetcode.cn/problems/corporate-flight-bookings/

    1. class Solution {
    2.     public int[] corpFlightBookings(int[][] bookings, int n) {
    3.         int[] diff = new int[n + 1];
    4.         int a;
    5.         int b;
    6.         int c;
    7.         // 构建差分数组
    8.         for(int i = 0; i < bookings.length; i++){
    9.             a = bookings[i][0];
    10.             b = bookings[i][1];
    11.             c = bookings[i][2];
    12.             diff[a - 1] += c;
    13.             diff[b] -= c;
    14.         }
    15.         int[] res = new int[n];
    16.         // 根据差分数组反推结果
    17.         res[0] = diff[0];
    18.         for(int j = 1; j < n; j++){
    19.             res[j] = res[j - 1] + diff[j];
    20.         }
    21.         return res;
    22.     }
    23. }

    力扣1094 拼车

    https://leetcode.cn/problems/car-pooling/

    1. class Solution {
    2.     public boolean carPooling(int[][] trips, int capacity) {
    3.         // 0到1000共1001
    4.         int[] diff = new int[1001];
    5.         int a,b,c;
    6.         // 构建差分数组
    7.         for(int i = 0; i < trips.length; i++){
    8.             a = trips[i][0];
    9.             b = trips[i][1];
    10.             c = trips[i][2];
    11.             diff[b] += a;
    12.             diff[c] -= a;
    13.         }
    14.         int[] res = new int[1001];
    15.         // 根据差分数组反推结果
    16.         res[0] = diff[0];
    17.         if(res[0] > capacity){
    18.             return false;
    19.         }
    20.         for(int j = 1; j < 1001; j++){
    21.             res[j] = res[j - 1] + diff[j];
    22.             if(res[j] > capacity){
    23.                 return false;
    24.             }
    25.         }
    26.         return true;
    27.     }
    28. }
  • 相关阅读:
    【业务场景】用户连点
    IDEA 中 Maven 报错 Cannot resolve xxx【终于解决了】
    pyqt5-tools的安装（深度学习）
    luffy-(2)
    报时机器人的rasa shell执行流程分析
    2022/7/27 算力-价格明细
    如何破坏开发板iNand中的uboot？
    Vue路由与nodejs环境搭建
    JVM的垃圾收集算法
    Java项目：JSP酒店客房管理系统
  • 原文地址：https://blog.csdn.net/qq_42082161/article/details/126863119