力扣labuladong一刷day7共3题

力扣labuladong一刷day7共3题"/>

力扣labuladong一刷day7共3题

力扣labuladong一刷day7共3题

文章目录

• • • 力扣labuladong一刷day7共3题
    • 一、216. 组合总和 III
    • 二、111. 二叉树的最小深度
    • 三、752. 打开转盘锁

一、216. 组合总和 III

题目链接：/
思路：还是组合只是既有n又有k。

class Solution {List<List<Integer>> arrayLists = new ArrayList<>();List<Integer> list = new ArrayList<>();int sum = 0;public List<List<Integer>> combinationSum3(int k, int n) {backTracking(k, n, 1);return arrayLists;}void backTracking(int k, int n, int index) {if (list.size() == k && sum == n) {arrayLists.add(new ArrayList<>(list));return;}if (list.size() > k) return;for (int i = index; i <= 9 && sum+i <= n; i++) {sum += i;list.add(i);backTracking(k, n, i+1);sum -= i;list.remove(list.size()-1);}}
}

二、111. 二叉树的最小深度

题目链接：/
思路：采用层序遍历。

public int minDepth(TreeNode root) {if (root == null) return 0;Deque<TreeNode> queue = new LinkedList<>();queue.add(root);int deep = 0;while (!queue.isEmpty()) {int size = queue.size();deep++;for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);if (node.left == null && node.right == null) {return deep;}}}return deep;}

三、752. 打开转盘锁

题目链接：/
思路：相当于一个点每次周围有8个点可以走，bfs。

class Solution {public int openLock(String[] deadends, String target) {Set<String> visited = new HashSet<>();Set<String> set = new HashSet<>();for (String deadend : deadends) {set.add(deadend);}Deque<String> queue = new LinkedList<>();queue.add("0000");visited.add("0000");int keep = 0;while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {String cur = queue.poll();if (cur.equals(target)) return keep;if (set.contains(cur)) continue;for (int j = 0; j < 4; j++) {String up = upOne(cur, j);if (!visited.contains(up)) {queue.add(up);visited.add(up);}String down = downOne(cur, j);if (!visited.contains(down)) {queue.add(down);visited.add(down);}}}keep++;}return -1;}String upOne(String s, int i) {char[] chars = s.toCharArray();if (chars[i] == '9') {chars[i] = '0';}else {chars[i] += 1;}return new String(chars);}String downOne(String s, int i) {char[] chars = s.toCharArray();if (chars[i] == '0'){chars[i] = '9';}else {chars[i] -= 1;}return new String(chars);}}