gitweixin
  • 首页
  • 小程序代码
    • 资讯读书
    • 工具类
    • O2O
    • 地图定位
    • 社交
    • 行业软件
    • 电商类
    • 互联网类
    • 企业类
    • UI控件
  • 大数据开发
    • Hadoop
    • Spark
    • Hbase
    • Elasticsearch
    • Kafka
    • Flink
    • 数据仓库
    • 数据挖掘
    • flume
    • Kafka
    • Hive
    • shardingsphere
    • solr
  • 开发博客
    • Android
    • php
    • python
    • 运维
    • 技术架构
    • 数据库
  • 程序员网赚
  • bug清单
  • 量化投资
  • 在线查询工具
    • 去行号
    • 在线时间戳转换工具
    • 免费图片批量修改尺寸在线工具
    • SVG转JPG在线工具

分类归档Java

精品微信小程序开发门户,代码全部亲测可用

  • 首页   /  大数据开发
  • 分类归档: "Java"
  • ( 页面2 )
Java 12月 22,2024

大厂面试手撕面试题:二分查找(亲测可用的java实现)

二分查找是一种在有序数组中查找特定元素的高效算法。其基本思路是通过逐步缩小查找范围来找到目标元素。每次将查找范围的中间元素与目标元素进行比较,根据比较结果决定继续查找左半部分还是右半部分。

二分查找的实现思路:

  1. 输入:一个有序数组 arr 和一个目标值 target。
  2. 初始化:设置两个指针,left 和 right,分别指向数组的左右两端(即 left = 0,right = arr.length - 1)。
  3. 循环查找:
    • 计算中间位置 mid = left + (right - left) / 2。
    • 如果 arr[mid] == target,则找到了目标值,返回 mid(即元素的索引)。
    • 如果 arr[mid] < target,说明目标值可能在右半部分,将 left 移动到 mid + 1。
    • 如果 arr[mid] > target,说明目标值可能在左半部分,将 right 移动到 mid - 1。
  4. 退出条件:如果 left 超过了 right,说明数组中没有目标元素,返回 -1。

时间复杂度与空间复杂度分析:

  • 时间复杂度:O(log n),每次查找将问题的规模减少一半,因此时间复杂度为对数级别。
  • 空间复杂度:O(1),使用常数空间,只需要几个额外的变量(left、right 和 mid)来存储指针,没有使用额外的空间。

Java 完整代码实现:

public class BinarySearch {

    // 二分查找函数
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        // 进行二分查找
        while (left <= right) {
            // 计算中间索引
            int mid = left + (right - left) / 2;

            // 检查中间元素是否为目标值
            if (arr[mid] == target) {
                return mid; // 找到目标,返回其索引
            }

            // 如果目标值大于中间元素,则调整搜索范围为右半部分
            if (arr[mid] < target) {
                left = mid + 1;
            }
            // 如果目标值小于中间元素,则调整搜索范围为左半部分
            else {
                right = mid - 1;
            }
        }

        // 目标值不存在于数组中,返回 -1
        return -1;
    }

    // 主函数,用于测试
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 7;
        
        // 调用二分查找方法
        int result = binarySearch(arr, target);
        
        if (result != -1) {
            System.out.println("目标元素 " + target + " 在数组中的索引是: " + result);
        } else {
            System.out.println("目标元素 " + target + " 不在数组中");
        }
    }
}

代码解释:

  • binarySearch 方法:接收一个有序整数数组 arr 和一个目标值 target。通过不断调整左右指针,最终找到目标值并返回其索引。如果没有找到目标元素,则返回 -1。
  • main 方法:用于测试 binarySearch 方法。数组 arr 是已排序的,target 是我们要查找的目标值。

样例输出:

目标元素 7 在数组中的索引是: 3
作者 east
Java 12月 22,2024

大厂面试手撕面试题:数组的全排列(亲测可用的java实现)

在面试中,关于数组的全排列问题是一个经典的考察题目,能够检验候选人的递归思维、回溯算法的理解和实现能力。

思路:

要获取一个数组的全排列,我们可以利用回溯算法。具体来说,回溯算法通过递归的方式逐步生成排列,在每一步都将一个元素加入排列中,然后在下一步递归中排除已选元素,回溯的时候撤销选择,尝试其他可能。

步骤:

  1. 递归生成排列:
    • 使用一个辅助数组来记录当前的排列。
    • 对于每个位置,我们尝试填充每一个可能的元素,并递归地填充后续的位置。
    • 使用回溯的方式,在完成一个排列后,撤回当前选择,继续尝试其他可能性。
  2. 交换元素:
    • 通过交换数组中的元素来生成排列,而不是额外使用空间存储状态。这样可以减少空间复杂度。

时间复杂度:

  • 生成全排列的时间复杂度是 O(n!),因为每个元素都需要和其他元素交换一遍,排列的总数为 n!。

空间复杂度:

  • 空间复杂度是 O(n),因为递归调用栈的深度是 n(每次递归深度为数组的长度),且我们只需要常数空间来交换数组元素。

Java 代码实现:

import java.util.ArrayList;
import java.util.List;

public class Permutations {

    // 主函数,返回所有的全排列
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, new ArrayList<>(), result, new boolean[nums.length]);
        return result;
    }

    // 回溯函数,生成排列
    private void backtrack(int[] nums, List<Integer> current, List<List<Integer>> result, boolean[] used) {
        // 当当前排列的长度等于nums的长度时,说明找到了一个全排列
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }

        // 遍历nums数组中的每个元素
        for (int i = 0; i < nums.length; i++) {
            // 如果该元素已经被使用过,则跳过
            if (used[i]) continue;

            // 做选择,标记当前元素为已使用
            used[i] = true;
            current.add(nums[i]);

            // 递归生成剩余的排列
            backtrack(nums, current, result, used);

            // 撤销选择,回溯
            used[i] = false;
            current.remove(current.size() - 1);
        }
    }

    // 测试主函数
    public static void main(String[] args) {
        Permutations solution = new Permutations();
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = solution.permute(nums);

        // 打印结果
        for (List<Integer> perm : result) {
            System.out.println(perm);
        }
    }
}

代码解析:

  1. 主函数 permute(int[] nums):
    • 该函数会返回所有的全排列。我们初始化一个空的 result 列表,并调用 backtrack 函数来生成排列。
  2. 回溯函数 backtrack(int[] nums, List<Integer> current, List<List<Integer>> result, boolean[] used):
    • current 存储当前的排列结果。
    • used 数组记录每个元素是否已经被选择过。
    • 每次递归,我们将一个没有被使用的元素添加到 current 中,并在递归完成后回溯,撤销当前选择。
  3. 时间复杂度和空间复杂度:
    • 时间复杂度:O(n!),因为要生成n个元素的所有排列,总共有n!个排列,每个排列需要O(n)的时间来生成。
    • 空间复杂度:O(n),递归调用栈深度最大为n。

测试示例:

对于输入 nums = [1, 2, 3],输出应为:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
作者 east
Java 12月 22,2024

大厂面试手撕面试题:合并两个有序数组(亲测可用的java实现)

在面试中,如果遇到要求合并两个有序数组的问题,可以通过以下步骤来实现:

思路:

  1. 双指针法:我们使用两个指针分别指向两个数组的起始位置。
  2. 比较大小:每次比较两个数组当前指针指向的元素,将较小的元素加入到结果数组中,并移动对应的指针。
  3. 处理剩余元素:当其中一个数组的所有元素都被合并到结果数组中时,另一个数组剩余的元素直接追加到结果数组中。

关键点:

  • 如果两个数组的长度分别为 n 和 m,那么合并的时间复杂度是 O(n + m),因为每个元素只会被处理一次。
  • 空间复杂度是 O(n + m),因为我们需要一个新的数组来存储结果。

时间复杂度:

  • 时间复杂度:O(n + m),其中 n 和 m 分别是两个数组的长度。我们需要遍历两个数组的每个元素一次。

空间复杂度:

  • 空间复杂度:O(n + m),因为我们需要一个新的数组来存储合并后的结果。

Java代码实现:

public class MergeSortedArrays {
    
    // 合并两个有序数组
    public static int[] merge(int[] arr1, int[] arr2) {
        // 创建一个新数组,大小为两个数组之和
        int n = arr1.length;
        int m = arr2.length;
        int[] result = new int[n + m];
        
        int i = 0, j = 0, k = 0;
        
        // 合并两个数组,直到有一个数组遍历完
        while (i < n && j < m) {
            if (arr1[i] <= arr2[j]) {
                result[k++] = arr1[i++];
            } else {
                result[k++] = arr2[j++];
            }
        }
        
        // 将剩余元素添加到结果数组中
        while (i < n) {
            result[k++] = arr1[i++];
        }
        while (j < m) {
            result[k++] = arr2[j++];
        }
        
        return result;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 7};
        int[] arr2 = {2, 4, 6, 8};
        
        int[] mergedArray = merge(arr1, arr2);
        
        // 打印合并后的数组
        System.out.print("Merged array: ");
        for (int num : mergedArray) {
            System.out.print(num + " ");
        }
    }
}

解释:

  • 我们通过 merge 方法来合并两个有序数组 arr1 和 arr2。
  • 使用三个指针 i, j, k:
    • i 用来遍历 arr1。
    • j 用来遍历 arr2。
    • k 用来填充合并结果数组 result。
  • 每次比较 arr1[i] 和 arr2[j],将较小的元素放入 result[k] 中,移动对应的指针。直到其中一个数组遍历完。
  • 剩余未遍历完的数组直接复制到结果数组的末尾。

输出:

Merged array: 1 2 3 4 5 6 7 8
作者 east
Java 12月 22,2024

大厂面试手撕面试题:求一个字符串中最长不重复子串的长度(亲测可用的java实现)

这是一个常见的面试题,要求找到字符串中最长的不重复子串的长度。我们可以使用 滑动窗口 和 哈希集合 的方法来有效地解决这个问题。

思路:

  1. 滑动窗口:我们通过维护一个窗口来追踪当前不重复的子串。窗口的左边和右边分别由两个指针表示,我们通过右指针来扩展窗口,左指针则会根据需要收缩窗口。
  2. 哈希集合:为了高效检查一个字符是否已经在当前窗口中,我们可以使用哈希集合来存储窗口中的字符。
  3. 当我们遇到重复字符时,左指针会移动到重复字符之后的位置,确保窗口内的字符不重复。

具体步骤:

  • 初始化一个空的哈希集合,用于存储当前窗口内的字符。
  • 使用两个指针:left 和 right。right 用于扩展窗口,left 用于收缩窗口。
  • 如果当前字符(s[right])不在哈希集合中,表示没有重复字符,将其加入集合,并更新最大长度。
  • 如果当前字符已经在集合中,移动 left 指针,直到窗口中的字符没有重复。
  • 每次移动 right 指针时,更新当前窗口的最大长度。

时间复杂度:

  • 时间复杂度是 O(n),其中 n 是字符串的长度。因为每个字符最多只会被访问两次(一次通过右指针,另一次通过左指针)。

空间复杂度:

  • 空间复杂度是 O(min(n, m)),其中 n 是字符串的长度,m 是字符集的大小(对于英语字符集而言,m 通常是常数 256)。

Java 代码实现:

import java.util.HashSet;

public class LongestUniqueSubstring {
    public static int lengthOfLongestSubstring(String s) {
        // 用一个哈希集合来记录当前窗口内的字符
        HashSet<Character> set = new HashSet<>();
        
        int left = 0;  // 滑动窗口的左指针
        int maxLength = 0;  // 记录最长子串的长度
        
        // 遍历字符串
        for (int right = 0; right < s.length(); right++) {
            // 当右指针指向的字符已经在集合中,收缩窗口
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left));
                left++;
            }
            // 将当前字符加入集合
            set.add(s.charAt(right));
            // 更新最大长度
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println("The length of the longest substring without repeating characters is: " 
                            + lengthOfLongestSubstring(s));  // Output: 3 ("abc")
    }
}

代码解释:

  1. set 是一个哈希集合,用来存储当前窗口中的字符。
  2. left 是滑动窗口的左指针,right 是滑动窗口的右指针。
  3. 遍历字符串时,检查当前字符 s.charAt(right) 是否已经在窗口中。如果在,就不断移动 left 指针,直到窗口内没有重复字符。
  4. 每次更新 right 指针时,计算当前窗口的长度,更新最大长度 maxLength。

示例:

对于输入 "abcabcbb":

  • 经过滑动窗口的计算,最长的不重复子串为 "abc",长度为 3。
作者 east
Java 12月 22,2024

大厂面试手撕面试题:输出 2 到 N 之间的全部素数(亲测可用的java实现)

在面试时,要求输出 2 到 N 之间的所有素数是一个经典的问题,通常会考察应聘者对算法和时间空间复杂度的理解。下面是思路的详细解释,以及 Java 代码实现。

思路

  1. 素数定义:素数是大于1的自然数,且仅能被1和自身整除。
  2. 方法选择:
    • 最直接的解法是对于每个数字 i,判断它是否为素数。这个判断过程是通过检查 i 是否能被小于等于 i 的所有整数整除来完成。显然,时间复杂度较高。
    • 更高效的方法是 埃拉托斯特尼筛法(Sieve of Eratosthenes)。该方法的思想是:从2开始,将所有2的倍数标记为非素数,然后依次处理3、4、5等,直到处理到 √N 为止。这个方法能够有效减少判断素数的次数。

时间复杂度和空间复杂度分析

  1. 埃拉托斯特尼筛法的时间复杂度:
    • 时间复杂度是 O(N log log N),这个复杂度是通过逐步标记每个合数来实现的,比暴力方法要高效得多。
  2. 空间复杂度:
    • 空间复杂度是 O(N),因为我们需要一个大小为 N 的布尔数组来存储每个数是否是素数。

Java 实现(埃拉托斯特尼筛法)

import java.util.ArrayList;
import java.util.List;

public class PrimeNumbers {

    // 埃拉托斯特尼筛法:输出2到N之间的素数
    public static List<Integer> sieveOfEratosthenes(int N) {
        // 布尔数组,true表示该数是素数,false表示该数不是素数
        boolean[] isPrime = new boolean[N + 1];
        
        // 初始时,所有数字都假设为素数
        for (int i = 2; i <= N; i++) {
            isPrime[i] = true;
        }
        
        // 从2开始,标记所有合数
        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                // 如果i是素数,将i的所有倍数标记为非素数
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // 收集所有素数
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= N; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
        
        return primes;
    }

    public static void main(String[] args) {
        int N = 50; // 可以根据需要修改N的值
        List<Integer> primes = sieveOfEratosthenes(N);
        
        // 输出素数
        System.out.println("2到" + N + "之间的素数:");
        for (int prime : primes) {
            System.out.print(prime + " ");
        }
    }
}

代码解释

  1. 布尔数组 isPrime[]:用于记录每个数字是否为素数,初始化时假设所有数字都为素数,之后逐步筛选。
  2. 筛法核心:
    • 从 i = 2 开始,如果 i 是素数,则将 i 的所有倍数标记为非素数。注意,i 的倍数可以从 i*i 开始,因为 i 的更小的倍数(例如 2*i)已经在之前的步骤中被处理过。
  3. 收集素数:遍历 isPrime[] 数组,所有值为 true 的位置对应的数字是素数,将它们加入结果列表 primes。

输出结果

如果 N = 50,输出的素数会是:

Copy Code2到50之间的素数:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
作者 east
Java 12月 22,2024

大厂面试手撕面试题:合并两个有序链表(亲测可用的java实现)

在面试中,合并两个有序链表的题目是非常常见的。这个问题的关键是利用两个链表的有序性来高效地合并它们。

思路:

  1. 初始化两个指针:
    • 一个指针指向链表A的头节点,另一个指针指向链表B的头节点。
  2. 比较两个指针所指向的节点值:
    • 比较当前两个节点的值,将较小的节点添加到新的链表中。
    • 然后,移动对应指针到下一个节点,继续比较。
  3. 处理剩余的部分:
    • 当其中一个链表的节点全部合并到新链表后,直接将另一个链表的剩余部分连接到新链表上。
  4. 返回结果:
    • 合并完成后返回新链表的头节点。

时间复杂度:

  • 每个链表的节点都需要访问一次,时间复杂度为 �(�+�)O(n+m),其中 �n 和 �m 分别是两个链表的长度。

空间复杂度:

  • 空间复杂度为 �(1)O(1),因为我们是在原地合并链表,没有使用额外的空间(除了新链表的头节点指针)。

Java代码实现:

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建一个虚拟头节点,简化处理
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        // 遍历两个链表
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        
        // 如果有一个链表还剩余节点,直接连接到合并链表的尾部
        if (l1 != null) {
            current.next = l1;
        } else if (l2 != null) {
            current.next = l2;
        }
        
        // 返回合并后的链表,跳过虚拟头节点
        return dummy.next;
    }
}

代码解析:

  1. ListNode类: 这是链表节点的定义,每个节点包含一个整数值和一个指向下一个节点的指针。
  2. mergeTwoLists方法:
    • dummy 是一个虚拟的头节点,它用于简化处理过程,最终返回合并后的链表。
    • current 用来追踪合并链表的最后一个节点。
    • 在 while 循环中,比较 l1 和 l2 的当前节点,选择较小的节点并将其加入到合并链表中。然后,继续移动指针。
    • 当一个链表结束时,直接将另一个链表剩余的部分连接到合并链表。
  3. 返回结果: 最后返回 dummy.next,这是合并后的链表的头节点。
作者 east
Java 12月 22,2024

大厂面试手撕面试题:字符串的全排列(要求去重)(java实现)

在面试中,字符串的全排列问题是一个经典的面试题,要求生成一个字符串的所有全排列,且去重。这个问题可以通过回溯法(Backtracking)来实现,同时利用一个 HashSet 来避免重复的排列。下面我会详细说明思路、时间复杂度和空间复杂度,并给出完整的 Java 代码。

1. 问题理解

给定一个字符串,要求输出该字符串的所有可能的排列(排列需要去重),并且考虑到字符串可能包含重复字符,结果中的排列也应该去重。

2. 思路分析

使用回溯法生成所有可能的排列。回溯法的核心思想是递归地交换字符,在每一层递归中交换一个字符到当前位置,并继续处理剩下的部分。为了避免重复的排列,可以在递归过程中使用一个 HashSet 来记录已经生成的排列。

步骤:

  1. 排序:首先对字符串进行排序,可以帮助我们提前跳过重复字符。例如,如果字符串是 “AAB”,排序后是 “AAB”,这样我们可以确保在递归过程中只处理一遍相同的字符。
  2. 回溯法生成排列:在递归中,每次交换一个字符到当前位置,然后递归处理剩余部分。
    • 在交换字符时,检查该字符是否已经在当前位置的前面出现过,如果出现过则跳过。
  3. 去重:为了避免重复的排列结果,我们可以使用一个 HashSet 来记录所有已生成的排列(字符串形式)。

3. 时间复杂度和空间复杂度

  • 时间复杂度:生成排列的总数是 n!,其中 n 是字符串的长度。每次递归交换的时间复杂度是 O(n),因此总体时间复杂度为 O(n * n!)。
  • 空间复杂度:空间复杂度主要由递归栈和存储结果的集合组成。递归栈的深度最大为 n,存储结果的集合最多保存 n! 个排列,因此空间复杂度为 O(n * n!)。

4. Java代码实现

import java.util.*;

public class Solution {
    public List<String> permuteUnique(String s) {
        // 用一个列表保存结果
        List<String> result = new ArrayList<>();
        // 将字符串转换为字符数组并排序,排序后有助于去重
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        
        // 结果集合,用来存储去重后的排列
        Set<String> set = new HashSet<>();
        
        // 通过回溯法生成排列
        backtrack(chars, 0, result, set);
        
        // 将集合转换为列表返回
        return new ArrayList<>(set);
    }

    private void backtrack(char[] chars, int index, List<String> result, Set<String> set) {
        // 当到达字符数组的最后一位时,生成一个排列
        if (index == chars.length) {
            String permutation = new String(chars);
            set.add(permutation);  // 将当前排列加入结果集合
            return;
        }

        // 遍历每个字符
        for (int i = index; i < chars.length; i++) {
            // 如果当前字符和前一个字符相同,跳过(避免重复排列)
            if (i > index && chars[i] == chars[i - 1]) {
                continue;
            }
            // 交换字符
            swap(chars, i, index);
            // 递归处理
            backtrack(chars, index + 1, result, set);
            // 回溯,恢复交换前的状态
            swap(chars, i, index);
        }
    }

    // 辅助函数:交换字符数组中的两个字符
    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "AAB";
        List<String> result = solution.permuteUnique(s);
        for (String str : result) {
            System.out.println(str);
        }
    }
}

5. 解释代码

  • permuteUnique 方法:首先将输入字符串转换为字符数组,并对字符数组进行排序。然后调用回溯方法 backtrack 来生成所有的排列。
  • backtrack 方法:这是回溯法的核心部分。在每一层递归中,遍历当前位置后面的所有字符,交换并递归处理。
  • swap 方法:用于交换字符数组中的两个字符。
  • 去重:通过 Set 来存储所有排列,确保没有重复的排列结果。

6. 举例说明

对于输入字符串 "AAB":

  1. 排序后得到 ['A', 'A', 'B']。
  2. 通过回溯法生成所有排列并使用 HashSet 去重,最终得到 [ "AAB", "ABA", "BAA" ]。

7. 测试

在 main 方法中,我们测试了输入 "AAB",并打印了结果。你可以替换 s 的值来测试其他输入。

8. 总结

这道题通过回溯法可以有效生成所有排列,并且通过排序和 Set 来保证去重。时间复杂度是 O(n * n!),空间复杂度是 O(n * n!),适合用来处理字符串全排列的相关问题。

作者 east
Java 12月 22,2024

大厂面试手撕面试题:单链表反转(java实现)

单链表反转是常见的面试题目之一,下面是关于如何反转一个单链表的思路、时间和空间复杂度分析以及完整的 Java 代码实现。

思路

单链表反转的关键在于改变每个节点的指向,使得原来指向下一个节点的指针指向前一个节点。为了做到这一点,我们可以通过迭代的方式来逐个调整节点的指针。

具体步骤:

  1. 初始化三个指针:
    • prev:指向前一个节点,初始化为 null。
    • curr:指向当前节点,初始化为链表的头节点。
    • next:指向当前节点的下一个节点,初始化为 null。
  2. 遍历链表:
    • 每次保存 curr 的下一个节点 (next = curr.next)。
    • 将当前节点的 next 指向 prev(反转指向)。
    • 将 prev 移动到 curr,将 curr 移动到 next,继续遍历。
  3. 完成遍历后,prev 会指向新链表的头节点。

时间复杂度

  • 时间复杂度:O(n),其中 n 是链表的长度。我们需要遍历一次整个链表。
  • 空间复杂度:O(1),我们只用了常数空间来存储指针,不需要额外的空间。

Java 完整代码实现

public class Solution {

    // 定义链表节点
    static class ListNode {
        int val;
        ListNode next;
        
        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }

    // 反转链表的函数
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;  // 初始化前一个节点为null
        ListNode curr = head;  // 当前节点从头节点开始
        
        while (curr != null) {
            ListNode next = curr.next;  // 保存下一个节点
            curr.next = prev;  // 反转当前节点的指针
            prev = curr;  // 前一个节点移动到当前节点
            curr = next;  // 当前节点移动到下一个节点
        }
        
        return prev;  // prev最终会是新的头节点
    }

    // 打印链表的辅助函数
    public static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " -> ");
            curr = curr.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        // 创建一个链表:1 -> 2 -> 3 -> 4 -> 5 -> null
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        
        // 打印原链表
        System.out.println("Original list:");
        printList(head);
        
        // 反转链表
        ListNode reversedHead = reverseList(head);
        
        // 打印反转后的链表
        System.out.println("Reversed list:");
        printList(reversedHead);
    }
}

代码解析:

  1. ListNode 类:定义了一个链表节点,每个节点包含一个整数值 val 和指向下一个节点的指针 next。
  2. reverseList 方法:用于反转链表。通过 prev、curr 和 next 三个指针来实现链表的反转。
  3. printList 方法:用于打印链表,用来测试链表是否正确反转。
  4. main 方法:在 main 方法中,创建一个示例链表,反转它并打印反转前后的链表。

测试示例:

输入链表:
1 -> 2 -> 3 -> 4 -> 5 -> null

输出链表:
5 -> 4 -> 3 -> 2 -> 1 -> null

总结:

  • 时间复杂度:O(n) —— 需要遍历一次链表。
  • 空间复杂度:O(1) —— 只使用了常量级别的额外空间。

这个问题考察了基本的链表操作和指针的使用,掌握这个技巧对于后续涉及链表的题目有很大帮助。

作者 east
Java 9月 29,2024

详解浏览器输入网址后发什么了

当你在浏览器中输入网址后,会发生以下一系列复杂的过程:
一、用户输入网址
你在浏览器地址栏中输入网址,例如 “www.example.com”。浏览器会对这个网址进行解析,判断其是否合法,并准备发起请求。
二、DNS 解析

  1. 浏览器首先检查自身的缓存,看是否有该网址对应的 IP 地址记录。如果有,则直接使用该 IP 地址进行后续步骤。
  2. 如果浏览器缓存中没有,它会查询操作系统的缓存。操作系统也会维护一份 DNS 记录缓存。
  3. 若操作系统缓存中也没有,浏览器会向本地 DNS 服务器发起查询请求。本地 DNS 服务器通常由你的互联网服务提供商(ISP)提供。
  4. 本地 DNS 服务器首先检查自身的缓存。如果找到对应的 IP 地址,就返回给浏览器。
  5. 如果本地 DNS 服务器也没有缓存该记录,它会从根域名服务器开始,逐步查询顶级域名服务器、权威域名服务器,最终获取到网址对应的 IP 地址,并将其返回给浏览器。

三、建立连接

  1. 有了目标服务器的 IP 地址后,浏览器会使用 TCP/IP 协议与服务器建立连接。这个过程首先是通过三次握手来建立 TCP 连接。
    • 第一次握手:浏览器向服务器发送一个带有 SYN 标志的数据包,表示请求建立连接。
    • 第二次握手:服务器收到请求后,返回一个带有 SYN 和 ACK 标志的数据包,表示同意建立连接。
    • 第三次握手:浏览器收到服务器的响应后,再发送一个带有 ACK 标志的数据包,确认连接建立。
  2. 连接建立后,浏览器和服务器就可以进行数据通信了。

四、发送 HTTP 请求

  1. 浏览器构建一个 HTTP 请求报文,其中包含请求方法(如 GET、POST 等)、请求头(如 User-Agent、Accept 等)和请求体(如果有)。
  2. 浏览器将这个请求报文通过已建立的 TCP 连接发送给服务器。

五、服务器处理请求

  1. 服务器接收到浏览器的请求后,根据请求的内容进行处理。
    • 如果是静态资源请求(如 HTML、CSS、JavaScript 文件等),服务器会从文件系统中读取相应的文件,并将其返回给浏览器。
    • 如果是动态请求(如 PHP、JSP、ASP.NET 等),服务器会执行相应的脚本或代码,生成动态内容,并将其返回给浏览器。
  2. 服务器在处理请求的过程中,可能会与数据库进行交互,获取所需的数据。

六、返回 HTTP 响应

  1. 服务器处理完请求后,会构建一个 HTTP 响应报文,其中包含响应状态码(如 200 OK、404 Not Found 等)、响应头(如 Content-Type、Content-Length 等)和响应体(即请求的资源内容)。
  2. 服务器将这个响应报文通过已建立的 TCP 连接发送回浏览器。

七、浏览器处理响应

  1. 浏览器接收到服务器的响应后,首先检查响应状态码。如果是 200 OK,表示请求成功,浏览器开始解析响应内容。
  2. 浏览器根据响应头中的 Content-Type 字段来确定响应内容的类型。例如,如果是 text/html,浏览器就知道这是一个 HTML 文档,并开始解析 HTML 代码。
  3. 浏览器在解析 HTML 代码的过程中,会遇到对其他资源的引用,如 CSS 文件、JavaScript 文件、图片等。浏览器会再次发起请求,获取这些资源。
  4. 当所有资源都加载完成后,浏览器会根据 HTML 代码和 CSS 样式表构建页面的布局,并执行 JavaScript 代码,实现页面的交互效果。

八、显示页面

  1. 浏览器完成页面的构建和渲染后,将页面显示在屏幕上,供你浏览。
  2. 此时,你可以与页面进行交互,如点击链接、填写表单等,浏览器会根据你的操作再次发起请求,重复上述过程。
作者 east
Java, 海豚调度器 6月 7,2024

海豚调度器调用api接口启动工作流(java版本实现)

海豚调度器调用api接口启动工作流(亲试可用),详细介绍怎样用python代码启动工作流,不过后来有的生成环境是安装在docker,不通外网,python环境不支持requests。

方案1:离线安装requests

方案2:改成用java语言现实,所有依赖包打包成jar。

import java.net.URI;
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.ResultSet;
import java.sql.Statement;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.apache.http.HttpRequest;
import org.apache.http.NameValuePair;
import org.apache.http.client.HttpClient;
import org.apache.http.client.methods.CloseableHttpResponse;
import org.apache.http.client.methods.HttpGet;
import org.apache.http.impl.client.CloseableHttpClient;
import org.apache.http.impl.client.HttpClients;
import org.apache.http.message.BasicNameValuePair;
import org.apache.http.util.EntityUtils;
import org.apache.http.HttpEntity;
import org.apache.http.client.methods.HttpPost;
import org.apache.http.client.utils.URIBuilder;
import org.json.JSONArray;
import org.json.JSONObject;

public static void startWorkflow(String token, String projectName, String processDefinitionName, String processDefinitionId, String startNode) {
        // 构建请求URL和参数
        String url = DOLPHIN_SCHEDULER_URL + "/projects/" + projectName + "/executors/start-process-instance";

        List<NameValuePair> params = new ArrayList<>();
        params.add(new BasicNameValuePair("processDefinitionName", processDefinitionName));
        params.add(new BasicNameValuePair("processDefinitionId", processDefinitionId));
        params.add(new BasicNameValuePair("failureStrategy", "CONTINUE"));
        params.add(new BasicNameValuePair("warningType", "NONE"));
        params.add(new BasicNameValuePair("warningGroupId", "0"));
        params.add(new BasicNameValuePair("scheduleTime", ""));
        params.add(new BasicNameValuePair("runMode", "RUN_MODE_SERIAL"));
        params.add(new BasicNameValuePair("processInstancePriority", "MEDIUM"));
        params.add(new BasicNameValuePair("workerGroup", "default"));
        params.add(new BasicNameValuePair("timeout", "100"));
        params.add(new BasicNameValuePair("startNodeList", startNode));
        params.add(new BasicNameValuePair("taskDependType","TASK_ONLY" ));


        CloseableHttpClient client = null;
        try {
        URI uri = new URIBuilder(url)
                .addParameters(params)
                .build();

        client = HttpClients.createDefault();
        HttpPost httpPost = new HttpPost(uri);
        httpPost.setHeader("Content-Type", "application/json");
        httpPost.setHeader("token", token);


            CloseableHttpResponse response = client.execute(httpPost);
            HttpEntity entity = response.getEntity();
            String responseString = EntityUtils.toString(entity, "UTF-8");
            if (response.getStatusLine().getStatusCode() == 200) {
                System.out.println("Workflow started successfully: " + responseString);
            } else {
                System.out.println("Failed to start workflow: " + response.getStatusLine().getStatusCode());
            }
        } catch (Exception e) {
            System.out.println("Error starting workflow: " + e.getMessage());
        } finally {
            try {
                client.close();
            } catch (Exception e) {
                System.out.println("Error closing HttpClient: " + e.getMessage());
            }
        }
    }
作者 east
Java, python 9月 7,2023

用ChatGPT自动生成流程图

我们看别人代码时,总希望有流程图,这样可以一目了然,不过自己写的代码,又不想花几个小时去画流程图。有没有更好的方法呢?

方法就是用ChatGPT等大模型自动生成流程图,并用python等语言实现自动输出流程图。

1、生成流程图的 Mermaid语法

ChatGPT提示语:

对下面的代码生成流程图,并用Mermaid语法输出 。

2、把Mermaid语法的流程图输出图片

要使用Python或Java生成Mermaid语法输出的流程图图片,您可以使用以下方法:

Python 方法:

  1. 使用 mermaid-cli 工具来将Mermaid代码转换为图片。首先,安装mmdc(mermaid-cli的执行程序)。
  2. 使用Python调用mmdc。
import os

def generate_mermaid_image(mermaid_code, output_path):
    with open("temp.mmd", "w") as file:
        file.write(mermaid_code)
    os.system(f"mmdc -i temp.mmd -o {output_path}")
    os.remove("temp.mmd")

mermaid_code = """
graph TD;
    A-->B;
    A-->C;
    B-->D;
    C-->D;
"""

generate_mermaid_image(mermaid_code, "output.png")

Java 方法:

  1. 与Python方法相同,首先安装 mermaid-cli。
  2. 使用Java的 Runtime 类来调用 mmdc。
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;

public class MermaidGenerator {

    public static void generateMermaidImage(String mermaidCode, String outputPath) throws IOException, InterruptedException {
        File tempFile = File.createTempFile("temp", ".mmd");
        try (FileWriter writer = new FileWriter(tempFile)) {
            writer.write(mermaidCode);
        }

        Process process = Runtime.getRuntime().exec("mmdc -i " + tempFile.getAbsolutePath() + " -o " + outputPath);
        process.waitFor();

        tempFile.delete();
    }

    public static void main(String[] args) throws IOException, InterruptedException {
        String mermaidCode = """
            graph TD;
                A-->B;
                A-->C;
                B-->D;
                C-->D;
            """;
        generateMermaidImage(mermaidCode, "output.png");
    }
}

请注意,这两种方法都需要您在计算机上安装并配置mermaid-cli。此外,这两种方法都是使用临时文件来存储Mermaid代码,并在转换后删除它。这是为了简化调用mmdc的过程,但您可以根据需要进行调整。

作者 east
doris, Java 8月 29,2023

如何用druid连接池连接doris

在对doris进行单元测试,要测试大量sql,没有连接池时,太多连接会出现问题。于是想采用druid连接池。

要使用Druid连接池连接Doris,你需要在Java代码中进行配置。以下是一个简单的示例,包含Druid连接池的配置和连接到Doris的Java代码。

首先,你需要在项目的依赖中添加Druid和Doris的驱动程序。在Maven项目中,可以在pom.xml文件中添加以下依赖:

<dependencies>
    <!-- Druid -->
    <dependency>
        <groupId>com.alibaba</groupId>
        <artifactId>druid</artifactId>
        <version>1.2.4</version>
    </dependency>

    <!-- Doris JDBC Driver -->
    <dependency>
        <groupId>com.mysql.jdbc</groupId>
        <artifactId>mysql-connector-java</artifactId>
        <version>8.0.23</version>
    </dependency>
</dependencies>

接下来,创建一个名为DruidDorisExample的Java类,并编写以下代码:

import com.alibaba.druid.pool.DruidDataSource;

import java.sql.Connection;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.Statement;

public class DruidDorisExample {
    public static void main(String[] args) {
        // 创建Druid连接池
        DruidDataSource dataSource = new DruidDataSource();
        dataSource.setUrl("jdbc:mysql://localhost:9030/my_database");
        dataSource.setUsername("username");
        dataSource.setPassword("password");

        try (Connection connection = dataSource.getConnection()) {
            // 执行查询语句
            Statement statement = connection.createStatement();
            ResultSet resultSet = statement.executeQuery("SELECT * FROM my_table");

            // 遍历结果集并输出数据
            while (resultSet.next()) {
                // 处理每一行的数据
                // 例如:String columnValue = resultSet.getString("column_name");
            }
        } catch (SQLException e) {
            e.printStackTrace();
        }
    }
}

在上面的代码中,你需要将jdbc:mysql://localhost:9030/my_database替换为Doris的连接信息,以及正确的用户名和密码。

此外,你还可以通过在代码中设置其他Druid连接池的配置来优化连接性能。例如,你可以设置最大连接数、是否开启预处理语句缓存等。

要进行更详细的Druid连接池和Doris配置,你需要创建一个名为druid.properties的配置文件,并在main()方法中加载它:

import com.alibaba.druid.pool.DruidDataSourceFactory;

import javax.sql.DataSource;
import java.io.IOException;
import java.io.InputStream;
import java.sql.Connection;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.Statement;
import java.util.Properties;

public class DruidDorisExample {
    public static void main(String[] args) throws IOException {
        Properties properties = new Properties();
        try (InputStream inputStream = DruidDorisExample.class.getClassLoader().getResourceAsStream("druid.properties")) {
            properties.load(inputStream);
        }

        try {
            DataSource dataSource = DruidDataSourceFactory.createDataSource(properties);
            Connection connection = dataSource.getConnection();

            // 执行查询语句...
            
            connection.close();
        } catch (SQLException e) {
            e.printStackTrace();
        }
    }
}
java复制代码import com.alibaba.druid.pool.DruidDataSourceFactory;

import javax.sql.DataSource;
import java.io.IOException;
import java.io.InputStream;
import java.sql.Connection;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.Statement;
import java.util.Properties;

public class DruidDorisExample {
    public static void main(String[] args) throws IOException {
        Properties properties = new Properties();
        try (InputStream inputStream = DruidDorisExample.class.getClassLoader().getResourceAsStream("druid.properties")) {
            properties.load(inputStream);
        }

        try {
            DataSource dataSource = DruidDataSourceFactory.createDataSource(properties);
            Connection connection = dataSource.getConnection();

            // 执行查询语句...
            
            connection.close();
        } catch (SQLException e) {
            e.printStackTrace();
        }
    }
}

上述代码会从类路径下加载名为druid.properties的配置文件,该文件包含了Druid连接池的详细配置项。你可以根据需要在配置文件中设置相关属性,例如连接URL、用户名、密码、最大连接数等。配置文件的示例:

# Druid连接池配置
driverClassName=com.mysql.jdbc.Driver
url=jdbc:mysql://localhost:9030/my_database
username=username
password=password

# 连接池配置
initialSize=5
maxActive=20
minIdle=1
maxWait=60000

请确保druid.properties文件与Java代码在同一个目录下或处于类路径中。

以上是连接到Doris的简单示例代码和配置文件。你可以根据自己的需求进行进一步调整和优化。

我自己实践时,参考网上别的配置文件,后来发现还是连接不上,而且一直在运行, 通过排查代码,参考
Druid连接池关键代码解读 ,发现是下面的配置影响了:

#测试SQL  
validationQuery=select 1 from test
原来这个表test并不存在,所以测试不通过,又没有明显报错。
作者 east

上一 1 2 3 … 6 下一个

关注公众号“大模型全栈程序员”回复“小程序”获取1000个小程序打包源码。回复”chatgpt”获取免注册可用chatgpt。回复“大数据”获取多本大数据电子书

标签

AIGC AI创作 bert chatgpt github GPT-3 gpt3 GTP-3 hive mysql O2O tensorflow UI控件 不含后台 交流 共享经济 出行 图像 地图定位 外卖 多媒体 娱乐 小程序 布局 带后台完整项目 开源项目 搜索 支付 效率 教育 日历 机器学习 深度学习 物流 用户系统 电商 画图 画布(canvas) 社交 签到 联网 读书 资讯 阅读 预订

官方QQ群

小程序开发群:74052405

大数据开发群: 952493060

近期文章

  • 详解Python当中的pip常用命令
  • AUTOSAR如何在多个供应商交付的配置中避免ARXML不兼容?
  • C++thread pool(线程池)设计应关注哪些扩展性问题?
  • 各类MCAL(Microcontroller Abstraction Layer)如何与AUTOSAR工具链解耦?
  • 如何设计AUTOSAR中的“域控制器”以支持未来扩展?
  • C++ 中避免悬挂引用的企业策略有哪些?
  • 嵌入式电机:如何在低速和高负载状态下保持FOC(Field-Oriented Control)算法的电流控制稳定?
  • C++如何在插件式架构中使用反射实现模块隔离?
  • C++如何追踪内存泄漏(valgrind/ASan等)并定位到业务代码?
  • C++大型系统中如何组织头文件和依赖树?

文章归档

  • 2025年6月
  • 2025年5月
  • 2025年4月
  • 2025年3月
  • 2025年2月
  • 2025年1月
  • 2024年12月
  • 2024年11月
  • 2024年10月
  • 2024年9月
  • 2024年8月
  • 2024年7月
  • 2024年6月
  • 2024年5月
  • 2024年4月
  • 2024年3月
  • 2023年11月
  • 2023年10月
  • 2023年9月
  • 2023年8月
  • 2023年7月
  • 2023年6月
  • 2023年5月
  • 2023年4月
  • 2023年3月
  • 2023年1月
  • 2022年11月
  • 2022年10月
  • 2022年9月
  • 2022年8月
  • 2022年7月
  • 2022年6月
  • 2022年5月
  • 2022年4月
  • 2022年3月
  • 2022年2月
  • 2022年1月
  • 2021年12月
  • 2021年11月
  • 2021年9月
  • 2021年8月
  • 2021年7月
  • 2021年6月
  • 2021年5月
  • 2021年4月
  • 2021年3月
  • 2021年2月
  • 2021年1月
  • 2020年12月
  • 2020年11月
  • 2020年10月
  • 2020年9月
  • 2020年8月
  • 2020年7月
  • 2020年6月
  • 2020年5月
  • 2020年4月
  • 2020年3月
  • 2020年2月
  • 2020年1月
  • 2019年7月
  • 2019年6月
  • 2019年5月
  • 2019年4月
  • 2019年3月
  • 2019年2月
  • 2019年1月
  • 2018年12月
  • 2018年7月
  • 2018年6月

分类目录

  • Android (73)
  • bug清单 (79)
  • C++ (34)
  • Fuchsia (15)
  • php (4)
  • python (43)
  • sklearn (1)
  • 云计算 (20)
  • 人工智能 (61)
    • chatgpt (21)
      • 提示词 (6)
    • Keras (1)
    • Tensorflow (3)
    • 大模型 (1)
    • 智能体 (4)
    • 深度学习 (14)
  • 储能 (44)
  • 前端 (4)
  • 大数据开发 (488)
    • CDH (6)
    • datax (4)
    • doris (30)
    • Elasticsearch (15)
    • Flink (78)
    • flume (7)
    • Hadoop (19)
    • Hbase (23)
    • Hive (40)
    • Impala (2)
    • Java (71)
    • Kafka (10)
    • neo4j (5)
    • shardingsphere (6)
    • solr (5)
    • Spark (99)
    • spring (11)
    • 数据仓库 (9)
    • 数据挖掘 (7)
    • 海豚调度器 (10)
    • 运维 (34)
      • Docker (3)
  • 小游戏代码 (1)
  • 小程序代码 (139)
    • O2O (16)
    • UI控件 (5)
    • 互联网类 (23)
    • 企业类 (6)
    • 地图定位 (9)
    • 多媒体 (6)
    • 工具类 (25)
    • 电商类 (22)
    • 社交 (7)
    • 行业软件 (7)
    • 资讯读书 (11)
  • 嵌入式 (70)
    • autosar (63)
    • RTOS (1)
    • 总线 (1)
  • 开发博客 (16)
    • Harmony (9)
  • 技术架构 (6)
  • 数据库 (32)
    • mongodb (1)
    • mysql (13)
    • pgsql (2)
    • redis (1)
    • tdengine (4)
  • 未分类 (6)
  • 程序员网赚 (20)
    • 广告联盟 (3)
    • 私域流量 (5)
    • 自媒体 (5)
  • 量化投资 (4)
  • 面试 (14)

功能

  • 登录
  • 文章RSS
  • 评论RSS
  • WordPress.org

All Rights Reserved by Gitweixin.本站收集网友上传代码, 如有侵犯版权,请发邮件联系yiyuyos@gmail.com删除.