算法|一维数组

611. 有效三角形的个数

class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int result = 0;
        for (int i = n - 1; i >= 0; i--){
            int left = 0;
            int rigth = i - 1;
            while (left < rigth) {
                int sum = nums[left] + nums[rigth];
                if (sum > nums[i]) {
                    result += (rigth - left);
                    rigth--;
                } else {
                    left++;
                }
            }
        }
        return result;
    }
}

219. 存在重复元素 II

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++){
            if (hashMap.containsKey(nums[i])) {
                int j = hashMap.get(nums[i]);
                if (Math.abs(i - j) <= k) return true;
            }
            hashMap.put(nums[i], i);
        }
        return false;
    }
}

350. 两个数组的交集 II

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int num:nums1){
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }
        List<Integer> list = new ArrayList<>();
        for (int num:nums2){
            int count = hashMap.getOrDefault(num, 0);
            if (count > 0) {
                list.add(num);
                hashMap.put(num, count - 1);
            }
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < result.length; i++){
            result[i] = list.get(i);
        }
        return result;
    }
}

228. 汇总区间

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<>();
        int j = 0;
        for (int i = 1; i <= nums.length; i++){
            if (i == nums.length || nums[i] - nums[i - 1] != 1) {
                //不是子序列了
                if (nums[i - 1] == nums[j]) {
                    result.add(nums[j] + "");
                } else {
                    result.add(nums[j] + "->" + nums[i - 1]);
                }
                j = i;
            }
        }
        return result;
    }
}

324. 摆动排序 II

class Solution {
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int[] temp = Arrays.copyOf(nums, n);
        int left = (n - 1) / 2;
        int right = n - 1;
        for (int i = 0; i < n; i++){
            nums[i] = i % 2 == 0 ? temp[left--] : temp[right--];
        }
    }
}

42. 接雨水

class Solution {
    public int trap(int[] height) {
        if (height == null) return 0;
        Stack<Integer> stack = new Stack<>();
        int result = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]){
                //形成一个凹槽
                int mid = height[stack.pop()];
                if (!stack.isEmpty()) {
                    int w = i - stack.peek() - 1;
                    int h = Math.min(height[i], height[stack.peek()]) - mid;
                    result += w * h;
                }
            }
            stack.push(i);
        }
        return result;
    }
}

189. 轮转数组

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        //备份最后k个
        int[] temp = new int[k];
        int index = n - 1;
        for (int i = k - 1; i >= 0; i--){
            temp[i] = nums[index--];
        }
        //移动复制
        int start = n - 1;
        for (int i = index; i >= 0; i--) {
            nums[start--] = nums[i];
        }
        //start
        for (int i = start; i >= 0; i--){
            nums[i] = temp[i];
        }
    }
}

class Solution {
    private void rever(int[] nums, int left, int right) {
        while (left < right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        rever(nums, 0, n - 1);
        rever(nums, 0, k - 1);
        rever(nums, k, n - 1);
    }
}

457. 环形数组是否存在循环

class Solution {
    private int next(int[] nums, int i) {
        int n = nums.length;
        return ((i + nums[i]) % n + n) % n;
    }
    public boolean circularArrayLoop(int[] nums) {
        for (int i = 0; i < nums.length; i++){
            int slow = i;
            int fast = next(nums, i);
            //同一个方向
            while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[next(nums, fast)] > 0) {
                if (fast == slow) {
                    if (slow == next(nums, slow)) {
                        break;
                    } else return true;
                }
                slow = next(nums, slow);
                fast = next(nums, next(nums, fast));
            }
        }
        return false;
    }
}

31. 下一个排列

class Solution {
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    private void rever(int[] nums, int left, int right){
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        for (int i = n - 1; i >= 0; i--){
            for (int j = n - 1; j > i; j--){
               if (nums[i] < nums[j]) {
                    swap(nums, i, j);
                    rever(nums, i + 1, n - 1);
                    return;
               }
              
            }
        }
        rever(nums, 0, n - 1);
    }
}

89. 格雷编码

class Solution {
    /*
    N = 3;
    000  0
    001  1
    011  3
    010  2

    110  6
    111  7
    101  5
    100  4 
*/
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        result.add(0);
        for (int i = 1; i <= n; i++){
            int size = result.size();
            for (int j = size - 1; j >= 0; j--){
                result.add(result.get(j) | (1 << (i - 1)));
            }
        }
        return result;
    }
}

166. 分数到小数

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        long a = (long)numerator;
        long b = (long)denominator;
        //整除
        if (a % b == 0){
            return String.valueOf(a / b);
        }
        StringBuilder str = new StringBuilder();
        //符号判断
        if ((a < 0 && b > 0) || (a > 0 && b < 0)) {
            str.append('-');
        }
        //整数
        a = Math.abs(a);
        b = Math.abs(b);
        str.append(a / b);
        str.append('.');
        long yushu = a % b;
    

        StringBuilder str1 = new StringBuilder();
        HashMap<Long, Integer> hashMap = new HashMap<>();
        int index = 0;
        // System.out.println(yushu);
        while (yushu != 0 && !hashMap.containsKey(yushu)){
            hashMap.put(yushu, index);
            yushu = yushu * 10;
            // System.out.println(yushu + " " + b + " " +  (yushu / b));
            str1.append(yushu / b);
            yushu = yushu % b;
            index++;
        }
        if (yushu != 0) {
            int reIndex = hashMap.get(yushu);
            str1.insert(reIndex, '(');
            str1.append(')');
        }
        str.append(str1.toString());
        return str.toString();
    }
}

171. Excel 表列序号

class Solution {
    public int titleToNumber(String columnTitle) {
        int result = 0;
        for (int i = 0; i < columnTitle.length(); i++){
            char c = columnTitle.charAt(i);
            result = result * 26 + (c - 'A' + 1);
        }
        return result;
    }
}

231. 2 的幂

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

136. 只出现一次的数字

class Solution {
    public int singleNumber(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < nums.length; i++){
            if (hashSet.contains(nums[i])) {
                hashSet.remove(nums[i]);
            } else {
                hashSet.add(nums[i]);
            }
        }
        for (int num:hashSet){
            return num;
        }
        return -1;
    }
}

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++){
            result ^= nums[i];
        }
        return result;
    }
}

260. 只出现一次的数字 III

class Solution {
    public int[] singleNumber(int[] nums) {
        int val = 0;
        for (int i = 0; i < nums.length; i++){
            val ^= nums[i];
        }
        //找出不同位
        int div = 1;
        while ((val & div) == 0){
            div = div << 1;
        }

        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++){
            if ((div & nums[i]) == 0) {
                result[0] ^= nums[i];
            } else {
                result[1] ^= nums[i];
            }
        }
        return result;

    }
}

剑指 Offer 15. 二进制中1的个数

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int result = 0;
    
        for (int i = 0; i < 32; i++){
            if ((n & (1 << i)) != 0) result++;
        }
        return result;
    }
}

338. 比特位计数

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for (int i = 0; i <= n; i++){
            if (i % 2 == 0) {
                result[i] = result[i / 2];
            } else {
                result[i] = result[i - 1] + 1;
            }
        }
        return result;
    }
}

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for (int i = 1; i <= n; i++){
            result[i] = result[i & (i - 1)] + 1;
        }
        return result;
    }
}

389. 找不同

class Solution {
    public char findTheDifference(String s, String t) {
        int[] temp = new int[26];
        for (int i = 0; i < s.length(); i++){
            temp[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++){
            temp[t.charAt(i) - 'a']--;
            if (temp[t.charAt(i) - 'a'] < 0) return t.charAt(i);
        }
        return ' ';
    }
}

class Solution {
    public char findTheDifference(String s, String t) {
        int result = 0;
        for (int i = 0; i < t.length(); i++){
            result += t.charAt(i);
        }
        for (int i = 0; i < s.length(); i++){
            result -= s.charAt(i);
        }
        return (char)result;
    }
}

class Solution {
    public char findTheDifference(String s, String t) {
        int result = 0;
        for (int i = 0; i < s.length(); i++){
            result ^= s.charAt(i);
        }

        for (int i = 0; i < t.length(); i++) {
            result ^= t.charAt(i);
        }
        return (char)result;
    }
}

268. 丢失的数字

class Solution {
    public char findTheDifference(String s, String t) {
        int result = 0;
        for (int i = 0; i < s.length(); i++){
            result ^= s.charAt(i);
        }

        for (int i = 0; i < t.length(); i++) {
            result ^= t.charAt(i);
        }
        return (char)result;
    }
}

238. 除自身以外数组的乘积

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        result[0] = 1;
        for (int i = 1; i < nums.length; i++){
            result[i] = result[i - 1] * nums[i - 1];
        }
        int right = 1;
        for (int i = nums.length - 1; i >= 0; i--){
            result[i] = result[i] * right;
            right = right * nums[i];
        }
        return result;
    }
}

905. 按奇偶排序数组

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int left = 0;
        int rigth = n - 1;
        for (int i = 0; i < n; i++){
            if (nums[i] % 2 == 0) {
                result[left++] = nums[i];
            } else {
                result[rigth--] = nums[i];
            }
        }
        return result;
    }
}

class Solution {
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public int[] sortArrayByParity(int[] nums) {
        int n = nums.length;
        int i = 0;
        int j = n;
        while (i < j) {
            if (nums[i] % 2 == 0) i++;
            else {
                //交换
                j--;
                swap(nums, i, j);
            }
        }
        return nums;
    }
}

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right){
            while (left < right && nums[left] % 2 == 0) left++;
            while (left < right && nums[right] % 2 == 1) right--;
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }
        return nums;
    }
}

922. 按奇偶排序数组 II

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int[] result = new int[nums.length];
        int g = 1;
        int k = 0;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] % 2 == 0) {
                result[k] = nums[i];
                k += 2;
            } else {
                result[g] = nums[i];
                g += 2;
            }
        }
        return result;
    }
}

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
        int i = 0;
        int j = 1;
        while (i < n && j < n){
            while (i < n && nums[i] % 2 == 0) i += 2;
            while (j < n && nums[j] % 2 == 1) j += 2;
            if (i < n && j < n) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            } 
        } 
        return nums;
    }
}

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
        int j = 1;
        for (int i = 0; i < n; i += 2){
            if (nums[i] % 2 == 1) {
                while (j < n && (nums[j] % 2 == 1)) {
                    j += 2;
                }
                if (i < n && j < n) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        return nums;
    }
}