题目：
求一个树的最小深度。
思路：
思路一：递归
class Solution {
public:
int run(TreeNode *root)
{
if(root == nullptr) return 0;
if(root->left == nullptr) // 若左子树为空，则返回右子树的最小深度+1
{
return run(root->right)+1;
}
if(root->right == nullptr) // 若右子树为空，则返回左子树的最小深度+1
{
return run(root->left)+1;
}
// 左右子树都不为空时，取较小值
int leftDepth = run(root->left);
int rightDepth = run(root->right);
return (leftDepth<rightDepth)?(leftDepth+1):(rightDepth+1);
}
};
思路二：层序遍历，找到的第一个叶节点的深度即是最小深度。
class Solution {
public:
typedef TreeNode* tree;
int run(TreeNode *root) {
//采用广度优先搜索，或者层序遍历，找到的第一个叶节点的深度即是最浅。
if(! root) return 0;
queue<tree> qu;
tree last,now;
int level,size;
last = now = root;
level = 1;qu.push(root);
while(qu.size()){
now = qu.front();
qu.pop();
size = qu.size();
if(now->left)qu.push(now->left);
if(now->right)qu.push(now->right);
if(qu.size()-size == 0)break;
if(last == now){
level++;
if(qu.size())last = qu.back();
}
}
return level;
}
};
------------------------------------------------------------------------------------------------------------------------------------------
题目
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
思路
用栈，遇数字则进栈，遇符号则出栈栈顶两数字并将计算结果进栈，最终栈中的结果即为所求。
import java.util.Stack;
public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<Integer>();
for(int i = 0;i<tokens.length;i++){
try{
int num = Integer.parseInt(tokens[i]);
stack.add(num);
}catch (Exception e) {
int b = stack.pop();
int a = stack.pop();
stack.add(get(a, b, tokens[i]));
}
}
return stack.pop();
}
private int get(int a,int b,String operator){
switch (operator) {
case "+":
return a+b;
case "-":
return a-b;
case "*":
return a*b;
case "/":
return a/b;
default:
return 0;
}
}
}
--------------------------------------------------------------------------
题目
用O(nlogn)的时间复杂度和O(1)的空间复杂度对链表进行排序。
思路
因为题目要求复杂度为O(nlogn),故可以考虑归并排序的思想。
归并排序的一般步骤为：
1）将待排序数组（链表）取中点并一分为二； 2）递归地对左半部分进行归并排序； 3）递归地对右半部分进行归并排序；4）将两个半部分进行合并（merge）,得到结果
所以对应此题目，可以划分为三个小问题：
1）找到链表中点 （快慢指针思路，快指针一次走两步，慢指针一次走一步，快指针在链表末尾时，慢指针恰好在链表中点）；
2）写出merge函数，即如何合并链表。
3）写出mergesort函数，实现上述步骤。
class Solution {
public:
ListNode* findMiddle(ListNode* head){
ListNode* chaser = head;
ListNode* runner = head->next;
while(runner != NULL && runner->next != NULL){
chaser = chaser->next;
runner = runner->next->next;
}
return chaser;
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == NULL){
return l2;
}
if(l2 == NULL){
return l1;
}
ListNode* dummy = new ListNode(0);
ListNode* head = dummy;
while(l1 != NULL && l2 != NULL){
if(l1->val > l2->val){
head->next = l2;
l2 = l2->next;
}
else{
head->next = l1;
l1 = l1->next;
}
head = head->next;
}
if(l1 == NULL){
head ->next = l2;
}
if(l2 == NULL){
head->next = l1;
}
return dummy->next;
}
ListNode* sortList(ListNode* head) {
if(head == NULL || head ->next == NULL){
return head;
}
ListNode* middle = findMiddle(head);
ListNode* right = sortList(middle->next);
middle -> next = NULL;
ListNode* left = sortList(head);
return mergeTwoLists(left, right);
}
};
---------------------------------------------------------------------------------
题目
用插入排序法排序链表。
思路
public class Solution {
public ListNode insertionSortList(ListNode head) {
//哑节点
ListNode dumy = new ListNode(Integer.MIN_VALUE);
ListNode cur = head;
ListNode pre = dumy;
while (cur != null) {
//保存当前节点下一个节点
ListNode next = cur.next;
pre = dumy;
//寻找当前节点正确位置的一个节点
while (pre.next != null && pre.next.val < cur.val) {
pre = pre.next;
}
//将当前节点加入新链表中
cur.next = pre.next;
pre.next = cur;
//处理下一个节点
cur = next;
}
return dumy.next;
}
}
----------------------------------------------------------------------------------------------------------------------
啥特喵的，不刷了好难...............................................