移除元素
class Solution {
public int removeElement(int[] nums, int val) {
int slow=0;
int fast=0;
for(fast=0;fast
反转字符串
class Solution {
public void reverseString(char[] s) {
for(int left=0,right=s.length-1;left<=right;left++,right--)
{
char temp=s[left];
s[left]=s[right];
s[right]=temp;
}
}
}
替换空格
class Solution {
public String replaceSpace(String s) {
if(s==null) return null;
StringBuilder sb=new StringBuilder();
for(int i=0;i
反转字符串里的单词
class Solution {
public String reverseWords(String s) {
StringBuilder sb=removeSpace(s);
reverse(sb,0,sb.length()-1);
reverseEach(sb);
return sb.toString();
}
public StringBuilder removeSpace(String s)
{
int left=0;
int right=s.length()-1;
while(s.charAt(left)==' ') left++;
while(s.charAt(right)==' ') right--;
StringBuilder sb=new StringBuilder();
while(left<=right)
{
char c=s.charAt(left);
if(c!=' '||sb.charAt(sb.length()-1)!=' ')
{
sb.append(c);
}
left++;
}
return sb;
}
public void reverse(StringBuilder sb,int left,int right)
{
while(left<=right){
char temp=sb.charAt(left);
sb.setCharAt(left,sb.charAt(right));
sb.setCharAt(right,temp);
left++;
right--;
}
}
public void reverseEach(StringBuilder sb)
{
int start=0;
int end=1;
while(start
反转链表
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null) return null;
ListNode pre=null;
ListNode cur=head;
ListNode temp=null;
while(cur!=null)
{
temp=cur.next;
cur.next=pre;
pre=cur;
cur=temp;
}
return pre;
}
}
删除链表倒数第n个节点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head==null) return null;
ListNode dummyNode=new ListNode(0);
dummyNode.next=head;
ListNode slow=dummyNode;
ListNode fast=dummyNode;
for(int i=0;i
链表相交
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode l1=headA;
ListNode l2=headB;
while(l1!=l2)
{
l1=l1==null?headB:l1.next;
l2=l2==null?headA:l2.next;
}
return l1;
}
//假设相交（相交点8->8）：headA（1->2->3->8->8）： 3+2；headB（7->6->8->8）: 2+2。则 h1走3+2+2+2 = 9步（每一步访问：1->2->3->8->8->7->6->8->8）; h2走2+2+2+3 = 9步（每一步访问：7->6->8->8->1->2->3->8->8）。 看最后两步。 不相交最终满足 h1 == h2 == null
}
环形链表
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null) return null;
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null)
{
slow=slow.next;
fast=fast.next.next;
if(slow==fast)
{
ListNode x=head;
ListNode y=slow;
while(x!=y)
{
x=x.next;
y=y.next;
}
return x;
}
}
return null;
}
}
有效的括号
class Solution {
public boolean isValid(String s) {
char[] m=s.toCharArray();
Stack stack=new Stack<>();
for(int i=0;i
删除字符串相邻重复项
class Solution {
public String removeDuplicates(String s) {
//Stack m=new Stack<>();
char[] m=s.toCharArray();
Stack stack=new Stack<>();
for(int i=0;i
逆波兰表达式求值
class Solution {
public int evalRPN(String[] tokens) {
int n=tokens.length;
Stack stack=new Stack<>();
for(int i=0;i
滑动窗口最大值
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque queue=new ArrayDeque<>();
int n=nums.length;
int[] res=new int[n-k+1];
int idx=0;
for(int i=0;i=k-1)
{
res[idx++]=nums[queue.peek()];
}
}
return res;
}
}
前k个高频元素（Stream流）
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
return map.entrySet()
.stream()
.sorted((m1, m2) -> m2.getValue() - m1.getValue())
.limit(k)
.mapToInt(Map.Entry::getKey)
.toArray();
}
}
二叉树层次遍历
class Solution {
public List> levelOrder(TreeNode root) {
List> sum=new LinkedList<>();
if(root==null) return sum;
Queue queue=new LinkedList<>();
queue.add(root);
while(!queue.isEmpty())
{
int t=queue.size();
List x=new LinkedList<>();
TreeNode temp;
for(int i=0;i
二叉树锯齿形遍历
class Solution {
public List> zigzagLevelOrder(TreeNode root) {
List> sum=new LinkedList<>();
if(root==null) return sum;
Queue queue=new LinkedList<>();
queue.add(root);
int k=1;
while(!queue.isEmpty())
{
int t=queue.size();
TreeNode temp;
List x=new LinkedList<>();
for(int i=0;i
二叉树的层序遍历Ⅱ
class Solution {
public List> levelOrderBottom(TreeNode root) {
List> sum=new LinkedList<>();
if(root==null) return sum;
Queue queue=new LinkedList<>();
queue.add(root);
while(!queue.isEmpty())
{
int t=queue.size();
TreeNode temp;
List x=new LinkedList<>();
for(int i=0;i
二叉树最大深度
class Solution {
public int maxDepth(TreeNode root) {
if(root==null) return 0;
int y=Math.max(maxDepth(root.left),maxDepth(root.right));
return y+1;
}
}
前序中序构造二叉树
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder==null||inorder==null||preorder.length!=inorder.length||preorder.length<1)
{
return null;
}
TreeNode root=construct(inorder,0,inorder.length-1,preorder,0,preorder.length-1);
return root;
}
public TreeNode construct(int[] inorder,int is,int ie,int[] preorder,int ps,int pe)
{
if(is>ie||ps>pe)
{
return null;
}
int curroot=preorder[ps];
int index=is;
while(is<=ie&&curroot!=inorder[index])
{
index++;
}
TreeNode root=new TreeNode(curroot);
root.left=construct(inorder,is,index-1,preorder,ps+1,ps+index-is);
root.right=construct(inorder,index+1,ie,preorder,ps+index-is+1,pe);
return root;
}
}
中序后序构造二叉树
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return construct(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
}
public TreeNode construct(int[] inorder,int is,int ie,int[] postorder,int ps,int pe)
{
if(is>ie||ps>pe)
{
return null;
}
int curroot=postorder[pe];
int index=is;
while(index<=ie&&curroot!=inorder[index])
{
index++;
}
TreeNode root=new TreeNode(curroot);
root.left=construct(inorder,is,index-1,postorder,ps,ps+index-is-1);
root.right=construct(inorder,index+1,ie,postorder,ps+index-is,pe-1);
return root;
}
}
二叉树的右视图
class Solution {
public List rightSideView(TreeNode root) {
List> sum=level(root);
List result=new LinkedList<>();
for(List x:sum)
{
result.add(x.get(0));
}
return result;
}
public List> level(TreeNode root)
{
List> sum=new LinkedList<>();
if(root==null) return sum;
Queue queue=new LinkedList<>();
queue.add(root);
while(!queue.isEmpty())
{
int t=queue.size();
TreeNode temp;
List x=new LinkedList<>();
for(int i=0;i
二叉树的每层的最大值
class Solution {
public List largestValues(TreeNode root) {
List> sum=level(root);
List result=new LinkedList<>();
for(List x:sum)
{
int temp=Integer.MIN_VALUE;
for(int y:x)
{
temp=Math.max(temp,y);
}
result.add(temp);
}
return result;
}
public List> level(TreeNode root)
{
List> sum=new LinkedList<>();
if(root==null) return sum;
Queue queue=new LinkedList<>();
queue.add(root);
while(!queue.isEmpty())
{
int t=queue.size();
TreeNode temp;
List x=new LinkedList<>();
for(int i=0;i
n叉树的层序遍历
class Solution {
public List> levelOrder(Node root) {
List> sum=new LinkedList<>();
if(root==null) return sum;
Queue queue=new LinkedList<>();
queue.add(root);
while(!queue.isEmpty())
{
int t=queue.size();
Node temp;
List x=new LinkedList<>();
for(int i=0;i
二叉树最小深度
class Solution {
public int minDepth(TreeNode root) {
if(root==null) return 0;
Queue queue=new LinkedList<>();
queue.add(root);
int depth=0;
while(!queue.isEmpty())
{
int t=queue.size();
TreeNode temp;
depth++;
for(int i=0;i
填充每个节点的下一个右侧节点指针
class Solution{
public TreeNode connect(TreeNode root)
{
if(root==null) return null;
if(root.left==null&&root.right==null) return root;
root.left.next=root.right;
if(root!=null)
{
root.right.next=root.next.left;
}
connect(root.left);
connect(root.right);
return root;
}
}
翻转二叉树
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) return null;
TreeNode x=root.left;
root.left=invertTree(root.right);
root.right=invertTree(x);
return root;
}
}
对称二叉树
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
return calulate(root.left,root.right);
}
public boolean calulate(TreeNode node1,TreeNode node2)
{
if(node1==null&&node2==null) return true;
if(node1==null||node2==null||node1.val!=node2.val) return false;
return calulate(node1.left,node2.right)&&calulate(node1.right,node2.left);
}
}
完全二叉树节点个数
class Solution {
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
二叉树的所有路径
class Solution {
List sum=new LinkedList<>();
public List binaryTreePaths(TreeNode root) {
if(root==null) return sum;
cal(new StringBuilder(),root);
return sum;
}
public void cal(StringBuilder sb,TreeNode root)
{
if(root==null) return;
sb.append(root.val);
if(root.left==null&&root.right==null)
{
sum.add(sb.toString());
}
if(root.left!=null) cal(new StringBuilder(sb).append("->"),root.left);
if(root.right!=null) cal(new StringBuilder(sb).append("->"),root.right);
}
}
平衡二叉树
class Solution {
public boolean isBalanced(TreeNode root) {
return cal(root)!=-1;
}
public int cal(TreeNode root)
{
if(root==null) return 0;
if(cal(root.left)==-1)
{
return -1;
}
if(cal(root.right)==-1)
{
return -1;
}
if(Math.abs(cal(root.left)-cal(root.right))>1)
{
return -1;
}
return Math.max(cal(root.left),cal(root.right))+1;
}
}