力扣每日练习-java版（一）_力扣练习

2000. 反转单词前缀

https://leetcode-cn.com/problems/reverse-prefix-of-word/

思路

1.找字符所在位置，没找到返回原字符串，否则进行第二步
2.反转0 ~ i位置的字符串，拼接上i+1 ~ n-1 位置的字符串，返回

代码

class Solution {
	public String demo(String word,char ch){
		int pos = word.indexOf(ch);
        if (pos < 0) return word;
		return new StringBuilder(word.substring(0,pos+1)).reverse().append(word.substring(pos+1)).toString();
	}
}
1
2
3
4
5
6
7

时空复杂度

1.时间复杂度 O(n)
遍历字符串
2.空间复杂度 O(n)

备注

1. str.charAt(i) 获取字符串str第i个位置上的字符，i从0开始
2. str.substring(a,b) 截取a ~ b位置的字符串 [a,b)
3. str.substring(a) 截取a位置之后的所有字符串（包括a位置）
4. new StringBuilder(str).reverse() 反转字符串
5. new StringBuilder(str).append(str2) 在当前字符串后追加字符串
6. new StringBuilder(str).toString() StringBuilder转String类型
7. char[] chars = str.toCharArray(); 字符串转字符数组

48. 旋转图像

https://leetcode-cn.com/problems/rotate-image/

思路

找规律

1. 顺时针转90度。
   - 二维矩阵 \ 方向对角线镜像处理
   - 二维矩阵 左右镜像
2. 逆时针90度。
   - 二维矩阵 / 方向对角线镜像处理
   - 二维矩阵 左右镜像

代码

class Solution {
    public void rotate(int[][] matrix) {
    //矩阵大小
		int n = matrix.length;
		// 先沿对角线镜像对称二维矩阵
		for(int i = 0;i < n;i++) {
			for(int j = i;j< n;j++) {
				if(j!=i){
					int tmp = matrix[i][j];
					matrix[i][j] = matrix[j][i];
					matrix[j][i] = tmp;
				}
			}
		}
		// 然后反转二维矩阵的每一行（左右镜像对称）
		for(int i = 0;i<n;i++){
			int j = 0,k = n-1;
			while(j<k){
				int tmp = matrix[i][j];
				matrix[i][j] = matrix[i][k];
				matrix[i][k] = tmp;
				j++;
				k--;
			}
		}
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

时空复杂度

1. 时间复杂度 O(N²)
   其中 N 是matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。
2. 空间复杂度 O(1)
   原地旋转，没有开辟新的空间。

备注

1. arr.length 数组长度
2. str.length() 字符串长度
3. list.size() / set.size() 列表/集合长度

22. 括号生成

https://leetcode-cn.com/problems/generate-parentheses/

思路

找出所有可行解->回溯
分析：
题目可以改写为，n对括号，共2n个位置，每个位置都可以放左括号或右括号，能够生成多少种合法的组合？
我们可以把所有情况穷举出来，去掉不合法的情况，就得到了最终结果。

明确下合法组合的要求：

1. 有效括号组合一定是左括号数和右括号数相等
2. 对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len( p ) 都有：子串 p[0…i] 中左括号的数量都大于或等于右括号的数量。

代码

class Solution {
    public List<String> generateParenthesis(int n) {
        if(n<=0) return new ArrayList<String>();
		//有效括号组合
		List<String> ans = new ArrayList<>();
		//每次回溯过程的路径
		StringBuilder track = new StringBuilder();
		//left剩下可用左括号的数量，right可用右括号数量，都初始化为n
		backtrack(n, n, track, ans);
		return ans;
    }

    public void backtrack(int left, int right, StringBuilder track, List<String> ans) {
        //如果左括号剩下的多，或数量小于0，不合法
        if(left>right || left <0 || right < 0) return;
        //所有括号都恰好用完，得到一个合法的括号组合
        if(left==0 && right==0) {
            ans.add(track.toString());
            return;
        }
        //否则，继续往下遍历
        //尝试放一个左括号
        track.append("(");
        backtrack(left-1,right,track,ans);
        track.deleteCharAt(track.length()-1);
        //尝试放一个右括号
        track.append(")");
        backtrack(left,right-1,track,ans);
        track.deleteCharAt(track.length()-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

时空复杂度

1. 时间复杂度：
   
   递归函数本身的时间复杂度是 O(1)，递归次数主要是看「状态」的个数，对于 backtrack 函数，状态有三个，分别是 left, right, track，这三个变量的所有组合个数就是 backtrack 函数的状态个数（调用次数）。left 和 right 的组合取值就是 0 ~ n ，组合起来 n² 种; track 的长度虽然取在 0~2n，但对于每一个长度，它还有指数级的括号组合，这个是不好算的。
   有时间可以了解下「卡特兰数」相关的知识。

2. 空间复杂度：O(n)

   除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 O(1) 的空间，最多递归 2n 层，因此空间复杂度为 O(n)

备注

1. str.deleteCharAt(i); 删除某位置的字符
2. 对于递归相关的算法，时间复杂度 =（递归次数）*（递归函数本身的时间复杂度）。

617. 合并二叉树

https://leetcode-cn.com/problems/merge-two-binary-trees/

思路

dfs，从根节点开始合并 -> 二叉树先序遍历。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        //两个节点都为null，返回null
		if(root1==null && root2==null) return null;
		//一个节点为null，另一个节点非空，直接合并为非空的节点
		if(root1==null) return root2;
		if(root2==null) return root1;
		//都不为空，合并数值
		TreeNode newNode = new TreeNode(root1.val+root2.val);
		newNode.left = mergeTrees(root1.left,root2.left);
		newNode.right = mergeTrees(root1.right,root2.right);
		return newNode;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

时空复杂度

1. 时间复杂度 O(min(m,n))
   其中 m 和 n分别是两个二叉树的节点个数。
2. 空间复杂度 O(min(m,n))
   递归栈的深度

160. 相交链表

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

思路

方法一：暴力解法，将链表A的节点装入set，再将链表B的节点依次存入set，如果有相交节点，就返回
方法二：双指针，将空间复杂度降为O(1)
这个方法关键在于怎么能让 p1 和 p2 能够同时到达相交节点 c1。
如果用两个指针 p1 和 p2 分别在两条链表上前进，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。

代码

方法一：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        Set<ListNode> set = new HashSet<>();
        ListNode tmpA = headA;
        while(tmpA != null) {
            set.add(tmpA);
            tmpA = tmpA.next;
        }
        ListNode tmpB = headB;
        while(tmpB != null) {
            if(!set.add(tmpB)){
                return tmpB;
            }
            tmpB = tmpB.next;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

方法二：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

时空复杂度

1. 时间复杂度
   方法一： O(m+n)
   其中 mm 和 nn 是分别是链表headA 和headB 的长度。需要遍历两个链表各一次。
   方法二：O(m+n)
   其中 m 和 n 是分别是链表headA 和headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。
2. 空间复杂度
   方法一：O(m)
   其中 m 是链表headA 的长度。需要使用哈希集合存储链表headA 中的全部节点。
   方法二：O(1)

备注

1. set.add(x) 插入成功返回true，失败(有重复的元素)返回false

78. 子集

https://leetcode-cn.com/problems/subsets/

思路

找出全部可行解->回溯。本质是遍历一颗回溯树。

代码

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        //记录走过的路径
        List<Integer> track = new ArrayList<>();
        backtrack(nums,0,track);
        return res;
    }
    void backtrack(int[] nums, int start, List<Integer> track) {
        //注意这里不能直接add(track)，否则add到res中的是track的引用，最后会全部变成空list []
        res.add(new ArrayList(track));
        for(int i = start;i<nums.length;i++){
            //做选择
            track.add(nums[i]);
            //回溯
            backtrack(nums,i+1,track);
            //撤销选择
            track.remove(track.size() - 1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时空复杂度

1. 时间复杂度 O(N*2^N)
   一个大小为 N 的集合的子集总共有2^N个，所以说至少要对 res 添加 2^N次元素,还要考虑将这些元素追加到res的效率，因为nums[i]也是数组，追加 是把 nums[i] copy 一份然后添加到数组的最后，所以一次操作的时间是 O(N)。总的时间复杂度就是 O(N*2^N)。

2. 空间复杂度 O(n)
   如果不计算储存返回结果所用的空间的，只需要 O(N) 的递归堆栈空间。如果计算 res 所需的空间，应该是 O(N*2^N)。

备注

1. res.add(new ArrayList(track));
   注意这里不能直接add(track)，否则add到res中的是track的引用，最后会全部变成空list，[]
2. list.remove(i) 移除list某位置的元素