- 基本排序算法
- 二叉树三种遍历方式
- 反转链表
- 反转链表的m到n个节点
- 股票买入卖出最大利润
- 全排列
- 去重的全排列
- LRU
- 从一个数组中找出和为T的组合
基本排序算法
快速排序：
class Solution(object):
def quickSort(self, arr, start, end):
i = start
j = end
sp = arr[start]
while i < j:
while i < j and arr[j] >= sp:
j -= 1
if i < j:
arr[i] = arr[j]
i += 1
while i < j and arr[i] <= sp:
i += 1
if i < j:
arr[j] = arr[i]
j -= 1
arr[i] = sp
if start < i-1:
self.quickSort(arr, start, i - 1)
if j+1 < end:
self.quickSort(arr, j + 1, end)
二叉树遍历
前序遍历：
public void PreOrderTraversal(BitNode root) {
if (root != null) {
System.out.print(root.data);
PreOrderTraversal(root.left);
PreOrderTraversal(root.right);
}
}
深度优先搜索：
public void DepthFirstSearch(BitNode root) {
Stack<BitNode> nodeStack = new Stack<>();
nodeStack.push(root);
while (!nodeStack.empty()) {
BitNode node = nodeStack.peek();
System.out.print(root.data);
nodeStack.pop();
if (node.right != null) {
nodeStack.push(node.right);
}
if (node.left != null) {
nodeStack.push(node.left);
}
}
}
广度优先搜索：
public void BreadthFirstSearch(BitNode root) {
Queue<BitNode> nodeQueue = new PriorityQueue<>();
nodeQueue.add(root);
while (!nodeQueue.isEmpty()) {
BitNode node = nodeQueue.peek();
System.out.print(root.data);
nodeQueue.poll();
if (node.left != null) {
nodeQueue.add(node.left);
}
if (node.right != null) {
nodeQueue.add(node.right);
}
}
}
打印出二叉树所有路径
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result= new ArrayList<>();
List<Integer> path = new ArrayList<>();
if (root!=null){
paths(result, path, root, 0);
}
return result;
}
private void paths(List<List<Integer>> result, List<Integer> curPath,TreeNode root, int depth){
curPath.add(depth, root.val);
if (root.left == null && root.right == null){
ArrayList<Integer> path=new ArrayList<>();
for (int i=0; i<=depth; i++){
path.add(curPath.get(i));
}
result.add(path);
return;
}
if (root.left!=null){
paths(result, curPath, root.left, depth+1);
}
if (root.right!=null){
paths(result, curPath, root.right, depth+1);
}
}
}
层次遍历
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result=new ArrayList<List<Integer>>();
if(root==null){
return result;
}
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
List<Integer> list=new ArrayList<Integer>();
for(int count=queue.size();count>0;count--){
TreeNode tempNode=queue.poll();
list.add(tempNode.val);
if(tempNode.left!=null){
queue.add(tempNode.left);
}
if(tempNode.right!=null){
queue.add(tempNode.right);
}
}
result.add(list);
}
return result;
}
}
反转链表
反转链表：
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev=null,curr=head,next=null;
while(curr!=null){
next=curr.next;
curr.next=prev;
prev=curr;
curr=next;
}
return prev;
}
}
反转m到n个节点：
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode mPre=dummy,nNext=null,curr=null,next=null,prev=null;
for(int i=0;i<m-1;i++){
mPre=mPre.next;
}
curr=mPre.next;
for(int i=0;i<=n-m;i++){
next=curr.next;
curr.next=prev;
prev=curr;
curr=next;
nNext=next;
}
mPre.next.next=nNext;
mPre.next=prev;
return dummy.next;
}
}
股票买入卖出最大利润
全排列
全排列：
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(nums==null || nums.length==0) {
return res;
}
range(nums,0,nums.length,res);
return res;
}
public void range(int[] nums, int start, int length, List<List<Integer>> res){
if (start == length-1){
res.add(toArrayList(nums));
return;
}
for (int i=start;i<nums.length;i++){
int temp=nums[start];
nums[start]=nums[i];
nums[i]=temp;
range(nums,start+1,length,res);
nums[i]=nums[start];
nums[start]=temp;
}
}
public List<Integer> toArrayList(int[] nums){
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<nums.length;i++){
list.add(nums[i]);
}
return list;
}
}
去重的全排列：
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(nums==null || nums.length==0) {
return res;
}
Arrays.sort(nums);
range(nums,0,nums.length,res);
return res;
}
public void range(int[] nums, int start, int length, List<List<Integer>> res){
if (start == length-1){
res.add(toArrayList(nums));
return;
}
for (int i=start;i<nums.length;i++){
boolean isSwap=true;
for(int j=start;j<i;j++){
if(nums[j]==nums[i]){
isSwap=false;
}
}
if(!isSwap){
continue;
}
int temp=nums[start];
nums[start]=nums[i];
nums[i]=temp;
range(nums,start+1,length,res);
nums[i]=nums[start];
nums[start]=temp;
}
}
public List<Integer> toArrayList(int[] nums){
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<nums.length;i++){
list.add(nums[i]);
}
return list;
}
}
全组合
public static void combination(char[] chars) {
if (chars == null) return;
int length = chars.length;
int count = 1 << length;
for (int i = 1; i < count; i++) {
for (int j = 0; j < length; j++) {
if ((i & (1 << j)) > 0) {
System.out.print(chars[j]);
}
}
System.out.println();
}
}
LRU
public class LRUCache {
private Map<Integer, Integer> map;
public LRUCache(int capacity) {
map = new LinkedHashMap<Integer, Integer>(capacity, 1.0f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return this.size() > capacity;
}
};
}
public int get(int key) {
return map.getOrDefault(key, -1);
}
public void put(int key, int value) {
map.put(key, value);
}
}
多线程
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class Main {
private final Lock lock = new ReentrantLock();// 通过JDK5中的Lock锁来保证线程的访问的互斥
private int state = 0;//通过state的值来确定是否打印
class ThreadA extends Thread {
@Override
public void run() {
for (int i = 0; i < 10; ) {
try {
lock.lock();
while (state % 3 == 0) {// 多线程并发，不能用if，必须用循环测试等待条件，避免虚假唤醒
System.out.print("A");
state++;
i++;
}
} finally {
lock.unlock();// unlock()操作必须放在finally块中
}
}
}
}
public static void main(String[] args) {
Main m = new Main();
m.new ThreadA().start();
}
}
