【算法】二刷lc记录2
##21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
- 思路
模拟＋归并
- 因为涉及到对头节点的操作，所以定义一个dummy,然后合并时需要知道为节点位置，再定义一个tail节点。
- 注意点 1.后面的查漏补缺只会有一个执行
code
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode tail = dummy;
ListNode a = l1;
ListNode b = l2;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
tail.next = l1;
tail = tail.next;
l1 = l1.next;
}else{
tail.next = l2;
tail = tail.next;
l2 = l2.next;
}
}
while(l1 != null){
tail.next = l1;
tail = tail.next;
l1 = l1.next;
}
while(l2 != null){
tail.next = l2;
tail = tail.next;
l2 = l2.next;
}
return dummy.next;
}
}
##25. K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
- 思路
##23. 合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
- 思路
##22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足：左括号必须以正确的顺序闭合。
- 思路
dfs
- 这里需要知道一个结论：如果一串括号是合法的，他的每个位置的前缀的左括号数量都要大于等于右括号的数量。
- 我们就可以去dfs, 左括号的添加限制只有数量小于n,而右括号的添加还需满足其数量小于等于左括号数量
code
class Solution {
List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
dfs(n,0,0,"");
return res;
}
public void dfs(int n,int l,int r,String path){
if(l == n && r == n){
res.add(path);
return;
}
if(l <= n)dfs(n,l + 1,r,path + "(");
if(r <= n && l > r)dfs(n,l,r + 1,path + ")");
}
}
##25. K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
- 思路
##26. 删除有序数组中的重复项
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
- 思路
双指针
一个k指针表示0 -> k 的元素都是不重复的，另一个指针遍历数组。
- **注意点：**第一个元素一定不重复，k直接从1开始
code
class Solution {
public int removeDuplicates(int[] nums) {
int k = 1;
for(int i = 1; i < nums.length; i ++){
if(nums[i] != nums[i - 1]){
nums[k ++] = nums[i];
}
}
return k;
}
}
##27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
- 思路
双指针
思路与上题类似。。。 code
class Solution {
public int removeElement(int[] nums, int val) {
int k = 0;
for(int i = 0; i < nums.length; i ++){
if(nums[i] != val)nums[k ++] = nums[i];
}
return k;
}
}a
##33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
- 思路
二分
1.因为在旋转有序数组之后，在分割点两边满足左边的数都大于右边的数，所以满足可以二分的条件，两边满足一些性质。 2.通过二分寻找到分割点，在通过target与nums[0]比较判断所在区间，再次二分即可。 (画画图可以更好理解)
code
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int l = 0, r = n - 1;
while(l < r){
int mid = r + l + 1 >> 1;
if(nums[mid] >= nums[0])l = mid ;
else r = mid - 1;
}
if(target >= nums[0])l = 0;
else{
l = r + 1;
r = n - 1;
}
while(l < r){
int mid = l + r >> 1;
if(nums[mid] >= target)r = mid;
else l = mid + 1;
}
// 这里写成nums[r], 当数组只有一个元素时, 两个二分查找代码都没有走, 而l在上面被+1, 这时会越界, 而r是length-1还是0, 不会产生越界
if(nums[r] != target)return -1;
return r;
}
}
##34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
` 思路
二分
根据y总的二分大法hh做即可hh code
class Solution {
public int[] searchRange(int[] nums, int target) {
int n = nums.length;
if(n == 0)return new int[]{-1,-1};
int[] res = new int[2];
int l = 0, r = n - 1;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] >= target)r = mid;
else l = mid + 1;
}
if(nums[r] != target)return new int[]{-1,-1};
res[0] = r;
l = 0;
r = n - 1;
while(l < r){
int mid = l + r + 1 >> 1;
if(nums[mid] <= target)l = mid;
else r = mid - 1;
}
res[1] = r;
return res;
}
}
##35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
- 思路
二分 从左往右看，找到第一个大于等于target的数既是所需位置
- 注意点
这里的有边界是可能取到n的。 code
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0, r = nums.length;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] >= target)r = mid;
else l = mid + 1;
}
return r
}
}
##54. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
模拟
思路：建立x y两个方向的向量(注意这里要满足顺时针的方向)，走下一步之前判断是否要变向，变向条件为
- 下一步位置越界或已经走过。 可以变4个方向，设一个方向数d,在需要变相时，因为是四个一循环，则 将其 + 1 % 4求出下一个方向
code
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int n = matrix.length;
if(n == 0)return new ArrayList<>();
int m = matrix[0].length;
List<Integer> res = new ArrayList<>();
int[] dx = {0,1,0,-1};
int[] dy = {1,0,-1,0};
boolean[][] st = new boolean[n][m];
for(int i = 0,x = 0,y = 0,d = 0; i < m * n; i ++){
st[x][y] = true;
res.add(matrix[x][y]);
int a = x + dx[d];
int b = y + dy[d];
if(a < 0 || a >= n || b < 0 || b >= m ||st[a][b]){
d = (d + 1) % 4;
a = x + dx[d];
b = y + dy[d];
}
x = a;
y = b;
}
return res;
}
}
##56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
贪心模拟
- 思路
以每个区间的第一个数排序，之后再分情况跟新答案
1.如果当前区间的最小值大于上个区间的最大值，则不合并区间。
- 反之则将两个区间合并，最小值为上个区间最小值，最大值为max(上个区间最大值，当前区间最大值)
本题可以加一个index记录区间个数
code
class Solution {
public int[][] merge(int[][] a) {
int[][] res = new int[a.length][2];
Arrays.sort(a,(x,y) ->x[0] - y[0]);
int idx = -1;
for(int[] b : a ){
if(idx == -1 || b[0] > res[idx][1]){
res[++ idx] = b;
}else{
res[idx][1] = Math.max(b[1],res[idx][1]);
}
}
return Arrays.copyOf(res,idx + 1);
}
}
##200. 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
- 思路
dfs(flood fill) or 并查集
1.遍历网格所有位置，如果该位置为1，就通过dfs把和他相连的所有为1的岛屿置为0; 2.这种dfs可以先定义四个方向数组以深度搜索
- 注意点 递归时的边界处理。 对于网格的副本处理。
华为工作强度 834人发布
