菜鸡的原地踏步史07(◐‿◑)

二分查找

搜索插入位置

class Solution {
    /** 
        在nums里面进行搜索
        二分查找,返回第一个不小于targer的nums[i]，插入i的位置
        返回left
    */
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while(left < right) {
            int mid = (left + right)/2;
            if(target > nums[mid]) {
                left = mid + 1;
            }
            else if(target < nums[mid]) {
                right = mid;
            }
            else {
                right = mid;
            }
        }
        return left;
    }
}

搜索二维矩阵

class Solution {
    /** 
        除了朴素的拉成一维矩阵，再二分查找
        没想到如何处理二维矩阵
    */
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int col = matrix[0].length;
        List<Integer> list = new ArrayList();
        int[] mt = new int[(row + 1) * (col + 1)];
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                list.add(matrix[i][j]);
            }
        }
        int left = 0;
        int right = list.size();
        while(left < right) {
            int mid = (left + right) / 2;
            if(target == list.get(mid)) {
                // System.out.print(mid + " " + mt[mid]);
                return true;
            }
            else if(target > list.get(mid)) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        return false;
    }
}

排序数字中开始和结束的位置

class Solution {
    /** 
        二分查找？
        分别用二分查找拿到左边界left_bound和右边姐right_bound
        这里是左开右开进行区间缩减，while判断的条件是left <= right
    */
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{searchLeftBound(nums, target), searchRightBound(nums, target)};
        return res;
    }
    public int searchLeftBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(target > nums[mid]) {
                left = mid + 1;
            }
            else if(target < nums[mid]) {
                right = mid - 1;
            }
            else {
                right = mid - 1;
            }
        }
        if(left >= nums.length || nums[left] != target) {
            return -1;
        }
        return left;
    }

    public int searchRightBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(target > nums[mid]) {
                left = mid + 1;
            }
            else if(target < nums[mid]) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        if(right < 0 || nums[right] != target) {
            return -1;
        }
        return right;
    }
}

搜索旋转排序数组

class Solution {
    /** 
        记录下第一次nums[i] > nums[i + 1]的位置的index
        寻找时，从0 ~ index、index + 1 ~ nums.len两处范围内找
    */
    public int search(int[] nums, int target) {
        int idx = 0;
        for(int i = 0; i < nums.length - 1; i++) {
            if(nums[i] > nums[i + 1]) {
                idx = i;
                break;
            }
        }
        int res = findTarget(0, idx, target, nums);
        if(res != -1) {
            return res;
        }
        if(idx + 1 < nums.length) {  // 要这么找，首先肯定要满足条件
            res = findTarget(idx + 1, nums.length - 1, target, nums);
        }
        return res;

    }
    public int findTarget(int left, int right, int target, int[] nums) {
        while(left < right) {
            int mid = (left + right) / 2;
            if(target > nums[mid]) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        return nums[left] == target ? left : -1;
    }
}

寻找旋转排序数组中的最小值

class Solution {
    /** 
        二分直接上左右指针
        如果mid比nums.len位置的值大，说明最小值在右边,left = mid + 1
        否则，由于可能mid就是最小值，right = mid
    */
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right) {
            int mid = (left + right) / 2;
            if(nums[mid] > nums[nums.length - 1]) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        return nums[left];
    }
}

有效的括号

class Solution {
    /** 
        利用栈的特性
        每次判断为( [ {，入栈的时候对应入栈) ] }
        当有同样的) ] } 时，出栈
        一旦栈不为空或者不对应，则直接返回false
    */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack();
        char[] ch = s.toCharArray();
        for(int i = 0; i < ch.length; i++) {
            if(ch[i] == '(' || ch[i] == '[' || ch[i] == '{') {
                if(ch[i] == '(') {
                    stack.push(')');
                }
                if(ch[i] == '[') {
                    stack.push(']');
                }
                if(ch[i] == '{') {
                    stack.push('}');
                }
            }
            else {
                if(stack.isEmpty() || stack.peek() != ch[i]) {
                    return false;
                }
                else {
                    stack.pop();
                }
            }
        }
        if(!stack.isEmpty()) {
            return false;
        }
        return true;
    }
}

最小栈

class MinStack {
    /** 
        两个栈，一个最小栈记录最小值
        一个正常入
    */

    Stack<Integer> stack = new Stack();
    Stack<Integer> minstack = new Stack();

    public MinStack() {
        stack = new Stack();
        minstack = new Stack();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minstack.isEmpty() || val <= minstack.peek()) {
            minstack.push(val);
        }
    }
    
    public void pop() {
        if(stack.pop().equals(minstack.peek())) {
            minstack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minstack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

字符串解码

class Solution {
    /** 
        遇到数字，进行count--
        循环打印字符（）
        数字，存入numstack（当连续时如123）用count计数 num = num*10 + ch - '0'
        str拼接存入strstack
    */
    public String decodeString(String s) {
        Stack<Integer> numstack = new Stack();
        Stack<StringBuffer> strstack = new Stack();
        StringBuffer sb = new StringBuffer();
        char[] ch = s.toCharArray();
        int num = 0;
        for(int i = 0; i < ch.length; i++) {
            // 尚未遇到[]时
            if(ch[i] >= '0' && ch[i] <= '9') { // 有数字计算数字
                num = num * 10 + ch[i] - '0';
            }
            else if(ch[i] >= 'a' && ch[i] <= 'z') { // 有字符放字符
                sb.append(ch[i]);
            }
            else if(ch[i] == '[') { // 遇到 "[" 开始更新存放的数字和字符
                numstack.push(num);
                strstack.push(sb);
                num = 0;
                sb = new StringBuffer();
            }
            else if(ch[i] == ']') { // 开始拼接
                int count = numstack.pop();
                StringBuffer temp = strstack.pop();
                while(count > 0) {
                    temp.append(sb.toString());
                    count--;
                }
                sb = temp;
            }
        }
        return sb.toString();
    }
}

每日温度

class Solution {
    /** 
        用栈实现
                   i = 1
        temp        74
        res         1
        stack 73   弹73，入74(1) res = 1
    */
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack();
        int[] res = new int[temperatures.length];
        for(int i = 0; i < res.length; i++) {
            while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()] ) {
                int j = stack.pop();
                res[j] = i - j;
            }
            stack.push(i);
        }
        return res;
    }
}

堆（没太接触过）

前K个高频元素

class Solution {
    /** 
        用堆进行筛选
        priority<int[]>，存放nums - 次数的数组
        这个数组由遍历nums,hashmap得到key - value（key: num, val: num出现次数
        pq > k，弹出小的元素
        剩余的直接全部拿出
    */
    public int[] topKFrequent(int[] nums, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int[] res = new int[k];
        HashMap<Integer, Integer> map = new HashMap();
        for(int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for(var node : map.entrySet()) {
            int[] tmp = new int[2];
            tmp[0] = node.getKey();
            tmp[1] = node.getValue();
            pq.offer(tmp);
            if(pq.size() > k) {
                pq.poll();
            }
        }
        int i = 0;
        while(!pq.isEmpty()) {
            res[i] = pq.poll()[0];
            i++;
        }
        return res;
    }
}

数组中的第K个最大元素

class Solution {
    /** 
        用堆,分分钟秒
        堆允许重复
    */
    public int findKthLargest(int[] nums, int k) {
        int res = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            public int compare(Integer i1, Integer i2) {
                return i2 - i1;
            }
        });
        for(int num: nums) {
            pq.offer(num);
        }
        while(k > 0) {
            res = pq.poll();
            k--;
        }
        return res;
    }
}