菜到怀疑人生

0%

剑指offer下

发表于 更新于 分类于
本文字数： 16k 阅读时长 ≈ 26 分钟

前言：剑指offer下

数字在排序数组中出现的次数

二分查找

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
public class Solution {
    public int GetNumberOfK(int[] array, int k) {
        int left = 0;
        int right = array.length - 1;
        int leftK, rightK;
        // 查找
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] == k) {
                right = mid - 1;
            } else if (array[mid] < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        leftK = left;
        right = array.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] == k) {
                left = mid + 1;
            } else if (array[mid] < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        rightK = right;

        return rightK - leftK + 1;
    }
}

二叉树的深度

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        return left > right ? left + 1 : right + 1;
    }
}

平衡二叉树

判断左右节点深度是否相差1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    private boolean balance = true;

    public boolean IsBalanced_Solution(TreeNode root) {
        getDepth(root);
        return balance;
    }

    public int getDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftDepth = getDepth(node.left);
        int rightDepth = getDepth(node.right);

        if (Math.abs(leftDepth - rightDepth) > 1) {
            balance = false;
        }
        return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
    }
}

数组中只出现一次的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @author shency
 * @description: TODO
 * @date: 2019/11/26
 */
public class Solution {
    public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
        Set<Integer> set = new HashSet<>();
        for (int i : array) {
            if (set.contains(i)) {
                set.remove(i);
            } else {
                set.add(i);
            }
        }
        Iterator<Integer> iterator = set.iterator();
        num1[0] = iterator.next();
        num2[0] = iterator.next();
    }
}

和为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
/**
 * @author shency
 * @description: TODO
 * @date: 2019/11/26
 */
public class Solution {
    public ArrayList<ArrayList><Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList><Integer>> result = new ArrayList<ArrayList><Integer>>();
        int left = 1, right = 2;
        while (left < right) {
            int currentSum = (left + right) * (right - left + 1) / 2;
            if (currentSum == sum) {
                ArrayList<Integer> list = new ArrayList<Integer>();
                for (int i = left; i <= right; i++) {
                    list.add(i);
                }
                result.add(list);
                right++;
            } else if (currentSum < sum) {
                right++;
            } else {
                left++;
            }
        }
        return result;
    }
}

和为S的两个数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    int left = 0, right = array.length - 1;

    while (left < right) {
        if (array[left] + array[right] == sum) {
            result.add(array[left]);
            result.add(array[right]);
            break;
        } else if (array[left] + array[right] < sum) {
            left++;
        } else {
            right--;
        }
    }
    return result;
}

左旋转字符串

1
2
3
4
5
6
7
8
public class Solution {
    public String LeftRotateString(String str, int n) {
        if (str.length() < n) {
            return "";
        }
        return str.substring(n) + str.substring(0, n);
    }
}

翻转单词顺序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @author shency
 * @description: TODO
 * @date: 2019/11/26
 */
public class Solution {
    public String ReverseSentence(String str) {
        if (str.trim().equals("")) {
            return str;
        }
        String s[] = str.split(" ");
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = s.length - 1; i >= 0; i--) {
            stringBuilder.append(s[i]);
            stringBuilder.append(" ");
        }
        return stringBuilder.toString().trim();
    }
}

扑克牌顺子

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 boolean isContinuous(int[] numbers) {
        if (numbers == null || numbers.length < 5) {
            return false;
        }
        int max = -1;
        int min = 14;
        Set<Integer> set = new HashSet<Integer>();
        for (int i : numbers) {
            if (i != 0) {
                if (set.contains(i)) {
                    return false;
                } else {
                    set.add(i);
                    if (i < min) {
                        min = i;
                    }
                    if (i > max) {
                        max = i;
                    }
                }
            }
        }
        return (max - min) < 5;
    }
}

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

模拟约瑟夫环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        int[] array = new int[n];
        int i = -1, step = m, count = n;

        while (count > 0) {
            i++;
            if (i >= n) {
                i = 0;
            }
            if (array[i] == 1) {
                continue;
            }
            if (--step == 0) {
                array[i] = 1;
                step = m;
                count--;
            }
        }
        // 返回最后一个出局的人位置
        return i;
    }
}

数学公式：f(n,k)=(f(n-1,k)+k)%n

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return 0;
        }
        return (LastRemaining_Solution(n - 1, m) + m) % n;
    }
}

求1+2+3+…+n

1
2
3
4
5
6
public class Solution {
    public int Sum_Solution(int n) {
        int sum = (int) (Math.pow(n, 2) + n);
        return sum >> 1;
    }
}

不用加减乘除做加法

1
2
3
4
5
public class Solution {
    public int Add(int num1, int num2) {
        return Integer.sum(num1, num2);
    }
}

把字符串转换成整数

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 int StrToInt(String str) {
        if (str.equals("") || str.length() == 0) {
            return 0;
        }
        char[] arr = str.toCharArray();
        boolean negative = false;
        if (arr[0] == '-') {
            negative = true;
        }
        long sum = 0;
        int i = (arr[0] == '-' || arr[0] == '+') ? 1 : 0;
        while (i < arr.length) {
            if (arr[i] < 48 || arr[i] > 57) {
                return 0;
            }
            sum = sum * 10 + arr[i] - 48;
            i++;
        }
        sum = negative ? sum * -1 : sum;
        if (sum > Integer.MAX_VALUE || sum < Integer.MIN_VALUE) {
            return 0;
        }
        return (int) sum;
    }
}

数组中重复的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public boolean duplicate(int numbers[], int length, int[] duplication) {
        Set<Integer> set = new HashSet<Integer>();
        duplication[0] = -1;
        if (numbers == null || length == 0) {
            return false;
        }
        for (int i : numbers) {
            if (set.contains(i)) {
                duplication[0] = i;
                return true;
            }
            set.add(i);
        }
        return false;
    }
}

构建乘积数组

image-20191225000513934

先算下三角，再算上三角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int[] multiply(int[] A) {
        int len = A.length;
        int[] B = new int[len];
        B[0] = 1;
        for (int i = 1; i < len; i++) {
            B[i] = B[i - 1] * A[i - 1];
        }
        int temp = 1;
        for (int i = len - 1; i >= 0; i--) {
            B[i] *= temp;
            temp *= A[i];
        }
        return B;
    }
}

正则表达式匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        if (str == null || pattern == null) {
            return false;
        }
        Pattern p = Pattern.compile(String.valueOf(pattern));
        Matcher matcher = p.matcher(String.valueOf(str));
        return matcher.matches();
    }
}

表示数值的字符串

1
2
3
4
5
6
public class Solution {
    public boolean isNumeric(char[] str) {
        String s = String.valueOf(str);
        return s.matches("[\\+\\-]?\\d*(\\.\\d+)?([eE][\\+\\-]?\\d+)?");
    }
}

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

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
/**
 * @author shency
 * @description: TODO
 * @date: 2019/11/26
 */
public class Solution {
    private Map<Character,Integer> map = new LinkedHashMap<>();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        if(map.containsKey(ch)){
            int temp = map.get(ch) + 1;
            map.put(ch,temp);
        }else{
            map.put(ch, 1);
        }
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        for(Map.Entry<Character,Integer> entry:map.entrySet()){
            if(entry.getValue()==1){
                return entry.getKey();
            }
        }
        return '#';
    }
}

链表中环的入口结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        Set<ListNode> set = new HashSet<>();
        ListNode p1 = pHead;
        while (p1 != null) {
            if (set.contains(p1)) {
                return p1;
            }
            set.add(p1);
            p1 = p1.next;
        }
        return null;
    }
}

删除链表中重复的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        // 哨兵结点
        ListNode guard = new ListNode(0);
        guard.next = pHead;
        ListNode p1 = pHead;
        ListNode p2 = guard;
        while (p1 != null) {
            if (p1.next != null && p1.next.val == p1.val) {
                while (p1.next != null && p1.next.val == p1.val) {
                    p1 = p1.next;
                }
                p1 = p1.next;
                p2.next = p1;
            } else {
                p1 = p1.next;
                p2 = p2.next;
            }
        }
        return guard.next;
    }
}

二叉树的下一个结点

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
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) {
            return null;
        }
        /**
         * 中序遍历，左根右，一个结点中序遍历顺序的下一个结点分以下几种情况：
         * 1、有右节点，输出右结点的最左结点
         * 2、无右节点，自己是父结点的左节点，输出父节点
         * 3、无右节点，自己是父结点的右节点，将当前结点赋值为父节点并继续第二种、第三种情况的分析
         */
        if (pNode.right != null) {
            pNode = pNode.right;
            while (pNode.left != null) {
                pNode = pNode.left;

            }
            return pNode;
        }
        while (pNode.next != null) {
            if (pNode.next.left == pNode) {
                return pNode.next;
            }

            pNode = pNode.next;
        }
        return null;
    }
}

对称的二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null) {
            return true;
        }
        return compareSubtree(pRoot.left, pRoot.right);
    }

    private boolean compareSubtree(TreeNode left, TreeNode right) {
        if (left == null) {
            return right == null;
        }
        if (right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        // 递归比较，左子树的左子树与右子树的右子树 和 左子树的右子树与右子树的左子树
        return compareSubtree(left.left, right.right) && compareSubtree(left.right, right.left);
    }
}

按之字形顺序打印二叉树

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
/**
 * @author shency
 * @description: TODO
 * @date: 2019/11/26
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}

public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) {
            return result;
        }
        ArrayList<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        // 分隔符
        queue.add(null);
        queue.add(pRoot);
        boolean leftToRight = true;
        while (queue.size() != 1) {
            TreeNode node = queue.poll();
            if (node == null) {
                Iterator<TreeNode> iter = null;
                if (leftToRight) {
                    iter = queue.iterator();
                } else {
                    iter = queue.descendingIterator();
                }
                leftToRight = !leftToRight;
                while (iter.hasNext()) {
                    TreeNode temp = (TreeNode) iter.next();
                    list.add(temp.val);
                }
                result.add(new ArrayList<Integer>(list));
                list.clear();
                queue.addLast(null);
            } else {
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        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
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * @author shency
 * @description: TODO
 * @date: 2019/12/11
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) {
            return result;
        }
        ArrayList<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(null);
        queue.add(pRoot);

        while (queue.size() != 1) {
            TreeNode node = queue.poll();
            if (node == null) {
                Iterator<TreeNode> iterator = queue.iterator();
                while (iterator.hasNext()) {
                    list.add(iterator.next().val);
                }
                result.add(new ArrayList<>(list));
                queue.add(null);
                list.clear();
            } else {
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        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
26
27
28
29
30
public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null) {
            sb.append("#,");
        } else {
            sb.append(root.val + ",");
            sb.append(Serialize(root.left));
            sb.append(Serialize(root.right));
        }
        return sb.toString();
    }

    TreeNode Deserialize(String str) {
        Queue<String> queue = new LinkedList<>();
        Collections.addAll(queue, str.split(","));
        return Deserialize(queue);
    }

    private TreeNode Deserialize(Queue<String> queue) {
        String string = queue.poll();
        if (string.equals("#")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(string));
        root.left = Deserialize(queue);
        root.right = Deserialize(queue);
        return root;
    }
}

二叉搜索树的第k个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    int index = 0;
    TreeNode target = null;

    TreeNode KthNode(TreeNode pRoot, int k) {
        index = k;
        inorderTraversal(pRoot);

        return null;
    }

    public void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            if (--index == 0) {
                target = root;
            }
            inorderTraversal(root.right);
        }
    }
}

数据流中的中位数

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
public class Solution {
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });
    private int count = 0;

    public void Insert(Integer num) {
        if (count % 2 == 0) {
            maxHeap.add(num);
            int temp = maxHeap.poll();
            minHeap.add(temp);
        } else {
            minHeap.add(num);
            int temp = minHeap.poll();
            maxHeap.add(temp);
        }
        count++;
    }

    public Double GetMedian() {
        if (count % 2 == 0) {
            return (minHeap.peek() + maxHeap.peek()) / 2.0;
        } else {
            return minHeap.peek().doubleValue();
        }
    }
}

滑动窗口的最大值

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
public class Solution {
    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        ArrayList<Integer> result = new ArrayList<>();
        LinkedList<Integer> queue = new LinkedList<>();
        if (num == null || num.length == 0 || size == 0) {
            return result;
        }
        int start;
        for (int i = 0; i < num.length; i++) {
            start = i - size + 1;
            if(queue.isEmpty()){
                queue.add(i);
            }
            else if(start > queue.peekFirst()){
                queue.pollFirst();
            }
            while((!queue.isEmpty()) && num[queue.peekLast()] <= num[i]){
                queue.pollLast();
            }
            queue.add(i);
            if(start >= 0){
                result.add(num[queue.peekFirst()]);
            }
        }
        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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution {
    boolean[] flag;
    char[] matrix;
    char[] str;
    int rows;
    int cols;

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        this.matrix = matrix;
        flag = new boolean[matrix.length];
        this.str = str;
        this.rows = rows;
        this.cols = cols;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (judge(i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean judge(int i, int j, int k) {
        int index = i * cols + j;

        if (i < 0 || j < 0 || i >= rows || j >= cols || matrix[index] != str[k] || flag[index]) {
            return false;
        }
        if (k == str.length - 1) {
            return true;
        }

        flag[index] = true;

        if (judge(i - 1, j, k + 1) ||
                judge(i + 1, j, k + 1) ||
                judge(i, j - 1, k + 1) ||
                judge(i, j + 1, k + 1)) {
            return true;
        }
        flag[index] = false;
        return false;
    }
}

机器人的运动范围

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
public class Solution {
    private int threshold, rows, cols;
    private boolean[][] visited;
    
    public int movingCount(int threshold, int rows, int cols) {
        this.threshold = threshold;
        this.rows = rows;
        this.cols = cols;
        visited = new boolean[rows][cols];
        checkVisit(0, 0);
        int result = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (visited[i][j]) {
                    result += 1;
                }
            }
        }
        return result;
    }

    private void checkVisit(int i, int j) {
        if (i < 0 || j < 0 || i >= rows || j >= cols || visited[i][j]) {
            return;
        }
        if (digitSum(i) + digitSum(j) <= threshold) {
            visited[i][j] = true;
            checkVisit(i - 1, j);
            checkVisit(i + 1, j);
            checkVisit(i, j - 1);
            checkVisit(i, j + 1);
        }
    }

    private int digitSum(int num) {
        int sum = 0;
        while (num != 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

剪绳子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int cutRope(int target) {
        if (target == 2) {
            return 1;
        } else if (target == 3) {
            return 2;
        }
        int[] dp = new int[target + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= target; i++) {
            dp[i] = Math.max(dp[i - 2] * 2, dp[i - 3] * 3);
        }
        return dp[target];
    }
}
-------------本文结束感谢您的阅读-------------