头像

三岁


访客:1528

离线:21天前



三岁
1个月前
class Solution {
    public int[] findNumsAppearOnce(int[] nums) {
        if (nums.length == 2) return nums;

        // 排除所有出现过两次的,只剩下A^B
        int threshold = 0;
        for (int i = 0; i < nums.length; i ++) {
            threshold ^= nums[i];
        }

        // 得到A^B,因为A、B不相同,所以A^B > 0
        // 所以对应的二进制表示,肯定有为1的一位
        // 以此作为分界,将整个数组分为两个,对应位为1的,和不为1的
        // 相同的数肯定在同一边,不同的两个数在两边
        int num = 1;
        while ((threshold & num) == 0) {
            num = num << 1;
        }

        // 对两个集合内部分别进行异或操作,最后两个集合剩下的就是结果了
        int num1 = 0;// 为0
        int num2 = 0;// 为1
        for (int i = 0; i < nums.length; i ++) {
            if ((nums[i] & num) == 0) {
                num1 ^= nums[i];
            } else {
                num2 ^= nums[i];
            }
        }

        int[] res = {num1, num2};
        return res;
    }
}


活动打卡代码 AcWing 72. 平衡二叉树

三岁
2个月前
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    boolean flag = true;
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;

        int left = dfs(root.left) + 1;
        int right = dfs(root.right) + 1;
        if (Math.abs(left - right) > 1) {
            flag = false;
        }

        return flag;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = dfs(node.left) + 1;
        int right = dfs(node.right) + 1;
        if (Math.abs(left - right) > 1) {
            flag = false;
        }

        return Math.max(left, right);
    }
}


活动打卡代码 AcWing 71. 二叉树的深度

三岁
2个月前
class Solution {

    int deep = 0;
    public int treeDepth(TreeNode root) {
        dfs(root, 0);

        return deep;
    }

    private void dfs(TreeNode node, int n) {
        if (node == null) {
            deep = Math.max(n, deep);
            return;
        }

        dfs(node.left, n + 1);
        dfs(node.right, n + 1);
    }
}



三岁
2个月前
class Solution {
    List<TreeNode> list = new ArrayList<TreeNode>();
    public TreeNode kthNode(TreeNode root, int k) {
        dfs(root);
        return list.get(k - 1);
    }

    private void dfs(TreeNode now) {
        if (now == null) return;

        if (now.left != null) {
            dfs(now.left);
        }
        list.add(now);
        if (now.right != null) {
            dfs(now.right);
        }
    }
}



三岁
2个月前
class Solution {
    public int getNumberSameAsIndex(int[] nums) {
        if (nums.length == 0) return -1;

        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (mid >= nums[mid]) l = mid;
            else r = mid - 1;
        }

        if (l != nums[l]) return -1;
        else return l;
    }
}



三岁
2个月前
class Solution {
    public int getMissingNumber(int[] nums) {
        if (nums.length == 0) return 0;

        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (mid != nums[mid]) r = mid;
            else l = mid + 1;
        }

        if (l == nums[l]) l ++;
        return l;
    }
}



三岁
2个月前
class Solution {
    public int getNumberOfK(int[] nums, int k) {
        long count = Arrays.stream(nums).filter((n) -> n == k).count();

        return (int) count;
    }
}



三岁
2个月前
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    public ListNode findFirstCommonNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        Set<ListNode> set = new HashSet<ListNode>();
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }

        while (headB != null) {
            if (!set.add(headB)) {
                return headB;
            }
            headB = headB.next;
        }


        return null;
    }
}



三岁
2个月前
class Solution {

    int res = 0;
    int[] tmp;
    public int inversePairs(int[] nums) {
        tmp = new int[nums.length];
        binarySort(nums, 0, nums.length - 1);
        // System.out.println(Arrays.toString(nums));
        return res;
    }

    private void binarySort(int[] nums, int l, int r) {
        if (l >= r) return;

        int mid = l + r >> 1;
        binarySort(nums, l, mid);
        binarySort(nums, mid + 1, r);

        int i = l, j = mid + 1, idx = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) tmp[idx ++] = nums[i ++];
            else {
                res += mid - i + 1;
                tmp[idx ++] = nums[j ++];
            }
        }
        while (i <= mid) tmp[idx ++] = nums[i ++];
        while (j <= r) tmp[idx ++] = nums[j ++];


        for (i = 0, j = l; j <= r; i ++, j ++) {
            nums[j] = tmp[i];
        }
    }
}



三岁
2个月前
class Solution {
    public char firstNotRepeatingChar(String s) {
        int[] f = new int[256];
        Arrays.fill(f, -1);

        for (int i = 0; i < s.length(); i ++) {
            int idx = s.charAt(i);
            if (f[idx] == -1) {
                f[idx] = i;
            } else {
                f[idx] = -2;
            }
        }

        char res = '#';
        int minIdx = -1;
        for (int i = 0; i < 256; i ++) {
            if (f[i] >= 0 && (minIdx < 0 || f[i] < minIdx)) {
                res = (char) i;
                minIdx = f[i];
            }
        }
        // System.out.println(Arrays.toString(f));

        return res;
    }
}