412. Fizz Buzz
class Solution {
public List<String> fizzBuzz(int n) {
List<String> res = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (i % 3 == 0 && i % 5 == 0) {
res.add("FizzBuzz");
} else if (i % 3 == 0) {
res.add("Fizz");
} else if (i % 5 == 0) {
res.add("Buzz");
} else {
res.add(i + "");
}
}
return res;
}
}
413. 等差数列划分
class Solution {
public int numberOfArithmeticSlices(int[] A) {
int[] dp = new int[A.length];
int res = 0;
for (int i = 2; i < A.length; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp[i] = dp[i - 1] + 1;
res += dp[i];
}
}
return res;
}
}
414. 第三大的数
class Solution {
public int thirdMax(int[] nums) {
long firstMax = Long.MIN_VALUE;
long secondMax = Long.MIN_VALUE;
long thirdMax = Long.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == firstMax || nums[i] == secondMax || nums[i] == thirdMax) {
continue;
}
if (nums[i] > firstMax) {
long temp = firstMax;
firstMax = nums[i];
thirdMax = secondMax;
secondMax = temp;
} else if (nums[i] > secondMax) {
thirdMax = secondMax;
secondMax = nums[i];
} else if (nums[i] > thirdMax) {
thirdMax = nums[i];
}
}
return thirdMax == Long.MIN_VALUE ? (int) firstMax : (int) thirdMax;
}
}
415. 字符串相加
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder res = new StringBuilder();
int carry = 0;
int k = Math.min(num1.length(), num2.length());
for (int i = 0; i < k; i++) {
int a = num1.charAt(num1.length() - i - 1) - '0';
int b = num2.charAt(num2.length() - i - 1) - '0';
int sum = a + b + carry;
carry = sum / 10;
res.append(sum % 10);
}
for (int i = k; i < num1.length(); i++) {
int a = num1.charAt(num1.length() - i - 1) - '0';
int sum = a + carry;
carry = sum / 10;
res.append(sum % 10);
}
for (int i = k; i < num2.length(); i++) {
int a = num2.charAt(num2.length() - i - 1) - '0';
int sum = a + carry;
carry = sum / 10;
res.append(sum % 10);
}
if (carry != 0) {
res.append(carry);
}
res.reverse();
return res.toString();
}
}
优化：
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder res = new StringBuilder();
int i = num1.length() - 1;
int j = num2.length() - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry != 0) {
int a = i >= 0 ? num1.charAt(i) - '0' : 0;
int b = j >= 0 ? num2.charAt(j) - '0' : 0;
int sum = a + b + carry;
carry = sum / 10;
res.append(sum % 10);
i--;
j--;
}
res.reverse();
return res.toString();
}
}
416. 分割等和子集
转化成0-1背包，先把数组的所有数之和找出来，如果为奇数，不可能有两个子数组之和相等，直接返回false。
如果为偶数，只要从数组中找到一个子数组的和为sum/2，那么就可以分割等和子集。
dp[i][j]代表数组的前i个数能否找到子集之和为j。
边界：
dp[0][j] = dp[j][0] = false
转移方程：
如果数组的某个数nums[i-1] 刚好等于j，那么dp[i][j]一定为true。
如果nums[i-1]大于j，那么dp[i][j] = dp[i-1][j]
如果nums[i-1]小于j，分两种情况，一种是选第i个数，等于dp[i-1][j-nums[i-1]]，一种是不选第i个数，等于dp[i-1][j]，只要有一个为真，那么就可以分割。
最后的答案输出dp[i][sum/2]即可。
时间复杂度O(n^2) ，空间复杂度O(n^2)。
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int i : nums) {
sum += i;
}
if (sum % 2 == 1) {
return false;
}
int n = nums.length, m = sum / 2;
boolean[][] dp = new boolean[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (nums[i - 1] == j) {
dp[i][j] = true;
} else if (nums[i - 1] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i-1]];
}
}
}
return dp[n][m];
}
}
优化，降维，降空间复杂度降到O(n)
417. 太平洋大西洋水流问题
太耗时了，待优化。
class Solution {
List<List<Integer>> res = new ArrayList<>();
int[] dirX = {1, -1, 0, 0};
int[] dirY = {0, 0, 1, -1};
boolean[][] isVisit;
boolean flag1 = false;//太平洋
boolean flag2 = false;//大西洋
private boolean dfs(int i, int j, int[][] matrix) {
if (i == 0 && j == matrix[0].length - 1) {
flag1 = true;
flag2 = true;
} else if (i == matrix.length - 1 && j == 0) {
flag1 = true;
flag2 = true;
} else if (i == 0 || j == 0) {
flag1 = true;
} else if (i == matrix.length - 1 || j == matrix[0].length - 1) {
flag2 = true;
}
if (flag1 == true && flag2 == true) {
return true;
}
isVisit[i][j] = true;
for (int flag = 0; flag < 4; flag++) {
int newI = i + dirX[flag];
int newJ = j + dirY[flag];
if (newI >= 0 && newI < matrix.length && newJ >= 0 && newJ < matrix[0].length &&
isVisit[newI][newJ] == false && matrix[newI][newJ] <= matrix[i][j] && dfs(newI, newJ, matrix) == true) {
return true;
}
}
isVisit[i][j] = false;
return false;
}
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
if (matrix.length == 0) {
return new ArrayList<>();
}
if (matrix.length == 1) {
for (int i = 0; i < matrix[0].length; i++) {
res.add(Arrays.asList(0, i));
}
return res;
}
if (matrix[0].length == 1) {
for (int i = 0; i < matrix.length; i++) {
res.add(Arrays.asList(i, 0));
}
return res;
}
isVisit = new boolean[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
for (int k = 0; k < isVisit.length; k++) {
Arrays.fill(isVisit[k], false);
}
flag1 = flag2 = false;
if (dfs(i, j, matrix) == true) {
res.add(Arrays.asList(i, j));
}
}
}
return res;
}
}
419. 甲板上的战舰
深度优先遍历，找连通块的个数。
class Solution {
boolean[][] isVisit;
int[] dirX = {0, 0, 1, -1};
int[] dirY = {1, -1, 0, 0};
private void dfs(int i, int j, char[][] board) {
isVisit[i][j] = true;
for (int flag = 0; flag < 4; flag++) {
int newI = i + dirX[flag];
int newJ = j + dirY[flag];
if (newI >= 0 && newI < board.length && newJ >= 0 && newJ < board[0].length &&
board[newI][newJ] == 'X' && isVisit[newI][newJ] == false) {
dfs(newI, newJ, board);
}
}
}
public int countBattleships(char[][] board) {
int res = 0;
if (board.length == 0) {
return 0;
}
isVisit = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == 'X' && isVisit[i][j] == false) {
dfs(i, j, board);
res++;
}
}
}
return res;
}
}
优化，只统计战舰的头部。
即遇到战舰的头部，计数加1，遇到'.'跳过，遇到战舰的身体部分（左边为'X'或者上面为'X'），跳过。
class Solution {
public int countBattleships(char[][] board) {
if (board.length == 0) {
return 0;
}
int res = 0;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == '.') {
continue;
}
if (j-1>=0 &&board[i][j - 1] == 'X') {
continue;
}
if (i - 1 >= 0 && board[i - 1][j] == 'X') {
continue;
}
res++;
}
}
return res;
}
}
421. 数组中两个数的最大异或值
class Solution {
public int findMaximumXOR(int[] nums) {
if (nums.length == 1) {
return 0;
}
int res = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
res = Math.max(res, nums[i] ^ nums[j]);
}
}
return res;
}
}
423. 从英文中重建数字
先统计每个字母出现的次数。
字母z只出现在zero中，字母w只出现在two中，字母u只出现在four中，字母x只出现在six中，字母g只出现在eight中。
字母h只出现在three和eight中，字母f只出现在five和four中，字母s只出现在seven和six中，字母i只出现在nine，five，six，eight中。
字母n只出现在one，nine，seven中。
这样就可以把每个单词出现的次数求出来了。
class Solution {
public String originalDigits(String s) {
// building hashmap letter -> its frequency
char[] count = new char[26 + (int) 'a'];
for (char letter : s.toCharArray()) {
count[letter]++;
}
// building hashmap digit -> its frequency
int[] out = new int[10];
// letter "z" is present only in "zero"
out[0] = count['z'];
// letter "w" is present only in "two"
out[2] = count['w'];
// letter "u" is present only in "four"
out[4] = count['u'];
// letter "x" is present only in "six"
out[6] = count['x'];
// letter "g" is present only in "eight"
out[8] = count['g'];
// letter "h" is present only in "three" and "eight"
out[3] = count['h'] - out[8];
// letter "f" is present only in "five" and "four"
out[5] = count['f'] - out[4];
// letter "s" is present only in "seven" and "six"
out[7] = count['s'] - out[6];
// letter "i" is present in "nine", "five", "six", and "eight"
out[9] = count['i'] - out[5] - out[6] - out[8];
// letter "n" is present in "one", "nine", and "seven"
out[1] = count['n'] - out[7] - 2 * out[9];
// building output string
StringBuilder output = new StringBuilder();
for (int i = 0; i < 10; i++)
for (int j = 0; j < out[i]; j++)
output.append(i);
return output.toString();
}
}
424. 替换后的最长重复字符
427. 建立四叉树
429. N 叉树的层序遍历
class Solution {
public List<List<Integer>> levelOrder(Node root) {
if (root == null) {
return new ArrayList<>();
}
List<List<Integer>> res = new ArrayList<>();
Queue<Node> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < size; i++) {
Node front = q.poll();
list.add(front.val);
if (front.children.size() != 0) {
for (Node n : front.children) {
q.offer(n);
}
}
}
res.add(list);
}
return res;
}
}
430. 扁平化多级双向链表
class Solution {
public Node flatten(Node head) {
if (head == null) {
return null;
}
Node cur = head;
while (cur != null) {
if (cur.child != null) {
Node next = cur.next;
Node child = flatten(cur.child);
cur.next = child;
child.prev = cur;
cur.child = null;
if (next != null) {
while (cur.next != null) {
cur = cur.next;
}
cur.next = next;
next.prev = cur;
}
}
cur = cur.next;
}
return head;
}
}
