- 26. 对称的二叉树
- 27. 顺时针打印矩阵
- 28. 包含min函数的栈
- 29. 栈的压入、弹出序列
- 30. 从上到下打印二叉树（1）
- 31. 从上到下打印二叉树（2）
- 32. 从上到下打印二叉树（3）之字形
- 33. 二叉搜索树的后序遍历序列
- 34. 二叉树中和为某一值的路径
- 35. 复杂链表的复制
- 36. 二叉搜索树与双向链表
- 37. 序列化/反序列化二叉树
- 38. 字符串的排列
- 39. 数组中出现次数超过一半的数字
- 40. 最小的k个数
- 41. 数据流中的中位数
- 42. 连续子数组的最大和
- 43. 1-n整数中1出现的次数
- 44. 数字序列中某一位的数字
- 45. 把数组排成最小的数
- 46. 把数字翻译成字符串
- 47. 礼物的最大价值
- 48. 最长不含重复字符的子字符串
- 49. 丑数
- 50. 第一个只出现一次的字符
26. 对称的二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
return isSym(root,root);
}
public boolean isSym(TreeNode rootA, TreeNode rootB){
if(rootA == null && rootB == null){
return true;
}
if(rootA == null || rootB == null){
return false;
}
if(rootA.val != rootB.val){
return false;
}
return isSym(rootA.left,rootB.right) && isSym(rootA.right,rootB.left);
}
}
27. 顺时针打印矩阵
class Solution {
int[] res;
int index = 0;
public int[] spiralOrder(int[][] matrix) {
if(matrix == null || matrix.length <= 0 || matrix[0].length <= 0){
return new int[]{};
}
int start = 0;
int rows = matrix.length;
int cols = matrix[0].length;
res = new int[rows*cols];
while(rows>start*2 && cols>start*2){
spiralOrderToInt(matrix,cols,rows,start);
start ++;
}
return res;
}
public void spiralOrderToInt(int[][] matrix,int cols,int rows,int start){
int rowEnd = rows-1-start;
int colEnd = cols-1-start;
//1.从左往右打印一行
for(int i=start; i<=colEnd; i++){
res[index] = matrix[start][i];
index ++;
}
//2.从上往下
if(start < rowEnd){
for(int i=start+1; i<=rowEnd; i++){
res[index] = matrix[i][colEnd];
index ++;
}
}
//3.从右往左
if(start<rowEnd && start<colEnd){
for(int i=colEnd-1; i>=start; i--){
res[index] = matrix[rowEnd][i];
index ++;
}
}
//4.从下往上
if(start<colEnd && start+1<rowEnd){
for(int i=rowEnd-1; i>=start+1; i--){
res[index] = matrix[i][start];
index ++;
}
}
}
}
28. 包含min函数的栈
class MinStack {
Stack<Integer> stack;
Stack<Integer> stackAssit;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack();
stackAssit = new Stack();
}
public void push(int x) {
stack.push(x);
if(stackAssit.empty() || stackAssit.peek() > x){
stackAssit.push(x);
} else {
stackAssit.push(stackAssit.peek());
}
}
public void pop() {
if(!stack.empty() && !stackAssit.empty()){
stack.pop();
stackAssit.pop();
}
}
public int top() {
return stack.peek();
}
public int min() {
return stackAssit.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.min();
*/
29. 栈的压入、弹出序列
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int i = 0;
for(int num : pushed) {
stack.push(num); // num 入栈
while(!stack.isEmpty() && stack.peek() == popped[i]) { // 循环判断与出栈
stack.pop();
i++;
}
}
return stack.isEmpty();
}
}
30. 从上到下打印二叉树（1）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int[] levelOrder(TreeNode root) {
if(root == null){
return new int[]{};
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
List<Integer> resArr = new ArrayList<Integer>();
while(!queue.isEmpty()){
TreeNode node = queue.poll();
resArr.add(node.val);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
int[] res = new int[resArr.size()];
for(int i=0; i<resArr.size(); i++){
res[i] = resArr.get(i);
}
return res;
}
}
31. 从上到下打印二叉树（2）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
List<List<Integer>> list = new ArrayList<>();
return list;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<Integer> listRow = new ArrayList<Integer>();
List<List<Integer>> list = new ArrayList<>();
int numNowLine = 1;
int numAfterLine = 0;
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
listRow.add(node.val);
numNowLine --;
if(node.left != null){
queue.offer(node.left);
numAfterLine ++;
}
if(node.right != null){
queue.offer(node.right);
numAfterLine ++;
}
if(numNowLine == 0){
list.add(listRow);
listRow = new ArrayList<Integer>();
numNowLine = numAfterLine;
numAfterLine = 0;
}
}
return list;
}
}
32. 从上到下打印二叉树（3）之字形
用了两个栈来回的方法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
List<List<Integer>> list = new ArrayList<>();
return list;
}
Stack<TreeNode> stack1 = new Stack<TreeNode>();
Stack<TreeNode> stack2 = new Stack<TreeNode>();
List<List<Integer>> list = new ArrayList<>();
stack1.push(root);
//int lines = 1;
while(!stack1.empty() || !stack2.empty()){
List<Integer> listRow = new ArrayList<Integer>();
TreeNode node;
while(!stack1.empty()){
node = stack1.pop();
listRow.add(node.val);
if(node.left != null){
stack2.push(node.left);
}
if(node.right != null){
stack2.push(node.right);
}
}
if(listRow.size() > 0){
list.add(listRow);
}
listRow = new ArrayList<Integer>();
while(!stack2.empty()){
node = stack2.pop();
listRow.add(node.val);
if(node.right != null){
stack1.push(node.right);
}
if(node.left != null){
stack1.push(node.left);
}
}
if(listRow.size() > 0){
list.add(listRow);
}
}
return list;
}
}
33. 二叉搜索树的后序遍历序列
class Solution {
public boolean verifyPostorder(int[] postorder) {
return verifySub(postorder, 0, postorder.length-1);
}
public boolean verifySub(int[] postorder, int i, int j){
if(i >= j) return true;
int p = i;
while(postorder[p] < postorder[j]) p++;
int m = p;
while(postorder[p] > postorder[j]) p++;
return p == j && verifySub(postorder, i, m - 1) && verifySub(postorder, m, j - 1);
}
}
34. 二叉树中和为某一值的路径
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/*
class Solution {
List<List<Integer>> list = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root == null){
return list;
}
LinkedList<Integer> path = new LinkedList<Integer>();
int currentSum = 0;
findPath(root,sum,path,currentSum);
return list;
}
public void findPath(TreeNode root, int sum, LinkedList<Integer> path, int currentSum){
currentSum = currentSum+root.val;
path.add(root.val);
boolean isLeaf = root.left==null && root.right==null;
if(currentSum==sum && isLeaf){
list.add(path);
path = new LinkedList<Integer>();
}
if(root.left != null){
findPath(root.left,sum,path,currentSum);
}
if(root.right != null){
findPath(root.right,sum,path,currentSum);
}
path.removeLast();
}
}*/
class Solution {
LinkedList<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
recur(root, sum);
return res;
}
void recur(TreeNode root, int tar) {
if(root == null) return;
path.add(root.val);
tar -= root.val;
if(tar == 0 && root.left == null && root.right == null)
res.add(new LinkedList(path));
recur(root.left, tar);
recur(root.right, tar);
path.removeLast();
}
}
35. 复杂链表的复制
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
if(head==null){
return null;
}
copy(head);
randomDirect(head);
return reList(head);
}
//拷贝链表
private void copy(Node head){
while(head!=null){
Node cloneNode = new Node(head.val);
Node nextNode = head.next;
head.next = cloneNode;
cloneNode.next = nextNode;
head = cloneNode.next;
}
}
//指定随机指针
private void randomDirect(Node head){
while(head!=null){
Node cloneNode = head.next;
if(head.random!=null){
Node direct = head.random;
cloneNode.random = direct.next;
}
head = cloneNode.next;
}
}
//重新连接 链表
private Node reList(Node head){
Node cloneNode = head.next;
Node cloneHead = cloneNode;
head.next = cloneNode.next;
head = head.next;
while(head!=null){
cloneNode.next = head.next;
head.next = head.next.next;
head = head.next;
cloneNode = cloneNode.next;
}
return cloneHead;
}
}
36. 二叉搜索树与双向链表
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
Node head, pre;
public Node treeToDoublyList(Node root) {
if(root==null) return null;
dfs(root);
pre.right = head;
head.left =pre;//进行头节点和尾节点的相互指向，这两句的顺序也是可以颠倒的
return head;
}
public void dfs(Node cur){
if(cur==null) return;
dfs(cur.left);
//pre用于记录双向链表中位于cur左侧的节点，即上一次迭代中的cur,当pre==null时，cur左侧没有节点,即此时cur为双向链表中的头节点
if(pre==null) head = cur;
//反之，pre!=null时，cur左侧存在节点pre，需要进行pre.right=cur的操作。
else pre.right = cur;
cur.left = pre;//pre是否为null对这句没有影响,且这句放在上面两句if else之前也是可以的。
pre = cur;//pre指向当前的cur
dfs(cur.right);//全部迭代完成后，pre指向双向链表中的尾节点
}
}
37. 序列化/反序列化二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
public String serialize(TreeNode root) {
if(root == null) return "[]";
StringBuilder res = new StringBuilder("[");
Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
if(node != null) {
res.append(node.val + ",");
queue.add(node.left);
queue.add(node.right);
}
else res.append("null,");
}
res.deleteCharAt(res.length() - 1);
res.append("]");
return res.toString();
}
public TreeNode deserialize(String data) {
if(data.equals("[]")) return null;
String[] vals = data.substring(1, data.length() - 1).split(",");
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
int i = 1;
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
if(!vals[i].equals("null")) {
node.left = new TreeNode(Integer.parseInt(vals[i]));
queue.add(node.left);
}
i++;
if(!vals[i].equals("null")) {
node.right = new TreeNode(Integer.parseInt(vals[i]));
queue.add(node.right);
}
i++;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
38. 字符串的排列
class Solution {
//为了让递归函数添加结果方便，定义到函数之外，这样无需带到递归函数的参数列表中
List<String> list = new ArrayList<>();
//同；但是其赋值依赖c，定义声明分开
char[] c;
public String[] permutation(String s) {
c = s.toCharArray();
//从第一层开始递归
dfs(0);
//将字符串数组ArrayList转化为String类型数组
return list.toArray(new String[list.size()]);
}
private void dfs(int x) {
//当递归函数到达第三层，就返回，因为此时第二第三个位置已经发生了交换
if (x == c.length - 1) {
//将字符数组转换为字符串
list.add(String.valueOf(c));
return;
}
//为了防止同一层递归出现重复元素
HashSet<Character> set = new HashSet<>();
//这里就很巧妙了,第一层可以是a,b,c那么就有三种情况，这里i = x,正巧dfs(0)，正好i = 0开始
// 当第二层只有两种情况，dfs(1）i = 1开始
for (int i = x; i < c.length; i++){
//发生剪枝，当包含这个元素的时候，直接跳过
if (set.contains(c[i])){
continue;
}
set.add(c[i]);
//交换元素，这里很是巧妙，当在第二层dfs(1),x = 1,那么i = 1或者 2， 不是交换1和1，要就是交换1和2
swap(i,x);
//进入下一层递归
dfs(x + 1);
//返回时交换回来，这样保证到达第1层的时候，一直都是abc。这里捋顺一下，开始一直都是abc，那么第一位置总共就3个交换
//分别是a与a交换，这个就相当于 x = 0, i = 0;
// a与b交换 x = 0, i = 1;
// a与c交换 x = 0, i = 2;
//就相当于上图中开始的三条路径
//第一个元素固定后，每个引出两条路径,
// b与b交换 x = 1, i = 1;
// b与c交换 x = 1, i = 2;
//所以，结合上图，在每条路径上标注上i的值，就会非常容易好理解了
swap(i,x);
}
}
private void swap(int i, int x) {
char temp = c[i];
c[i] = c[x];
c[x] = temp;
}
}
39. 数组中出现次数超过一半的数字
class Solution {
public int majorityElement(int[] nums) {
int cnt = 1;
int element = nums[0];
for(int i=1; i<nums.length; i++){
if(cnt == 0){
element = nums[i];
cnt = 1;
}
else if(nums[i] == element){
cnt ++;
} else {
cnt --;
}
}
//还可以验证一下这个是不是大于一半多的数字
return element;
}
}
40. 最小的k个数
class Solution {
/*
//用快速选择排序来实现
public int[] getLeastNumbers(int[] arr, int k) {
int[] res = new int[k];
if(arr.length <= k){
return arr;
}
if(k == 0){
return res;
}
for(int i=0; i<k; i++){
int minIndex = i;
int min = arr[i];
for(int j=i+1; j<arr.length; j++){
if(min > arr[j]){
min = arr[j];
minIndex = j;
}
}
if(minIndex != i){
arr[minIndex] = arr[i];
arr[i] = min;
}
}
for(int i=0; i<k; i++){
res[i] = arr[i];
}
return res;
}
*/
//用一个队列来维护
public int[] getLeastNumbers(int[] arr, int k) {
int[] vec = new int[k];
if (k == 0) { // 排除 0 的情况
return vec;
}
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer num1, Integer num2) {
return num2 - num1;
}
});
for (int i = 0; i < k; ++i) {
queue.offer(arr[i]);
}
for (int i = k; i < arr.length; ++i) {
if (queue.peek() > arr[i]) {
queue.poll();
queue.offer(arr[i]);
}
}
for (int i = 0; i < k; ++i) {
vec[i] = queue.poll();
}
return vec;
}
}
41. 数据流中的中位数
class MedianFinder {
Queue<Integer> A, B;
public MedianFinder() {
A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
}
public void addNum(int num) {
if(A.size() != B.size()) {
A.add(num);
B.add(A.poll());
} else {
B.add(num);
A.add(B.poll());
}
}
public double findMedian() {
return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
42. 连续子数组的最大和
动态规划
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
for(int i=1; i<nums.length; i++){
if(nums[i-1] > 0){
nums[i] = nums[i-1] +nums[i];
}
if(res < nums[i]){
res = nums[i];
}
}
return res;
}
}
43. 1-n整数中1出现的次数
class Solution {
public int countDigitOne(int n) {
int res = 0;
int cur = n%10;
int high = n/10;
int low = 0;
int digit = 1;
while(high!=0 || low!=n){
if(cur == 0){
res += high*digit;
} else if(cur == 1){
res += high*digit + low + 1;
} else{
res += (high+1)*digit;
}
low += cur*digit;
cur = high%10;
high = high/10;
digit *= 10;
}
return res;
}
}
44. 数字序列中某一位的数字
class Solution {
public int findNthDigit(int n) {
if(n == 0){
return 0;
}
int digit = 1;
long start = 1;
long count = 9;
while(n > count){
n -= count;
digit ++;
start *= 10;
count = 9*start*digit;
}
long num = start+(n-1)/digit;
return Long.toString(num).charAt((n-1)%digit)-'0';
}
}
45. 把数组排成最小的数
/*
class Solution {
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for(int i = 0; i < nums.length; i++)
strs[i] = String.valueOf(nums[i]);
fastSort(strs, 0, strs.length - 1);
StringBuilder res = new StringBuilder();
for(String s : strs)
res.append(s);
return res.toString();
}
void fastSort(String[] strs, int l, int r) {
if(l >= r) return;
int i = l, j = r;
String tmp = strs[i];
while(i < j) {
while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
tmp = strs[i];
strs[i] = strs[j];
strs[j] = tmp;
}
strs[i] = strs[l];
strs[l] = tmp;
fastSort(strs, l, i - 1);
fastSort(strs, i + 1, r);
}
}
*/
class Solution {
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for(int i = 0; i < nums.length; i++)
strs[i] = String.valueOf(nums[i]);
Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
StringBuilder res = new StringBuilder();
for(String s : strs)
res.append(s);
return res.toString();
}
}
46. 把数字翻译成字符串
class Solution {
public int translateNum(int num) {
String s = String.valueOf(num);
int dp0 = 1;
int dp1 = 1;
int res = 0;
for(int i=2; i<=s.length(); i++){
String tmp = s.substring(i-2,i);
if(tmp.compareTo("10")>=0 && tmp.compareTo("25")<=0){
res = dp0 + dp1;
} else{
res = dp1;
}
dp0 = dp1;
dp1 = res;
}
return dp1;
}
}
47. 礼物的最大价值
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
int up = 0;
int left = 0;
if(i > 0){
up = dp[i-1][j];
}
if(j > 0){
left = dp[i][j-1];
}
dp[i][j] = Math.max(up,left) + grid[i][j];
}
}
return dp[m-1][n-1];
}
}
48. 最长不含重复字符的子字符串
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> dic = new HashMap<>();
int res = 0, tmp = 0;
for(int j = 0; j < s.length(); j++) {
int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i
dic.put(s.charAt(j), j); // 更新哈希表
tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
}
return res;
}
}
49. 丑数
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int a = 0, b = 0, c = 0;
for(int i=1; i<n; i++){
int n2=dp[a]*2, n3=dp[b]*3, n5=dp[c]*5;
dp[i] = Math.min(Math.min(n2,n3),n5);
while(dp[a]*2 <= dp[i]){
a++;
}
while(dp[b]*3 <= dp[i]){
b++;
}
while(dp[c]*5 <= dp[i]){
c++;
}
}
return dp[n-1];
}
}
50. 第一个只出现一次的字符
/*写法一
class Solution {
public char firstUniqChar(String s) {
if(s.length() == 0 || s == null){
return ' ';
}
char[] arrays = s.toCharArray();
Map<Character,Boolean> map = new HashMap<>();
for(char array: arrays){
if(map.containsKey(array)){
map.put(array,false);
} else {
map.put(array,true);
}
}
for(char array: arrays){
if(map.get(array)){
return array;
}
}
return ' ';
}
}
*/
class Solution {
public char firstUniqChar(String s) {
HashMap<Character, Boolean> dic = new HashMap<>();
char[] sc = s.toCharArray();
for(char c : sc)
dic.put(c, !dic.containsKey(c));
for(char c : sc)
if(dic.get(c)) return c;
return ' ';
}
}
