letcode算法题集锦

描述

示例

解题思路

遍历所有城市&＃xff0c;对于每个城市&＃xff0c;如果该城市尚未被访问过&＃xff0c;则从该城市开始深度优先搜索&＃xff0c;通过矩阵 isConnected 得到与该城市直接相连的城市有哪些&＃xff0c;这些城市和该城市属于同一个连通分量&＃xff0c;然后对这些城市继续深度优先搜索&＃xff0c;直到同一个连通分量的所有城市都被访问到&＃xff0c;即可得到一个省份。遍历完全部城市以后&＃xff0c;即可得到连通分量的总数&＃xff0c;即省份的总数

代码

class Solution {public int findCircleNum(int[][] isConnected) {//城市数量int length&＃61;isConnected.length;//表示哪个城市被访问过boolean[]visited&＃61;new boolean[length];//开始都为0&＃xff0c;falseint count&＃61;0;//省份数量for(int i&＃61;0;i}
day04 JZ25 合并两个排序的链表

描述

输入两个递增的链表&＃xff0c;单个链表的长度为n&＃xff0c;合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围&＃xff1a; 0≤ n ≤ 1000&＃xff0c;-1000 ≤节点值 ≤1000
要求&＃xff1a;空间复杂度 O(1)O(1)&＃xff0c;时间复杂度 O(n)O(n)

示例1

输入&＃xff1a;{1,3,5},{2,4,6}

复制返回值&＃xff1a;{1,2,3,4,5,6}

思路

方法一&＃xff1a;迭代版本求解

初始化&＃xff1a;定义cur指向新链表的头结点
操作&＃xff1a;

1. 如果l1指向的结点值小于等于l2指向的结点值&＃xff0c;则将l1指向的结点值链接到cur的next指针&＃xff0c;然后l1指向下一个结点值
2. 否则&＃xff0c;让l2指向下一个结点值
3. 循环步骤1,2&＃xff0c;直到l1或者l2为nullptr
4. 将l1或者l2剩下的部分链接到cur的后面

代码&＃xff1a;

class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2){ListNode *vhead &＃61; new ListNode(-1);ListNode *cur &＃61; vhead;while (pHead1 && pHead2) {if (pHead1->val <&＃61; pHead2->val) {cur->next &＃61; pHead1;pHead1 &＃61; pHead1->next;}else {cur->next &＃61; pHead2;pHead2 &＃61; pHead2->next;}cur &＃61; cur->next;}cur->next &＃61; pHead1 ? pHead1 : pHead2;return vhead->next;}
};t;

方法二&＃xff1a;递归版本

写递归代码&＃xff0c;最重要的要明白递归函数的功能。可以不必关心递归函数的具体实现。
比如这个ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
函数功能&＃xff1a;合并两个单链表&＃xff0c;返回两个单链表头结点值小的那个节点。

如果知道了这个函数功能&＃xff0c;那么接下来需要考虑2个问题&＃xff1a;

1. 递归函数结束的条件是什么&＃xff1f;
2. 递归函数一定是缩小递归区间的&＃xff0c;那么下一步的递归区间是什么&＃xff1f;
   对于问题1.对于链表就是&＃xff0c;如果为空&＃xff0c;返回什么
   对于问题2&＃xff0c;跟迭代方法中的一样&＃xff0c;如果PHead1的所指节点值小于等于pHead2所指的结点值&＃xff0c;那么phead1后续节点和pHead节点继续递归

代码&＃xff1a;

class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2){if (!pHead1) return pHead2;if (!pHead2) return pHead1;if (pHead1->val <&＃61; pHead2->val) {pHead1->next &＃61; Merge(pHead1->next, pHead2);return pHead1;}else {pHead2->next &＃61; Merge(pHead1, pHead2->next);return pHead2;}}
};

方法三&＃xff1a;非递归

代码&＃xff1a;

public class Solution {public ListNode Merge(ListNode list1, ListNode list2) {if (list1 &＃61;&＃61; null) { // 特判return list2;} else if (list2 &＃61;&＃61; null) {return list1;}ListNode list &＃61; null; // 使list1指向头结点为最小值的链表&＃xff0c;list1也是最终要返回的链表if (list1.val > list2.val) {list &＃61; list1;list1 &＃61; list2;list2 &＃61; list;}list &＃61; list1;while (list1.next !&＃61; null && list2 !&＃61; null) { // list1.next!&＃61;null 很巧妙&＃xff0c;而不是list1!&＃61;null if (list1.next.val <&＃61; list2.val) {list1 &＃61; list1.next;} else {// 图解12345ListNode nex &＃61; list1.next; // 1list1.next &＃61; list2; // 2list2 &＃61; list2.next; // 3list1 &＃61; list1.next; // 4list1.next &＃61; nex; // 5}}if (list2 !&＃61; null) { // 最后只关心list2不为空list1.next &＃61; list2;}return list;}
}

day 4 只出现一次的数字

给定一个非空整数数组&＃xff0c;除了某个元素只出现一次以外&＃xff0c;其余每个元素均出现两次。找出那个只出现了一次的元素。

说明&＃xff1a;你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗&＃xff1f;

示例 1: 输入:  [2,2,1]  输出: 1

思路&＃xff1a;

方法1&＃xff0c;通过双层for循环&＃43;计数器&＃xff0c;得到count为初始值的数&＃xff0c;返回对应的数值

方法2&＃xff1a;使用Set集合存储&＃xff0c;Set集合不存储重复值&＃xff0c;add()方法返回值为boolean类型&＃xff0c;这一特点可以利用。当要添加的数与集合中已存在的数重复时&＃xff0c;不会再进行添加操作&＃xff0c;返回false&＃xff0c;这时再进行remove操作&＃xff0c;将集合中已存在的那个与要添加的数相同的元素移除

代码实例&＃xff1a;

方法1&＃xff1a;

public static Integer Find_Num_1(int[] arr){for(int i &＃61; 0; i

方法2&＃xff1a;

public static Integer Find_Num_2(int[] arr) {Set set &＃61; new HashSet();//创建Set集合for(int i : arr) {//增强for循环遍历数组if(!set.add(i))//添加不成功返回false&＃xff0c;前加上&＃xff01;运算符变为trueset.remove(i);//移除集合中与这个要添加的数重复的元素}if(set.size() &＃61;&＃61; 0) return null;//如果Set集合长度为0&＃xff0c;返回null表示没找到return set.toArray(new Integer[set.size()])[0];}


day 5 加一 

给定一个由 整数 组成的 非空 数组所表示的非负整数&＃xff0c;在该数的基础上加一。

最高位数字存放在数组的首位&＃xff0c; 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外&＃xff0c;这个整数不会以零开头。

题解&＃xff1a;

• 如果数组中的所有元素都是9&＃xff0c;类似9999&＃xff0c;加1之后肯定会变为10000&＃xff0c;也就是数组长度会增加1位。
• 如果数组的元素只要有一个不是9&＃xff0c;加1之后直接返回即可

代码&＃xff1a;

class Solution {public int[] plusOne(int[] digits) {int length &＃61; digits.length;for(int i &＃61;length-1;i>&＃61;0;i--){if(digits[i] !&＃61; 9){digits[i]&＃43;&＃43;;return digits;}else{digits[i] &＃61;0;}}int temp[] &＃61; new int [length &＃43;1];temp[0] &＃61; 1;return temp; }
}

移动零

给定一个数组 nums&＃xff0c;编写一个函数将所有 0 移动到数组的末尾&＃xff0c;同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

1. 必须在原数组上操作&＃xff0c;不能拷贝额外的数组。
2. 尽量减少操作次数。

代码&＃xff1a;

class Solution {public void moveZeroes(int[] nums) {if(nums &＃61;&＃61; null || nums.length &＃61;&＃61; 0)return;int index &＃61; 0;for(int i &＃61;0;i}