题目12
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
限制：
1 <= target <= 10^5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution
{
public int[][] findContinuousSequence(int target)
{
List<int[]> list = new ArrayList<>();
int[][] ans1 = new int[1][1];
ans1[0][0] = 0;
if(target < 3) return ans1;
int[][] ans2 = new int[1][2];
ans2[0][0] = 1;
ans2[0][1] = 2;
if(target == 3) return ans2;
for(int i = 2;i <= (target/2 + 1);i++)
{
for(int j = 1;j < i;j++)
{
int[] arr = new int[i-j+1];
if( (j+i)*(i-j+1)/2 == target )
{
for(int p = 0;p < i-j+1;p++)
arr[p] = p+j;
list.add(arr);
}
}
}
int[][] ans = new int[list.size()][];
return list.toArray(ans);
}
}
//brute force，超出时间限制
//外循环从2开始，内循环从1开始，把所有的可能遍历
class Solution
{
public int[][] findContinuousSequence(int target)
{
List<int[]> list = new ArrayList<>();
int low = 1;
int high = 2;
int sum = low + high;
while(low < high && high <= target/2+1)
{
if(sum < target)
{
high++;
sum = sum + high;
}
else if(sum > target)
{
sum = sum - low;
low++;
}
else
{
int[] arr = new int[high-low+1];
for(int i = 0;i < high-low+1;i++)
{
arr[i] = i+low;
}
list.add(arr);
sum = sum - low;
low++;
}
}
int[][] ans = new int[list.size()][];
return list.toArray(ans);
}
}
使用双指针的方式进行求解。low指针代表窗口左边，起始值为1；high指针代表窗口右边，起始值为2。当窗口中的值加起来小于target时，说明连续数列需要更大的数字，则把high指针向右移动，并加上移动后的指针；如果sum值大于了target的值，则说明需要将low指针向右移动。
题目13
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution
{
public List<Integer> inorderTraversal(TreeNode root)
{
List<Integer> ans = new ArrayList<Integer>();
if(root != null) inorder(root,ans);
return ans;
}
public void inorder(TreeNode root,List<Integer> ans)
{
if(root.left != null) inorder(root.left,ans);
ans.add(root.val);
if(root.right != null) inorder(root.right,ans);
}
}
class Solution
{
List<Integer> list = new ArrayList<Integer>();
public List<Integer> inorderTraversal(TreeNode root)
{
TreeNode myTree = root;
Stack<TreeNode> temp = new Stack<>();
while(myTree != null || !temp.empty())
{
while(myTree != null)
{
temp.push(myTree);
myTree = myTree.left;
}
if(!temp.empty())
{
myTree = temp.pop();
list.add(myTree.val);
myTree = myTree.right;
}
}
return list;
}
}
题目14
给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
示例:
输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution
{
public List<TreeNode> generateTrees(int n)
{
List<TreeNode> list = new ArrayList<>();
if(n == 0)
{
//list.add(null);
return list;//为0则直接返回空
}
return getTree(1,n);
}
private List<TreeNode> getTree(int start, int end)
{
List<TreeNode> ans = new ArrayList<TreeNode>();
if(start > end) //如果左值大于右值，则返回空
{
ans.add(null);
return ans;
}
if(start == end)
{
TreeNode tree = new TreeNode(start);
ans.add(tree); //如果左右相等，则返回该值
return ans;
}
for(int i = start;i <= end;i++)//遍历每一个start与end之间的值
{
List<TreeNode> lefttrees = getTree(start, i-1);
List<TreeNode> righttrees = getTree(i+1, end);
for(TreeNode lefttree : lefttrees)
{
for(TreeNode righttree : righttrees)
{
TreeNode root = new TreeNode(i);
root.left = lefttree;
root.right = righttree;
ans.add(root);
}
}
}
return ans;
}
}
题目15
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public int numTrees(int n)
{
long C = 1;
for (int i = 0; i < n; ++i)
{
C = C * 2 * (2 * i + 1) / (i + 2);
}
return (int) C;
}
}
题目16
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
class Solution
{
public int maxDepth(TreeNode root)
{
int depth = 0;
if(root != null)
{
int ldepth = maxDepth(root.left);
int rdepth = maxDepth(root.right);
depth = ldepth > rdepth ? ldepth+1: rdepth+1;
}
return depth;
}
}
题目17
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution
{
public boolean isValid(String s)
{
Stack<Character> stack = new Stack<>();
char[] chars = s.toCharArray();
for(char myChar : chars)
{
if(stack.size() == 0) stack.push(myChar);
else if (isSymmetric(stack.peek(),myChar)) stack.pop();
else stack.push(myChar);
}
return stack.size() == 0;
}
private boolean isSymmetric(char c1, char c2)
{
return (c1 == '(' && c2 == ')' || c1 == '[' && c2 == ']' || c1 == '{' && c2 == '}');
}
}
