剑指offer（牛客网）

作者: 神奇的小青蛙 | 来源:发表于2020-12-14 08:41 被阅读0次

共67道，未完成47道

第1题：在二维数组中查找

这道题就属于巧妙的利用了数组的特点，从一个特定点开始找起。

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

第2题：替换空格

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

最简单的调用string的api

public String replaceSpace(StringBuffer str) {
        return str.toString().replace(" ", "%20");
    }

全部遍历，遇到" "就追加"%20"

public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ' ') {
                stringBuilder.append("%20");
            } else {
                stringBuilder.append(str.charAt(i));
            }
        }
        return stringBuilder.toString();
    }
}

第3题：从尾到头打印链表

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

import java.util.*;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack();
        ArrayList arraylist = new ArrayList();
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while (!stack.empty()) {
            arraylist.add(stack.pop());
        }
        return arraylist;
    }
}

这道题就非常的简单了，需要注意的就是从尾到头打印内容，所以需要考虑到其对应的数据结构，就是栈。
栈常用的api有4 + 1个因为search我几乎是不用的

入栈：push()
出栈：pop()
返回栈顶元素：peek()
判断栈是否为空：empty()
查找栈的元素：search()，在就返回1，不在返回-1

第4题重建二叉树

第5题用两个栈来实现一个队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。
思考：毫无思路的就就是模拟进行考虑
总结：

push的话就直接放到stack1中
pop的话，先看stack2有没有元素，有的话就弹出。没有的话，把所有的stack1中的元素放到stack2中，然后stack2再出栈。

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);
    }
    //这个写的就不是很好，return上都重复了，就进行一波重构。
    public int pop() {
        if (!stack2.empty()) {
            return stack2.pop();
        } else {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    }

    //上边的方法写的就不是很好，有重复的语句
    public int pop() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

第6题旋转数组中最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
思考：
有三种情况

情况1，arr[mid] > target：4 5 6 1 2 3
- arr[mid] 为 6， target为右端点 3， arr[mid] > target, 说明[first ... mid] 都是 >= target 的，因为原始数组是非递减，所以可以确定答案为 [mid+1...last]区间,所以 first = mid + 1
情况2，arr[mid] < target:5 6 1 2 3 4
- arr[mid] 为 1， target为右端点 4， arr[mid] < target, 说明答案肯定不在[mid+1...last]，但是arr[mid] 有可能是答案,所以答案在[first, mid]区间，所以last = mid;
情况3，arr[mid] == target:
如果是 1 0 1 1 1， arr[mid] = target = 1, 显然答案在左边
如果是 1 1 1 0 1, arr[mid] = target = 1, 显然答案在右边
所以这种情况，不能确定答案在左边还是右边，那么就让last = last - 1;慢慢缩少区间，同时也不会错过答案。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int i = 0, j = array.length - 1;
        while (i < j) {
            if (array[i] < array[j]) {
                return array[i];
            }
            int mid = (i + j) >> 1;
            if (array[mid] > array[i]) {
                i = mid + 1;
            } else if (array[mid] < array[i]) {
                j = mid;
            } else i++;
        }
        return array[i];
    }
}

第7题斐波那契数列

递归

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

动态规划

public class Solution {
    public int Fibonacci(int n) {
        int[] dp = new int[n + 2];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

第8题跳台阶

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

**思考：*这个题和上边的那个题是一样的，都是需要来写一个公式，然后进行反推的。
public class Solution {
    public int JumpFloor(int target) {
        if (target == 1 || target == 2 || target == 0) return target;
        int[] dp = new int[target + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= target; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[target];
    }
}

第9题变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思考：这道题属于有一些公式上的推导了，本身上也不是特别的有意思的呢，不过这里边有一个强转，我有段时间没有写，确实是忘记了的

public class Solution {
    public int JumpFloorII(int target) {
        if (target == 0 || target == 1) return 1;
        return (int) Math.pow(2, target - 1);
    }
}

第10题矩阵覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思考：这个和上边的情况基本上还是一样的，不过这次使用一种特别的方法来写一下

public class Solution {
    public int RectCover(int target) {
        if (target == 0 || target == 1 || target == 2) return target;
        int a = 1, b = 2, c = 0;
        for (int i = 3; i <= target; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

第11题二进制中1的个数

输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。
思考：以后扯到了二进制，就考虑使用位运算

与（AND，&）：全1为1，有0则0。
特殊情况&0，得到的就是0
或（OR，|）：有1则1，全0为0。
异或（XOR，^）：不同为1，相同为0。
非（NOT，~）：取反。

在这道题里就是使用的有一个技巧
如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

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

第13题调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思考：这里边用的是插入思想的方法

如果遇到偶数，j++
如果遇到奇数,假设位置为j，就将此奇数插入到i所指的位置，然后i往后移动一个位置，在插入之前，显然会涉及到数据的移动，也就是将[i,j-1]整体往后移动。
直到整个数组遍历完毕，结束

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

第14题链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个结点。
思考：链表是不知道长度的，所以要么是先一次遍历以后再二次遍历，或者是使用快慢指针的方法，我就让快指针比慢指针快k-1个身位，就可以解决这个问题了。

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < k; i++) {
            if (fast == null) return null;
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

第15题反转列表

输入一个链表，反转链表后，输出新链表的表头。
思考：这里也是需要用两个指针，一个是新的链表，一个要遍历的链表。然后挨个节点，指向输出链表，即可得到需要的内容了。

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

第20题包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
思考：因为是要用O(1)来实现，所以使用一个辅助栈，来解决。但一定要让两个栈的数量是相等的，才能实现这个同进同出的效果。

import java.util.Stack;

public class Solution {

    Stack<Integer> stackTotal = new Stack<Integer>();
    Stack<Integer> stackMin = new Stack<Integer>();
    public void push(int node) {
        stackTotal.push(node);
        if (stackMin.empty()) stackMin.push(node);
        else {
            if (node < stackMin.peek()) stackMin.push(node);
            else stackMin.push(stackMin.peek());
        }
    }
    
    public void pop() {
        stackTotal.pop();
        stackMin.pop();
    }
    
    public int top() {
        return stackTotal.peek();
    }
    
    public int min() {
        return stackMin.peek();
    }
}

第21题栈的压入和退出

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思考：模拟法，新建一个栈，将数组A压入栈中，当栈顶元素等于数组B时，就将其出栈，当循环结束时，判断栈是否为空，若为空则返回true.

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<Integer>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (!stack.empty() && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}

第32题把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
思考：这里边用的是贪心算法，贪心算法就是在求局部最优解，从而逼近全局最优解。这里的做法，就是先得到第一个和别人拼接后最小的值，以此类推，进行循环遍历。在这里自定义一个比较大小的函数，比较两个字符串s1, s2大小的时候，先将它们拼接起来，比较s1+s2,和s2+s1那个大，如果s1+s2大，那说明s2应该放前面，所以按这个规则，s2就应该排在s1前面。

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                int sum1 = Integer.valueOf(numbers[i] + "" + numbers[j]);
                int sum2 = Integer.valueOf(numbers[j] + "" + numbers[i]);
                if (sum1 > sum2) {
                    int temp = numbers[j];
                    numbers[j] = numbers[i];
                    numbers[i] = temp;
                }
            }
        }
        String answer = "";
        for (int i = 0; i < numbers.length; i++) {
            answer += numbers[i];
        }
        return answer;
    }
}

第34题第一个只出现一次的字符

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
思考：这个其实也没啥的，就是先用数组存一次，然后再遍历一次，看看谁等于1

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if (str == null || str.length() == 0) return -1;
        int[] tmp = new int[256];
        for (int i = 0; i < str.length(); i++) {
            tmp[str.charAt(i)]++;
        }
        for (int i = 0 ; i < str.length(); i++) {
            if (tmp[str.charAt(i)] == 1) {
                return i;
            }
        }
        return -1;
    }
}

第36题两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
思考：设置a和b两个指针，a走head1，b走head2，走到尽头了以后就再走另一个链表，这样第一次重合的地方就是两者第一个公共节点。

//这个方法很简单，但是问题是如果两个链表没有交点就会死循环。
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) return null;
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while (p1 != p2) {
            p1 = p1 != null ? p1.next : pHead2;
            p2 = p2 != null ? p2.next : pHead1;
        }
        return p1;
    }
}

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) return null;
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
            //这个方法的问题是不加if判断这一句就会死循环，我没有搞懂
            if (p1 != p2) {       
                if (p1 == null) p1 = pHead2;
                if (p2 == null) p2 = pHead1;
            }
        }
        return p1;
    }
}

第37题数字在升序数组中重现的次数

统计一个数字在升序数组中出现的次数。
思考：看到有序数组就考虑使用二分查找

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int lbound = 0, rbound = 0;
        int left = 0, right = array.length;
        int mid = 0;
        while (left < right) {
            mid = (left + right) >> 1;
            if (array[mid] < k) left = mid + 1;
            else right = mid;
        }
        lbound = left;
        left = 0;
        right = array.length;
        while (left < right) {
            mid = (left + right) >> 1;
            if (array[mid] <= k) left = mid + 1;
            else right = mid;
        }
        rbound = left;
        
        return rbound - lbound;
    }
}

总结：二分查找

寻找左侧边界的二分搜索

    public int left_bound(int[] nums, int target) {
        int left = 0; int right = nums.length;  //因为就算是左边界，可能所有的数都比他小
        int mid = 0;
        while (left < right) {                  //这里是<
            mid = left + (right - left) / 2;
            if (nums[mid] < target) mid = left + 1;
            //上边没有判断等号情况，而是在这里进行判断的，因为这个“=”不一定就是最左侧的，还需要继续逼近
            else mid = right;       
        }
        return nums[left] == target ? left : -1;
    }

寻找右侧边界的二分搜索

    public int right_bound(int[] nums, int target) {
        int left = 0; int right = nums.length;  //因为就算是左边界，可能所有的数都比他小
        int mid = 0;
        while (left < right) {                  //这里是<
            mid = left + (right - left) / 2;
            //left的指向的位置本身就是要最右侧的右一个，所以相等了，可以继续逼近的
            if (nums[mid] <= target) mid = left + 1;
            else mid = right;
        }
        //这里返回的是最右侧的值
        return nums[left] == target ? left - 1 : -1;
    }

第42题和为s的两个数字

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
思考：最外围的情况时才是两个数的乘积是最小的。所以设置两个指针左右逼夹就好了。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int left = 0;
        int right = array.length - 1;
        int tmp = 0;
        while (left < right) {
            tmp = array[left] + array[right];
            if (tmp == sum) {
                list.add(array[left]);
                list.add(array[right]);
                return list;
            } else if (tmp > sum) right--;
            else left++;
        }
        return list;
    }
}

第43题左旋字符串

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它
思考：这个题就很简单的了，拼接字符串就可以了

public class Solution {
    public String LeftRotateString(String str,int n) {
        // 这里图省事了，n要是大于字符串的长度，应该是做一个除模处理的
        if (str == null || n > str.length()) {
            return str;
        }
        //substring(pos):表示开始位置，一直截取完
        //substring(begin, end):从begin截取到end，左闭右开的格式
        return str.substring(n) + str.substring(0, n);
    }
}

别人的方法

public:
    string LeftRotateString(string str, int n) {
        int len = str.length();
        if(len == 0) return "";
        n = n % len;
        str += str;
        return str.substr(n, len + n);
    }
};

第44题翻转单词顺序

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
思考：就也没啥的，分割以后装进去呗。

    public String ReverseSentence(String str) {
        if (str.trim().equals("")) return str;
        String[] tmp = str.split(" ");
        StringBuffer answer = new StringBuffer();
        for (int i = tmp.length - 1; i >= 0; i--) {
            answer.append(tmp[i]);
            if (i != 0) answer.append(" ");
        }
        return answer.toString();
    }

第46题孩子们的游戏（圆圈中最后剩下的孩子）

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

第50题

第55题链表中环的入口位置

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思考：快慢指针解决

剑指offer（牛客网）

共67道，未完成47道

第1题：在二维数组中查找

第2题：替换空格

第3题：从尾到头打印链表

第4题重建二叉树

第5题用两个栈来实现一个队列

第6题旋转数组中最小数字

第7题斐波那契数列

第8题跳台阶

第9题变态跳台阶

第10题矩阵覆盖

第11题二进制中1的个数

第13题调整数组顺序使奇数位于偶数前面

第14题链表中倒数第k个节点

第15题反转列表

第20题包含min函数的栈

第21题栈的压入和退出

第32题把数组排成最小的数

第34题第一个只出现一次的字符

第36题两个链表的第一个公共节点

第37题数字在升序数组中重现的次数

第42题和为s的两个数字

第43题左旋字符串

第44题翻转单词顺序

第46题孩子们的游戏（圆圈中最后剩下的孩子）

第50题

第55题链表中环的入口位置

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

剑指offer（牛客网）

共67道，未完成47道

第1题：在二维数组中查找

第2题：替换空格

第3题：从尾到头打印链表

第4题 重建二叉树

第5题 用两个栈来实现一个队列

第6题 旋转数组中最小数字

第7题 斐波那契数列

第8题 跳台阶

第9题 变态跳台阶

第10题 矩阵覆盖

第11题 二进制中1的个数

第13题 调整数组顺序使奇数位于偶数前面

第14题 链表中倒数第k个节点

第15题 反转列表

第20题 包含min函数的栈

第21题 栈的压入和退出

第32题 把数组排成最小的数

第34题 第一个只出现一次的字符

第36题 两个链表的第一个公共节点

第37题 数字在升序数组中重现的次数

第42题 和为s的两个数字

第43题 左旋字符串

第44题 翻转单词顺序

第46题 孩子们的游戏（圆圈中最后剩下的孩子）

第50题

第55题 链表中环的入口位置

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

第4题重建二叉树

第5题用两个栈来实现一个队列

第6题旋转数组中最小数字

第7题斐波那契数列

第8题跳台阶

第9题变态跳台阶

第10题矩阵覆盖

第11题二进制中1的个数

第13题调整数组顺序使奇数位于偶数前面

第14题链表中倒数第k个节点

第15题反转列表

第20题包含min函数的栈

第21题栈的压入和退出

第32题把数组排成最小的数

第34题第一个只出现一次的字符

第36题两个链表的第一个公共节点

第37题数字在升序数组中重现的次数

第42题和为s的两个数字

第43题左旋字符串

第44题翻转单词顺序

第46题孩子们的游戏（圆圈中最后剩下的孩子）

第55题链表中环的入口位置