三只松鼠的网站建设的意义,深圳移动网站建设公,仓库网站开发,汕头模版网站建设环形链表排列硬币合并两个有序数组#xff08;没错#xff0c;出现过一次的LeetCode合并数组又双叒叕出现了#xff01;#xff09;经典算法题java解法 目录1 环形链表题目描述解题思路与代码解法一#xff1a;哈希表解法二#xff1a;双指针2 排列硬币题目描述解题思路与… 环形链表排列硬币合并两个有序数组没错出现过一次的LeetCode合并数组又双叒叕出现了经典算法题java解法 目录1 环形链表题目描述解题思路与代码解法一哈希表解法二双指针2 排列硬币题目描述解题思路与代码解法一迭代解法二二分查找解法三牛顿迭代3 合并两个有序数组题目描述解题思路与代码解法一合并后排序解法二双指针解法三双指针优化1 环形链表
题目描述
给定一个链表判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达该节点则链表中存在环
如果链表中存在环则返回 true 。 否则返回 false 。
解题思路与代码
解法一哈希表 public static boolean hasCycle(ListNode head) {SetListNode seen new HashSetListNode();while (head ! null) {if (!seen.add(head)) {return true;}head head.next;}return false;}解法二双指针 public static boolean hasCycle2(ListNode head) {if (head null || head.next null) {return false;}ListNode slow head;ListNode fast head.next;while (slow ! fast) {if (fast null || fast.next null) {return false;}slow slow.next;fast fast.next.next;}return true;}2 排列硬币
题目描述
总共有 n 枚硬币将它们摆成一个阶梯形状第 k 行就必须正好有 k 枚硬币。 给定一个数字 n找出可形成完整阶梯行的总行数。 n 是一个非负整数并且在32位有符号整型的范围内
解题思路与代码
解法一迭代
从第一行开始排列排完一列、计算剩余硬币数排第二列直至剩余硬币数小于或等于行数 public static int arrangeCoins(int n) {for(int i1; in; i){n n-i;if (n i){return i;}}return 0;}解法二二分查找
假设能排 n 行计算 n 行需要多少硬币数如果大于 n则排 n/2行再计算硬币数和 n 的大小关系 public static int arrangeCoins2(int n) {int low 0, high n;while (low high) {long mid (high - low) / 2 low;long cost ((mid 1) * mid) / 2;if (cost n) {return (int)mid;} else if (cost n) {high (int)mid - 1;} else {low (int)mid 1;}}return high;}解法三牛顿迭代
使用牛顿迭代求平方根(x n/x)/2
假设能排 x 行 则 1 2 3 … x n即 x(x1)/2 n 推导出 x 2n - x public static double sqrts(double x,int n){double res (x (2*n-x) / x) / 2;if (res x) {return x;} else {return sqrts(res,n);}}3 合并两个有序数组
题目描述
两个有序整数数组 nums1 和 nums2将 nums2 合并到 nums1 中使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。假设 nums1 的空间大小等于 m n这样它就
有足够的空间保存来自 nums2 的元素。
解题思路与代码
解法一合并后排序 public void merge(int[] nums1, int m, int[] nums2, int n) {System.arraycopy(nums2, 0, nums1, m, n);Arrays.sort(nums1);}时间复杂度 : O((nm)log(nm))。空间复杂度 : O(1)。
解法二双指针
从前往后
将两个数组按顺序进行比较放入新的数组 public void merge(int[] nums1, int m, int[] nums2, int n) {int [] nums1_copy new int[m];System.arraycopy(nums1, 0, nums1_copy, 0, m);//拷贝数组1int p1 0;//指向数组1的拷贝int p2 0;//指向数组2int p 0;//指向数组1//将数组1当成空数组比较数组1的拷贝和数组2将较小的放入空数组while ((p1 m) (p2 n))nums1[p] (nums1_copy[p1] nums2[p2]) ? nums1_copy[p1] :nums2[p2];//数组2和数组1不等长将多出的元素拷贝if (p1 m)System.arraycopy(nums1_copy, p1, nums1, p1 p2, m n - p1 - p2);if (p2 n)System.arraycopy(nums2, p2, nums1, p1 p2, m n - p1 - p2);}时间复杂度 : O(n m)。 空间复杂度 : O(m)。
解法三双指针优化
从后往前 public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 m - 1;int p2 n - 1;int p m n - 1;while ((p1 0) (p2 0))nums1[p--] (nums1[p1] nums2[p2]) ? nums2[p2--] : nums1[p1--];System.arraycopy(nums2, 0, nums1, 0, p2 1);}时间复杂度 : O(n m)。空间复杂度 : O(1)。
