剑指offer个人算法准备

剑指Offer

数据结构

链表双指针

JZ6 从尾到头打印链表

翻转，浪费时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer>result = new ArrayList<>();


        ListNode last = null;

        while (listNode != null) {
            ListNode next = listNode.next;
            listNode.next = last;
            last = listNode;
            if (next != null) {
                listNode = next;
            } else {
                break;
            }
        }

        while (listNode != null) {
            result.add(listNode.val);
            listNode = listNode.next;
        }

        return result;
    }
}

借助插入特性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer>result = new ArrayList<>();

        while(listNode!=null){
            result.add(0,listNode.val);
            listNode = listNode.next;
        }

        return result;
    }
}

JZ24 反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        ListNode last = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = last;
            last = head;
            if (next != null) {
                head = next;
            } else {
                break;
            }
        }
        return head;
    }
}

JZ25 合并两个排序的链表

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null) {
            return pHead2;
        } else if (pHead2 == null) {
            return pHead1;
        }
        ListNode head = null;
        if (pHead1.val < pHead2.val) {
            head = pHead1;
            //立即移动到下一个
            pHead1 = pHead1.next;
        } else {
            head = pHead2;
            //立即移动到下一个
            pHead2 = pHead2.next;
        }
        ListNode temp = head;
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val < pHead2.val) {
                temp.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                temp.next = pHead2;
                pHead2 = pHead2.next;
            }
            temp = temp.next;
        }
        // 连接剩余部分
        temp.next = (pHead1 != null) ? pHead1 : pHead2;
        return head;
    }
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead1 ListNode类 
     * @param pHead2 ListNode类 
     * @return ListNode类
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null) {
            return pHead2;
        } else if (pHead2 == null) {
            return pHead1;
        }
        if(pHead1.val<pHead2.val){
            //递归向下
            pHead1.next = Merge(pHead1.next,pHead2);
            return pHead1;
        }else{
            //递归向下
            pHead2.next = Merge(pHead1,pHead2.next);
            return pHead2;
        }
    }
}

JZ52 两个链表的第一个公共结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode t1 = pHead1, t2 = pHead2;
        while (t1 != t2) {
            t1 = (t1 == null) ? pHead2 : t1.next;
            t2 = (t2 == null) ? pHead1 : t2.next;
        }
        return t1;
    }
}

JZ23 链表中环的入口结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //寻找是否有环
        ListNode fast = pHead, slow = pHead, slow_real = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                slow_real = slow;//相交点
                break;
            }
        }
        if (slow_real == null) {
            return null;//没有环
        }
        //寻找进入环找第一个节点
        fast = pHead;
        while (fast != slow_real) {
            fast = fast.next;
            slow_real = slow_real.next;
        }
        return slow_real;
    }
}

JZ22 链表中倒数最后k个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if (pHead == null) {
            return null;
        }
        //让快指针移动到位
        ListNode fast = pHead;
        for (int i = 0; i < k; i++) {
            if (i != k - 1 && fast.next == null) {
                return null;
            }
            fast = fast.next;
        }
        //让慢指针和快指针同时移动，直到快指针为空
        ListNode slow = pHead;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

JZ35 复杂链表的复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.*;
/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }
        //添加一个新头部节点
        RandomListNode newHead = pHead;
        //遍历原始链表，开始复制
        while (newHead != null) {
            RandomListNode clone = new RandomListNode(newHead.label);
            //拼接在原本节点后面
            clone.next = newHead.next;
            newHead.next = clone;
            newHead = clone.next;
        }
        //连接新链表的random节点
        newHead = pHead;
        RandomListNode clone =
            pHead.next;//不会为空，一开始链表为空返回了，不为空克隆出来一个，这个就不为空了
        while (newHead != null) {
            if (newHead.random == null) {
                clone.random = null;
            } else {
                //原本指向的下一个节点就是新链表的random应该指向的
                clone.random = newHead.random.next;
            }
            //移动处理下个位置,newHead.next一定被复制了一个，不会为空
            newHead = newHead.next.next;
            //检查末尾节点
            if (clone.next != null) {
                clone = clone.next.next;
            }
        }
        //拆分两个链表
        RandomListNode result = pHead.next;
        newHead = pHead.next;
        while (pHead != null) {
            pHead.next = pHead.next.next;
            pHead = pHead.next;
            //检查末尾节点
            if (newHead.next != null) {
                newHead.next = newHead.next.next;
            }
            newHead = newHead.next;
        }
        return result;
    }
}

JZ76 删除链表中重复的结点

难得递归直接写出来

就是每次都判断当前的开头是不是不同的，不同就处理下一个，返回当前的，相同就不断排除掉相同的，递归处理下一个，下一个可能相同，可能不同，可能为null，交给下一次递归处理，特殊情况就是一开始只有一个或者为空

（每轮处理的都是新数字！！！）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        //递归结束条件
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        //判断当前的第一个是不是不同的
        if (pHead.val != pHead.next.val) {
            pHead.next = deleteDuplication(pHead.next);
            return pHead;
        } else {
            //第一个都是跟后面相等的
            int val = pHead.val;
            //排除掉相同的
            while (pHead.next != null) {
                if (pHead.next.val != val) {
                    break;
                }
                pHead = pHead.next;
            }
            //排除掉相同的，现在是新的数字或者null
            return deleteDuplication(pHead.next);
        }
    }
}

JZ18 删除链表的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param val int整型
     * @return ListNode类
     */
    public ListNode deleteNode (ListNode head, int val) {
        if (head.val == val) {
            return head.next;
        }
        ListNode last = head, temp = last.next;
        while (temp != null) {
            if (temp.val == val) {
                last.next = temp.next;
                break;
            } else {
                last = temp;
                temp = temp.next;
            }
        }
        return head;
    }
}

树

树的递归

JZ55 二叉树的深度

深度就是左子树和右子树的最大深度+1，为空就返回0，递归秒了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;
/**
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 Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
    }
}

JZ54 二叉搜索树的第k个节点

搜索树直接中序遍历即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param proot TreeNode类
     * @param k int整型
     * @return int整型
     */
    public int KthNode (TreeNode proot, int k) {
        Stack<TreeNode>stack = new Stack<>();
        int count = 0;
        while (proot != null || !stack.isEmpty()) {
            //一直左边遍历下去
            while (proot != null) {
                stack.push(proot);
                proot = proot.left;
            }
            //左边放完了，取出第一个，也就是中间的了
            count++;
            if (count == k) {
                return stack.pop().val;
            }
            //开始处理右边的
            proot = stack.pop().right;
        }
        return -1;
    }
}

JZ7 重建二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param preOrder int整型一维数组
     * @param vinOrder int整型一维数组
     * @return TreeNode类
     */
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        //处理两个数组为空的特殊情况
        int preLength = preOrder.length, vinLength = vinOrder.length;
        if (preLength == 0 || vinLength == 0) {
            return null;
        }
        //构建当前这棵树的根节点，前序遍历的第一个就是根节点
        TreeNode root = new TreeNode(preOrder[0]);
        //找到中序遍历的这个值，左右划分子树
        for (int i = 0; i < vinLength; i++) {
            if (preOrder[0] == vinOrder[i]) {
                //递归处理左右子树
                root.left = reConstructBinaryTree(
                                Arrays.copyOfRange(preOrder, 1, i + 1),
                                Arrays.copyOfRange(vinOrder, 0, i)
                            );
                root.right = reConstructBinaryTree(
                                 Arrays.copyOfRange(preOrder, i + 1, preLength),
                                 Arrays.copyOfRange(vinOrder, i + 1, vinLength)
                             );
                break;
            }
        }
        return root;
    }
}

JZ26 树的子结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;

public class Solution {
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        // 判断root1本身是否包含root2，或者root1的左子树或右子树是否包含root2
        return isSame(root1, root2) || HasSubtree(root1.left, root2) ||
               HasSubtree(root1.right, root2);
    }

    public boolean isSame(TreeNode root1, TreeNode root2) {
        // 如果root2为null，说明已经匹配完
        if (root2 == null) {
            return true;
        }
        // 如果root1为null或者值不同，说明不匹配
        if (root1 == null || root1.val != root2.val) {
            return false;
        }
        // 递归比较左右子树
        return isSame(root1.left, root2.left) && isSame(root1.right, root2.right);
    }
}

JZ27 二叉树的镜像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        //递归，每次处理一棵树的左右交换，为空就不处理，返回上一层了
        //终止条件
        if(pRoot==null){
            return null;
        }
        //先递归子树
        TreeNode left = Mirror(pRoot.left);
        TreeNode right = Mirror(pRoot.right);
        //交换
        pRoot.left = right;
        pRoot.right = left;
        return pRoot;
    }
}

JZ32 从上往下打印二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;
import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer>result = new ArrayList<>();
        if (root != null) {
            Queue<TreeNode>queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode tmp = queue.poll();
                result.add(tmp.val);
                if (tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if (tmp.right != null) {
                    queue.offer(tmp.right);
                }
            }
        }
        return result;
    }
}

JZ33 二叉搜索树的后序遍历序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.*;
public class Solution {
    //二叉搜索树，也叫二叉排序树，右子树的任何值比根节点大，左子树的任何值都比根节点小
    public boolean VerifySquenceOfBST(int [] sequence) {
        //常规方法就是递归解决
        if (sequence == null || sequence.length == 0) {
            //题目规定特殊情况，空树不是
            return false;
        }

        //不为空就递归解决，先判断当前大树是不是二叉树，再递归判断左右子树
        return isBSTTree(sequence, 0, sequence.length - 1);
    }

    //判断这个范围内的数组是否是一个二叉搜索树
    public boolean isBSTTree(int[] sequence, int l, int r) {
        //递归的中止条件，可以考虑只有两个元素和只有一个元素的时候，
        if (l >= r) {
            return true;
        }

        //根节点一定是当前范围内的最后一个，后序遍历规则
        int root = sequence[r];

        //找到第一个大于等于根节点，保存下标
        int k = l;
        while (sequence[k] < sequence[r]) {
            k++;
        }
        //找到这个元素说明左边都是比根节点小了，那么从找到这个元素到结束是右子树，都要比根节点大，存在一个比根节点小的就说明有问题了
        for (int i = k; i < r; i++) {
            if (sequence[i] < sequence[r]) {
                return false;
            }
        }
        //到这里说明当前树满足，递归左右子树
        return isBSTTree(sequence, l, k - 1) && isBSTTree(sequence, k, r - 1);
    }


}

JZ36 二叉搜索树与双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    //保存结果的头
    TreeNode head = null;
    //保存上次访问的节点，下次访问的节点要跟这个连接
    TreeNode last = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree != null) {
            //不为空才进行中序遍历
            Convert(pRootOfTree.left);
            //这里处理不同，需要连接双向链表，第一次到最左边，这时候初始化last为这个位置，也就是last还为null的时候，之后不会为空了，head也为这个位置
            if (last == null) {
                head = pRootOfTree;
                last = pRootOfTree;
            } else {
                //连接双向链表
                last.right = pRootOfTree;
                pRootOfTree.left = last;
                last = pRootOfTree;
            }
            Convert(pRootOfTree.right);
        }
        return head;
    }
}

JZ79 判断是不是平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*;

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

public class Solution {

    //求树的最大深度
    int deep(TreeNode node) {
        //终止条件
        if (node == null) {
            return 0;
        }
        //左和右
        int left = deep(node.left);
        int right = deep(node.right);
        //左右子树的深度最大值+1
        return Math.max(left, right) + 1;
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return bool布尔型
     */
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        if (pRoot == null) {
            return true;
        }
        int left = deep(pRoot.left);
        int right = deep(pRoot.right);
        //左右子树的绝对值大于1
        if (Math.abs(left - right) > 1) {
            return false;
        }
        //左右子树必须是平衡的
        return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
    }
}

JZ8 二叉树的下一个结点

仔细观察，可以把中序下一结点归为几种类型：

  1. 有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H
  2. 无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E
  3. 无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A；例如 G，并没有符合情况的结点，所以 G 没有下一结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {

public TreeLinkNode GetNext(TreeLinkNode pNode) {
     // 1. 
     if (pNode.right != null) {
         TreeLinkNode pRight = pNode.right;
         while (pRight.left != null) {
             pRight = pRight.left;
         }
         return pRight;
     }
     // 2. 
     if (pNode.next != null && pNode.next.left == pNode) {
         return pNode.next;
     }
     // 3. 
     if (pNode.next != null) {
         TreeLinkNode pNext = pNode.next;
         while (pNext.next != null && pNext.next.right == pNext) {
             pNext = pNext.next;
         }
         return pNext.next;
     }
     return null;
 }
}

JZ78 把二叉树打印成多行

这个简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (pRoot != null) {
            Queue<TreeNode>queue = new LinkedList<>();
            queue.offer(pRoot);
            while (!queue.isEmpty()) {
                int size = queue.size();
                ArrayList<Integer>temp = new ArrayList<>();
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();
                    temp.add(node.val);
                    if (node.left != null) {
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        queue.offer(node.right);
                    }
                }
                if (!temp.isEmpty()) {
                    result.add(temp);
                }
            }
        }
        return result;
    }
}

JZ37 序列化二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    // 序列化二叉树
    String Serialize(TreeNode root) {
        if (root == null) {
            return "#";
        }
        StringBuilder stringBuilder = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                stringBuilder.append("#,");
            } else {
                stringBuilder.append(node.val).append(",");
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }

        return stringBuilder.toString();
    }

    // 反序列化二叉树
    TreeNode Deserialize(String str) {
        if (str.equals("#")) {
            return null;
        }
        String[] nodes = str.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int index = 1;

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (!nodes[index].equals("#")) {
                node.left = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(node.left);
            }
            index++;

            if (!nodes[index].equals("#")) {
                node.right = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(node.right);
            }
            index++;
        }

        return root;
    }
}

JZ84 二叉树中和为某一值的路径(三)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return int整型
     */
    public int FindPath (TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        return FindPathByNode(root, sum) + FindPath(root.left, sum) +
               FindPath(root.right, sum);
    }

    public int FindPathByNode(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        if (sum - root.val == 0) {
            return FindPathByNode(root.left, sum - root.val) + FindPathByNode(root.right,
                    sum - root.val) + 1;
        } else {
            return FindPathByNode(root.left, sum - root.val) + FindPathByNode(root.right,
                    sum - root.val);
        }
    }
}

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return int整型
     */
    public int FindPath (TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        return FindPathByNode(root, sum) + FindPath(root.left, sum) +
               FindPath(root.right, sum);
    }

    public int FindPathByNode(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        int result = 0;
        if (root.val == sum) {
            result++;
        }

        result += FindPathByNode(root.left, sum - root.val);
        result += FindPathByNode(root.right, sum - root.val);
        return result;
    }
}

JZ86 在二叉树中找到两个节点的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
        return helper(root, o1, o2).val;
    }

    public TreeNode helper(TreeNode root, int o1, int o2) {
        if (root == null || root.val == o1 || root.val == o2)
            return root;
        TreeNode left = helper(root.left, o1, o2);
        TreeNode right = helper(root.right, o1, o2);
        //如果left为空，说明这两个节点在root结点的右子树上，我们只需要返回右子树查找的结果即可
        if (left == null)
            return right;
        //同上
        if (right == null)
            return left;
        //如果left和right都不为空，说明这两个节点一个在root的左子树上一个在root的右子树上，
        //我们只需要返回cur结点即可。
        return root;
    }
}

队列 & 栈

JZ31 栈的压入、弹出序列

下面有原地栈的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int整型一维数组
     * @param popV int整型一维数组
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        //新开一个辅助栈
        Stack<Integer>stack = new Stack<>();
        //遍历入栈的下标
        int j = 0;
        //遍历出栈数组
        for (int i = 0; i < pushV.length; i++) {
            //辅助栈为空或者栈顶不等于出栈数组并且还有内容去放进来
            while (j < pushV.length && (stack.isEmpty() || stack.peek() != popV[i])) {
                stack.push(pushV[j++]);
            }
            //到这里说明放完了或者遇到想等的了，遇到相等的抛出，不然就是匹配不到合适的
            if (stack.pop() != popV[i]) {
                return false;
            }
        }
        return true;
    }
}

也可以一直入栈，每次遍历出栈的是否相等，相等就继续出栈，直到栈空了，最后看栈是不是空放回即可，借鉴了原地栈的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型一维数组 
     * @param popV int整型一维数组 
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        //栈空间的大小，初始化为0
        int n = 0;
        //记录出栈的下标
        int i = 0;
        //遍历入栈队列
        for(int temp:pushV){
            pushV[n] = temp;

            //看是否能出栈
            while(n>=0&&pushV[n]==popV[i]){
                n--;
                i++;
            }

            n++;
        }
        return n==0;
    }
}

JZ73 翻转单词序列

看下面双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.*;

public class Solution {
    public String ReverseSentence(String str) {
        Stack<Character> stack1 = new Stack<>();
        ArrayList<String> list1 = new ArrayList<>();
        StringBuilder result = new StringBuilder();

        // 判断输入是否为 null 或空字符串
        if (str == null || str.length() == 0) {
            return "";
        }

        // 遍历字符串从后向前
        for (int i = str.length() - 1; i >= 0; i--) {
            char c = str.charAt(i);

            // 如果遇到空格
            if (c == ' ') {
                // 将栈中的字符拼成单词
                if (!stack1.isEmpty()) {
                    StringBuilder temp = new StringBuilder();
                    while (!stack1.isEmpty()) {
                        temp.append(stack1.pop());
                    }
                    list1.add(temp.toString());
                }
                // 将空格作为单独的一个元素添加到列表
                list1.add(" ");
            } else {
                // 将字符压入栈
                stack1.push(c);
            }
        }

        // 处理最后一个单词（如果有）
        if (!stack1.isEmpty()) {
            StringBuilder temp = new StringBuilder();
            while (!stack1.isEmpty()) {
                temp.append(stack1.pop());
            }
            list1.add(temp.toString());
        }

        // 拼接结果
        for (String word : list1) {
            result.append(word);
        }

        return result.toString();
    }
}

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;
public class Solution {
    //双指针
    public String ReverseSentence(String str) {
        //删除首尾空格
        String temp = str.trim();

        int j = str.length() - 1, i = j;
        StringBuilder result = new StringBuilder();
        while (i >= 0) {
            //找到第一个空格
            while (i >= 0 && temp.charAt(i) != ' ') {
                i--;
            }
            //添加单词,i会移动到下一个位置才停止，这里加1，左闭右开，j+1
            result.append(temp.substring(i + 1, j + 1) + " ");
            //跳过空格
            while (i >= 0 && temp.charAt(i) == ' ') {
                i--;
            }
            //j指向下一个开头位置
            j = i;
        }
        return result.toString().trim();
    }
}

JZ59 滑动窗口的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @param size int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        //保存结果
        ArrayList<Integer>result = new ArrayList<>();
        if (size > num.length || size == 0) {
            return result;
        }
        //当前要移除的下标
        int index = 0;
        //大顶堆,一开始大小为size-1
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2)->o2 - o1);
        for (int i = 0; i < size - 1; i++) {
            queue.offer(num[i]);
        }
        //之后每次加入一个元素，加入当前窗口最大值，移除窗口区域最后一个元素，保证窗口为size
        for (int i = size - 1; i < num.length; i++) {
            queue.offer(num[i]);
            result.add(queue.peek());
            queue.remove(num[index++]);
        }
        return result;
    }
}

搜索算法

一次过，爽，其实就是二分搜索，出现三种情况，相等就递归搜索左边和右边的加1，小于就往右边递归，大于就往左边递归，左指针大于右指针就说明没有找到

JZ53 数字在升序数组中出现的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.*;


public class Solution {
    public int dichotomy(int[] nums,int k,int left,int right){
        if(left>right){
            return 0;
        }
        int mid = (left+right)/2;
        if(nums[mid]>k){
            return dichotomy(nums,k,left,mid-1);
        }else if(nums[mid]<k){
            return dichotomy(nums,k,mid+1,right);
        }else {
            return dichotomy(nums,k,left,mid-1)+dichotomy(nums,k,mid+1,right)+1;
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param k int整型 
     * @return int整型
     */
    public int GetNumberOfK (int[] nums, int k) {
        return dichotomy(nums,k,0,nums.length-1);
    }
}

JZ11 旋转数组的最小数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int minNumberInRotateArray (int[] nums) {
        //右边的集合一定比左边的集合大
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            //中间值比右边大就找中间值到右边之间的值即可
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else if (nums[mid] > nums[right]) {
                //中间值比右边的值小，就找左边到中间值即可
                right = mid;
            } else {
                //相等说明有连续相等的，减一重新查找
                right--;
            }
        }
        return nums[left];
    }
}

JZ38 字符串的排列

严格算不重复的全排列，那么就先排序，字典输出，如果前一个字符没有使用过并且跟他相等说明当前字符也不能用来全排列（前面用过但跟他相等），剪枝，全排列就回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.*;


public class Solution {

    public void backTrack(ArrayList<String>result,
                          String str, StringBuilder temp, boolean[] isDistance, int index) {
        if (index == str.length()) {
            result.add(new String(temp));
            return;
        }
        for (int i = 0; i < str.length(); i++) {
            //访问过就不访问了
            if (isDistance[i]) {
                continue;
            }
            // 当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了
            if (i > 0 && str.charAt(i - 1) == str.charAt(i) && !isDistance[i - 1]) {
                continue;
            }
            temp.append(str.charAt(i));
            isDistance[i] = true;
            backTrack(result, str, temp, isDistance, index + 1);
            temp.deleteCharAt(temp.length() - 1);
            isDistance[i] = false;
        }
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        ArrayList<String> result = new ArrayList<String>();
        char[] chars = str.toCharArray();
        Arrays.sort(chars); // 先排序
        backTrack(result, new String(chars), new StringBuilder(),
                  new boolean[str.length()], 0);
        return result;
    }
}

JZ44 数字序列中某一位的数字

找规律，感觉好难

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int findNthDigit (int n) {
        // 确认n的位数，也就是范围
        // digit代表当前数字的位数，一开始为1位
        int digit = 1;
        // 代表当前位数内开始的数字，注意从下标0开始，那么第0位才是0，第一位就是1
        long start = 1;
        // count是当前位数区间内的总共位数
        long count = 9;
        while (n > count) {
            n -= count;
            digit++;
            start *= 10;
            count = digit * start * 9;
        }
        // 确认n所在的数字
        long num = start + (n - 1) / digit;
        // 确认n究竟是这个数字中的哪一位，输出
        return Long.toString(num).charAt((n - 1) % digit) - '0';
    }
}

动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

这里经典的就是以斐波那契数列开始，然后就是0-1背包问题，还有就是要么加上当前数值，要么以当前的数值干什么，更新状态（简单抉择）

贪心算法和动态规划是两种不同的算法设计思想，它们适用于解决不同类型的问题，且并不相互包含。

  • 贪心算法

    贪心算法（Greedy Algorithm）是一种在每一步选择中都选择当前最优解的算法思想。它的核心在于选择的局部最优解会带来全局最优解。贪心算法通常不回溯，一旦作出选择，就不再考虑其他可能性。这使得贪心算法在某些问题中非常高效，但也可能因为局部最优选择而无法得到全局最优解。

    贪心算法通常用于问题具有 贪心选择性质（即每一步选择的局部最优解不会影响全局最优解）和 最优子结构性质（问题的最优解包含其子问题的最优解）的问题。

  • 动态规划

    动态规划（Dynamic Programming, DP）是一种通过将问题分解为多个子问题来解决问题的算法思想。它通常适用于有重叠子问题和最优子结构的问题。动态规划通过存储中间结果来避免重复计算，提升算法效率。

    动态规划的核心思想包括 状态定义、状态转移方程 和 初始状态。它一般分为两种方式：自顶向下（带备忘录的递归）和 自底向上（迭代）。

    这里以斐波那契数列给出两种区别

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    //自顶向下，递归
    fun fib(n: Int, memo: IntArray): Int {
        if (n <= 1) return n
        if (memo[n] != -1) return memo[n]
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
        return memo[n]
    }

    fun main() {
        val n = 10
        val memo = IntArray(n + 1) { -1 }
        println(fib(n, memo))  // 输出：55
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    //自底向上，迭代
    fun fib(n: Int): Int {
        if (n <= 1) return n
        val dp = IntArray(n + 1)
        dp[0] = 0
        dp[1] = 1
        for (i in 2..n) {
            dp[i] = dp[i - 1] + dp[i - 2]
        }
        return dp[n]
    }

    fun main() {
        val n = 10
        println(fib(n))  // 输出：55
    }

总结

  • 贪心算法 是每一步都选择当前的最优解，但不保证全局最优。
  • 动态规划 则通过记录所有可能的情况，确保最终解是全局最优。

JZ85 连续子数组的最大和(二)

思路：

既然是连续子数组，如果我们拿到了当前的和，对于后面一个即将加入的元素，如果加上他这一串会变得更大，我们肯定会加上它，如果它自己会比加上前面这一串更大，说明从它自己开始连续子数组的和可能会更大。

那我们可以用dp数组表示以下标i为终点的最大连续子数组和，则每次遇到一个新的数组元素，连续的子数组要么加上变得更大，要么它本身就更大，因此状态转移为dp[i]=max(dp[i−1]+array[i],array[i])，这是最基本的求连续子数组的最大和。

但是题目要求需要返回长度最长的一个，我们则每次用left、right记录该子数组的起始，需要更新最大值的时候（要么子数组和更大，要么子数组和相等的情况下区间要更长）顺便更新最终的区间首尾，这样我们的区间长度就是最长的。

具体做法：

  • step 1：创建动态规划辅助数组，记录到下标i为止的最大连续子数组和，下标为0的时候，肯定等于原数组下标为0的元素。
  • step 2：准备左右区间双指针记录每次连续子数组的首尾，再准备两个双指针记录最大和且区间最长的连续子数组的首尾。
  • step 3：遍历数组，对于每个元素用上述状态转移公式记录其dp值，更新区间首尾（如果需要）。
  • step 4：出现一个最大值。且区间长度更大的时候，更新记录最长区间的双指针。
  • step 5：根据记录的最长子数组的位置取数组。

基础版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.*;
public class Solution {
    public int[] FindGreatestSumOfSubArray (int[] array) {
        //记录到下标i为止的最大连续子数组和
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int maxsum = dp[0];
        //滑动区间
        int left = 0, right = 0; 
        //记录最长的区间
        int resl = 0, resr = 0; 
        for(int i = 1; i < array.length; i++){
            right++;
            //状态转移：连续子数组和最大值
            dp[i] = Math.max(dp[i - 1] + array[i], array[i]); 
            //区间新起点
            if(dp[i - 1] + array[i] < array[i])
                left = right;
            //更新最大值
            if(dp[i] > maxsum || dp[i] == maxsum && (right - left + 1) > (resr - resl + 1)){ 
                maxsum = dp[i];
                resl = left;
                resr = right;
            }
        }
        //取数组
        int[] res = new int[resr - resl + 1];
        for(int i = resl; i <= resr; i++) 
            res[i - resl] = array[i];
        return res;
    }
}

进阶，只保存dp[i-1]即可，不用每次都保存dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        //保存历史最大值和最大区间的左边和右边的下标
        int max = array[0], maxl = 0, maxr = 0;
        //保存当前的情况的最大值和左指针和右指针,last为上次的状态，也就是dp[i-1]，temp保存临时状态
        int last = array[0], l = 0, r = 0, temp = 0;
        //动规，这里就是贪心，贪心策略是要么在原本的基础上加上这个数，要么取这个数，看哪个情况大
        for (int i = 1; i < array.length; i++) {
            //右指针右移
            r++;
            //状态转移
            temp = Math.max(array[i], last + array[i]);
            //判断区间起点是否变化
            if (array[i] > last + array[i]) {
                l = r;
            }
            //更新最大值
            if (temp > max || temp == max && (r - l + 1) > (maxr - maxl + 1)) {
                maxl = l;
                maxr = r;
                max = temp;
            }
            //更新dp[i-1]，也就是last
            last = temp;
        }
        //输出结果
        int[] result = new int[maxr - maxl + 1];
        for (int i = maxl; i <= maxr; i++) {
            result[i - maxl] = array[i];
        }
        return result;
    }
}

JZ69 跳台阶

在本子上列出来就找到规律了，首先1只能走1步到；2能走1+1，2；3能1+1+1，2+1，1+2；

4能1+1+1+1，2+1+1，1+2，1+1+2，2+2，到这里就发现了，4的时候就是3的情况上走1步和2的情况上走2步的情况可能总和，3的时候一样，1走两步和2走1步的情况总和，就是斐波那契数列的规律，2的时候变化了一下数值而已

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param number int整型
     * @return int整型
     */
    public int jumpFloor (int number) {
        int first = 1, second = 1;
        for (int i = 2; i <= number; i++) {
            int temp = first + second;
            first = second;
            second = temp;
        }
        return second;
    }
}

JZ10 斐波那契数列

first为前面第一个值，second为第二个值，每次计算first+second放到second，first变为之前的second即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int Fibonacci (int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        int first = 1, second = 1;
        for (int i = 2; i < n; i++) {
            int temp = first + second;
            first = second;
            second = temp;
        }
        return second;
    }
}

JZ71 跳台阶扩展问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param number int整型
     * @return int整型
     */
    public int jumpFloorII (int number) {
        //跟普通的跳台阶很像，但是就是不是只能1步和2步了，而是前面的可能的总和+1，因为自己永远能一步迈上去，这里result保存当前这层的结果，lastSum保存之前所有层数的可能的总和
        int lastSum = 0, result = 0;
        for (int i = 0; i < number; i++) {
            result = lastSum + 1;
            lastSum += result;
        }
        return result;
    }
}

JZ70 矩形覆盖

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

首先如果n=0，则只有0种；

如果n=1，也只有1种；

如果n=2，有横竖2种情况;

如果n=3，有3种情况;

而如果n=4，有5种情况;

由规律发现，2*n矩阵的情况数为f(n)=f(n−1)+f(n−2)，即这就是一个斐波那契数列，按照斐波那契数列的解法来即可，需要注意不同点在于n小于等于2时，都只有n种。

1
2
3
4
5
6
7
8
9
10
import java.util.*;
public class Solution {
    //总结规律，是一个斐波那契数列，可以递归，可以迭代
    public int rectCover(int target) {
        if (target <= 2) {
            return target;
        }
        return rectCover(target - 1) + rectCover(target - 2);
    }
}

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;
public class Solution {
    //迭代实现
    public int rectCover(int target) {
        if (target <= 2) {
            return target;
        }
        int first = 1, second = 2, temp = 0;
        //控制计算次数，计算3到target次
        for (int i = 2; i < target; i++) {
            temp = first + second;
            first = second;
            second = temp;
        }
        return temp;
    }
}

JZ47 礼物的最大价值

第一行和第一列只有一种走法，剩下位置就是要么从上面来，要么从左边来，判断哪种走法大就用哪种走法，保存到dp数组即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型二维数组
     * @return int整型
     */
    public int maxValue (int[][] grid) {
        // 这个以前写过类似的了，只有两种选择，要么从左边走到当前位置，要么从上面走到当前位置，每次当前位置的保存了最大值，抉择从上面来，还是从左边来就行了，记录怎么来的就回溯呗
        int[][] dp = new int[grid.length][grid[0].length];
        //先处理最左边的一列和最上面的一行，最上面的一行只能从第一个一直往右边走，最左边的一列只能从第一个一直往下面走，当然一个可以直接在遍历中根据条件处理
        //处理第一个位置
        dp[0][0] = grid[0][0];
        //处理最上面一行
        for (int j = 1; j < grid[0].length; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        //处理最左边一列
        for (int i = 1; i < grid.length; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        //处理剩下的
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                dp[i][j] = Math.max( grid[i][j] + dp[i][j - 1], grid[i][j] + dp[i - 1][j]);
            }
        }
        // for (int i = 0; i < grid.length; i++) {
        //     for (int j = 0; j < grid[0].length; j++) {
        //         if (i == 0) {
        //             if (j == 0) {
        //                 dp[i][j] = grid[i][j];
        //             } else {
        //                 dp[i][j] = grid[i][j] + dp[i][j - 1];
        //             }
        //         } else if (j == 0) {
        //             dp[i][j] = grid[i][j] + dp[i - 1][j];
        //         } else {
        //             dp[i][j] = Math.max( grid[i][j] + dp[i][j - 1], grid[i][j] + dp[i - 1][j]);
        //         }
        //     }
        // }
        //返回结果
        return dp[grid.length - 1][grid[0].length - 1];
    }
}

其实还有优化空间，只需要一维数组即可，一开始处理最上面一行，只保存一行的值，之后从第2列开始处理，第一个就是最上面的相加，第二个开始就是上面的想加还是最左边的相加，一直更新即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型二维数组
     * @return int整型
     */
    public int maxValue (int[][] grid) {
        //其实还有优化空间，只需要一维数组即可，一开始处理最上面一行，只保存一行的值，之后从第2列开始处理，第一个就是最上面的相加，第二个开始就是上面的想加还是最左边的相加，一直更新即可
        int[] dp = new int[grid[0].length];
        //处理第一个位置
        dp[0] = grid[0][0];
        //处理第一行
        for (int j = 1; j < grid[0].length; j++) {
            dp[j] = dp[j - 1] + grid[0][j];
        }
        //处理剩下的
        for (int i = 1; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (j == 0) {
                    //最左边的只能由上面下面
                    dp[j] += grid[i][j];
                } else {
                    //最左边的已经更新好，并且放在第一个，之后每次同一行上的上一个更新好的都放在了前一个，而dp当前位置上的就是上面一个位置的最优值
                    dp[j] = Math.max(dp[j - 1] + grid[i][j], dp[j] + grid[i][j]);
                }
            }
        }
        return dp[grid[0].length - 1] ;
    }
}

JZ48 最长不含重复字符的子字符串

如果对于某个前面的子串，如果我们新加入一个字符，与前面的都不重复，那么最长无重复子串肯定就是在前面的基础上加1，如果与前面重复了，那就是当前位置减去它重复之前字符出现的位置的长度。因此我们使用动态规划递推。

具体做法：

  • step 1：dp[i]表示以下标i结尾的字符串最长不含重复子串的长度，用哈希表记录是否重复出现字符，并记录其位置。
  • step 2：遍历字符串，哈希表中没有出现过的就不是重复，因此考虑dp[i]=dp[i−1]+1，即在前一个字符的基础上加上它。
  • step 3：哈希表中出现过的，这是重复的字符，考虑i−mp[s[i−1]]，但是为了防止中间出现其他重复的字符，还是应该考虑它的前一个字符的基础，因此实际转移方程为dp[i]=min(dp[i−1]+1,i−mp[s[i−1]])。
  • step 4：遍历过程中遇到的字符都要加入哈希表，同时维护最大的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public int lengthOfLongestSubstring (String s) {
        //如果对于某个前面的子串，如果我们新加入一个字符，与前面的都不重复，那么最长无重复子串肯定就是在前面的基础上加1，如果与前面重复了，那就是当前位置减去它重复之前字符出现的位置的长度。因此我们使用动态规划递推。
        //dp[i]表示以下标i结尾的字符串最长不含重复子串的长度
        int[] dp = new int[s.length()];
        //保存结果
        int result = 0;
        //保存每个字符遍历过程中出现的位置，不重复
        HashMap<Character, Integer>map = new HashMap<>();
        //遍历每个位置去更新dp数组
        for (int i = 0; i < s.length(); i++) {
            //当前字符没出现过
            if (!map.containsKey(s.charAt(i))) {
                //第一个位置特殊处理，或者dp长度一开始就+1
                if (i == 0) {
                    dp[0] = 1;
                } else {
                    dp[i] = dp[i - 1] + 1;
                }
            } else {
                //当前字符出现过就需要考虑上次出现的位置到现在出现位置的长度，还需要防止这=段之中还会出现其他重复字符，还需要考虑上一个字符的基础上出现的情况，Math.min(dp[i - 1] + 1, i - map.get(s.charAt(i))): 我们需要取上述两个值中的最小值作为 dp[i] 的值。这是因为如果 dp[i - 1] + 1 超过了 i - map.get(s.charAt(i))，说明当前的最长无重复子串已经包含了重复的字符，所以我们必须缩短子串长度。因此，必须选取较小的值以确保子串无重复。（因为哈希表保存过这个值不一定代表是上一个位置取的可能中存在这个位置，故外层的判断并不能一定保证）
                dp[i] = Math.min(dp[i - 1] + 1, i - map.get(s.charAt(i)));
            }
            //更新哈希表
            map.put(s.charAt(i), i);
            //更新最大值
            result = Math.max(result, dp[i]);
        }
        return result;
    }
}

JZ46 把数字翻译成字符串

难搞

对于普通数组1-9，译码方式只有一种，但是对于11-19，21-26，译码方式有可选择的两种方案，因此我们使用动态规划将两种方案累计。

具体做法：

  • step 1：用辅助数组dp表示前i个数的译码方法有多少种。
  • step 2：对于一个数，我们可以直接译码它，也可以将其与前面的1或者2组合起来译码：如果直接译码，则dp[i]=dp[i−1]；如果组合译码，则dp[i]=dp[i−2]。
  • step 3：对于只有一种译码方式的，选上种dp[i−1]即可，对于满足两种译码方式（10，20不能）则是dp[i−1]+dp[i−2]
  • step 4：依次相加，最后的dp[length]即为所求答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        // 处理特殊情况
        if (nums.equals("0")) {
            return 0;
        }
        //排除掉只有一种可能的情况
        if (nums.equals("10") || nums.equals("20")) {
            return 1;
        }
        //当0的前面不是1或2时，无法破译，为0
        for (int i = 1; i < nums.length(); i++) {
            if (nums.charAt(i) == '0') {
                if (nums.charAt(i - 1) != '1' && nums.charAt(i - 1) != '2') {
                    return 0;
                }
            }
        }
        //正常情况
        int[] dp = new int[nums.length() + 1];
        //初始化dp数组为1
        Arrays.fill(dp, 1);
        //开始处理
        for (int i = 2; i <= nums.length(); i++) {
            //在11-29，21-26之间的情况
            if ((nums.charAt(i - 2) == '1' && nums.charAt(i - 1) != '0') ||
                    (nums.charAt(i - 2) == '2' && nums.charAt(i - 1) > '0' &&
                     nums.charAt(i - 1) < '7')) {
                        dp[i] = dp[i-1]+dp[i-2];
            }else{
                //只能自己单独处理
                dp[i] = dp[i-1];
            }
        }
        return dp[nums.length()];
    }
}

回溯

JZ12 矩阵中的路径

每个位置作为起始点开始遍历回溯，对于每轮，传入矩阵，字符串，当前下标和当前判断字符串的位置，如果位置越界或者当前位置不等就结束（剪枝），然后当当前位置等于字符串长度就可以返回了，一开始判断了是否相等了，之后就记录当前位置的元素，后面把他赋值为一个不可能出现的字符，后面分别向左向右向上向下走递归看结果，最后把值还原并返回上下左右的结果。（这里每个位置都可以作为出发点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        for(int i = 0;i<matrix.length;i++){
            for(int j = 0;j<matrix[0].length;j++){
                if(backtrack(matrix,word,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean backtrack(char[][] matrix,String word,int i,int j,int index){

        //结束条件，越界和当前位置字符跟数组字符不一样，剪枝
        if(i>=matrix.length||i<0||j>=matrix[0].length||j<0||matrix[i][j]!=word.charAt(index)){
            return false;
        }

        //当前位置前面判断过了，当前位置一样，走到这里说明所有字符都一样，找到结果
        if(index==word.length()-1){
            return true;
        }

        //记录位置，回溯
        char temp = matrix[i][j];
        //修改位置，防止回头走到这里
        matrix[i][j] = '.';
        //开始回溯，向左向右。。。
        boolean res = backtrack(matrix,word,i-1,j,index+1)||backtrack(matrix,word,i+1,j,index+1)||backtrack(matrix,word,i,j+1,index+1)||backtrack(matrix,word,i,j-1,index+1);
        matrix[i][j] = temp;
        return res;
    }
}

JZ13 机器人的运动范围

回溯思路跟上面很像，就是先越界判断剪纸条，上面用了技巧，不用保存是否访问过，这里需要，同样传入位置，看当前位置是否满足条件，不满足返回，满足结果加1修改访问数组继续向4个方向移动，最后返回全局变量的结果就行。（需要注意的是这里访问过不能再访问，别把flags数组又修改回去）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;
public class Solution {

    int result = 0;

    public int movingCount(int threshold, int rows, int cols) {
        //标记是否走过
        boolean[][] flags = new boolean[rows][cols];
        backtrack(threshold,rows,cols,0,0,flags);
        return result;
    }

    public void backtrack(int threshold, int rows, int cols
                          , int i, int j, boolean[][] flags) {
        //越界和访问过就终止，剪枝
        if (i < 0 || i >= rows || j < 0 || j >= cols || flags[i][j]) {
            return;
        }
        //判断当前位置
        if(getSum(i)+getSum(j)>threshold){
            return;
        }
        result++;
        //回溯，走过的不能再走
        flags[i][j] = true;
        //向四个方向走
        backtrack(threshold,rows,cols,i+1,j,flags);
        backtrack(threshold,rows,cols,i-1,j,flags);
        backtrack(threshold,rows,cols,i,j+1,flags);
        backtrack(threshold,rows,cols,i,j-1,flags);
    }


    //传入一个数字，求各个数位的和
    public int getSum(int num) {
        int result = 0;
        while (num != 0) {
            result += num % 10;
            num /= 10;
        }
        return result;
    }
}

排序

JZ3 数组中重复的数字

由于题目说了，数字永远小于给定数组长度，那么就可以借助下标来完成，相同下标存在数字，那么就说明存在一样的了，可以新开一个数组搞定，题目要求on空间即可，这里学空间o1的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        int result = -1;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] != i) {
                if (numbers[numbers[i]] == numbers[i]) {
                    //说明之前存在过相同的数字
                    result = numbers[i];
                } else {
                    //numbers[i]当前数字，也是需要查找的下标，numbers[number[i]]为需要查找的数字
                    //未存在过，把当前数字放入正确的下标，交换到这里,并重新遍历这个位置，因为可能交换来的数字刚好等于当前下标
                    int temp = numbers[numbers[i]];
                    numbers[numbers[i]] = numbers[i];
                    numbers[i] = temp;
                    i--;
                }
            }
        }
        return result;
    }
}

JZ51 数组中的逆序对

经典逆序对问题，二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.util.*;


public class Solution {
    public int mod = 1000000007;
    //nums为原本数组，temp为辅助数组，start为开始排序下标，end为结束排序下标
    public int mergeSort(int[] nums, int[] temp, int start, int end) {
        if (start >= end) {
            return 0;
        }
        int mid = (start + end) / 2;
        //保存当前的res，左右两边划分合并
        int res = mergeSort(nums, temp, start, mid) + mergeSort(nums, temp, mid + 1,
                  end);
        //防止越界
        res %= mod;
        //开始合并
        int left = start, right = mid + 1, index = start;
        //左右都有元素,左边比右边大就计算逆序对
        while (left <= mid && right <= end) {
            if (nums[left] > nums[right]) {
                temp[index++] = nums[right++];
                // nums[left] 及其后面的所有元素都大于 nums[right]，计算逆序对
                res += (mid - left + 1);
                res %= mod;
            } else {
                temp[index++] = nums[left++];
            }
        }
        //只剩左边，说明这些都比右边的大，前面已经计算过这些数字的逆序对数量了，不用再计算了
        while (left <= mid) {
            temp[index++] = nums[left++];
        }
        //剩右边，右边的大，不用计算逆序对
        while (right <= end) {
            temp[index++] = nums[right++];
        }
        //将temp排好序放回原数组
        for (int i = start; i < index; i++) {
            nums[i] = temp[i];
        }
        //返回
        return res % mod;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int InversePairs (int[] nums) {
        int[] temp = new int[nums.length];
        return mergeSort(nums, temp, 0, nums.length - 1);
    }
}

JZ40 最小的K个数

top k问题，直接优先队列搞定，注意特殊测试样例即可，k就是优先队列的数量，保存最小的k个即可，一开始就填充k个，后面不断与队头比较，比他小就加入并抛出对头，那么要保证队列内队头最大，那么就是大顶堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param input int整型一维数组
     * @param k int整型
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (k != 0 && input.length != 0) {
            //新建大顶堆
            PriorityQueue<Integer>queue = new PriorityQueue<>((o1, o2)->o2 - o1);
            for (int i = 0; i < k; i++) {
                queue.offer(input[i]);
            }
            //之后剩下元素和大顶堆的最大值去比较，大的弹出，小的进去，最后堆中为最小的k个数字
            for (int i = k; i < input.length; i++) {
                if (queue.peek() > input[i]) {
                    queue.poll();
                    queue.offer(input[i]);
                }
            }

            //输出堆,不要求顺序
            for (int i = 0; i < k; i++) {
                result.add(queue.poll());
            }
        }


        return result;
    }
}

JZ41 数据流中的中位数

类似top k问题，这里是找中位数，奇数就取中间的，偶数取中间和的平均数，top k都是用优先队列解决，这里可以思考到使用两个优先队列，但是优先队列只能取头部的值，那么就要考虑两个头部值是连在一起的，并且两边数量一样多，那么就是一个大顶堆，一个小根堆，这时候为奇数怎么办，那么就要考虑有一个是多的，可以考虑统一哪个比较多，这里让大顶堆统一多。那么最后大顶堆是放偏小的数，小顶堆放偏大的数，因为我们要考虑中间的部分，而优先队列只能取头部，要让头部在中间部分就要这么存。

总体插入思路就是先加入大顶堆，每次只插入一个，那么取出头部即可，放入小顶堆，之后平衡数量，让大顶堆多一个或者平等，最后根据条件判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;


public class Solution {

    PriorityQueue<Integer>big = new PriorityQueue<Integer>(
        (o1, o2)->o2 - o1
    );

    PriorityQueue<Integer>small = new PriorityQueue<Integer>();

    public void Insert(Integer num) {
        //保证big保存较小的，small保存较大的
        big.offer(num);
        small.offer(big.poll());
        if (big.size() < small.size()) {
            big.offer(small.poll());
        }
    }

    public Double GetMedian() {
        if (big.size() > small.size()) {
            return (double)big.peek();
        } else {
            return (double)(small.peek() + big.peek()) / 2;
        }
    }


}

位运算

用位运算维护状态码，同事直呼牛X！位运算是一种非常高效的运算方式。在算法考察中比较常见，它使用位级别的操作来表示和控制状 - 掘金 (juejin.cn)

  • 与（AND）运算：只有当两个位都是1时，结果才是1（a & b）。
  • 或（OR）运算：如果两个位中至少有一个为1，那么结果就是1（a | b）。
  • 异或（XOR）运算：如果两个位不同，则结果为1（a ^ b）。
  • 非（NOT）运算：反转位的值（~a）。
  • 左移：将位向左移动，右侧填充0（a << b）。
  • 右移：将位向右移动，左侧填充0（a >> b）。

算法题每日一练—第45天：位运算在计算机内部，各种信息都必须经过数字化编码后才能被传送、存储和处理，所有的数据以二进 - 掘金 (juejin.cn)

JZ65 不用加减乘除做加法

下面博客分析了加法和减法，负数就是取反+1，+1就用加法表示就好

算法 | 如何用位运算实现加减运算？开启掘金成长之旅！这是我参与「掘金日新计划 · 12 月更文挑战」的第35天，本文主 - 掘金 (juejin.cn)

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.*;
public class Solution {
    public int Add(int num1, int num2) {
        //十进制转换为二进制的相加就是各位做异或操作，之后两数与操作左移一位得到进位值，之后异或的结果再和进位值相加，不断重复直到进位为0
        while (num2 != 0) {
            int temp = num1 ^ num2;
            num2 = (num1 & num2) << 1;
            num1 = temp;
        }
        return num1;
    }
}

JZ15 二进制中1的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int NumberOf1 (int n) {
        // 我们可以检查该数字的二进制每一位是否为1，如果遍历二进制每一位呢？可以考虑移位运算，每次移动一位就可以。至于怎么统计到1呢？我们都只知道数字1与数字相位与运算，其实只是最后一位为1就是1，最后一位为0就是0，这样我们只需要将数字1移位运算，就可以遍历二进制的每一位，再去做位与运算，结果为1的就是二进制中为1的。
        int result = 0;
        for (int i = 0; i < 32; i++) {
            //这里1<<i控制二进制下哪位为1，其余为0，那么n的这位为1才能&得到结果为1
            if ((n & (1 << i)) != 0) {
                result++;
            }
        }
        return result;
    }
}

JZ16 数值的整数次方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;
public class Solution {
    public double Power(double base, int exponent) {
        //基础数学方式解决，不用库函数的话，就是一直累乘就好，特殊情况就是幂是负数的情况，这时候底数变成分数，幂变为相反数就好
        if (exponent < 0) {
            base = 1 / base;
            exponent = -exponent;
        }

        double result = 1.0;
        for (int i = 0; i < exponent; i++) {
            result *= base;
        }
        return result;
    }
}

位运算减少时间复杂度

这里就是运用了二分法的思想，如果计算5的10次方，一直累乘就需要计算9次，如果5∗5=25(二次）、25∗25=62525∗25=625（四次）、625∗625=…625∗625=…（八次），这样时间缩短到了log2 n,

计算x的13次方的话，13 = 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0，最后可以为x^13 = x^(2^3) * x^(2^2) * x^(2^0)，也就是当某位为1才需要乘进去结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.*;
public class Solution {
    public double Power(double base, int exponent) {
        //基础数学方式解决，不用库函数的话，就是一直累乘就好，特殊情况就是幂是负数的情况，这时候底数变成分数，幂变为相反数就好
        if (exponent < 0) {
            base = 1 / base;
            exponent = -exponent;
        }
        return solve(base,exponent);
    }


    //快速幂
    public static double solve(double x,int y){
        double result = 1.0;

        while(y!=0){

            //如果 y 的当前最低位是 1（即 y 是奇数），则需要把当前的 x 乘入结果
            if((y & 1)!=0){
                result*=x;
            }

            //将 x 自己乘以自己，相当于 x^2, x^4, x^8...（逐步平方）
            x   *= x;

            //减少乘的次数   
            y = y >> 1;
        }

        return result;
    }
}

JZ56 数组中只出现一次的两个数字

  1. 利用异或特性：异或运算 (^) 有一个很好的性质：相同的数字异或后结果为0，不同的数字异或后得到的结果与这两个数之间的位差有关。因此，如果数组中只有两个数出现一次，其他数都出现两次，遍历整个数组对所有数做异或操作，结果就是这两个只出现一次的数的异或结果。
  2. 区分这两个数：得到的异或结果可以帮助我们找到这两个数在某一位上的不同，这可以用来区分这两个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型一维数组
     */
    public int[] FindNumsAppearOnce (int[] nums) {
        // 哈希表就很容易解决，直接哈希表保存每个数字出现的个数，然后遍历一次找到出现一次的即可，因为哈希表无序，最后调整两个数字的顺序即可，这里学习位运算的异或运算来解决

        //异或运算 (`^`) 有一个很好的性质：相同的数字异或后结果为0，不同的数字异或后得到的结果与这两个数之间的位差有关。因此，如果数组中只有两个数出现一次，其他数都出现两次，遍历整个数组对所有数做异或操作，结果就是这两个只出现一次的数的异或结果。
        int temp = 0;
        for (int i = 0; i < nums.length; i++) {
            temp ^= nums[i];
        }

        //下面得到a和b的异或结果，下面需要区分出a和b，但是直接区分不好区分，这里可以分为两部分来进行异或，分别得到a和b，这里找到异或结果temp的第一位为1的结果，就是a和b不同的第一个位数，这里通过1左移来实现
        int k = 1;
        while ((k & temp) == 0) {
            k <<= 1;
        }

        //之后根据这个位数分为两部分进行异或运算
        int res1 = 0, res2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & k) != 0) {
                //位数上为1的部分分到第一组
                res1 ^= nums[i];
            } else {
                res2 ^= nums[i];
            }
        }

        //调整两个数字的位置
        if (res1 < res2) {
            return new int[] {res1, res2};
        } else {
            return new int[] {res2, res1};
        }
    }
}

JZ64 求1+2+3+…+n

1
2
3
4
5
6
7
8
9
import java.util.*;
public class Solution {
    public int Sum_Solution(int n) {
        //不能乘除，那么就只能一个个加，可以递归，不为0就返回n+Sum_Solution(n-1)，为0就返回0就好，但是这里不能用if
        //这里运用了&&的短路特性，如果前面为false就不会继续运行，保证n为负数结束递归
        boolean flag = (n > 1) && ((n += Sum_Solution(n - 1)) > 0);
        return n;
    }
}

模拟

JZ29 顺时针打印矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> result = new ArrayList<>();
        int rows = matrix.length;
        if (rows == 0) {
            return result;
        }
        int cols = matrix[0].length;
        if (cols == 0) {
            return result;
        }

        int top = 0, bottom = rows - 1, left = 0, right = cols - 1;

        while (top <= bottom && left <= right) {
            // 从左到右
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            top++;

            // 从上到下
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--;

            // 确保当前还有行
            if (top <= bottom) {
                // 从右到左
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                bottom--;
            }

            // 确保当前还有列
            if (left <= right) {
                // 从下到上
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }

        return result;
    }
}

JZ61 扑克牌顺子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @return bool布尔型
     */
    public boolean IsContinuous (int[] numbers) {
        //这题只有空间复杂度O1，时间复杂度Onlogn或者时间复杂度On，空间复杂度On的做法(另外就哈希表，1-13看是否重复出现以及更新上下界看是不是上下界相差5)
        //先排序
        Arrays.sort(numbers);
        //0的数量
        int zero = 0, temp = 0;
        for (int i = 0; i < numbers.length - 1; i++) {
            if (numbers[i] == 0) {
                zero++;
            } else {
                //不允许重复
                if (numbers[i + 1] - numbers[i] == 0) {
                    return false;
                } else {
                    //间隔多少张
                    temp += numbers[i + 1] - numbers[i] - 1;
                }
            }
        }
        if (zero >= temp) {
            return true;
        }
        return false;
    }
}

其他算法

JZ49 丑数

也可以用优先队列，看乘2乘3乘5哪个未出现过就加进去优先队列，每轮取优先队列最小的一个（取index次就是正确值了），用哈希表去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;


public class Solution {
    
    //寻找三个数字中的最小值
    private int findMin(int x,int y,int z){
        int temp = Math.min(x,y);
        return Math.min(temp,z);
    }

    public int GetUglyNumber_Solution (int index) {
        // 我们都知道如果x是丑数，则2x、3x、5x都是丑数，丑数也是从1开始由每个丑数这样构建而来的，我们要做的就是找到这样前n个数，即最小的n个
        if(index==0){
            return 0;
        }
        //正常情况下保存丑数的队列
        ArrayList<Integer>result = new ArrayList<>();
        //第一个丑数为1
        result.add(1);
        //当前记录到第几个丑数
        int count = 1;
        //i,j,k分别表示本轮要乘上2，3，5的坐标
        int i = 0,j = 0,k = 0;
        while(count<index){
            //每轮放一个进去，就是每轮为count+1个，那么这里小于index的遍历次数即可
            //先找到最小的
            result.add(findMin(result.get(i)*2,result.get(j)*3,result.get(k)*5));
            count++;
            //判断由哪个乘过来的，那个位置可以继续前移了
            if(result.get(count-1)==result.get(i)*2){
                i++;
            }
            if(result.get(count-1)==result.get(j)*3){
                j++;
            }
            if(result.get(count-1)==result.get(k)*5){
                k++;
            }
        }
        return result.get(index-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.*;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        //排除0
        if(index == 0)
            return 0; 
        //要乘的因数
        int[] factors = {2, 3, 5}; 
        //去重
        HashMap<Long, Integer> mp = new HashMap<>();
        //小顶堆
        PriorityQueue<Long> pq = new PriorityQueue<>(); 
        //1先进去
        mp.put(1L, 1);
        pq.offer(1L);
        long res = 0;
        for(int i = 0; i < index; i++){ 
            //每次取最小的
            res = pq.poll(); 
            for(int j = 0; j < 3; j++){
                //乘上因数
                long next = (long)res * factors[j]; 
                //只取未出现过的
                if(!mp.containsKey(next)){  
                    mp.put(next, 1);
                    pq.offer(next);
                }
            }
        }
        return (int)res;
    }
}

JZ74 和为S的连续正数序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param sum int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> FindContinuousSequence (int sum) {
       
        //保存结果
        ArrayList<ArrayList<Integer>>result = new ArrayList<ArrayList<Integer>>();
        if(sum==0||sum==1){
            return result;
        }
        //保存当前在list中的数字
        ArrayList<Integer>temp = new ArrayList<>();
        //当前和
        int total = 0;
        //当前轮次要加的值
        int strat = 1;
        //从1开始一直加，直到加到等于或者小于且最接近目标值的时候        
        while(total<=sum){
            temp.add(strat);
            total+=strat;
            strat++;
        }
        if(total>sum&&!temp.isEmpty()){
            strat--;
            temp.remove(temp.size()-1);
            total-=strat;
        }
        //这时候temp保存最接近目标值，从1开始的序列
        for(int i = 0;i<=sum/2;i++){
            if(total==sum){
                ArrayList<Integer>possible = new ArrayList<>();
                possible.addAll(temp);
                result.add(possible);
            }
            temp.add(strat);
            total+=strat;
            if(total>sum){
                total-=temp.get(0);
                temp.remove(0);
                if(total>sum){
                    strat--;
                    total-=temp.get(temp.size()-1);
                    temp.remove(temp.size()-1);
                }
            }
            strat++;
        }
        return result;
    }
}

JZ57 和为S的两个数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
        ArrayList<Integer>result = new ArrayList<>();
        if (array.length < 2) {
            return result;
        }
        int  left = 0, right = array.length - 1;
        while (left < right) {
            if (array[left] + array[right] > sum) {
                right--;
            } else if (array[left] + array[right] < sum) {
                left++;
            } else {
                result.add(array[left]);
                result.add(array[right]);
                return result;
            }
        }
        return result;
    }
}

JZ58 左旋转字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @param n int整型
     * @return string字符串
     */
    public String LeftRotateString (String str, int n) {
        if (str.isEmpty()) {
            return "";
        }
        //实际需要移动的位数
        int real = n % str.length();
        char[] result = new char[str.length()];
        int index = 0;
        for (int i = real; i < str.length(); i++) {
            result[index++] = str.charAt(i);
        }
        for (int i = 0; i < real; i++) {
            result[index++] = str.charAt(i);
        }
        return new String(result);
    }
}

JZ62 孩子们的游戏(圆圈中最后剩下的数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    public int LastRemaining_Solution (int n, int m) {
        if (n == 0) {
            return -1; // 如果没有人，返回 -1 表示无解
        }

        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);  // 初始化0到n-1的数组
        }

        int index = 0;  // 从第0个开始
        while (list.size() > 1) {
            index = (index + m - 1) % list.size();  // 计算下一个要移除的人的下标
            list.remove(index);  // 移除这个人
        }

        return list.get(0);  // 返回最后剩下的人
    }
}

JZ75 字符流中第一个不重复的字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;
public class Solution {
    private StringBuilder s = new StringBuilder();
    private HashMap<Character, Integer>hashMap = new HashMap<>();
    //Insert one char from stringstream
    public void Insert(char ch) {
        //保存字符
        s.append(ch);
        //哈希表记录字符出现过的次数
        hashMap.put(ch, hashMap.getOrDefault(ch, 0) + 1);
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce() {
        //遍历字符串
        for (int i = 0; i < s.length(); i++) {
            //找到第一个出现次数为1的
            if (hashMap.get(s.charAt(i)) == 1) {
                return s.charAt(i);
            }
        }
        //没有找到
        return '#';
    }
}

JZ14 剪绳子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int cutRope (int n) {
        //通过对函数求导我们发现，当x=n/e的时候，也就是每段绳子的长度是n/x=n/(n/e)=e的时候乘积最大。我们知道e=2.718281828459。而题中我们的绳子剪的长度都是整数，所以不可能取e，我们只能取接近e的值，也就是3的时候乘积最大。

        //但也有例外，当n<=4的时候会有特殊情况，因为2*2>1*3。明白了这点代码就容易多了，如果n大于4，我们不停的把绳子减去3
        if (n == 2 || n == 3) {
            //必须要剪
            return n - 1;
        }
        int result = 1;
        while (n > 4) {
            n -= 3;
            result *= 3;
        }
        //4会直接乘上1到这里，其他就是乘上剩下的
        return n * result;
    }
}

去掉循环直接公式完成的话

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int cutRope (int n) {
        //通过对函数求导我们发现，当x=n/e的时候，也就是每段绳子的长度是n/x=n/(n/e)=e的时候乘积最大。我们知道e=2.718281828459。而题中我们的绳子剪的长度都是整数，所以不可能取e，我们只能取接近e的值，也就是3的时候乘积最大。

        //但也有例外，当n<=4的时候会有特殊情况，因为2*2>1*3。明白了这点代码就容易多了，如果n大于4，我们不停的把绳子减去3
        if (n == 2 || n == 3) {
            //必须要剪
            return n - 1;
        } else if (n % 3 == 0) {
            //刚好被3整除，全部剪为3
            return (int)Math.pow(3, n / 3);
        } else if (n % 3 == 1) {
            //对3求余等于1，剪出一个4，其余为3
            return 4 * (int)Math.pow(3, (n - 4) / 3);
        } else {
            //求余剩下2，检出一个2，其余为3
            return 2 * (int)Math.pow(3, n / 3);
        }
    }
}