✨前言
美好的一天从刷算法开始。
文章目录
一、合并两个有序数组
题目描述
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
思路详解
1.直接合并后排序
直接把nums2合并到nums1中，再进行排序。
2.双指针
通过方法一看出并没有很好的利用nums1和nums2已经排序的条件，思路二则很好的利用了这个条件
首先定义p1和p2用来指示nums1和nums2的当前数值，通过判断把小的放入到sorted数组，若其中一个数组已经结束，另一个数组中的继续放入到sorted数组中，最后循环赋值。
代码及结果
思路1
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { for (int i = 0; i != n; ++i) { nums1[m + i] = nums2[i]; } Arrays.sort(nums1); } }
思路2
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int p1 = 0, p2 = 0; int[] sorted = new int[m + n]; int temp; while (p1 < m || p2 < n) { if (p1 == m) { temp = nums2[p2];//nums1数组结束，nums2继续加入到sorted数组 p2++; } else if (p2 == n) { temp = nums1[p1];//nums2数组结束了，nums1继续加入到sorted数组 p1++; } else if (nums1[p1] < nums2[p2]) { temp = nums1[p1];//判断两者较小的加入到数组 p1++; } else { temp = nums2[p2];//判断两者较小的加入数组 p2++; } sorted[p1 + p2 - 1] = temp; } for (int i = 0; i != m + n; ++i) {//循环赋值 nums1[i] = sorted[i]; } } }
二、环形链表
题目描述
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
思路详解
1.哈希表
利用简单的方法就是，所有的节点全部遍历一遍，遍历过的存入到set visted的集合中（可以自动判断重复），如果添加不成功则表示已经添加过了即有环，返回true，否则全部循环结束返回false
2.快慢指针
这个思路就比较有意思了，采用「Floyd 判圈算法」（又称龟兔赛跑算法）。
假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。
具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，快慢指针都在位置 head，这样的话只能使用do-while循环，因为判断条件就是慢指针与快指针相等。如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
代码及结果
思路1
public class Solution { public boolean hasCycle(ListNode head) { Set<ListNode> visted = new HashSet<ListNode>(); while (head != null) { if (!visted.add(head)) { return true; } head = head.next; } return false; } }
1- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
思路2
public class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head; do{ if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; }while (slow != fast); return true; } }
三、三数之和
题目描述
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
思路详解
首先想到的就是直接三重循环，然后去重，但是这样处理下来，时间复杂度显然已经超过O(N3),虽然三重循环思路是对的，但是依旧需要改进。
那么首先对数组进行排序，这样就避免了最后去重的一步，因为遍历的时候是有顺序的，那么同时也要保证两次相邻的循环取到的数值也不能相同。例如：【0，1，2，2，2，3】，如果第三层循环第一次取2，那么下一次取到的还是2，那么结果就会产生重复，要避免这种情况。
继续改进，我们注意到这三个数是存在巨大关系的，当a的值确定之后，b和c的关系就比较强烈了，b增大，那么c肯定减小，基于这样的关系，使c从大到小循环，来和b对应。这样第三重循环变成一个从数组最右端开始向左移动的指针。
还有一些细节，直接上代码，注释清晰。
代码及结果
class Solution { public List<List<Integer>> threeSum(int[] nums) { int n = nums.length; Arrays.sort(nums); List<List<Integer>> ans = new ArrayList<List<Integer>>(); // 枚举 a for (int first = 0; first < n; ++first) { // 需要和上一次枚举的数不相同 if (first > 0 && nums[first] == nums[first - 1]) { continue; } // c 对应的指针初始指向数组的最右端 int third = n - 1; int target = -nums[first]; // 枚举 b for (int second = first + 1; second < n; ++second) { // 需要和上一次枚举的数不相同 if (second > first + 1 && nums[second] == nums[second - 1]) { continue; } // 需要保证 b 的指针在 c 的指针的左侧 while (second < third && nums[second] + nums[third] > target) { --third; } // 如果指针重合，随着 b 后续的增加 // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环 if (second == third) { break; } if (nums[second] + nums[third] == target) { List<Integer> list = new ArrayList<Integer>(); list.add(nums[first]); list.add(nums[second]); list.add(nums[third]); ans.add(list); } } } return ans; } }
四、Z mod X = C
题目描述
给你三个整数a,b,c，请你找出三个整数x,y,z。使得满足x%y=a，y%z=b，z%x=a。可以保证一定存在答案。
思路详解
这个题的思路有点考察数学了，
通过题目得知，
x/y=n…a,
y/z=m…b,
z/x=l…c.
这里m,n,l可以是任意值，这里为了方便都取1。等式就变成了
z=c,y=b+z,x=a+y
代码及结果
#include<iostream> using namespace std; int main() { int n, a, b, c; int x , y , z; cin >> n; while(n --) { cin >> a >> b >> c; z = c; y = b + z; x = a + y; cout << x << " "<< y << " " << z << endl; } return 0; }
✨总结
今天的四道算法题，成功一直是留给努力的人的，一起加油！！！
每天几个小时的算法真的很提自己的逻辑思维，坚持就是胜利，梦想一直在！！！
😎The man who fears losing has already lost.
怕输的人已经输了。 - 《权力的游戏》😎
