【leetcode】部分思路整理

题目：

求一个树的最小深度。

思路：

思路一：递归

若为空树返回0；

若左子树为空，则返回右子树的最小深度+1；（加1是因为要加上根这一层，下同）

若右子树为空，则返回左子树的最小深度+1；

若左右子树均不为空，则取左、右子树最小深度的较小值，+1；

class Solution {

public:

    int run(TreeNode *root)

    {

        if(root == nullptr) return ;

        if(root->left == nullptr) // 若左子树为空，则返回右子树的最小深度+1

        {

            return run(root->right)+;

        }

        if(root->right == nullptr) // 若右子树为空，则返回左子树的最小深度+1

        {

            return run(root->left)+;

        }

        // 左右子树都不为空时，取较小值

        int leftDepth = run(root->left);

        int rightDepth = run(root->right);

        return (leftDepth<rightDepth)?(leftDepth+):(rightDepth+);

    }

};

思路二：层序遍历，找到的第一个叶节点的深度即是最小深度。

class Solution {

public:

    typedef TreeNode* tree;

    int run(TreeNode *root) {

        //采用广度优先搜索，或者层序遍历，找到的第一个叶节点的深度即是最浅。

      if(! root) return ;

      queue<tree> qu;

      tree last,now;

      int level,size;

      last = now = root;

      level = ;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 == )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();

        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;

    }

}

----------------------------------------------------------------------------------------------------------------------
啥特喵的，不刷了好难...............................................

巴特西

【leetcode】部分思路整理

最新文章

热门文章