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

2000. 反转单词前缀

思路代码时空复杂度备注 48. 旋转图像

思路代码时空复杂度备注 22. 括号生成

思路代码时空复杂度备注 617. 合并二叉树

思路代码时空复杂度 160. 相交链表

思路代码时空复杂度备注 78. 子集

思路代码时空复杂度备注

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.时间复杂度 O(n)
遍历字符串
2.空间复杂度 O(n)

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

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

找规律

顺时针转90度。
- 二维矩阵 方向对角线镜像处理
- 二维矩阵 左右镜像逆时针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 
时空复杂度 
时间复杂度 O(N2)
 其中 N 是matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。空间复杂度 O(1)
 原地旋转，没有开辟新的空间。
 
备注 
arr.length 数组长度str.length() 字符串长度list.size() / set.size() 列表/集合长度
 
22. 括号生成 
https://leetcode-cn.com/problems/generate-parentheses/
 
 
思路 
找出所有可行解->回溯
 分析：
 题目可以改写为，n对括号，共2n个位置，每个位置都可以放左括号或右括号，能够生成多少种合法的组合？
 我们可以把所有情况穷举出来，去掉不合法的情况，就得到了最终结果。
 
明确下合法组合的要求：
 
有效括号组合一定是左括号数和右括号数相等对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len( p ) 都有：子串 p[0…i] 中左括号的数量都大于或等于右括号的数量。
 
代码 
class Solution {
    public List generateParenthesis(int n) {
        if(n<=0) return new ArrayList();
		//有效括号组合
		List 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 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);
    }
}
 
时空复杂度 
 
时间复杂度：
 
 递归函数本身的时间复杂度是 O(1)，递归次数主要是看「状态」的个数，对于 backtrack 函数，状态有三个，分别是 left, right, track，这三个变量的所有组合个数就是 backtrack 函数的状态个数（调用次数）。left 和 right 的组合取值就是 0 ~ n ，组合起来 n2 种; track 的长度虽然取在 0~2n，但对于每一个长度，它还有指数级的括号组合，这个是不好算的。
 有时间可以了解下「卡特兰数」相关的知识。
  
空间复杂度：O(n)
 
除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 O(1) 的空间，最多递归 2n 层，因此空间复杂度为 O(n)
 
 
备注 
str.deleteCharAt(i); 删除某位置的字符对于递归相关的算法，时间复杂度 =（递归次数）*（递归函数本身的时间复杂度）。
 
617. 合并二叉树 
https://leetcode-cn.com/problems/merge-two-binary-trees/
 
 
思路 
dfs，从根节点开始合并 -> 二叉树先序遍历。
 
代码 
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;
    }
}
 
时空复杂度 
时间复杂度 O(min(m,n))
 其中 m 和 n分别是两个二叉树的节点个数。空间复杂度 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，这样相当于「逻辑上」两条链表接在了一起。
 
代码 
方法一：
 
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        Set 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;
    }
}
 
方法二：
 
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;
    }
}
 
时空复杂度 
时间复杂度
 方法一： O(m+n)
 其中 mm 和 nn 是分别是链表headA 和headB 的长度。需要遍历两个链表各一次。
 方法二：O(m+n)
 其中 m 和 n 是分别是链表headA 和headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。空间复杂度
 方法一：O(m)
 其中 m 是链表headA 的长度。需要使用哈希集合存储链表headA 中的全部节点。
 方法二：O(1)
 
备注 
set.add(x) 插入成功返回true，失败(有重复的元素)返回false
 
78. 子集 
https://leetcode-cn.com/problems/subsets/
 
 
思路 
找出全部可行解->回溯。本质是遍历一颗回溯树。
 
 
代码 
class Solution {
    List> res=new ArrayList<>();
    public List> subsets(int[] nums) {
        //记录走过的路径
        List track = new ArrayList<>();
        backtrack(nums,0,track);
        return res;
    }
    void backtrack(int[] nums, int start, List track) {
        //注意这里不能直接add(track)，否则add到res中的是track的引用，最后会全部变成空list []
        res.add(new ArrayList(track));
        for(int i = start;i 
时空复杂度 
 
时间复杂度 O(N*2N)
 一个大小为 N 的集合的子集总共有2N个，所以说至少要对 res 添加 2N次元素,还要考虑将这些元素追加到res的效率，因为nums[i]也是数组，追加 是把 nums[i] copy 一份然后添加到数组的最后，所以一次操作的时间是 O(N)。总的时间复杂度就是 O(N*2N)。
  
空间复杂度 O(n)
 如果不计算储存返回结果所用的空间的，只需要 O(N) 的递归堆栈空间。如果计算 res 所需的空间，应该是 O(N*2N)。
 
 
备注 
res.add(new ArrayList(track));
 注意这里不能直接add(track)，否则add到res中的是track的引用，最后会全部变成空list，[]list.remove(i) 移除list某位置的元素