美文网首页
算法|一维数组

算法|一维数组

作者: 激扬飞雪 | 来源:发表于2023-01-31 09:45 被阅读0次

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;
    }
}

相关文章

  • PHP常用数组排序算法

    title: PHP常用数组排序算法tags: [PHP,数组,排序,算法] 这几天写到的代码中，用到了许多对数组...

  • LeetCode基础算法-数组

    LeetCode基础算法-数组 算法 LeetCode 数组相关 1. 从排序数组中删除重复项 描述：给定一个排序...

  • 整数二分查找原理及代码模板

    1.整数二分算法原理 ps：数组具有单调性，则一定可以使用整数二分算法；但是，能够使用整数二分算法的数组，数组未必...

  • Hash算法

    数据结构与算法分析：大纲数据结构：数组算法：hash算法算法：排序算法Java实现 1 Hash算法？ 将任意长度...

  • （2）数组相关算法题目

    数组是最简单的数据结构，占据连续内存并且按顺序存储。 以下是与数组有关的算法题目。 （1）查询数组中重复数字 算法...

  • 算法-数组

    数组(array)是一种线性表数据结构.它用一组连续的内存空间,来储存一组具有相同类型的数据. 数组随机访问的实现...

  • 数组算法

    1、数组中不重复的数只有一个，并找出 思路 ：初始化一个值 int a = 0; 遍历数组每个 item^a ;最...

  • 算法：数组

    简介 2019年新学期起，决定开始Leetcode刷题，并在博客总结记录。 内容 292 Nim游戏这其实是一个B...

  • 数组算法

    优点： 读取速度快。 缺点： 插入删除元素慢。 事先需要知道数据长度。 需要大块连续的内存块。

  • iOS面试之算法大全

    算法 算法内容如下: 字符串反转 链表反转 有序数组合并 Hash算法 查找两个子视图的共同父视图 求无序数组当中...

网友评论

      本文标题：算法|一维数组

      本文链接：https://www.haomeiwen.com/subject/xyqehdtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|算法|一维数组|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！