翻转问题

翻转数字问题

7. Reverse Integer

这道题知道原理会非常容易弄懂,值得注意是要注意溢出问题

贴上代码:

class Solution{
public:
int reverse(int x) {
        long long sum = 0;

        while (x!= 0)
        {

            sum = sum * 10 + x%10;
            if(sum>INT_MAX || sum<INT_MIN)
            {
                return 0;
            }
            x = x / 10;
        }
        return sum;
    }
};

9. Palindrome Number

题意:若数字为回文数字,则返回true,否则返回false

class Solution {
public:
    bool isPalindrome(int x) {
        if (x<0)
            return false;
        int temp = 0;
        int y =x ;
        while(y)
        {
            temp = y%10+10*temp;
            y = y / 10;
        }
        if(temp == x)
            return true;
        else return false;
    }
};

这道题不必考虑溢出问题,因为最大的回文数字没有达到溢出的范围

反转string字符串

344. Reverse String

题意即翻转字符串

代码如下:

class Solution {
public:
    string reverseString(string s) {
        int len = s.length();
        for(int i = 0;i<len/2;i++)
        {
            char temp = s[len-i-1];
            s[len-i-1] = s[i];
            s[i] = temp;
        }
        return s;
    }
};

这道题并没有什么好说的,但是还有其他翻转问题,我们以后更新

翻转链表

206. Reverse Linked List

题意即翻转链表

贴上神奇的代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr||head->next == nullptr)
            return head;

        ListNode *p= head->next;
        ListNode*n = reverseList(p);
        head->next = nullptr;
        p->next = head;
        return n;

 }
};

这道题刚开始想并没有想到(因为蠢)所以直接去百度搜到了这个答案,这个答案巧妙运用了递归方法,值得学习

接下来贴上一个不递归的方法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        while (head) {
            ListNode* next = head -> next;
            head -> next = pre;
            pre = head;
            head = next;
        } 
        return pre;
    }
};

这个代码是运用了循环原理,先生成一个临时的next量保存head指向的next,然后最后用next恢复head构成一个循环

翻转二叉树

226. Invert Binary Tree

此翻转非彼翻转

Invert a binary tree.
4
/

2 7
/ \ /

1 3 6 9

to
4
/

7 2
/ \ /

9 6 3 1

此题的基本思路是

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr)
            return nullptr;
        TreeNode*temp = root->left;
        root->left = root->right;
        root->right = temp;
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

建立一个temp临时参量将left于right保存,然后利用递归的思路,把每一个树枝都当成原来的二叉树进行递归

此方法效率很低,让我们看看一个效率更高的方法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> q;
        if(root) q.push(root);
        while (!q.empty())
        {
            auto t = q.front();
            q.pop();
            swap(t->left, t->right);
            if (t->left) q.push(t->left);
            if (t->right) q.push(t->right);
        }
        return root;
    }
};

这个思路是建立一个queue队列,然后将第一个root排第一个队,然后将root取出来成为一个t,再把root剔除队伍,剔除后再把t的两支进队

就这样不停的循环,直到最后一个元素的两支都是空,那么结束循环,返回root。

但还有另外一种改进措施(针对第一种)

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL) {
            return root;
        }
        TreeNode* temp = invertTree(root->left);
        root->left = invertTree(root->right);
        root->right = temp;
        return root;
    }
};

利用该函数返回值一定为进去的root翻转版本来设计