当前位置：首页 > article >正文

Java实现经典算法题之模拟双指针用法

article 2025/1/26 15:49:58

1、移动零

在这里插入图片描述

package wdzt.test.utils;

import com.alibaba.fastjson2.JSON;

public class AlgorithmTest {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 3, 12}; // 定义并初始化一个整型数组
        solution(nums);//移动零算法
    }

    private static void solution(int[] nums) {
        // 1、下标初始化
        int dest = -1, cur = 0;
        // 2、数组划分
        while (cur < nums.length) {
            if (nums[cur] != 0) {
                swap(nums, ++dest, cur++);//java中没有应用和指针，没有swap方法
            } else {
                ++cur;
            }
        }
        System.out.println("最终数组的结果：" + JSON.toJSONString(nums));
    }

    //交换位置方法
    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

运行结果：

在这里插入图片描述
代码分析：

在这里插入图片描述

思路就是使用两个指针，一个记录需要交换的位置，一个记录数值是否非零，如果非零，则进行位置替换，在交换前加1，进行位置替换，为零的话，则记录数字继续往后判断，直到非零后又继续替换位置。

2、复写零

在这里插入图片描述

package wdzt.test.utils;

import com.alibaba.fastjson2.JSON;

public class AlgorithmTest {
    public static void main(String[] args) {
        int[] nums = {1, 0, 2, 3, 0, 4, 5, 0}; // 定义并初始化一个整型数组
        duplicateZeros(nums);//复写零算法
    }

    private static void duplicateZeros(int[] nums) {
        // 1、初始化
        int dest = -1, cur = 0, n = nums.length;
        // 2、找到最后一个复写的数
        while (true) {
            if (nums[cur] != 0) {
                dest += 1;
            } else {
                dest += 2;
            }
            if (dest >= n - 1) {
                break;
            }
            ++cur;
        }
//        cout << nums[cur] << endl;
        // 1.5、预处理 -> 让 dest 的下标有效
        if (dest == n) {
            if (nums[cur] != 0) {
                --cur;
                --dest;
            } else {
                nums[n - 1] = 0;
                dest -= 2;
                cur -= 1;
            }
        }
        // 2、双指针从后往前进行复写操作
        while (cur >= 0) {
            if (nums[cur] != 0) {
                nums[dest--] = nums[cur--];
            } else {
                nums[dest--] = 0;
                nums[dest--] = 0;
                cur--;
            }
        }
        System.out.println("最终数组的结果：" + JSON.toJSONString(nums));
    }
}

运行结果：
在这里插入图片描述
代码分析：

找到最后一个复写数，dest记录遇0复写后满数组的位置，cur记录的是当dest满数组了，不复写0的数值位置，也就是5，从5开始再往前进行复写0的操作是刚刚好把数组写满。

在这里插入图片描述

从第5的位置开始复写，非零则把第5的位置值换到dest第7的位置上，如果是0则把当前位置前两个都写成0，然后cur–往前走一个，直到判断完，以此类推，非零则替换位置到后面，是0则替换位置前两个都写成0即可。

3、快乐数

在这里插入图片描述

package wdzt.test.utils;

import com.alibaba.fastjson2.JSON;

public class AlgorithmTest {
    public static void main(String[] args) {
        int nums = 19; // 定义并初始化一个整型
        boolean happy = isHappy(nums);//快乐数算法
        System.out.println(nums + "是否为快乐数：" + happy);
    }

    private static boolean isHappy(int n) {
        int slow = n, fast = BitSum(n);
        while (slow != fast) {
            slow = BitSum(slow);
            fast = BitSum(BitSum(fast));
        }
        return slow == 1;
    }

    private static int BitSum(int n) {
        int ret = 0;
        while (n > 0) {
            int t = n % 10;
            ret += t * t;
            n /= 10;
        }
        return ret;
    }
}