剑指offer刷题（一）

秒速五厘米 2022-03-26 09:46 254阅读 0赞

【Vector、stack、queue】

[https://blog.csdn.net/u013846293/article/details/79410293][https_blog.csdn.net_u013846293_article_details_79410293]

1.二叉树深度

int height(TreeNode* pRoot){
            if(pRoot == NULL){
                return 0;
            }
            int leftlen = height(pRoot->left);
            int rightlen = height(pRoot->right);
            return leftlen > rightlen? leftlen+1 : rightlen+1;
        }

2.输入一棵二叉树，判断该二叉树是否是平衡二叉树。（注意中英文括号和变量名）

class Solution {
    public:   
        int height(TreeNode* pRoot){
            if(pRoot == NULL){
                return 0;
            }
            int leftlen = height(pRoot->left);
            int rightlen = height(pRoot->right);
            return leftlen > rightlen? leftlen+1 : rightlen+1;
        }
        bool IsBalanced_Solution(TreeNode* pRoot) {
            if(pRoot == NULL)
                return 1;
            int left_len = height(pRoot->left);
            int right_len = height(pRoot->right);
            if((left_len - right_len > 1)||(left_len - right_len < -1))
                return 0;
            else
                return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);       
        }
    };

3.一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。

class Solution {
    public:
        void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {     
            int temp = 0;
    
            int len = sizeof(data) / sizeof(data[0]);
            for(int i = 0; i<len; i++){
                temp = temp ^ data[i];
            }
            int j = 0;
            while(((temp >> j )& 1) != 1){
                j++;  
            }
            int k1 = 0;
            int k2 = 0;
            for(int i = 0;i < len;i++){
                if(((data[i] >> j) &1) == 0){
                    num1[k1++] = data[i];
                }else{
                    num2[k2++] = data[i];             
                }  
            }
            temp=0;
            for(int i = 0; i< k1; i++){
                temp = temp ^ num1[i];
            }
            num1[0] = temp;
            temp=0;
            for(j = 0 ; j< k2; j++){
                temp = temp ^ num2[j];
            }
            num2[0] = temp;  
        }
            
    };

4.在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：找出最右上角的元素，如果此整数为右上元素，返回True;此整数>右上元素，删除行；否则删除列（删除用动态的”指针“指向表示）

# -*- coding:utf-8 -*-
    class Solution:
        # array 二维列表
        def Find(self, target, array):
            # write code here
            #列
            
            cols = len(array[0])
            rows = len(array)
            if(cols == 0 or rows == 0):
                return False
            if(target < array[0][0] or target > array[rows-1][cols-1]):
                return False
    
            row = 0
            col = cols - 1
            
            while(row < rows and col >= 0):
                if array[row][col] == target:
                    return True
                elif array[row][col] < target:
                    row += 1
                else:
                    col -= 1
            return False

5.请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路：创建一个新字符串，当前串不为空格直接添加到新串，否则将%20加入新串

# -*- coding:utf-8 -*-
    class Solution:
        # s 源字符串
        def replaceSpace(self, s):
            # write code here
            a=""
            for i in s:
                if i != ' ':
                    a += i
                else:
                    a += "%20"
            return a

6.(python)输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

思路：列表实现栈

# -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        # 返回从尾部到头部的列表值序列，例如[1,2,3]
        def printListFromTailToHead(self, listNode):
            # write code here
            a = []
            b = []
            if not listNode:
                return b
            p = listNode
            while p:
                a.append(p.val)
                p = p.next
            while a:
                b.append(a.pop())
            return b

7.输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

思路：先序递归

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # 返回构造的TreeNode根节点
        def reConstructBinaryTree(self, pre, tin):
            # write code here
            
            if len(pre)== 0:
                return None
            T = TreeNode(pre[0]) 
            i = tin.index(pre[0])
            T.left = self.reConstructBinaryTree(pre[1:i+1],tin[:i])
            T.right = self.reConstructBinaryTree(pre[i+1:],tin[i+1:])     
            return T

8.用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思路：

入队 判断s1是否为空，空将s2压入s1，压栈到s1；否则直接压栈到s1

出队 判断s2是否为空，空将s1压入s2，s2出栈；否则直接出栈

居然还需要自己写类属性s1，s2

# -*- coding:utf-8 -*-
    class Solution:
        def __init__(self):
            self.s1 = []
            self.s2 = []
        def push(self, node):
            # write code here
            if  self.s1:
                self.s1.append(node)
            else:
                while self.s2:
                    self.s1.append(self.s2.pop())
                self.s1.append(node)
        def pop(self):
            if not self.s2:
                while self.s1:
                    self.s2.append(self.s1.pop())
            return self.s2.pop()
            # return xx

9.把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

思路：找到第一个比array\[0\]小的元素即可

# -*- coding:utf-8 -*-
    class Solution:
        def minNumberInRotateArray(self, rotateArray):
            # write code here
            if len(rotateArray) == 0:
                return 0
            for i in rotateArray:
                if(i < rotateArray[0]):
                    j = rotateArray.index(i)
                    return rotateArray[j]

10.大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

n<=39

思路：用两个变量暂存中间值（非递归），f(2),f(n) 计算n-1次range（1，n）

# -*- coding:utf-8 -*-
    class Solution:
        def Fibonacci(self, n):
            # write code here
            if(n == 0):
                return 0
            if(n == 1):
                return 1
            Fibonacci0 = 0
            Fibonacci1 = 1     
            for i in range(1,n):
                Fibonacci = Fibonacci0 + Fibonacci1
                Fibonacci0 = Fibonacci1
                Fibonacci1 = Fibonacci
            return Fibonacci

11.一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

思路：递归(考虑到复杂的 不使用递归)

1级跳1种

2级跳2种（1，1；2）

3级 ：第一次条1级，剩下的3-1级有n1种跳法；第一次跳2级，剩下的3-2级有n2种跳法

n级别：F(n-1)+F(n-2)

# -*- coding:utf-8 -*-
    class Solution:
        def jumpFloor(self, number):
            # write code here 
            if(number <= 0):
                return 0
            if(number == 1):
                return 1   
            if(number == 2):
                return 2
            floor1 = 1;
            floor2 = 2
            for i in range(2,number):
                floor =floor1+ floor2
                floor1 = floor2
                floor2 = floor
            return floor

12.我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？

思路：

竖着1块，剩下f（n-1）

横着2快，剩下f（n-2）

递归的思想

# -*- coding:utf-8 -*-
    class Solution:
        def rectCover(self, number):
            # write code here
            if(number == 1):
                return 1
            if(number == 2):
                return 2
            temp1 = 1
            temp2 = 2
            temp = 0
            for i in range(2,number):
                temp = temp1 + temp2
                temp1 = temp2
                temp2 = temp
            return temp

13.输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

思路：一个数-1 与 原数字相比 只是将原数字最右边1的（含）右边的所有二进制取反，所以计算二进制1的个数也就是这样操作的个数

不太明白n<0 为何python 写成 n=n&0xFFFF

# -*- coding:utf-8 -*-
    class Solution:
        def NumberOf1(self, n):
            # write code here
            count = 0   
            if n<0:
                n = n & 0xffffffff
            while n:
                count += 1
                n = n & (n - 1)
            return count

14.给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

思路：base为0 Fasle   exponent<0   1/(base\*\*exponent) 否则 base\*\*exponent)

考虑到别的编程语言，\*\* 利用for计算

# -*- coding:utf-8 -*-
    class Solution:
        def Power(self, base, exponent):
            # write code here
            if base ==  0:
                return False  
            
            ret = 1
            exp = abs(exponent)    
            for i in range(exp):
                ret *= base
            if exponent <0:
                return 1/ret
            else:
                return ret

或者利用python的指数运算\*\*

# -*- coding:utf-8 -*-
    class Solution:
        def Power(self, base, exponent):
            # write code here
            if base ==  0:
                return False  
            return base**exponent

15.在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组\{2,3,1,0,2,5,3\}，那么对应的输出是第一个重复的数字2。

思路：数字是0-n-1，联想到哈希表，将数组近似重排：0索引放0,1索引放1....遇到索引和元素不同的，交换，直到发现重复数字，while(numbers\[i\] != i)\{     ------------不能用if

class Solution {
    public:
        // Parameters:
        //        numbers:     an array of integers
        //        length:      the length of array numbers
        //        duplication: (Output) the duplicated number in the array number
        // Return value:       true if the input is valid, and there are some duplications in the array number
        //                     otherwise false
        bool duplicate(int numbers[], int length, int* duplication) {
            int t = 0,temp = 0;
            if(length <= 0 || duplication == NULL)
                return false;
            
            for( int i = 0;i < length;i++){
                
                while(numbers[i] != i){
                    t = numbers[i];
                    if(numbers[t] == t){
                        *duplication = t;
                        return true;
                    }
                    temp = numbers[t];
                    numbers[t] = numbers[i];
                    numbers[i] = temp;     
                }          
            }
            
        return false;
        }
    };
    
    //O（n）
    class Solution {
    public:
        // Parameters:
        //        numbers:     an array of integers
        //        length:      the length of array numbers
        //        duplication: (Output) the duplicated number in the array number
        // Return value:       true if the input is valid, and there are some duplications in the array number
        //                     otherwise false
        bool duplicate(int numbers[], int length, int* duplication) {
            int temp = 0;
            if(length <= 0 || duplication == NULL)
                return false;
            
            for( int i = 0;i < length;i++){
                
                while(numbers[i] != i){
                    if(numbers[i] == numbers[numbers[i]]){
                        *duplication = numbers[numbers[i]];
                        return true;
                    }
                    temp = numbers[i];
                    numbers[i] = numbers[temp];
                    numbers[temp] = temp;     
                }          
            }
            
        return false;
        }
    };

fun（int \*t）\{

\*t=8；

不修改数组找出重复数字：（创建辅助数组，1——n 无重复数字应该有n个数，二分查找，统计区间数据个数）

int getDuplication(const int *numbers,int length)
    {
        if(numbers == NULL || length <= 0)
            return -1;
        int start = 1;
        int end = length - 1;
        while(end >= start ){
        int middle =  ((end - start) >> 1) + start;
        int count = countRange(numbers,length,start,end);
        if(end == start){
            if(count > 1)
                return start;
            else
                break;
        }
    
    }
    
    
    }

16.从上往下打印出二叉树的每个节点，同层节点从左至右打印。

/*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };*/
    class Solution {
    public:
        vector<int> PrintFromTopToBottom(TreeNode* root) {
            queue<TreeNode *> nodequeue;
            vector<int> node;
            if(root == NULL){
                return node;
            }else{
                nodequeue.push(root);
            }
            while(!nodequeue.empty()){
                TreeNode* p = nodequeue.front();
                nodequeue.pop();
                node.push_back(p->val);
                if(p->left){
                    nodequeue.push(p->left);             
                }
                if(p->right){
                    nodequeue.push(p->right);                
                }
            }
          return node; 
        }
    };

17:题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路：

输入空字符串返回空；

输入只有1个字符的串直接返回；

abc ---》sort().....................

a   bc全排列

b  ac全排列

c  ab全排列

连接首字母+子串全排列

# -*- coding:utf-8 -*-
    class Solution:
        def Permutation(self, ss):
            str = [];
            if ss == []:
                return
            if len(ss)==1:
                return ss
            str = list(ss)
            str.sort()   
            pstr =[]
            for i in range(len(str)):
                if i>0 and str[i] == str[i-1]:
                    continue
                temp = self.Permutation(''.join(str[:i])+''.join(str[i+1:]))
                for j in temp:
                    pstr.append(str[i]+j)                
            return pstr
                
            # write code here

[https_blog.csdn.net_u013846293_article_details_79410293]: https://blog.csdn.net/u013846293/article/details/79410293