常见算法题整理 - 来自《剑指Offer》

数据结构	算法	概念
链表	广度优先搜索	位操作
树、单词查找树、图	深度优先搜索	内存（堆、栈）
栈和队列	二分查找	递归
堆	归并排序	动态规划
向量、数组列表	快排	时间、空间复杂度
散列表

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。(要求线性时间复杂度，即$O(1)$)

实例：输入：[1,2,3,2,1] 输出：3

public int singleNumber(int[] nums) {
    int result = 0;
    for(int x : nums){
        result = result ^ x; //利用异或位运算 实现 同则为0 不同则为 1
    }
    return result;
}

给定一个正整数，如何判断该数是否为2的幂次方？

实例：输入 32 输出 true

​ 输入 25 输出 false

public boolean isMi(int num){
  return num & (num -1 ) == 0；
}

输入一颗二叉树，求树的深度 利用递归实现

public class TreeNode{
  int val = 0;
  TreeNode left = null;
  TreeNode right = null;
  
  public TreeNode(int val){
    this.val = val;
  }
}

public class Solution{
  public int TreeDepth(TreeNode root){
    if(root ==null){
      return 0;
    }
    return 1 + Math.max(TreeDepth(root.left),TreeDepth(root.right));
  }
}

不用加减乘除实现 加法 减法

public class Solution {
    public int Add(int num1,int num2) {
        if(num2==0){
            return num1;
        }
        int res = num1 ^ num2;
        int res2 = (num1&num2) << 1;
        return Add(res,res2);
    }
  
   public int minus(int num1,int num2){
    
  }
}

二叉树镜像

public class Solution{
  public void Mirror(TreeNode root){
    if(root == null)
      return;
    swap(root);
    Mirror(root.left);
    Mirror(root.right);
  }
  
  private void swap(TreeNode root){
    TreeNode node = root.left;
    root.left= root.right;
    root.right = node;
  }
}

两个栈实现队列

public class Solution{
  Stack<Integer> in = new Stack<Integer>();
  Stack<Integer> out = new Stack<Integer>();
  
  public void push(int node){
    in.push(node);
  }
  
  public int pop(){
    if(out.isEmpty()){
      while(!in.isEmpty()){
        out.push(in.pop());
      }
    }
    
    return out.pop();
  }
}

两个队列实现一个栈

获取链表倒数第K个节点

public class Solution{
   public ListNode FindKthToTail(ListNode head,int k) {
     if(head == null){
       return null
     } 
     ListNode first = head;
     while(first!=null && k-->0){
       first = first.next;
     }
     if(k>0){
       return null;
     }
     ListNode kNode = head;
     while(first!=null){
       first = first.next;
       kNode = kNode.next;
     }
     return kNode;
     
   }
}

反转链表并输出表头

public class Solution{
  public ListNode ReverseList(ListNode head){
    ListNode reverseList = new ListNode(-1);
    while(head!=null){
      ListNode next = head.next;
      head.next = reverseList.next;
      reverseList.next = head;
      reverseList = next;
    }
    return reverseList.next;
  }
  
  public ListNode ReverseList1(ListNode head){
    ListNode pre = null;
    ListNode cur = head;
    ListNode next = null;
    while(cur!=null){
      next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
    }
    
    return pre;
  }
}

LeetCode 24：交换链表中节点

public class Solution{
  public ListNode swapPairs(ListNode head){
    if(head==null || head.next ==null)
      return head;
    
    ListNode next = head.next;
    head.next = swapPairs(next.next);
    next.next = head;
    reyurn next;
  }
}

实现一个包含min()的栈，可以返回栈中的最小值

public class Solution{
  private Stack<Integer> minStack = new Stack();
  private Stack<Integer> inputStack = new Stack();
  
  public void push(int node){
    inputStack.push(node);
    //与顶端进行比较 取小
    minStack.push(minStack.isEmpty()?node:Math.min(minStack.peek(),node));
  } 
  
  public void pop(){
    inputStack.pop();
    minStack.pop();
  }
  
  public int top(){
    return inputStack.peek();
  }
  
  public int min(){
    return minStack.peek();
  }
}

斐波那契数列

public class Solution{
  public int Fibonacci(int n) {
  if(n<=1){
    return n;
  }
  int[] fib = new int[n+1];
    fib[1] = 1;
    for(int i=2;i<=n;i++){
      fib[i] = fib[i-1]+fib[i-2];
    }
    return fib[n];
  }
}

重建二叉树

• 已知前序遍历和中序遍历

  > 例如 前序遍历为 {1,2,4,7,3,5,6,8} //根节点在前方
  \>
  > ​ 中序遍历为{4,7,2,1,5,3,8,6} //根节点左侧为 左子树 右侧为 右子树

public class Solution{
  private HashMap<Integer,Integer> map = new HashMap<>();
  private int rootIndex ;
  public TreeNode buildTree(int[] pre,int[] in){
    int len = in.length;
    for(int i=0;i<len;i++){
      map.put(in[i],i);
    }
    rootIndex = 0;
    return buildTree(pre,0,len-1);
  }
  
  public TreeNode buildTree(int[] pre,int start,int end){
    if(start>end){
      return null;
    }
    TreeNode rootNode = new TreeNode(pre[rootIndex++])
    int index = map.get(rootNode.val);
    
    rootNode.left = buildTree(pre,start,index-1);
    rootNode.right = buildTree(pre,index+1,end);
    return rootNode;
  }
}

• 已知中序遍历和后序遍历

public class Solution{
  private HashMap<Integer,Integer> map = new HashMap<>();
  private int rootIndex;
  public TreeNode BuildTree(int[] post,int[] in){
    int len = in.length;
    for(int i=0;i<len;i++){
      map.put(in[i],i);
    }
    rootIndex = len-1;
    return buildTree(post,0,len-1);
  }
  
  public TreeNode buildTree(int[] post ,int start ,int end){
    if(start>end)
      return null;
    TreeNode rootNode = new TreeNode(post[rootIndex--]);
    int index = map.get(rootNode.val);
    //先计算右子树
    rootNode.right = buildTree(post,index+1,end);
    rootNode.left = buildTree(post,start,index-1);
    return rootNode;
    
  }
}

• 二叉树的遍历

-

判断链表是否成环，若成环找出入口点

1. 判断next是否为null，不为null则成环
2. 利用Set存储每个节点，每到新节点判断是否出现重复。时间复杂度O(n)

public class Solution{
  public ListNode EntryNodeOfLoop(ListNode head){
    if(head==null)
      return null;
    ListNode fast = head;
    ListNode slow = head;
    while(fast!=null && fast.next!=null){
      fast = fast.next.next;
      slow = slow.next;
      //表明链表成环
      if(fast==slow){
        ListNode result = head;
        while(head!=slow){
          result = result.next;
          slow = slow.next;
        }
        return result;
      }
    }
  }
}

删除链表中重复的节点

public class Solution{
    public ListNode deleteDuplication(ListNode head){
      if(head == null || head.next ==null)
        return head;
      ListNode next = head.next;
      if(head.val == next.val){
        while(next!=null && head.val == next.val)
          next = next.next;
        return deleteDuplication(next);
      }else{
        head.next = deleteDuplication(next);
        return head;
      }
    }
}

判断是否为平衡二叉树

平衡二叉树：左子树和右子树高度相差不到1

public class Solution{
  private boolean isBalanced = true;
  public boolean IsBalanced_Solution(TreeNode node){
    
    return isBalanced;
  }
  
  private int getTreeHeight(TreeNode node){
    if(node == null || !isBalanced){
      return 0;
    }
    int left = getTreeHeight(node.left);
    int right = getTreeHeight(node.right);
    if(Math.abs(left-right)<1){
      isBalanced = false;
    }
    return 1+Math.max(left,right);
  }
}

字符流中第一个不重复字符串

public class Solution {
    HashMap<Character,Integer> map = new LinkedHashMap();
    char firstChar = "#".charAt(0);
    
    //Insert one char from stringstream
    public void Insert(char ch)
    {
       if (map.containsKey(ch)) {
            map.put(ch, 0);      
        } else {
            map.put(ch, 1);
        }

        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                firstChar = entry.getKey();
                break;
            }else{
                firstChar = "#".charAt(0);
            }
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        return firstChar;
    }
}

二叉搜索树的后序遍历序列
后序遍历过程： 左->右->中
二叉搜索树：设x是树中的一个节点，如果y是x左子树中的一个节点，那么y<=x，如果y是x右子树的一个节点，那么y>=x

public class Solution {
 public static  boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length ==0 || sequence==null){
            return false;
        }
        if(sequence.length == 1){
            return true;
        }
        return search(sequence,0,sequence.length-1);
    }

    private static boolean search(int[] array ,int start,int end){
        if(start > end){
            return true;
        }
        int i = end;
        //向前倒序寻找到左子树
        while(i>start && array[i-1] > array[end]){
            i--;
        }
        for(int j = i-1;j>=start;j--){
            if(array[j] > array[end]){
                return false;
            }
        }
        return search(array,start,i-1) && search(array,i+1,end-1);
    }
}

二叉树中和为某一值的路径

public class Solution {
    private static ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        arrayLists.clear();
        addPath(root,new ArrayList(),0,target);
        return arrayLists;
    }
    
    private static void addPath(TreeNode root, ArrayList<Integer> path, int num, int target) {
        if (root == null) {
            return;
        }
        num += root.val;
        path.add(root.val);
        //递归完毕
        if (root.left == null && root.right == null) {
            if (num == target) {
                arrayLists.add(new ArrayList<>(path));
            }
        } else {
            addPath(root.left, path, num, target);
            addPath(root.right, path, num, target);
        }
        path.remove(path.size() - 1);
    }
}

实现一个LFU算法

淘汰一定时期内被访问次数最少的元素

Leetcode 703

采用优先队列机制实现，比较第K大元素问题
优先队列采用 小顶堆 小的数据放在根节点，这样在插入节点时只要与根节点比较即可

class KthLargest {
    PriorityQueue<Integer> priorityQueue;
    int maxSize = 0;

    public KthLargest(int k, int[] nums) {
        this.maxSize = k;
        priorityQueue = new PriorityQueue<Integer>(k);
        for (int var : nums) {
            add(var);
        }

    }

    public int add(int val) {
        if (priorityQueue.size() < maxSize) {
            priorityQueue.offer(val);
        } else if (priorityQueue.peek() < val) {
            priorityQueue.poll();
            priorityQueue.offer(val);
        }
        return priorityQueue.peek();
    }
}

Leetcode 239：Sliding Window Maximum

Leetcode 15: 3Sum

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

解题思路：

先对数组进行排序，按照从小到大的顺序。将排序后的数组全部放入到HashMap中

题目中要求a+b+c=0 ==> c=-a-b即 在Map中找到-a-b对应的值并取出即可

时间复杂度：`O(n2)`

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        HashMap<Integer, Integer> set = new HashMap<>();
        int len = nums.length;
        if (nums.length < 3)
            return result;
        // 排序
        Arrays.sort(nums);

        for (int i = 0; i < len; i++) {
            set.put(nums[i], i);
        }

        for (int i = 0; i < len; i++) {
            if (i != 0 && nums[i] == nums[i - 1])
                continue;

            for (int j = i + 1; j < len; j++) {
                // 
                if (nums[i] > 0)
                    break;
                if (nums[j] == nums[j - 1] && j != i + 1)
                    continue;
                if (set.containsKey(-nums[i] - nums[j]) && set.get(-nums[i] - nums[j]) > j) {
                    List<Integer> l = new ArrayList<Integer>();
                    l.add(nums[i]);
                    l.add(nums[j]);
                    l.add(-nums[i] - nums[j]);
                    result.add(l);
                }
            }
        }
        return result;
    }
}

优化解法

还是先进行排序，固定首位数据a，然后在剩下的数据内，设置下一位为b，数组最后一位为c，如果a+b+c=0直接取出对应值，

• 若>0，则c向左移
• 若<0，则b向右移

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();

        int len = nums.length;
        if (nums.length < 3)
            return result;
        // 排序
        Arrays.sort(nums);

        for (int i = 0; i < len - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int low = i + 1;
            int high = len - 1;
            while (low < high) {
                int resultNum = nums[i] + nums[low] + nums[high];
                if (resultNum == 0) {
                    List<Integer> l = new ArrayList<Integer>();
                    l.add(nums[i]);
                    l.add(nums[low]);
                    l.add(nums[high]);
                    result.add(l);
                    //此处为了防止 因为重复数据导致问题 
                    while (low < high && nums[low] == nums[low + 1]) low++;
                    while (low < high && nums[high] == nums[high - 1]) high--;
                    low++;
                    high--;
                } else if (resultNum > 0) {
                    high--;
                } else {
                    low++;
                }
            }
        }
        return result;
    }
}