1. 题目
https://leetcode-cn.com/problems/generate-parentheses/https://leetcode-cn.com/problems/powx-n/https://leetcode-cn.com/problems/subsets/https://leetcode.cn/problems/word-search/https://leetcode-cn.com/problems/majority-element/description/（高频老题）https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/https://leetcode-cn.com/problems/n-queens/
2. 题解
2.1 括号生成#22（中等）
class Solution {
public List<String> generateParenthesis(int n) {
//法一:递归.时间复杂度O(n*2^(2n)),空间复杂度O(n)
//要生成2n个括号，就在2n-1个括号的基础上填"("或")"
//一旦生成了2n个括号，就判断是否符合要求
List<String> ans = new LinkedList<>();
char[] current = new char[2*n];
generateAll(current, 0, ans);
return ans;
}
private void generateAll(char[] current, int index, List<String> ans) {
if (index == current.length) {
//这两个if是不能合并的，否则会影响下面的判断
if (valid(current)) {
ans.add(new String(current));
}
} else {
current[index] = '(';
generateAll(current, index + 1, ans);
current[index] = ')';
generateAll(current, index + 1, ans);
}
}
private boolean valid(char[] temp) {
int num = 0;
for (char c : temp) {
if (c == '(') {
num++;
} else if (c == ')') {
num--;
}
if (num < 0) {
return false;
}
}
return num == 0;
}
}
class Solution {
public List<String> generateParenthesis(int n) {
//法二:dfs.时间复杂度O(2^(2n)),空间复杂度O(n)
List<String> ans = new LinkedList<>();
dfs("", n, n, ans);
return ans;
}
private void dfs(String curStr, int left, int right, List<String> ans) {
if (left == 0 && right == 0) {
ans.add(curStr);
return;
}
//剪枝, 右括号剩余个数 > 左括号剩余个数时，才可以使用右括号
//那么相反的情况就得剪枝。
if (right < left) {
return;
}
//dfs
if (left > 0) {
dfs(curStr + "(", left - 1, right, ans);
}
if (right > 0) {
dfs(curStr + ")", left, right - 1, ans);
}
}
}
class Solution {
public List<String> generateParenthesis(int n) {
//法三:回溯.时间复杂度和空间复杂度见官方题解
List<String> ans = new LinkedList<>();
StringBuilder path = new StringBuilder();
dfs(path, n, n, ans);
return ans;
}
private void dfs(StringBuilder path, int left, int right, List<String> ans) {
if (left == 0 && right == 0) {
ans.add(path.toString());
return;
}
//剪枝, 右括号剩余个数 > 左括号剩余个数时，才可以使用右括号
//那么相反的情况就得剪枝。
if (right < left) {
return;
}
//注意观察回溯和dfs的区别
if (left > 0) {
path.append("(");
dfs(path, left - 1, right, ans);
path.deleteCharAt(path.length() - 1);
}
if (right > 0) {
path.append(")");
dfs(path, left, right - 1, ans);
path.deleteCharAt(path.length() - 1);
}
}
}
2.2 Pow(x, n)#50（中等）
class Solution {
public double myPow(double x, int n) {
//法一:快速幂+递归.时间复杂度O(logn),空间复杂度O(logn)
long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
private double quickMul(double x, long N) {
if (N == 0) {
return 1.0;
}
double y = quickMul(x, N / 2);
return N % 2 == 0 ? y * y : y * y * x;
}
}
class Solution {
public double myPow(double x, int n) {
//法二:快速幂+迭代.时间复杂度O(logn),空间复杂度O(1)
long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
private double quickMul(double x, long N) {
double ans = 1.0;
//贡献的初始值为x
double xContribute = x;
//在对N进行二进制拆分的同时计算答案
while (N > 0) {
if (N % 2 == 1) {
//如果N二进制表示的最低位为1，那么需要计入贡献
ans *= xContribute;
}
//将贡献不断的平方
xContribute *= xContribute;
//舍弃N二进制表示的最低位，这样每次只需要判断最低位即可
N /= 2;
//这里都不用换成真正的二进制表示法，如果是奇数，二进制的最低位一定是1.
//去掉二进制最右边的（或者说是最低位）就是右移运算，相当于除以2.
}
return ans;
}
}
2.3 子集#78（中等）
class Solution {
public List<List<Integer>> subsets(int[] nums) {
//法一:回溯.时间复杂度O(n*(2^n)),空间复杂度O(n)
List<List<Integer>> ans = new LinkedList<>();
List<Integer> temp = new LinkedList<>();
dfs(0, nums, ans, temp);
return ans;
}
private void dfs(int index, int[] nums, List<List<Integer>> ans, List<Integer> temp) {
if (index == nums.length) {
ans.add(new ArrayList<>(temp));
return;
}
temp.add(nums[index]);
dfs(index + 1, nums, ans, temp);
temp.remove(temp.size() - 1);
dfs(index + 1, nums, ans, temp);
}
}
//下面是官方题解给的比较巧妙的一种解法
class Solution {
List<Integer> t = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) {
int n = nums.length;
//一个无重复元素其个数为n的集合 的 所有子集 个数 为2^n个。
//将其化成二进制，这里会遍历这2^n个集合。
for (int mask = 0; mask < (1 << n); ++mask) {
t.clear();
for (int i = 0; i < n; ++i) {
//这里这个!=0的判断太妙了，妙到我看不懂。。。。
if ((mask & (1 << i)) != 0) {
t.add(nums[i]);
}
}
ans.add(new ArrayList<Integer>(t));
}
return ans;
}
}
单词搜索#79（中等）
2.4 多数元素#169（简单）(高频）
https://leetcode-cn.com/problems/majority-element/description/
class Solution {
public int majorityElement(int[] nums) {
//法一:哈希表:时间复杂度O(n),空间复杂度O(n)
int criticalValue = nums.length / 2;
Map<Integer, Integer> map = new HashMap<>();
int ans = nums[0];
for (int ele : nums) {
if (map.containsKey(ele)) {
map.put(ele, map.get(ele) + 1);
} else {
map.put(ele, 0);
}
if (map.get(ele) >= criticalValue) {
//一共n个数，如果必定有一个数出现次数会超过n/2，那么直接返回即可。
ans = ele;
break;
}
}
return ans;
}
}
class Solution {
public int majorityElement(int[] nums) {
//法二:排序.时间复杂度O(nlogn),空间复杂度O(logn)
//如果数组中所有元素排好序，那么下标为⌊n/2⌋的元素一定是众数
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
class Solution {
public int majorityElement(int[] nums) {
//法三:随机化.时间复杂度O(n),空间复杂度O(1)
//这个就直接看官网题解吧，比较巧妙
Random rand = new Random();
int majorityCount = nums.length / 2;
while (true) {
int candidate = nums[randRange(rand, 0, nums.length)];
if (countOccurences(nums, candidate) > majorityCount) {
return candidate;
}
}
}
private int randRange(Random rand, int min, int max) {
return rand.nextInt(max - min) + min;
}
private int countOccurences(int[] nums, int num) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}
}
class Solution {
public int majorityElement(int[] nums) {
//法四:分治.时间复杂度O(nlogn),空间复杂度O(logn)
return majorityElementRec(nums, 0, nums.length - 1);
}
private int majorityElementRec(int[] nums, int lo, int hi) {
if (lo == hi) {
return nums[lo];
}
int mid = (lo + hi) / 2;
int left = majorityElementRec(nums, lo, mid);
int right = majorityElementRec(nums, mid + 1, hi);
if (left == right) {
return left;
}
int leftCount = countInRange(nums, left, lo, hi);
int rightCount = countInRange(nums, right, lo, hi);
return leftCount > rightCount ? left : right;
}
private int countInRange(int[] nums, int num, int lo, int hi) {
int count = 0;
for (int i = lo; i <= hi; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}
}
class Solution {
public int majorityElement(int[] nums) {
//法五:摩尔投票法.时间复杂度O(n),空间复杂度O(1)
int count = 0;
Integer candidate = null;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}
2.5 电话号码的字母组合#17（中等）
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
class Solution {
Map<String, List<String>> digitToCharMap = new HashMap<>();
public List<String> letterCombinations(String digits) {
//法一:回溯.时间复杂度O(3^m * 4^n),空间复杂度O(m + n)
//m和n分别是输入的三个字母的数字个数和4个字母的数字个数
//数据初始化
digitToCharMap.put("2", Arrays.asList("a", "b", "c"));
digitToCharMap.put("3", Arrays.asList("d", "e", "f"));
digitToCharMap.put("4", Arrays.asList("g", "h", "i"));
digitToCharMap.put("5", Arrays.asList("j", "k", "l"));
digitToCharMap.put("6", Arrays.asList("m", "n", "o"));
digitToCharMap.put("7", Arrays.asList("p", "q", "r", "s"));
digitToCharMap.put("8", Arrays.asList("t", "u", "v"));
digitToCharMap.put("9", Arrays.asList("w", "x", "y", "z"));
char[] array = digits.toCharArray();
int length = digits.length();
List<String> ans = new LinkedList<>();
StringBuilder temp = new StringBuilder();
if (length == 0) {
return ans;
}
dfs(array, length, 0, ans, temp);
return ans;
}
private void dfs(char[] array, int length, int index, List<String> ans, StringBuilder temp) {
if (index == length) {
ans.add(temp.toString());
return;
}
int size = digitToCharMap.get(String.valueOf(array[index])).size();
for (int i = 0; i < size; i++) {
temp.append(digitToCharMap.get(String.valueOf(array[index])).get(i));
dfs(array, length, index + 1, ans, temp);
temp.deleteCharAt(temp.length() - 1);
}
}
}
// 法二
class Solution {
Map<String, List<String>> digitToCharMap = new HashMap<>();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return new ArrayList();
}
Map<Character, String> map = new HashMap<Character, String>();
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");
List<String> res = new LinkedList<>();
search("", digits, 0, res, map);
return res;
}
private void search(String s, String digits, int length, List<String> res, Map<Character, String> map) {
if (i == digits.length()) {
res.add(s);
return;
}
String letters = map.get(digits.charAt(i));
for (int j = 0; i j letters.length(); j++) {
search(s + letters.charAt(j), digits, i + 1, res, map);
}
}
}
2.6 N皇后#51（困难）
若有收获，就点个赞吧
0 人点赞
