Hexo

Posted 2022-04-16Updated 2022-04-16LeetCode / Medium / 复习2 minutes read (About 315 words)

34. Find First and Last Position in Sorted Array

问题
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

二分搜索，搜索中间项。
中间项等于左侧和右侧指针的中点，根据搜索左侧边界和右侧边界选择二分向下舍去或是二分向上补足。
当中间项小于目标，则更新左侧边界。
若中间项大于目标，则更新右侧边界。
当中间项等于目标时，根据搜索左侧边界还是右侧边界选择更新左侧或右侧。
由于有可能有重复元素存在，因此需要继续二分搜索下去，直到右侧边界大于左侧边界。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{searchLeft(nums,target),searchRight(nums,target)};
    } 

    private int searchRight(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int result = -1;
        
        while(left <= right){
            mid = (right-left)/2+left;
            if(nums[mid] < target){
                left = mid+1;
            }
            else if(nums[mid] > target){
                right = mid-1;
            }
            else{
                result = mid;
                left = mid+1;
            }
        }
        return result;
    }
    
    private int searchLeft(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int result = -1;
        
        while(left <= right){
            mid = (right-left+1)/2+left;
            if(nums[mid] < target){
                left = mid+1;
            }
            else if(nums[mid] > target){
                right = mid-1;
            }
            else{
                result = mid;
                right = mid-1;
            }
        }
        return result;
    }
}

Posted 2022-04-16Updated 2022-04-16LeetCode / Easy / 复习2 minutes read (About 311 words)

190. Reverse Bits

问题
Reverse bits of a given 32 bits unsigned integer.

Note:

Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.

In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

创建返回值ans。
每次向左移动一位ans，然后取n的尾数进行二进制或运算（相当于在尾部进行不进位的加和）。
然后将n向左移动一位。

二进制下的或运算只保留两数间较大的位。(0011 | 0110 = 0111)
二进制下的与运算只保留两数间皆为1的位。(0011 & 0110 = 0010)
掩码（Mask）是在二进制下进行与运算。以1作为掩码时，前面的31为皆为0，因此进行与运算后只保留最后一位。

因此(n & 1)相当于n的二进制与000…001运算，只保留n的尾数。
然后(ans << 1)向左移动一位，用 | 操作将n的尾数加入ans。

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int ans = 0;
        for(int i = 0; i < 32; i++){
            ans = (ans << 1) | (n & 1);
            n >>= 1;
        }
        return ans;
    }
}

Posted 2022-04-16Updated 2022-04-16LeetCode / Easy4 minutes read (About 526 words)

169. Majority Element

问题
Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Boyer-Moore投票算法
基本思想：
众数的值为+1，非众数的值为-1。其加和作为投票值。
遍历整个数组，由于众数数量大于非众数，因此最后结果一定为正数。

设置count记录票数，遍历数组。
当count为0时，则将当前的数组设为众数。当之后的数字与其相等，则count+1，反之则-1。
遍历完成后返回当前的众数。

根据以上规则，每次我们选择的众数，都是已遍历数组范围内出现最多次数的数值之一。
由于给定的数组的众数超过半数，因此遍历到最后的众数，一定是整个数组中出现最多次的数值。

核心就是对拼消耗。
玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。

那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。

最后能剩下的必定是自己人。

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int major = 0;
        
        for(int num : nums){
            if(count == 0){
                major = num;
            }
            if(major == num){
                count++;
            }
            else{
                count--;
            }
        }
        return major;
    }
}

遍历数组，并将各个数值出现的次数记录在哈希表中。
当出现的次数大于数组的一半，则该数值是众数。

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            map.put(num, map.getOrDefault(num,0)+1);
            if(map.get(num) > nums.length/2){
                return num;
            }
        }
        return -1;
    }
}

Posted 2022-04-16Updated 2022-04-16LeetCode / Easy / 复习a minute read (About 154 words)

136. Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

位运算，对所有数值做二进制异或运算。
两个同样的值异或运算会等于0，最后和与单独的数字相等。

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int num : nums){
            ans = ans ^ num;
        }
        return ans;
    }
}

排序，然后遍历数组，如果第i个值不等于第i+1个则返回。

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0; i < nums.length-1; i+=2){
            if(nums[i] != nums[i+1]){
                return nums[i];
            }
        }
        return nums[nums.length-1];
    }
}

Posted 2022-04-16Updated 2022-04-16LeetCode / Easya minute read (About 197 words)

653. Two Sum IV - Input is a BST

问题
Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

DFS搜索，每次递归时检查HashSet中是否有当前节点的值。如没有则将目标值减去当前节点的值加入HashSet。如有则返回true。
递归左侧节点和右侧节点，并返回二者的或运算。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    HashSet<Integer> set;
    public boolean findTarget(TreeNode root, int k) {
        set = new HashSet();
        return dfs(root,k);
    }
    
    private boolean dfs(TreeNode root, int k){
        if(root == null){
            return false;
        }
        if(set.contains(root.val)){
            return true;
        }
        set.add(k - root.val);

        return dfs(root.left,k) || dfs(root.right,k);
    }
}

Recents

Archives

Links