头像

Lunaticf


访客:1977

离线:4个月前



Lunaticf
7个月前

当长度奇数时,没问题

当链表长度为偶数时,如何定位中间的前一个还是后一个,两种写法

定位中间左边的节点

while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

定位右边的只要改一下

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}


活动打卡代码 AcWing 23. 矩阵中的路径

Lunaticf
9个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
    public boolean hasPath(char[][] matrix, String str) {
        int n = matrix.length;
        if (n == 0) {
            return false;
        }
        int m = matrix[0].length;
        if (m == 0) {
            return false;
        }


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (dfs(matrix, str, 0,  i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] matrix, String str, int u, int i, int j) {
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length || matrix[i][j] == '*' || u >= str.length()) {
            return false;
        }


        if (u == str.length() - 1 && str.charAt(u) == matrix[i][j]) {
            return true;
        } 

        if (str.charAt(u) != matrix[i][j]) {
            return false;
        }

        char c = matrix[i][j];

        matrix[i][j] = '*';

        boolean res1 = dfs(matrix, str, u+1, i + 1, j);


        boolean res2 = dfs(matrix, str, u+1,i, j + 1);


        boolean res3 = dfs(matrix, str, u+1, i - 1, j);


        boolean res4 = dfs(matrix, str, u+1,  i, j - 1);

         matrix[i][j] = c;




        return res1 || res2 || res3 || res4;
    }
}



Lunaticf
9个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode father;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode p) {
        // 找出中序遍历下一个节点 注意节点是有father的
        // 左根右
        // 分情况讨论 
        // 1. 节点的左孩子必然不用看了 节点如果有右孩子 直接就到右孩子的最左节点
        // 2. 节点没有右孩子 1. 如果节点是父亲的左孩子 那么答案就是父亲 2. 如果节点是父亲的右孩子 那需要一路向上找到相应的节点
        // 那么这两种情况实际是可以合并的 往上找到一个不是右孩子的节点即可

        // 如果有右孩子
        if (p.right != null) {
            p = p.right;
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }

        // 如果没有右孩子
        // 如果节点是左孩子
        while (p.father != null && p == p.father.right) {
            p = p.father;
        }
        return p.father;

    }
}



Lunaticf
9个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {

    public int[] printListReversingly(ListNode head) {
        // 可以用栈 N N
        // 先求长度把

        ListNode p = head;
        int count = 0;
        while (p != null) {
            p = p.next;
            count++;
        }


        int[] res = new int[count];
        int idx = res.length - 1;

        p = head;
        while (p != null) {
            res[idx--] = p.val;
            p = p.next;
        }

        return res;
    }
}


活动打卡代码 AcWing 16. 替换空格

Lunaticf
9个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
    public String replaceSpaces(StringBuffer str) {
        StringBuilder s = new StringBuilder();
        for (int i =0; i < str.length(); i++) {
            if (str.charAt(i) != ' ') {
                s.append(str.charAt(i));
            } else {
                s.append("%20");
            }
        }
        return s.toString();
    }
}



Lunaticf
9个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
    public boolean searchArray(int[][] array, int target) {
        // 这题没得说 从右上角来找
        int m = array.length;

        if (m == 0) {
            return false;
        }
        int n = array[0].length;

        int x = 0, y = n - 1;

        while (x >= 0 && x < m && y >= 0 && y < n) {
            if (array[x][y] == target) {
                return true;
            } else if (array[x][y] > target) {
                y--;
            } else {
                x++;
            }
        }

        return false;
    }
}



Lunaticf
9个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
    public int duplicateInArray(int[] nums) {
        // 问题是不能修改数组
        // 二分这题竟然是 那只能靠背了 这题并不是对索引做二分 还是对数的值做二分

        int i = 1, j = nums.length - 1;
        while (i < j) {
            int mid = (i + j) >>> 1;
            // 扫描整个数组 
            int res = 0;
            for (int num : nums) {
                if (num <= mid && num >= i) {
                    res++;
                }
            }

            if (res > mid - i + 1) {
                // 那说明左边肯定有重复的数字
                j = mid;
            } else {
                i = mid + 1;
            }

        }

        return j;
    }
}



Lunaticf
9个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
    public int duplicateInArray(int[] nums) {
        // [2, 3, 5, 4, 3, 2, 6, 7]
        //  0  1  2  3  4  5  6  7
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] < 0 || nums[i] >= n) {
                return -1;
            }
        }

        for (int i = 0; i < n; i++) {
            // 如果当前数不在正确的位置
            if (nums[i] != i) {
                // 尽力调换到正确的位置
                while (nums[i] != i) {

                    // 如果该位置已有正确的数
                    if (nums[i] == nums[nums[i]]) {
                        return nums[i];
                    }

                    swap(nums, i, nums[i]);
                }
            }

        }

        return -1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}



Lunaticf
9个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {

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

    // 这题很明显是BFS
    public int movingCount(int threshold, int rows, int cols)
    {
        LinkedList<Point> queue = new LinkedList<>();
        boolean[][] visited = new boolean[rows][cols];

        if (threshold == 0) {
            return 1;
        }

        if (rows ==  0 && cols == 0) {
            return 0;
        }

        queue.offer(new Point(0, 0));
        int res = 0;

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


        // 不为空的时候
        while (!queue.isEmpty()) {
            Point p = queue.poll();

            if (!visited[p.x][p.y]) {
                res++;
                visited[p.x][p.y] = true;
            } else {
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int cx = p.x + dx[i];
                int cy = p.y + dy[i];
                if (cx >=0 && cx < rows && cy >= 0 && cy < cols && cal(cx, cy) <= threshold) {
                    queue.offer(new Point(cx, cy));
                }
            }
        }
        return res;
    }

    private int cal(int x, int y) {
        int res = 0;
        while (x != 0) {
            res += (x%10);
            x/=10;
        }

        while (y != 0) {
            res += (y%10);
            y/=10;
        }

        return res;
    }
}



Lunaticf
9个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
class Solution {
    public double Power(double base, int exponent) {
        // O(n)固然不行 所以就是logn 快速幂把
        if (exponent  < 0) {
            return 1/recur(base, -exponent);
        }
        return recur(base, exponent);
    }

    public double recur(double base, int exponent) {
        // 10的100次方其实等于10^50*10^50
        if (exponent == 0) {
            return 1;
        } 

        if (exponent % 2 == 1) {
            return recur(base,  exponent/2) * recur(base,  exponent/2) * base;
        } else {
            return recur(base,  exponent/2) * recur(base,  exponent/2);
        }

    }
}