头像

tt2767


访客:46711

离线:16小时前



tt2767
5个月前
/**
1. 先倒着找到第一个字母, 然后统计连续的字母个数即可

*/

class Solution {
    public int lengthOfLastWord(String s) {
        if (s == null || s.length() == 0) return 0;
        int p = s.length() - 1, n = s.length();
        while (0 <= p && s.charAt(p) == ' ') p--;
        if (p < 0) return 0;
        int result = 0;
        while (0 <= p && s.charAt(p) != ' ') {
            p--;
            result++;
        }
        return result;
    }
}



tt2767
5个月前
/**
1. 模拟 + 进位
*/

class Solution {
    public int[] plusOne(int[] digits) {

        int n = digits.length;
        digits[n-1] += 1;
        for (int i = n - 1 ; i > 0; i--){
            if (digits[i] < 10 ) break;
            digits[i - 1] ++;
            digits[i] -= 10;
        }

        if (digits[0] >= 10) {
            int[] res = new int[n + 1];
            res[0] = 1;
            digits[0] -= 10;
            for (int i = 1 ;i <= n ; i++){
                res[i] = digits[i-1];
            }
            return res;
        }

        return digits;
    }
}



tt2767
5个月前
/**
1. 范围>=s, 双指针去找值
*/


class Solution {

    public int minSubArrayLen(int s, int[] nums) {
        return doublePoint(s, nums);
    }

    public int doublePoint(int s, int[] nums){
        int sum = 0, left = 0, right = 0, n = nums.length, result = Integer.MAX_VALUE;
        while (left < n && right < n){
            while (right < n && sum < s){
                sum += nums[right++];
            }

            while (left < n && sum >= s){
                result = Math.min(result, right - left);
                sum -= nums[left++];
            }
        }
        if (sum >= s) result = Math.min(result, right - left);
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}



tt2767
5个月前
/**
1. 环状数组的一个经典处理方法是, 复制一份相同的追加到后面
2. 找一侧恰好比当前数大可以用单调栈
*/

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        if (nums == null || nums.length == 0) return nums;
        int n = nums.length;
        int[] range = new int[n * 2];
        for (int i = 0 ; i < n; i++){
            range[i] = nums[i];
            range[i + n] = nums[i];
        }

        Stack<Integer> stack = new Stack<>();
        for (int i = 2 * n - 1; i >= 0; i--){
            int num = range[i];
            while (!stack.isEmpty() && num >= stack.peek()) stack.pop();
            range[i] = stack.isEmpty() ? -1 :stack.peek();
            stack.push(num);
        }

        for (int i = 0; i < n ;i ++) nums[i] = range[i];
        return nums;
    }
}



tt2767
5个月前
/**
1. 其实就是下一个排列, 找到恰好比它大且元素相同的数, 那么肯定要是低位较大的数和高位较小的数swap,
    1.1 高位满足恰好大于n : 从后向前找到恰好第一个相邻逆序对(a,b), a < b , 然后在a后面找一个恰好大于a的最小和数c, swap(a, c)
    1.2 低位满足恰好大于n : 对a后面的数排序

2. 特判:
    2.1 特判掉前导零的情况
    2.2 特判掉没找到的情况
    2.3 特判掉超出int的情况
*/

class Solution {
    public int nextGreaterElement(int n) {
        if (n < 10) return -1;
        char[] num = String.valueOf(n).toCharArray();
        int p1 = num.length - 2, p2 = num.length - 1;
        while (0 <= p1 && 0 <= p2 && num[p1] >= num[p2]){
            p1 --;
            p2 --;
        }

        if (p1 < 0 || p2 < 0) return -1;
        int p3 = p2;
        while (p3 < num.length && num[p1] < num[p3] && num[p3] <= num[p2]) p3++;
        p3 --;
        if (p1 == 0 && num[p3] == '0') return -1;

        char temp = num[p1];
        num[p1] = num[p3];
        num[p3] = temp;
        Arrays.sort(num, p2, num.length);

        long next = Long.parseLong(new String(num));
        if(next > Integer.MAX_VALUE) return -1;

        return (int)next;
    }
}



tt2767
5个月前
/**
1. 2^n 一定大于0
2. 2^n 的二进制表示一定只有一个1 -> x == lowbit(x)
*/


class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && n == (n & (-n));
    }
}



tt2767
5个月前
/**
1. 左开右闭区间的范围维护:
    1.1 因为边界范围是 1e9, 所以不可能存每个数来查, 
    1.2 但是查询和写入次数较少所以可以维护顺序的二元组[left, right) 列表, 通过二分查找确定位置
    1.3 怎么快速二分查找, 并且动态添加删除 -> 平衡二叉查找树 -> TreeSet

2. 各操作
    1. 确定区间范围 [left, right) 区间应该扫描[-∞, left) 到 [right+1, +∞) 之间的所有区间
    2. add: 扩展可覆盖的交集, 并删除set内元素, 最后放入扩展后的区间
    3. del: in.left < left ,   说明原区间前面有切割剩余, 加入 [in.left, left)
            right < in.right , 说明原区间后面有切割剩余, 加入 [right, in.righ)
    4. query: [left, right) 只可能和两个区间相交: [left, right)  前面的区间a, 和 a后面的区间b ,如果a,b都不包含[left, right) ,返回 false
*/

class RangeModule {

    class Node{
        int left, right;
        public Node(int left, int right){
            this.left = left;
            this.right = right;
        } 
    }

    TreeSet<Node> data;
    public RangeModule() {
        data = new TreeSet<>((a,b)->(a.right == b.right ? a.left - b.left : a.right - b.right));
    }

    public void addRange(int left, int right) {
        Iterator<Node> it = data.tailSet(new Node(0, left)).iterator();
        while (it.hasNext()){
            Node node = it.next();
            if (right < node.left) break;
            left = Math.min(left, node.left);
            right = Math.max(right, node.right);
            it.remove();
        }
        data.add(new Node(left, right));
    }

    public boolean queryRange(int left, int right) {
        if (data.isEmpty()) return false;
        Node node = new Node(left, right);
        Node prev = data.lower(node);
        if (prev != null && prev.left <= left && right <= prev.right) return true;
        Node next = prev == null ? data.first() : data.higher(prev);
        if (next != null && next.left <= left && right <= next.right) return true;
        return false;
    }

    public void removeRange(int left, int right) {
        Iterator<Node> it = data.tailSet(new Node(0, left)).iterator();
        List<Node> buffer = new ArrayList<>();
        while (it.hasNext()){
            Node node = it.next();
            if (right < node.left) break;
            if (node.left < left)   buffer.add(new Node(node.left, left));
            if (right < node.right) buffer.add(new Node(right,  node.right));
            it.remove();
        }
        data.addAll(buffer);
    }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.addRange(left,right);
 * boolean param_2 = obj.queryRange(left,right);
 * obj.removeRange(left,right);
 */



tt2767
5个月前
/**
1. 怎么找递增路径? 怎么找最长的?
2. 搜索: 从起点集合中找一个点, bfs 按严格升序遍历所有情况,  返回达到的最远距离
3. 剪枝: 
    3.1 一个路径中a->b, a能到达b, 则a点能到达的最长路径必定大于b点能达到的, 所以应该把能到达的点都从起点集合中删除
*/

class Solution {

    static final int[] dx = {0, 0, 1, -1};
    static final int[] dy = {1, -1, 0, 0};

    class Node{
        int x, y;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int n = matrix.length , m = matrix[0].length;
        boolean[][] notStart = new boolean[n][m];
        Queue<Node> queue = new LinkedList<>();
        int result = 1;
        for (int i = 0;  i < n ; i ++){
            for (int j = 0; j < m ; j++){
                if (notStart[i][j]) continue;
                result = Math.max(result, bfs(i, j, matrix, queue, notStart));
            }
        }
        return result;
    }

    private int bfs(int x, int y, int[][] matrix, Queue<Node> queue, boolean[][] notStart){
        queue.clear();
        Node start = new Node(x, y);
        int n = matrix.length , m = matrix[0].length, result = 1;
        int[][] dis = new int[matrix.length][matrix[0].length];   
        queue.offer(start);
        dis[x][y] = 1;
        while (!queue.isEmpty()){
            Node node = queue.poll();
            for (int i = 0 ; i < 4 ; i++){
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                if (!(0 <= nx && nx < n && 0 <= ny && ny < m)) continue;
                if (dis[node.x][node.y] >= dis[nx][ny] && matrix[nx][ny] > matrix[node.x][node.y]){
                    dis[nx][ny] = dis[node.x][node.y] + 1;
                    result = Math.max(result, dis[nx][ny]);
                    notStart[nx][ny] = true;
                    queue.offer(new Node(nx, ny));
                }
            }
        }
        return result;
    }
}



tt2767
5个月前
/**
1. 深搜不断累加路径上的值, 当累加到叶子节点时, 合并结果
2. 搜索顺序: 不断累加路径上的值
3. 搜索状态: cur, prev_value | result
4. 剪枝: cur == null 跳出
*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        int[] result = new int[1];
        dfs(root, 0, result);
        return result[0];
    }

    public void dfs(TreeNode cur, int prev, int[] result){
        if (cur == null) return;
        int value = prev * 10 + cur.val;
        if (cur.left == null && cur.right == null) result[0] += value;
        dfs(cur.left, value, result);
        dfs(cur.right, value, result);
    }
}



tt2767
5个月前
/**
1. 将左右子树都转移到右子树上形成一条链, 关键的问题是把左子节点赋值给右子节点时, 怎么保存右子节点
2. 看一下先序遍历, 右子树应该接到左子树的最右的右儿子上
3. 注意要把左儿子置为null
*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        for (; root != null ; root = root.right){
            if (root.left == null) continue;
            TreeNode cur = root.left;
            while (cur.right != null) cur = cur.right;
            cur.right = root.right;
            root.right = root.left;
            root.left = null;
        }
    }
}