1 汉诺塔难点

1.主题材料陈说

在一个二维数组中,每风姿罗曼蒂克行都遵从从左到右依次增加的相继排序,每一列都根据从上到下递增的逐条排序。请完毕一个函数,输入那样的二个二维数组和多少个整数,推断数组中是还是不是带有该整数。 

public class Solution {
    public boolean Find(int target, int [][] array) {
        int row = 0;
        int column = array[0].length-1;
        while(row<array.length && column>=0){
            if(array[row][column]==target)
                return true;
            if(array[row][column]>target)
                column--;
            else
                row++;
        }
        return false;
    }
}

11. 二进制中1的个数

  • 输入二个卡尺头,输出该数二进制表示中1的个数。当中负数用补码表示。

// Solution:位运算
// Tips:整数右移一位与整数除以二在数学上等价,但除法效率很低
// (1)如果整数右移一位,再与1做与运算判断最后一位是不是1,负数会造成死循环
// (2)因此,采用整数与1按位与,然后把1左移1位,再按位与...
// (3)把一个整数减去1,再和原整数按位与,会将最右边的1变成0;所以一个整数的二进制有多少1,就可进行多少次操作。
class Solution {
public:
     int  NumberOf1(int n) {
         /*(2)
         int count = 0;
         unsigned int flag = 1;
         while (flag) {
             if (n & flag) {
                 count ++;
             }
             flag = flag << 1;
         }
         return count;*/
         // (3)
         int count = 0;
         while(n) {
             count ++;
             n = n & (n-1);
         }
         return count;
     }
};

2 Joseph环

2.标题叙述

请完成一个函数,将多个字符串中的空格替换到“%20”。比如,当字符串为We Are
Happy.则经过替换之后的字符串为We%20Are%20Happy。

public static String replaceSpace(StringBuffer str) {
        StringBuffer sb = new StringBuffer();
        String tmp = new String(str);
        for (int i = 0; i < tmp.length(); i++) {
            if(tmp.charAt(i) == ' ')
                sb.append("%20");
            else
                sb.append(tmp.charAt(i));

        }
        return new String(sb);
    }

12. 数值的整数14遍方

  • 给定三个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

// Solution: 需要考虑多种边界条件,以及使用斐波那契乘方、位运算提高循环乘法效率
// Tips:(1)考虑指数<=0,小于0时需要先求|e|,再求倒数,此时要求base!=0;
//      (2)e=0时,0^0没有意义,可考虑输出1或0;
//      (3)double/float浮点数判断相等,不使用==,|做差|<sigma;

class Solution {
public:
    bool gInvalidInput = false;

    double Power(double base, int exponent) {
        gInvalidInput = false;

        // 判断指数e<0时,底数base是否等于0.0
        if (exponent <= 0 && (equal(base, 0.0))) {
            gInvalidInput = true;
            return 0.0;
        }

        // 判断指数e<0时,需要求-e,并计算指数结果后求倒数
        unsigned int absExponent = (unsigned int)exponent;
        if (exponent < 0) {
            absExponent = (unsigned int)(-exponent);
        }

        double result = PowerWithUnsignedExponent(base, absExponent);
        if (exponent < 0)
            result = 1.0 / result;
        return result;
    }

    bool equal(double num1, double num2) {
        if ((num1 - num2 < 0.0000001) && (num1 - num2 > -0.0000001))
            return true;
        else
            return false;
    }

    double PowerWithUnsignedExponent(double base, unsigned int exponent) {
        /* 效率较低的循环乘法
        double res = 1.0;
        for (int i=1; i <= exponent; i ++) {
            res *= base;
        }*/

        // 使用a^n公式及位运算:
        // (1)n为偶数,a^n = a^(n/2) * a^(n/2)
        // (2)n为奇数,a^n = a^((n-1)/2) * a^((n-1)/2) * a
        if (exponent == 0)
            return 1;
        if (exponent == 1)
            return base;

        double res = PowerWithUnsignedExponent(base, exponent >> 1);
        res *= res;
        if (exponent & 0x1 == 1)
            res *= base;
        return res;
    }        
};

《剑指offer面试题12:打字与印刷1到最大的n位数》
(1卡塔尔大数用字符串表示,最前补0;
(2卡塔尔国递归打字与印刷0~9的全排列。
(3卡塔尔国特殊输入如0,-1等供给思量。

《剑指offer面试题13:在O(1)时间删除链表结点》给定单向链表头指针和二个结点指针,删除该结点
(1卡塔尔国O(n)依次找到要去除结点的前叁个结点, 改革pNext;
(2卡塔 尔(英语:State of Qatar)O(1)复制下四个结点,删除下二个结点,尾结点费时(另需考虑仅多个结点卡塔 尔(英语:State of Qatar),时间复杂度=[(n-1)*O(1)+O(n)]/n=O(1)。

3 求“斐波纳契数列:1,1,2,3,5,8,13,21…”函数:递归与非递归

3.标题陈述

输入三个链表,从尾到头打字与印刷链表每一个节点的值。

package com.lxc.tet;

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<ListNode> stack = new Stack<ListNode>();
        while (listNode != null) {
            stack.push(listNode);
            listNode = listNode.next;
        }
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        while (!stack.isEmpty())
            arrayList.add(stack.pop().val);
        return arrayList;
    }
}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

13. 调治数组顺序使奇数位于偶数前面(注意erase时,iterator需求扭转卡塔 尔(英语:State of Qatar)

  • 输入三个整数数组,实现贰个函数来调整该数组中数字的相继,使得全体的奇数位于数组的前半部分,全部的偶数位于位于数组的后半有些,并保证奇数和奇数,偶数和偶数之间的相对地点不改变

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        if (array.size() == 0) {
            return;
        }
        vector<int> right;
        vector<int>::iterator itArray;
        for (itArray = array.begin(); itArray != array.end(); itArray ++) {
            if (isEven(*itArray)) {
                right.push_back(*itArray);
                array.erase(itArray);
                itArray --; // 因为删除vector元素后,循环itArray++会导致跳过访问一个元素,以及后续访问溢出
            }
        }
        vector<int>::iterator itRight;
        for (itRight = right.begin(); itRight != right.end(); itRight++) {
            array.push_back(*itRight);
        }
    }
    // 解耦判断条件
    bool isEven(int n) {
        return !(n & 1);
    }
};

4 判定三个数是或不是是 2的幂次数:

4.主题素材陈诉

输入某二叉树的前序遍历和中序遍历的结果,请重新建立出该二叉树。假使输入的前序遍历和中序遍历的结果中都不含重复的数字。比如输入前序遍历体系{1,2,4,7,3,5,6,8}和中序遍历类别{4,7,2,1,5,3,8,6},则重新建立二叉树并回到。

import java.util.Arrays;

public class Solution {
    public BinaryTreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre == null||in == null)
            return null;
        //新建二叉树根节点
        BinaryTreeNode root = new BinaryTreeNode();
        //遍历中序遍历
        for (int i = 0; i < in.length; i++) {
            //如果当前元素等于前序遍历的第一个元素
            if(in[i] == pre[0]){
                root.val = in[i];
                System.out.println(root.val);
                root.leftNode = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1),Arrays.copyOfRange(in, 0, i));
                root.rightNode = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length),Arrays.copyOfRange(in, i+1, in.length));
            }
        }
        return root;
    }
}
class BinaryTreeNode {
    int val;
    BinaryTreeNode leftNode;
    BinaryTreeNode rightNode;
}

14. 链表中的倒数第k个结点

  • 输入二个链表,输出该链表中尾数第k个结点。

// Tips:(1)pListHead==NULL; (2)unsigned int k==0时, k-1是4294967295; (3)链表个数<k.
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if (pListHead == NULL || k == 0) {//k==0时,不返回,unsigned int会导致循环崩溃
            return NULL;
        }

        ListNode* pAhead = pListHead;
        ListNode* pBehind = pListHead;
        for (unsigned int i=0; i < k-1; i ++) {
            if (pAhead->next != NULL) {//链表个数小于k时
                pAhead = pAhead->next;
            } else {
                return NULL;
            }
        }

        while (pAhead->next != NULL) {
            pAhead = pAhead->next;
            pBehind = pBehind->next;
        }
        return pBehind;
    }
};

5 计算四个整数的二进制数的 1的个数num

5.难点汇报

用五个栈来落成二个连串,完毕队列的Push和Pop操作。
队列中的元素为int类型。

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty())
                stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
}

 

15. 反转链表

  • 输入三个链表,反转链表后,输出链表的全数因素。

// Solution:使用三个指针pPrev,pNode,pNext完成反转
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* pPrev = NULL;
        ListNode* pNode = pHead;
        // ListNode* pReverseHead = NULL;  
        while (pNode != NULL) {
            ListNode* pNext = pNode->next;
            // if (pNext == NULL) {
            //     pReverseHead = pNode;
            // } 
            pNode->next = pPrev;
            pPrev = pNode;
            pNode = pNext;
        }
        // return pReverseHead;
        return pPrev;
    }
};

6
输入一个板寸数组,调度数组中数字的相继,使得全数奇数位于数组的前半有的,全体偶数位于数组的后半局地。要求时间复杂度为O(n)。
—-像这种供给时间复杂度的 平日供给调换的算法

7.难题陈说

我们都掌握斐波那契数列,以往供给输入一个整数n,请你输出斐波那契数列的第n项。

n<=39,在数学上,斐波纳契数列以如下被以
递归的秘技定义:F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)

递归法:

public class Solution {
    public int fibonacci(int n) {
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        return fibonacci(n-1)+fibonacci(n-2);
    }
}

 迭代法:(动态规划卡塔 尔(英语:State of Qatar)

public int Fibonacci(int n) {
    int preOne = 0;
    int preTwo = 1;
    int result = 0;
    if(n==0)
        return preOne;
    if(n==1)
        return preTwo;
    for(int i=2;i<=n;i++){
        result = preOne+preTwo;
        preOne = preTwo;
        preTwo = result;
    }
    return result;
} 

===========================================================================================

8.标题陈说

输入八个卡尺头,输出该数二进制表示中1的个数。当中负数用补码表示。

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n!=0){
            count++;
            n=n&(n-1);
        }
        return count;
    }
}

1 汉诺塔难点

9.主题素材陈说

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

public class Solution {
    public double Power(double base, int exponent) {
        if(exponent==0)
            return 1;
        if(exponent==1)
            return base;
        double result=1.0;
        int len = exponent<0?-exponent:exponent;
        for(int i=0;i<len;i++)
            result*=base;
        return exponent<0?1.0/result:result;
  }
}

//第风华正茂,把X上的n-1个盘通过Z移动到Y。

10.难题讲述

叁只青蛙一回能够跳上1级台阶,也能够跳上2级。求该引体向上上叁个n级的阶梯总共有稍稍种跳法。

public int JumpFloor(int target) {
        if(target<=0)
            return 0;
        if(target==1)
            return 1;
        if(target==2)
            return 2;
        int result=0;
        int preOne=1;
        int preTwo=2;
        for(int i=2;i<target;i++){
            result=preOne+preTwo;
            preOne=preTwo;
            preTwo=result;
        }
        return result;    
    }

第二,把X上的最下边包车型地铁盘移到Z。
//第三,因为n-1个盘全在Y上了,所以把Y当作X重复以上步骤就好了。递归中会保存数据

11.标题陈说

贰只青蛙一遍能够跳上1级台阶,也足以跳上2级……它也能够跳上n级。求该青蛙跳上三个n级的阶梯总共有个别许种跳法。

//跳到n级有2n-1种跳法
public class Solution {
    public int JumpFloorII(int target) {
        if(target==0)
            return 0;
        if(target==1)
            return 1;
        int result=1;
        for(int i=1;i<target;i++)
            result*=2;
        return result;
    }
}

 或者:

public int JumpFloorII(int target) {
    return 1<<(target-1);
}

12.标题陈诉

作者们得以用2*1的小矩形横着如故竖着去隐讳越来越大的矩形。请问用n个2*1的小矩形无重叠地蒙蔽二个2*n的大矩形,总共有稍许种方法?

public class Solution {
    public int RectCover(int target) {
        if(target==0)
            return 0;
        if(target==1)
            return 1;
        int result = 0;
        int one = 0;
        int two = 1;
        for(int i=0;i<target;i++){
            result=one+two;
            one=two;
            two=result;
        }
        return result;
    }
}
void moveNext( char pre, char next )
{
    cout<<pre<<"-->"<<next<<endl;
}
void hanio(int n,char XBlock,char YBlock,char ZBlock)
{
    if(n==1)
    {
        moveNext(XBlock,ZBlock);
    }
    else
    {
        hanio(n-1,XBlock,ZBlock,YBlock);
        moveNext(XBlock,ZBlock);
        hanio(n-1,YBlock,XBlock,ZBlock);
    }
}

13.难点呈报

输入三个整数数组,达成贰个函数来调节该数组中数字的依次,使得全部的奇数位于数组的前半有的,全数的偶数位于位于数组的后半局地,并保证奇数和奇数,偶数和偶数之间的周旋地点不改变。

public class Solution {
    public void reOrderArray(int [] array) {
        int temp=0;
        for(int i=0;i<array.length-1;i++){
            for(int j=0;j<array.length-1-i;j++){
               if(array[j+1]%2==1 && array[j]%2==0){
                    temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;              
                }    
            }                        
        }
    }
}

2 Joseph环

14.标题叙述

输入三个链表,输出该链表中尾数第k个结点。

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null||k==0)
            return null;
        ListNode p1=head;
        ListNode p2=null;
        for(int i=0;i<k-1;++i){
            if(p1.next!=null)
                p1=p1.next;
            else
                return null;
        }
        p2=head;
        while(p1.next!=null){     
            p1=p1.next;
            p2=p2.next;
        }
        return p2;
    }
}
class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}

率先创造多个首尾相继的循环链表,for循环定义计算器,抵达m更改链表的总是关系。

15.标题陈述

输入一个链表,反转链表后,输出链表的享有因素。

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null)
            return null;
        ListNode temp=null;
        ListNode pre=null;
        ListNode current=head;
        ListNode reverse=null;
        while(current!=null){
            temp=current.next;
            current.next=pre;
            pre=current;
            if(temp==null)
                reverse=current;
            current=temp;
        }
        return reverse;
    }
}
class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}

结束 最终剩下一个结点,pre=purnode。

16.主题素材陈诉

输入三个干燥依次增加的链表,输出三个链表合成后的链表,当然我们须求合成后的链表满意单调不减法则。

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null)
            return list2;
        if(list2==null)
            return list1;
        ListNode list3 = null;
        if(list1.val<list2.val){
            list3=list1;
            list3.next=Merge(list1.next,list2);
        }else{
            list3=list2;
            list3.next=Merge(list1,list2.next);
        }  
        return list3;
    }
}
class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
typedef struct node 
{
    int num;
    struct node *next;
}LinkNode;

LinkNode * create_link( int num )
{
    LinkNode *p,*current,*head;   // p用来循环,current用来记录当前的位置。head(第一个数)用来返回一个链表
    p=(LinkNode*)malloc(sizeof(LinkNode));
    p->num=1;
    p->next=NULL;
    head=p;
    current=p;
    for(int i=2;i<=num;i++)
    {
        //生成新的结点---建立连接----转移到下一个
        p=(LinkNode*)malloc(sizeof(LinkNode));
        p->num=i;
        p->next=NULL;
        current->next=p;
        current=p;
    }
    current->next=head;     //链表的rail指向head,构成循环(循环列表list)。
    return head;
}
void make_play( LinkNode *link,int mcode )
{
    assert(link!=NULL&&mcode!=0);
    LinkNode *pLink=link,*pPre=NULL;   //错误:要给pre赋值才能使用。
    LinkNode *pDelte;                  //删除节点---free标记结点)
    cout<<"亲,游戏开始了!"<<endl;
    while(pLink!=pPre)           //最后只留一个元素。
    {
        for(int n=1;n<mcode;n++)
        {
            pPre=pLink;
            pLink=pLink->next;
        }
        pDelte=pLink;
        cout<<"出列的是"<<pDelte->num<<endl;
        pPre->next=pLink->next;
        pLink=pPre->next;
        free(pDelte);
    }
    cout<<"最后出列的是:"<<pLink->num<<endl;
}

17.标题陈诉

输入两棵二叉树A,B,判别B是还是不是A的子结构。(ps:大家约定空树不是随意一个树的子结构卡塔尔

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean result=false;
        if(root1!=null && root2!=null){
            if(root1.val==root2.val){
                result=doesTree1HaveTreee2(root1,root2);
                if(!result)
                    result=HasSubtree(root1.left,root2);
                if(!result)
                    result=HasSubtree(root1.right,root2);
            }
        }
        return result;
    }
    boolean doesTree1HaveTreee2(TreeNode root1,TreeNode root2){
        if(root2==null)
            return true;
        if(root1==null)
            return false;
        if(root1.val!=root2.val)
            return false;
        return doesTree1HaveTreee2(root1.left,root2.left) && doesTree1HaveTreee2(root1.right,root2.right);
    }
}
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

3 求“斐波纳契数列:1,1,2,3,5,8,13,21…”函数:递归与非递归

18.标题描述

操作给定的二叉树,将其转换为源二叉树的镜像。

import java.util.Stack;
public class Solution {
    public void Mirror(TreeNode root) {
        if(root==null || (root.left==null && root.right==null))
            root=null;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode temp = null;
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                temp=root.left;
                root.left=root.right;
                root.right=temp;
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            root=root.right;
        }
    }
}
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

 

重大正是 最初化退出规范卡塔 尔(英语:State of Qatar)和循环条件转移递归关系卡塔 尔(阿拉伯语:قطر‎的三个转移的涉嫌。

int fib( int n )
{
    /*if(n==1||n==2)
    {
    return 1;
    }
    else
    {
    return fib(n-1)+fib(n-2);
    }*/
    if(n<=2)
    {
        return 1;
    }
    int valN1,valN2,sumN;         //是不是可以写成static形式的
    valN1=1;
    valN2=1;
    //sum ,n1,n2往后移动位置
    for(int i=1;i<=n-2;i++)      //计算的次数
    {
        sumN=valN1+valN2;
        valN2=valN1;
        valN1=sumN;
    }
    return sumN;
}

4 剖断一个数是还是不是是 2的幂次数:0==(a[i]&(a[i]-1)

int find2power( int a[] ,int len)
{
    int count=0;
    for(int i=0;i<len;i++)
    {
        if(0==(a[i]&(a[i]-1)))
        {
            count++;
        }
    }
    cout<<count<<endl;
    return count;
}

5 计算贰个寸头的二进制数的 1的个数num

计算叁个子弹头的二进制数的 1的个数:
num&1(叁回计算最左边的十分数值是不是是1)

int num1OfBinery( int num )
{
    int count=0;
    while(num)
    {
        if(num&1)
        {
            count++;
        }
        num>>=1;   //向右移动,除以2
    }
    return count;
}

6
输入一个平头数组,调度数组中数字的相继,使得全数奇数位于数组的前半部分,全数偶数位于数组的后半部分。必要时间复杂度为O(n)。

—像这种必要时间复杂度On卡塔 尔(英语:State of Qatar)的
日常必要沟通的算法:增多三个总结当前遇见的奇数个要素的mark标志标记下二个遇上的奇数应该插入的岗位卡塔 尔(阿拉伯语:قطر‎,遇到奇数的话—swapi,mark卡塔 尔(阿拉伯语:قطر‎

void swapElement( int arr[], int i, int mark )
{
    int tmp;
    tmp=arr[i];
    arr[i]=arr[mark];
    arr[mark]=tmp;
}
void printArrray( int arr[], int num )
{
    cout<<"输出的数组是:"<<endl;
    for(int i=0;i<num;i++)
    {
        cout<<arr[i]<<endl;
    }
}
// 两个变量:一个i遍历数组,另一个标记需要的位置 有几个奇数符合条件的,排在前几位)
//1 找到第一个,判断移动  2 循环
void partition( int arr[],int num )
{
    int i=0,mark=0;
    while(i<num&&(arr[i]&1==0))  //找到第一个奇数:= while +if(break)
    {
        i++;
    }
    if(i==num)                //全是偶数
        return;
    swapElement(arr,i,mark);
    i++;
    mark++;
    while(i<num)
    {
        if((arr[i]&1)==1)
        {
            swapElement(arr,i,mark);
            mark++;
            printArrray(arr,num);
        }
        i++;
    }
    printArrray(arr,num);
}

===========================================================================

测量检验的代码:

/*
    int n;
    printf("请输入要移动的块数:");
    scanf("%d",&n);
    hanio(n,'X','Y','Z');*/
    int num=7;
    //cout<<fib(num)<<endl;
    LinkNode *head=create_link(num);
    make_play(head,5);
    int arr[]={1,2,3,4,5,6,7,8,16,50};
    int len=sizeof(arr)/sizeof(int);
    find2power(arr,len);
    /*int num=7;
    cout<<num1OfBinery(num)<<endl;*/
    /*int arr[]={1,2,4,6,7,5,8,9};
    int n=sizeof(arr)/sizeof(int);
    partition(arr,n);*/

汉诺塔难题 2 约瑟夫环 3
求“斐波纳契数列:1,1,2,3,5,8,13,21…”函数:递归与非递归 4
判定多少个数是还是不是是 2的幂次数: 5 总计一个整数的二进…

相关文章