算法练习（9）：牛客在线编程09 双指针

曾经终败给现在 2023-10-15 09:18 17阅读 0赞

package jz.bm;
    
    import jz.Interval;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    
    public class bm9 {
        
        /**
         * BM87 合并两个有序的数组
         */
        public void merge(int A[], int m, int B[], int n) {
        
            int i = m - 1, j = n - 1, k = m + n - 1;
            while (i >= 0 || j >= 0) {
        
                int a = i >= 0 ? A[i] : Integer.MIN_VALUE;
                int b = j >= 0 ? B[j] : Integer.MIN_VALUE;
                if (a > b) {
        
                    A[k] = a;
                    i--;
                } else {
        
                    A[k] = b;
                    j--;
                }
                k--;
            }
        }
    
        /**
         * BM88 判断是否为回文字符串
         */
        public boolean judge (String str) {
        
            if (str == null || str.equals("")) {
        
                return true;
            }
            for (int i = 0; i < str.length() / 2; i++) {
        
                if (str.charAt(i) != str.charAt(str.length() - 1 - i)) {
        
                    return false;
                }
            }
            return true;
        }
    
        /**
         * BM89 合并区间
         */
        public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        
            intervals.sort((o1, o2) -> o1.start - o2.start);
            int pre = 0, cur = 1;
            while (cur < intervals.size()) {
        
                //无法合并
                if (intervals.get(pre).end < intervals.get(cur).start) {
        
                    pre = cur;
                    cur++;
                } else if (intervals.get(pre).end >= intervals.get(cur).start) {
         //可以合并
                    intervals.get(cur).start = intervals.get(pre).start;
                    intervals.get(cur).end = Math.max(intervals.get(pre).end, intervals.get(cur).end);
                    intervals.remove(pre);
                }
            }
            return intervals;
        }
    
        /**
         * BM91 反转字符串
         */
        public String solve (String str) {
        
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = str.length() - 1; i >= 0; i--) {
        
                stringBuilder.append(str.charAt(i));
            }
            return stringBuilder.toString();
        }
    
        /**
         * BM92 最长无重复子数组
         */
        public int maxLength (int[] arr) {
        
            //双指针 + hashmap去重
            if (arr.length == 0) {
        
                return 0;
            }
            int res = 0;
            int i = 0, j = 0;
            HashMap<Integer, Integer> map = new HashMap<>();
            while (j < arr.length) {
        
                //新加入是字符有重复，更新i
                if (map.containsKey(arr[j])) {
        
                    i = Math.max(i, map.get(arr[j]) + 1);
                }
                map.put(arr[j], j);
                res = Math.max(res, j - i + 1);
                j++;
            }
            return res;
        }
    
        /**
         * BM93 盛水最多的容器
         */
        public int maxArea (int[] height) {
        
            //双指针 + 贪心算法
            if (height.length <= 1) {
        
                return 0;
            }
            int i = 0, j = height.length - 1, res = 0;
            while (i < j) {
        
                res = Math.max(res, Math.min(height[i], height[j]) * (j - i));
                if (height[i] < height[j]) {
        
                    i++;
                } else {
        
                    j--;
                }
            }
            return res;
        }
    }