221. 最大正方形
暴力法：
class Solution {
private boolean judge(char[][] matrix, int row, int col, int d) {
for (int i = row; i < row + d; i++) {
for (int j = col; j < col + d; j++) {
if (matrix[i][j] == '0') {
return false;
}
}
}
return true;
}
public int maximalSquare(char[][] matrix) {
if (matrix.length == 0) {
return 0;
}
int row = matrix.length, col = matrix[0].length;
int d = Math.min(row, col);
while (d >= 0) {
for (int i = 0; i < row - d + 1; i++) {
for (int j = 0; j < col - d + 1; j++) {
if (judge(matrix, i, j, d)) {
return d * d;
}
}
}
d--;
}
return 0;
}
}
動態(tài)規(guī)劃：
dp[i][j]代表以第i行第j列的格子作為正方形最右下頂點的正方形最大邊長覆醇。
邊界：
第一行和第一列的某個格子如果為0而账，則dp值為0。如果為1谆膳，則dp值為1皮官。
轉(zhuǎn)移方程：
matrix[i][j]如果等于1脯倒，則dp[i][j] 與它左邊，上邊捺氢，左上 三個格子有關(guān)藻丢。等于三者最小值+1。
matrix[i][j]如果等于0摄乒，則dp[i][j] = 0
class Solution {
public int maximalSquare(char[][] matrix) {
int res = 0;
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
res = Math.max(res, dp[i][0]);
}
for (int j = 0; j < n; j++) {
dp[0][j] = matrix[0][j] == '1' ? 1 : 0;
res = Math.max(res, dp[0][j]);
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == '1') {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
res = Math.max(dp[i][j], res);
}
}
}
return res * res;
}
}
222. 完全二叉樹的節(jié)點個數(shù)
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
223. 矩形面積
用兩個矩形面積相加再減去交集面積悠反。
class Solution {
private int getInter(int[] a, int[] b) {
long res = (long)Math.min(a[1], b[1]) - (long)Math.max(a[0], b[0]);
return res >= 0 ? (int)res : 0;
}
public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int[] rec1X = {A, C}, rec1Y = {B, D}, rec2X = {E, G}, rec2Y = {F, H};
return (C - A) * (D - B) + (G - E) * (H - F) - getInter(rec1X, rec2X) * getInter(rec1Y, rec2Y);
}
}
224. 基本計算器
中綴轉(zhuǎn)后綴，再用后綴求值馍佑。
class Solution {
Map<String, Integer> inPriority, outPriority;
public Solution() {
inPriority = new HashMap<>();//棧內(nèi)優(yōu)先級
outPriority = new HashMap<>();//棧外優(yōu)先級
inPriority.put("#", 0);
inPriority.put("(", 1);
inPriority.put("*", 5);
inPriority.put("/", 5);
inPriority.put("+", 3);
inPriority.put("-", 3);
inPriority.put(")", 6);
outPriority.put("#", 0);
outPriority.put("(", 6);
outPriority.put("*", 4);
outPriority.put("/", 4);
outPriority.put("+", 2);
outPriority.put("-", 2);
outPriority.put(")", 1);
}
public int calculate(String s) {
List<String> infix = new ArrayList<>();//中綴表達式
boolean flag = false;//只有遇到數(shù)字時斋否，flag才為true，避免把初始0加進去拭荤。
int num = 0;
for (char c : s.toCharArray()) {
if (c == ' ') {
continue;
} else if (Character.isDigit(c)) {
flag = true;
num = num * 10 + (c - '0');
} else {
if (flag == true) {
infix.add(String.valueOf(num));
flag = false;
num = 0;
}
infix.add(String.valueOf(c));
}
}
if (flag == true) {
infix.add(String.valueOf(num));
}
List<String> rpn = getRpn(infix);
return (int) cal(rpn);
}
//中綴表達式轉(zhuǎn)后綴
public List<String> getRpn(List<String> infix) {
Deque<String> stack = new ArrayDeque<>();
stack.push("#");
List<String> rpn = new ArrayList<>();
for (String str : infix) {
if ("(".equals(str) || ")".equals(str) || "+".equals(str) || "-".equals(str) ||
"*".equals(str) || "/".equals(str)) {
if (comparePriority(stack.peek(), str) == 1) {
stack.push(str);
} else if (comparePriority(stack.peek(), str) == 0) {
stack.pop();
} else {
while (comparePriority(stack.peek(), str) == -1) {
String z = stack.pop();
rpn.add(z);
}
if (")".equals(str)) {
stack.pop();
} else {
stack.push(str);
}
}
} else {
rpn.add(str);
}
}
while (!stack.isEmpty()) {
rpn.add(stack.pop());
}
rpn.remove(rpn.size() - 1);
return rpn;
}
private int comparePriority(String in, String out) {
if (outPriority.get(out) > inPriority.get(in)) {
return 1;
} else if (outPriority.get(out) == inPriority.get(in)) {
return 0;
} else {
return -1;
}
}
//后綴表達式求值
public double cal(List<String> s) {
Deque<Double> stack = new ArrayDeque<>();
for (int i = 0; i < s.size(); i++) {
double a, b;
if (s.get(i).equals("+")) {
b = stack.pop();
a = stack.pop();
stack.push(a + b);
continue;
} else if (s.get(i).equals("-")) {
b = stack.pop();
a = stack.pop();
stack.push(a - b);
continue;
} else if (s.get(i).equals("*")) {
b = stack.pop();
a = stack.pop();
stack.push(a * b);
continue;
} else if (s.get(i).equals("/")) {
b = stack.pop();
a = stack.pop();
stack.push(a / b);
continue;
} else {
stack.push(Double.valueOf(s.get(i)));
}
}
return stack.peek();
}
}
225. 用隊列實現(xiàn)棧
兩個隊列實現(xiàn)棧：
class MyStack {
Queue<Integer> q1, q2;
/**
* Initialize your data structure here.
*/
public MyStack() {
q1 = new LinkedList();
q2 = new LinkedList();
}
/**
* Push element x onto stack.
*/
public void push(int x) {
q1.offer(x);
while (!q2.isEmpty()) {
q1.offer(q2.poll());
}
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
}
/**
* Removes the element on top of the stack and returns that element.
*/
public int pop() {
return q2.poll();
}
/**
* Get the top element.
*/
public int top() {
return q2.peek();
}
/**
* Returns whether the stack is empty.
*/
public boolean empty() {
return q2.isEmpty();
}
}
一個隊列實現(xiàn)棧:
class MyStack {
Queue<Integer> q;
/** Initialize your data structure here. */
public MyStack() {
q = new LinkedList<>();
}
/** Push element x onto stack. */
public void push(int x) {
int size = q.size();
q.offer(x);
for (int i = 0; i < size; i++) {
q.offer(q.poll());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return q.poll();
}
/** Get the top element. */
public int top() {
return q.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return q.isEmpty();
}
}
226. 翻轉(zhuǎn)二叉樹
后序遍歷訪問根結(jié)點的時候交換左右子樹茵臭。
class Solution {
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
public TreeNode invertTree(TreeNode root) {
postOrder(root);
return root;
}
}
227. 基本計算器 II
直接復(fù)制224題了。
class Solution {
Map<String, Integer> inPriority, outPriority;
public Solution() {
inPriority = new HashMap<>();//棧內(nèi)優(yōu)先級
outPriority = new HashMap<>();//棧外優(yōu)先級
inPriority.put("#", 0);
inPriority.put("(", 1);
inPriority.put("*", 5);
inPriority.put("/", 5);
inPriority.put("+", 3);
inPriority.put("-", 3);
inPriority.put(")", 6);
outPriority.put("#", 0);
outPriority.put("(", 6);
outPriority.put("*", 4);
outPriority.put("/", 4);
outPriority.put("+", 2);
outPriority.put("-", 2);
outPriority.put(")", 1);
}
public int calculate(String s) {
List<String> infix = new ArrayList<>();//中綴表達式
boolean flag = false;
int num = 0;
for (char c : s.toCharArray()) {
if (c == ' ') {
continue;
} else if (Character.isDigit(c)) {
flag = true;
num = num * 10 + (c - '0');
} else {
if (flag == true) {
infix.add(String.valueOf(num));
flag = false;
num = 0;
}
infix.add(String.valueOf(c));
}
}
if (flag == true) {
infix.add(String.valueOf(num));
}
List<String> rpn = getRpn(infix);
return (int) cal(rpn);
}
//中綴表達式轉(zhuǎn)后綴
public List<String> getRpn(List<String> infix) {
Deque<String> stack = new ArrayDeque<>();
stack.push("#");
List<String> rpn = new ArrayList<>();
for (String str : infix) {
if ("(".equals(str) || ")".equals(str) || "+".equals(str) || "-".equals(str) ||
"*".equals(str) || "/".equals(str)) {
if (comparePriority(stack.peek(), str) == 1) {
stack.push(str);
} else if (comparePriority(stack.peek(), str) == 0) {
stack.pop();
} else {
while (comparePriority(stack.peek(), str) == -1) {
String z = stack.pop();
rpn.add(z);
}
if (")".equals(str)) {
stack.pop();
} else {
stack.push(str);
}
}
} else {
rpn.add(str);
}
}
while (!stack.isEmpty()) {
rpn.add(stack.pop());
}
rpn.remove(rpn.size() - 1);
return rpn;
}
private int comparePriority(String in, String out) {
if (outPriority.get(out) > inPriority.get(in)) {
return 1;
} else if (outPriority.get(out) == inPriority.get(in)) {
return 0;
} else {
return -1;
}
}
//后綴表達式求值
public int cal(List<String> s) {
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < s.size(); i++) {
int a, b;
if (s.get(i).equals("+")) {
b = stack.pop();
a = stack.pop();
stack.push(a + b);
continue;
} else if (s.get(i).equals("-")) {
b = stack.pop();
a = stack.pop();
stack.push(a - b);
continue;
} else if (s.get(i).equals("*")) {
b = stack.pop();
a = stack.pop();
stack.push(a * b);
continue;
} else if (s.get(i).equals("/")) {
b = stack.pop();
a = stack.pop();
stack.push(a / b);
continue;
} else {
stack.push(Integer.valueOf(s.get(i)));
}
}
return stack.peek();
}
}
228. 匯總區(qū)間
class Solution {
public List<String> summaryRanges(int[] nums) {
if (nums.length == 0) {
return new ArrayList<>();
}
List<String> res = new ArrayList<>();
int begin = 0, end = 0;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == nums[i + 1] - 1) {
end++;
} else {
if (begin == end) {
res.add(nums[begin] + "");
} else {
res.add(nums[begin] + "->" + nums[end]);
}
begin = i + 1;
end = i + 1;
}
}
if (begin == end) {
res.add(nums[begin] + "");
} else {
res.add(nums[begin] + "->" + nums[end]);
}
return res;
}
}
229. 求眾數(shù) II
時間復(fù)雜度On,空間復(fù)雜度On
class Solution {
public List<Integer> majorityElement(int[] nums) {
Set<Integer> set = new HashSet<>();
int n = nums.length / 3;
Map<Integer, Integer> map = new HashMap<>();
for (int i : nums) {
map.put(i, map.getOrDefault(i, 0) + 1);
if (map.get(i) > n) {
set.add(i);
}
}
return new ArrayList<>(set);
}
}
摩爾投票算法舅世，最多可能有兩個候選人旦委，初始都設(shè)為第一個人，不斷遍歷雏亚，如果等于第一個候選人缨硝，第一個候選人票數(shù)count1加1，如果等于第二個候選人罢低，第二個候選人票數(shù)count2加1查辩，如果count1等于0，更換第一個候選人，如果count2等于0宜岛，更換第二個候選人匀钧，如果兩個候選人的票數(shù)都不等于0且都不等于nums[i]，則兩個候選人票數(shù)都減1谬返。
最后答案可能有一個人也有可能有兩個人之斯，得把兩個候選人都判斷一下出現(xiàn)的次數(shù)才行。
時間復(fù)雜度On遣铝，空間復(fù)雜度O1:
class Solution {
public List<Integer> majorityElement(int[] nums) {
int res1 = nums[0], res2 = nums[0], count1 = 0, count2 = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == res1) {
count1++;
} else if (nums[i] == res2) {
count2++;
} else if (count1 == 0) {
res1 = nums[i];
count1 = 1;
} else if (count2 == 0) {
res2 = nums[i];
count2 = 1;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == res1) {
count1++;
} else if (nums[i] == res2) {
count2++;
}
}
List<Integer> res = new ArrayList<>();
if (count1 > nums.length / 3) {
res.add(res1);
}
if (count2 > nums.length / 3) {
res.add(res2);
}
return res;
}
}
230. 二叉搜索樹中第K小的元素
中序遍歷得到有序的集合佑刷，然后直接找到第K小的元素。
class Solution {
List<Integer> list = new ArrayList<>();
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
list.add(root.val);
inOrder(root.right);
}
public int kthSmallest(TreeNode root, int k) {
inOrder(root);
return list.get(k - 1);
}
}
