257. 二叉树的所有路径
class Solution {
List<String> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
private void dfs(TreeNode root) {
if (root == null) {
return;
}
temp.add(root.val);
if (root.left == null && root.right == null) {
StringBuilder sb = new StringBuilder();
sb.append(temp.get(0));
for (int i = 1; i < temp.size(); i++) {
sb.append("->" + temp.get(i));
}
res.add(sb.toString());
}
dfs(root.left);
dfs(root.right);
temp.remove(temp.size() - 1);
}
public List<String> binaryTreePaths(TreeNode root) {
dfs(root);
return res;
}
}
258. 各位相加
class Solution {
public int addDigits(int num) {
while (num >= 10) {
int sum = 0;
while (num != 0) {
sum += num % 10;
num /= 10;
}
num = sum;
}
return num;
}
}
O(1)复杂度:
class Solution {
public int addDigits(int num) {
return (num - 1) % 9 + 1;
}
}
260. 只出现一次的数字 III
使用HashSet，时间复杂度On:
class Solution {
public int[] singleNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (set.add(nums[i]) == false) {
set.remove(nums[i]);
}
}
Iterator<Integer> it = set.iterator();
return new int[]{it.next(), it.next()};
}
}
263. 丑数
class Solution {
public boolean isUgly(int num) {
if (num <= 0) {
return false;
}
while (num % 5 == 0) {
num /= 5;
}
while (num % 3 == 0) {
num /= 3;
}
while (num % 2 == 0) {
num /= 2;
}
return num == 1;
}
}
264. 丑数 II
最小堆：
class Solution {
public int nthUglyNumber(int n) {
int[] ugly = new int[1690];
Set<Long> isVisit = new HashSet<>();
Queue<Long> heap = new PriorityQueue<>();
long curUgly, newUgly;
int[] primes = {2, 3, 5};
heap.offer(1L);
isVisit.add(1L);
for (int i = 0; i < 1690; i++) {
curUgly = heap.poll();
ugly[i] = (int) curUgly;
for (int j : primes) {
newUgly = curUgly * j;
if (!isVisit.contains(newUgly)) {
isVisit.add(newUgly);
heap.offer(newUgly);
}
}
}
return ugly[n - 1];
}
}
三指针：
class Solution {
public int nthUglyNumber(int n) {
if (n == 0) {
return 0;
}
int[] uglies = new int[n], pos = {0, 0, 0};
uglies[0] = 1;
for (int i = 1; i < n; i++) {
int a = uglies[pos[0]] * 2, b = uglies[pos[1]] * 3, c = uglies[pos[2]] * 5;
int next = Math.min(a, Math.min(b, c));
if (next == a) {
pos[0]++;
}
if (next == b) {
pos[1]++;
}
if (next == c) {
pos[2]++;
}
uglies[i] = next;
}
return uglies[n - 1];
}
}
268. 丢失的数字
容易想到的方法有排序或者使用哈希表。
下面使用异或，时间复杂度On，空间复杂度O1。
class Solution {
public int missingNumber(int[] nums) {
int res = nums.length;
for (int i = 0; i < nums.length; i++) {
res ^= nums[i] ^ i;
}
return res;
}
}
274. H 指数
class Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations);
int len = citations.length;
for (int i = len; i >= 1; i--) {
if (citations[len - i] >= i) {
return i;
}
}
return 0;
}
}
275. H 指数 II
时间复杂度On：
class Solution {
public int hIndex(int[] citations) {
int len = citations.length;
for (int i = len; i >= 1; i--) {
if (citations[len - i] >= i) {
return i;
}
}
return 0;
}
}
278. 第一个错误的版本
套模板，找到第一个满足isBadVersion(mid) == true的数。
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int lo = 1, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (isBadVersion(mid) == true) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
}
279. 完全平方数
dp[i]代表给定正整数i，最少的完全平方数之和等于i的个数。
边界：
dp[0] = 0
转移方程：
dp[i] 等于 所有 dp[i - j * j]的最小者再加1， 其中 j * j <= i。
时间 30 ms。
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
for (int j = 1; j * j <= i; j++) {
min = Math.min(min, dp[i - j * j] + 1);
}
dp[i] = min;
}
return dp[n];
}
}
优化，把dp设为静态变量，它属于整个类所有，而不是某个对象所有，即被类的所有对象共享，这样就不用每次不用重新算一遍dp数组了。
时间 8 ms。
class Solution {
static ArrayList<Integer> dp = new ArrayList<>();
public int numSquares(int n) {
//第一次进入将 0 加入
if (dp.size() == 0) {
dp.add(0);
}
//之前是否计算过 n
if (dp.size() <= n) {
//接着之前最后一个值开始计算
for (int i = dp.size(); i <= n; i++) {
int min = Integer.MAX_VALUE;
for (int j = 1; j * j <= i; j++) {
min = Math.min(min, dp.get(i - j * j) + 1);
}
dp.add(min);
}
}
return dp.get(n);
}
}
