高频率面试编程题

与堆有关的问题，前K大，构建容量为K的小顶堆，前K小，构建容量为K的大顶堆

 

面试题 17.14. 最小K个数

美团面试的时候，写随机快排，quicksort函数的quicksort(array,left,index - 1)写错成quicksort(array,left,index)导致stackoverflowerror

解法1：快排

import java.util.*;
import java.lang.*;
class Solution {
    public int findKthLargest(int[] nums, int k) {
        quicksort(nums);
        
        return nums[nums.length - k];
    }
    public void quicksort(int[] nums) {
        if(nums.length <= 1) {
            return;
        }else {
            quick(nums,0,nums.length - 1);
        }
    }
    public void quick(int[] nums,int left,int right) {
        if(left < right) {
            int index = partition(nums,left,right);
            //1.quick(nums,left,index - 1);而不是quick(nums,left,index);
            //因为[left,index - 1]都小于哨兵，[index + 1,right]都大于哨兵
            quick(nums,left,index - 1);
            quick(nums,index + 1,right);
        }
    }
    public int randomPartition(int[] nums,int left,int right) {
        Random random = new Random();
        int flag = random.nextInt(right - left + 1) + left;
        int privot = nums[flag];
        int index = left - 1;
        swap(nums,flag,right);
        for(int i = left;i <= right;i ++) {
            if(nums[i] <= privot) {
                index ++;
                swap(nums,i,index);
            }
        }
        return index;
    }
    //
    public int partition(int[] nums,int left,int right) {
        int privot = nums[left];
        //2.确定哨兵之后，和nums[right]交换是必须的
        //把nums[left]的值，放到最右侧，就是为了算法结束之后，nums[left]能把数组分成两部分，一部分是小于等于nums[left]的，另一部分是大于nums[left]的
        swap(nums,left,right);
        //index的意思是区间[left,index]都小于等于哨兵，因此index的初始值是left - 1，并当nums[i]小于哨兵，先让index增加
        int index = left - 1;
        for(int i = left;i <= right;i ++) {
            if(nums[i] <= privot) {
                index ++;
                swap(nums,i,index);
            }
        }
        return index;
    }
    public void swap(int[] nums,int index1,int index2) {
        int tem = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tem;
    }
}

剑指 Offer 40. 最小的k个数

解法：建立容量为k的大顶堆

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k == 0) {
            return new int[0];
        }else if(k >= arr.length) {
            return arr;
        }else {
            int[] heap = new int[k];
            for(int i = 0;i < k;i ++) {
                heap[i] = arr[i];
            }
            //1.对于数组heap要建大顶堆堆
            buildMaxHeap(heap,k);
            for(int i = k;i < arr.length;i ++) {
                //2.heap[0]是大顶堆最大的元素，如果arr[i]小于heap[0]，那么arr[i]就把heap[0]替换，从0开始调整堆，注意这里不是建堆
                if(arr[i] < heap[0]) {
                    heap[0] = arr[i];
                    heapify(heap,0,k);
                }
            }
            return heap;
        }   
    }
    //寻找前k个最小的数，用大顶堆。调整容量为k的大顶堆,k就是大顶堆的容量
    public void buildMaxHeap(int[] heap,int k) {
        //大顶堆heap[0]是最大的
        //3.建堆应该自底向上，不应该自上而下，因此下面的for循环是不对的
        /*
        for(int i = 0;i <= (k - 1) / 2;i ++) {
            heapify(heap,i,k);
        }
        */
        for(int i = (k - 1) / 2;i >= 0;i --) {
            heapify(heap,i,k);
        }
    }
    //4.调整heap[index]的左节点heap[2 * index  + 1]和右节点heap[2 * index + 2]，符合大顶堆的定义
    public void heapify(int[] heap,int index,int k) {
        if(index >= k) {
            return;
        }else {
            int leftindex = 2 * index + 1;
            int rightindex = 2 * index + 2;
            int maxindex = index;
            if(leftindex < k && heap[maxindex] < heap[leftindex]) {
                maxindex = leftindex;
            }
            if(rightindex < k && heap[maxindex] < heap[rightindex]) {
                maxindex = rightindex;
            }
            if(maxindex != index) {
                int tem = heap[index];
                heap[index] = heap[maxindex];
                heap[maxindex] = tem;
                //如果index和它的左节点或者右节点交换，应该考虑heap[index]被交换到heap[maxindex]会不会继续引发堆调整
                heapify(heap,maxindex,k);
            }
        }
    }
}

347. 前 K 个高频元素

解法：前K个出现最多的，，构建一个大小为K的小顶堆

class Solution {
    //可以按任意顺序返回答案
    //时间复杂度必须优于 O(n log n)
    //前k个高频的，构建小顶堆
    HashMap<Integer,Integer> map;
    public int[] topKFrequent(int[] nums, int k) {
        map = new HashMap<>();
        //LinkedList<Integer> list = new LinkedList<>();
        if(nums.length == 0 || k == 0) {
            return new int[0];
        }else {
            for(int i = 0;i < nums.length;i ++) {
                if(map.containsKey(nums[i])) {
                    map.put(nums[i],map.get(nums[i]) + 1);
                }else {
                    map.put(nums[i],1);
                }
            }
            //keys是去重的nums元素
            int[] keys = new int[map.keySet().size()];
            int index = 0;
            for(int key : map.keySet()) {
                keys[index ++] = key;
                //System.out.println(index);
            }
            //答案不要求数组元素的顺序，如果k大于等于keys的长度，可以直接返回key
            if(k >= map.keySet().size()) {
                return keys;
            }else {
                int[] answer = new int[k];
                //1.把answer作为小顶堆，先填充数据，然后进行建堆
                for(int i = 0;i < k;i ++) {
                    answer[i] = keys[i];
                }
                //2.自下而上建小顶堆
                buildHeap(answer,k);
                for(int i = k;i < keys.length;i ++) {
                    if(map.get(keys[i]) > map.get(answer[0])) {
                        //3.替换堆顶元素，引发堆调整
                        answer[0] = keys[i];
                        heapify(answer,0);
                    }
                }
                return answer;
            }
        }
    }
    //4.建堆函数，自下而上调整，详见数据结构，不能自上而下，也就是不能for(i = 0;i < length;i ++){code}
    public void buildHeap(int[] heap,int length) {
        //把i --写成i ++导致错误
        //i建议从length开始，方便记忆
        //当然也可以从(length - 1) / 2 + 1开始，因为这个节点对应的左子树或者右子树是heap数组的最后一个节点
        /*
        for(int i = length;i >=0;i --) {
            heapify(heap,i);
        }
        */
        for(int i = (length - 1) / 2 + 1;i >=0;i --) {
            heapify(heap,i);
        }
    }
    //5.堆调整函数
    //调整heap[index]的左右子节点heap[2*index + 1],heap[2*index + 2],依据是他们出现的次数
    public void heapify(int[] heap,int index) {
        if(index >= heap.length) {
            return;
        }else {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            int min = index;
            if(left < heap.length && map.get(heap[min]) > map.get(heap[left])) {
                min = left;
            }
            if(right < heap.length && map.get(heap[min]) > map.get(heap[right])) {
                min = right;
            }
            //小顶堆比较的依据不是元素的大小而是出现的次数
            /*
            if(right < heap.length && heap[min] > heap[right]) {
                min = right;
            }
            */
            if(min != index) {
                int tem = heap[index];
                heap[index] = heap[min];
                heap[min] = tem;
                //index和子节点交换之后，可能会触发新一轮的交换，因此要调用一下，这个时候，heap[min]保存的是之前heap[index]
                heapify(heap,min);
            }
        }
    }
}

剑指 Offer 45. 把数组排成最小的数

解法：

注意：

1.new 一个比较器的时候，new Comparator<> (T) {重写的compare方法}，T是代表一个类型，其实就是泛型，不能是int,long,float，得是Integer，Float,Long等对应的包装类型。但是int[],long[],float[]可以。

        Arrays.sort(nums1,new Comparator<Integer>() {

            public int compare(Integer a,Integer b) {

                return a * 10 + b - b * 10 + a;

            }

        });

2.对于本题，比较器是比较两个数，比如30和3,是303大还是330大，因此使用Integer数组不方便，两个数的位数不一样，因此使用String的数组，“30” + “3”可以直接拼接，拼接之后(“30” + “3”).compareTo("3" + "30");用String.valueOf()这个静态方法（重载的，建议）可以得到数字对应的String。

3.另外，可以有String类型的数组不可以有Stringbuilder和StringBuffer类型的数组，虽然创建StringBuilderStringBuffer的数组不报错，但是数组的内容就不能改变了，个人认为如果改变，不符合数组的内存地址连续性。

4.Comparator与Comparable：

https://blog.csdn.net/weixin_34066347/article/details/85621968

https://blog.csdn.net/qq_40693828/article/details/81409004?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-3.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-3.channel_param

 

class Solution {
    public String minNumber(int[] nums) {
        //
		/*
		Integer[] nums1 = new Integer[nums.length];
		for(int i = 0; i < nums.length;i ++) {
			nums1[i] = new Integer(nums[i]);
		}
        StringBuilder sb = new StringBuilder();
        Arrays.sort(nums1,new Comparator<Integer>() {
            public int compare(Integer a,Integer b) {
                return a * 10 + b - b * 10 + a;
            }
        });
        */
		String[] nums1 = new String[nums.length];
		for(int i = 0; i < nums.length;i ++) {
			nums1[i] = String.valueOf(nums[i]);
		}
        StringBuilder sb = new StringBuilder();
        Arrays.sort(nums1,new Comparator<String>() {
            public int compare(String a,String b) {
                //return Integer.parseInt(a + b) - Integer.parseInt(b + a);
                return (a + b).compareTo((b + a));
            }
        });
        for(int i = 0;i < nums1.length;i ++) {
            sb.append(nums1[i]);
        }
        return sb.toString();
    }
}

179. 最大数 

解法：类似于上面的

import java.util.Arrays;
class Solution {
    public String largestNumber(int[] nums) {
        if(nums.length == 0) {
            return null;
        }else {
            //1.转化为String数组
            String[] strings = new String[nums.length];
            for(int i = 0;i < nums.length;i ++) {
                strings[i] = String.valueOf(nums[i]);
            }
            Arrays.sort(strings,new Comparator<String>(){
                
                public int compare(String a,String b) {
                    //错误return Integer.parseInt(a + b) - Integer.parseInt(b + a);
                    //2.比较字符串调用compareTo方法
                    return (b + a).compareTo(a + b);
                }
            });
            StringBuilder sb = new StringBuilder();
            if(strings[0].equals("0")) {
                return "0";
            }
            for(int i = 0;i < strings.length;i ++) {
                //错误sb.add(nums[i]);
                //3.详见StringBuilder的append方法，可以把基本数据类型转换为Character加入StringBuilder中
                sb.append(strings[i]);
            }
            return sb.toString();
        }
    }
}

215. 数组中的第K个最大元素

解法：PriorityQueue是用堆实现的

待完成：用数组实现堆

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(k > nums.length){
            return 0;
        }
        /*
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(nums.length,(a,b) -> a - b);
        
        for(int i = 0;i < nums.length;i ++){
            minHeap.add(nums[i]);
        }
        for(int i = 0;i < nums.length - k;i ++){
            minHeap.poll();
        }
        return minHeap.peek();
        */
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k,(a,b) -> a - b);
        for(int i = 0;i < k;i ++){
            minHeap.add(nums[i]);
        }
        for(int i = k;i < nums.length;i ++){
            if(nums[i] > minHeap.peek()){
                minHeap.poll();
                minHeap.add(nums[i]);
            }
        }
        return minHeap.peek();
    }
}

3. 无重复字符的最长子串

解法：这是滑动窗口系列题目之一

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() <= 1){
            return s.length();
        }
        HashMap<Character,Integer> map = new HashMap<>();
        int left = 0;
        int max = 0;
        for(int i = 0;i < s.length();i ++){
            if(map.containsKey(s.charAt(i))){
                //更新left的时候与i无关
                left = Math.max(map.get(s.charAt(i)) + 1,left);
            }
            //更新max
            max = Math.max(max,i - left + 1);
            //添加map
            map.put(s.charAt(i),i);
        }
        return max;
    }
}

24. 两两交换链表中的节点

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode ans = reserveN(head,2);
        
        ans.next.next = swapPairs(ans.next.next);
        return ans;
    }
    ListNode lastofnext = null;
    //从head节点开始反转N个链表
    public ListNode reserveN(ListNode head,int N){
        if(N == 1){
            lastofnext = head.next;
            return head;
        }
        //last是指向反转后头节点的指针，因此应返回last
        ListNode last = reserveN(head.next,N - 1);
        head.next.next = head;
        head.next = lastofnext;
        //返回的是last而不是head
        return last;
    }
}

128. 最长连续序列

解法：使用HashSet，符合题意的最长递增子序列的开始数字X，set里肯定不包含X - 1

比如最长的递增子序列是 2 3  4，那么1肯定不能在数组和set里。

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length <= 1) {
            return nums.length;
        }else {
            HashSet<Integer> set = new HashSet<>();
            int answer = 1;
            int currentlength;
            int currentnumber;
            for(int i = 0;i < nums.length;i ++) {
                set.add(nums[i]);
            }
            for(int i = 0;i < nums.length;i ++) {
                //点睛之处，对于数N，如果N - 1也在set里，那么最长的递增序列一定不是从N开始的，
                //最长的递增序列，开始的数字X，set里肯定没有X - 1
                if(! set.contains(nums[i] - 1)) {
                    currentlength = 1;
                    currentnumber = nums[i];
                    while(set.contains(currentnumber + 1)) {
                        currentlength ++;
                        currentnumber ++;
                    }
                    answer = Math.max(answer,currentlength);
                }
                
            }
            return answer;
        }
    }
}

151. 翻转字符串里的单词

解法：一般会问递归的解法。

class Solution {
    StringBuilder sb;
    public String reverseWords(String s) {
        sb = new StringBuilder();
        //第一个单词变成最后一个单词，因此第一个单词加入sb的时候，不加空格
        getReverseWord(sb,s,0,false);
        return sb.toString();
    }
    //把单词存储到sb中，left表示从s的下标left开始添加下一个单词，flag表示在sb后面添加单词之后，sb后面还要不要加空格，原来的第一个单词加入sb之后，sb后面不需要加了
    public void getReverseWord(StringBuilder sb,String s,int left,boolean flag) {
        while(left < s.length() && s.charAt(left) == ' ') {
            left ++;
        }
        //left指向下一个单词的开始字母，或者left等于s.length()
        if(left == s.length()) {
            return;
        }
        int right = left;
        //right指向空格（left指向那个单词之后的第一个空格）或者right等于s.Length()
        while(right < s.length() && s.charAt(right) != ' ') {
            right ++;
        }
        getReverseWord(sb,s,right,true);
        //下面可以代替上面的for循环，
        //sb.append(s.substring(left,right));
        //为什么是小于right?因为right没有指向单词的字母
        
        for(int i = left;i < right;i ++) {
            sb.append(s.charAt(i));
        }
        
        if(flag) {
            sb.append(' ');
        }
    }
}

38. 外观数列

解法：迭代，很明显n个外观数需要依靠第n-1个外观数得到

class Solution {
    public String countAndSay(int n) {
         if(n == 1){
             return "1";
         }else{
            String before = countAndSay(n - 1);
            StringBuilder sb = new StringBuilder();
            int index = 0;
            while(index < before.length()){
                int counter = 1;
                char character = before.charAt(index);
                while(index + 1 < before.length()  && before.charAt(index + 1) == character){
                    index ++;
                    counter ++;
                }
                sb.append(counter);
                sb.append(character);
                index ++;
            }
            return sb.toString();
         }
    }
}

886. 可能的二分法

class Solution {
    //
    public ArrayList<Integer>[] graph;
    //点如果涂颜色，就加入map
    public HashMap<Integer,Integer> map;
    //0代表红色，1代表蓝色
    public boolean possibleBipartition(int N, int[][] dislikes) {
        graph = new ArrayList[N + 1];
        map = new HashMap<Integer,Integer>();
        for(int i = 0;i <= N;i ++){
            graph[i] = new ArrayList<Integer>();
        }
        //graph[i]表示i + 1不能共存的链表
        for(int i = 0;i < dislikes.length;i ++){
            graph[dislikes[i][0]].add(dislikes[i][1]);
            graph[dislikes[i][1]].add(dislikes[i][0]);
        }
        for(int i = 1;i <= N;i ++){
            if(! map.containsKey(i) && ! dfs(i,0)){
                return false;
            }
        }
        return true;
    }
    //把node的节点涂成color，是否合理
    public boolean dfs(int node,int color){
        //如果node已经存在，判断node的值与color是否相同
        if(map.containsKey(node)){
            return map.get(node) == color;
        }
        //如果不含有key
        map.put(node,color);
        for(int i = 0;i < graph[node].size();i ++){
            //^是逐位 
            if(! dfs(graph[node].get(i),color ^ 1)){
                return false;
            }
        }
        return true;
    }
}

322. 零钱兑换

解法：待实现：贪心+二分查找+动态规划，也就是先尽量换大的零钱

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0){
            return 0;
        }
        //dp[i]代表凑成i元，需要的硬币个数
        int[] dp = new int[amount + 1];

        Arrays.sort(coins);
        for(int i = 0;i < coins.length && coins[i] <= amount;i ++){
            dp[coins[i]] = 1;
        }
        if(dp[amount] != 0){
            return dp[amount];
        }

        for(int i = coins[0];i <= amount;i ++){
            if(dp[i] == 1){
                continue;
            }else{
                //下面的超时间
                /*
                int min = Integer.MAX_VALUE;
                for(int j = coins[0];j <= i - coins[0];j ++){
                    if(dp[j] != 0 && dp[i - j] != 0){
                        min = Math.min(min,dp[j] + dp[i - j]);
                    }
                }
                if(min == Integer.MAX_VALUE){
                    dp[i] = 0;
                }else{
                    dp[i] = min;
                }
                */
                int min = Integer.MAX_VALUE;
                for(int j = 0;j < coins.length && coins[j] <= i;j ++){
                    if(dp[i - coins[j]] != 0){
                        min = Math.min(dp[coins[j]] + dp[i - coins[j]],min);
                    }
                    
                }
                dp[i] = min == Integer.MAX_VALUE ? 0 : min;
            }
        }
        //System.out.println(dp[10]);
        return dp[amount] == 0 ? -1 : dp[amount];
    }
    public int find(int[] array,int target){
        return 1;
    }
}

class Solution {
    public int coinChange(int[] coins,int amount) {
        if(amount == 0){
            return 0;
        }
        int[] dp =new int[amount + 1];
        //第一个不一样的地方
        Arrays.fill(dp,amount + 1);
        //循环计算dp[i]
        //第二个不一样的地方
        dp[0] = 0;
        //金钱的循环再外面，否则会出现重复的情况
        for(int coin : coins){
            for(int i = coin;i <= amount;i ++){
                //第三个不一样的地方
                dp[i] = Math.min(dp[i],dp[i - coin] + 1);
            }
        }
        //第四个不一样的地方
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}

518. 零钱兑换 II

解法：类似与爬楼梯问题

class Solution {
    //类似于爬楼梯
    public int change(int amount, int[] coins) {
        if(amount == 0){
            return 1;
        }
        int[] dp =new int[amount + 1];
        //循环计算dp[i]
        dp[0] = 1;
        //金钱的循环再外面，否则会出现重复的情况
        for(int coin : coins){
            for(int i = coin;i <= amount;i ++){
                //相当于爬楼梯问题
                //dp[n] = dp[n - 1] + dp[n - 2]
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}

739. 每日温度

解法：递减栈

class Solution {
    //递减栈的思想
    public int[] dailyTemperatures(int[] T) {
        if(T.length <= 1){
            return new int[T.length];
        }else{
            //存储数据并不方便，因为还要得到数组下标，因此不如直接存储下标
            Stack<Integer> stack = new Stack<>();
            int[] answer = new int[T.length];
            for(int i = 0;i < T.length;i ++){
                while(! stack.isEmpty() && T[i] > T[stack.peek()]){
                    answer[stack.peek()] = i - stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }
            return answer;
        }
    }
}

406. 根据身高重建队列

解法：见注释

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        //按照身高递减，身高相同排名递增的顺序重新排列二维数组
        Arrays.sort(people,new Comparator<int[]>(){
            public int compare(int[] a,int[] b){
                return a[0] == b[0] ? a[1] - b[1] : b[0] - a[0];
            }
        });
        List<int[]> list = new LinkedList<>();
        for(int[] p : people){
            //在list的指定下标插入数据
            list.add(p[1],p);
        }
        return list.toArray(new int[people.length][2]);
    }
}

面试题 16.25. LRU缓存

解法：HashMap+LinkedList

HashMap表示key是否存在，LinkedList模拟队列

class LRUCache {
    public int capacity;
    public HashMap<Integer,Integer> map;
    public LinkedList<Integer> list;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        list = new LinkedList<>();
    }
    
    public int get(int key) {
        //
        if(map.containsKey(key)){
            /*
            //使用就把key从list中取出来加到队尾
            int index = 0;
            for(int i = 0;i < list.size();i ++){
                if(list.get(i) == key){
                    index = i;
                    break;
                }
            }
            list.remove(index);
            list.addLast(key);
            */
            //应该注意remove(index)和remove(Object key)的区别
            //这里不能直接remove(key)
            list.remove((Integer) key);
            list.addLast(key);
            return map.get(key);
        }else{
            return  -1;
        }
    }
    
    public void put(int key, int value) {
        //如果有key存在也触发使用条件
        if(map.containsKey(key)){
            list.remove((Integer) key);
            list.addLast(key);
            map.put(key,value);
        }else if(list.size() < capacity){
            //长度小于capacity可以put
            map.put(key,value);
            list.addLast(key);
        }else{
            map.remove(list.getFirst());
            list.removeFirst();
            map.put(key,value);
            list.addLast(key);
        }
    }
}

836. 矩形重叠

解法：降维，把问题看作XY两个方向的区间合并，不同的是，区间只相交一个点不算相交

class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        if(rec1.length != 4 || rec2.length != 4){
            throw new IllegalArgumentException();
        }else{
            
            int[] array1 = {rec1[0],rec1[2]};
            int[] array2 = {rec2[0],rec2[2]};
            int[] array3 = {rec1[1],rec1[3]};
            int[] array4 = {rec2[1],rec2[3]};
            if(judge(array1,array2) && judge(array3,array4)){
                return true;
            }else{
                return false;
            }
        }
    }
    //降维
    public boolean judge(int[] array1,int[] array2){
        if(array1.length != 2 || array2.length != 2){
            return false;
        }else{
            
            if(array1[0] <= array2[0]){
                //根据题意等于不对
                if(array1[1] > array2[0]){
                    return true;
                }
            }else{
                if(array2[1] > array1[0]){
                    return true;
                }
            }
            return false;
        }
    }
}

9. 回文数

解法1：双指针，Integer.toString(int x)可以把x转化为String

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0){
            return false;
        }else if(x < 10){
            return true;
        }else{
            String number = Integer.toString(x);
            int left = 0;
            int right = number.length() - 1;
            while(left < right){
                if(number.charAt(left) != number.charAt(right)){
                    return false;
                }else{
                    left ++;
                    right --;
                }
            }
            return true;
        }
    }
}

解法2：数学的方法模拟双指针

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0){
            return false;
        }else if(x < 10){
            return true;
        }else{
            int div = 1;
            int tem = x;
            //必须是大于等于10
            while(tem >= 10){
                tem = tem / 10;
                div *= 10;
            }
            //System.out.println(div);
            //x >= 10不对，无法解决1000021的情况
            while(x > 0){
                int left = x % 10;
                int right = x / div;
                if(left != right){
                    return false;
                }else{
                    //原来的x除去最高位和最低位
                    x = (x % div) / 10;
                    div = div / 100;
                }
            }
            return true;
        }
    }
}

43. 字符串相乘

解法：1.字符串反转，让最低位是个位；2.num1 * num2 = answer,由于999 * 999 = 998901，answer数组的长度是num1的长度加上num2的长度即可。不考虑进位：answer[i+j] += num1[i] * num2[j] =;最后统一进位。

class Solution {
    public String multiply(String num1, String num2) {
        //999*999=998001
        //x位的数乘以y位的数，结果肯定是x+y位的数
        if(num1 == null){
            return num2;
        }else if(num2 == null){
            return num1;
        }else if(num1.equals("0") || num2.equals("0")){
            //不应该用==，应该用.equals()
            return "0";
        }else{
            int[] answer = new int[num1.length() + num2.length()];
            /*
            int number1;
            int number2;
            */
            //经过反转之后，个位在0
            num1 = reverse(num1);
            num2 = reverse(num2);
            for(int i = 0;i < num1.length();i ++){
                for(int j = 0;j < num2.length();j ++){
                    //最后统一进位
                    answer[i + j] += ((num1.charAt(i) - '0') * (num2.charAt(j) - '0'));
                    /*
                    answer[i + j] += (number1 * number2) % 10;
                    answer[i + j + 1] += (number1 * number2) / 10;
                    */
                }
            }
            //统一进位，注意一个是等于一个是加等于,并且顺序不能反
            for(int i = 0;i < answer.length - 1;i ++){
                /*
                answer[i] = answer[i] % 10;
                answer[i + 1] += answer[i] / 10;
                */
                answer[i + 1] += answer[i] / 10;
                answer[i] = answer[i] % 10;
            }
            StringBuilder sb = new StringBuilder();
            int i = 0;
            for(i = answer.length - 1;i >= 0;i --){
                if(answer[i] != 0){
                    break;
                }
            }
            for(;i >= 0;i --){
                sb.append(answer[i]);
            }
            return sb.toString();
        }
    }
    //反转字符串函数
    public String reverse(String num){
        if(num == null){
            return null;
        }else{
            StringBuilder sb = new StringBuilder();
            for(int i = num.length() - 1;i >= 0;i --){
                sb.append(num.charAt(i));
            }
            return sb.toString();
        }
    }
}

[牛客网编程题]链表中环的入口节点

解法：快慢指针+双指针，剑指offer23，链表中环的入口节点

//解法：快慢指针+双指针
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode node = getNode(head);
        //面试写的时候，就是忘记判断node == null，导致NullPointerException
        if(node == null) {
            return null;
        }else {
            ListNode answer = head;
            int length = getLength(node);
            //让front先向前走length步，answer和front一起往后一次走一步
            ListNode front = head;
            for(int i = 0;i < length;i ++) {
                front = front.next;
            }
            while(answer != front) {
                answer = answer.next;
                front = front.next;
            }
            return answer;
        }
    }
    //如果有环，得到环的长度
    public int getLength(ListNode node) {
        int answer = 1;
        ListNode tem = node.next;
        while(node != tem) {
            answer ++;
            tem = tem.next;
        }
        return answer;
    }
    //快慢指针，返回的要么是环中的节点，要么是null
    public ListNode getNode(ListNode head) {
        if(head == null) {
            return null;
        }else {
            ListNode fast = head.next;
            ListNode slow = head;
            while(fast != null && fast.next != null) {
                if(fast == slow) {
                    return fast;
                }
                slow = slow.next;
                
                fast = fast.next.next;
            }
            return null;
        }
    }
}

268. 缺失数字

解法：1+...+n减去nums数组之和，但是直接求nums数组之和，可能会int溢出。

class Solution {
    //直接求nums数组的和可能会溢出
    public int missingNumber(int[] nums) {
        if(nums.length == 0){
            throw new IllegalArgumentException();
        }else{
            int sum = 0;
            for(int i = 0;i < nums.length;i ++){
                sum += nums[i];
            }
            return nums.length * (nums.length + 1) / 2 - sum;
        }
    }
}

class Solution {
    //直接求nums数组的和可能会溢出
    public int missingNumber(int[] nums) {
        if(nums.length == 0){
            throw new IllegalArgumentException();
        }else{
            /*
            int sum = 0;
            for(int i = 0;i < nums.length;i ++){
                sum += nums[i];
            }
            return nums.length * (nums.length + 1) / 2 - sum;
            */
            //原理和上面的一样，但是避免了int溢出
            int result = 0;
            for(int i = 1;i <= nums.length;i ++){
                result += i - nums[i - 1];
            }
        }
    }
}

67. 二进制求和

解法：存储答案的Stringbuilder的先存储个位，并且两个数都从低位相加

class Solution {
    //存储答案的Stringbuilder的先存储
    public String addBinary(String a, String b) {
        if(b == null || b.equals("0")){
            return a;
        }else if(a == null || a.equals("0")){
            return b;
        }else{
            int index1 = a.length() - 1;
            int index2 = b.length() - 1;
            int number = 0;
            int sum = 0;
            StringBuilder sb = new StringBuilder();
            while(index1 >= 0 && index2 >= 0){
                sum = number + (a.charAt(index1) - '0') + (b.charAt(index2) - '0');
                number = sum / 2;
                sb.append(sum % 2);
                index1 --;
                index2 --;
            }
            while(index1 >= 0){
                sum = (a.charAt(index1) - '0') + number;
                number = sum / 2;
                sb.append(sum % 2);
                index1 --;
            }
            while(index2 >= 0){
                sum = (b.charAt(index2) - '0') + number;
                number = sum / 2;
                sb.append(sum % 2);
                index2 --;
            }
           
            if(number != 0){
                sb.append(number);
            }
            return sb.reverse().toString();
        }
    }
}

268. 缺失数字

异或运算的思路见解析：https://leetcode-cn.com/problems/missing-number/solution/que-shi-shu-zi-by-leetcode/

class Solution {
    //异或是逐位异或的，比如0^3=3
    public int missingNumber(int[] nums) {
        int answer = 0;
        for(int i = 0;i < nums.length;i ++){
            answer ^= (i ^ nums[i]);
        }
        return answer ^ nums.length;
    }
}

20. 有效的括号

解法：哔哩哔哩笔试题，原来用动态规划写的，动态规划不适合{}{}{}()情况，只适合{({[]})}情况，应该用栈。

class Solution {
    public boolean isValid(String s) {
        if(s.length() == 0){
            return true;
        }else if(s.length() % 2 == 1) {
            return false;
        }else {
            HashMap<Character,Character> map = new HashMap<>();
            map.put(')','(');
            map.put('}','{');
            map.put(']','[');
            Stack<Character> stack = new Stack<>();
            for(int i = 0;i < s.length();i ++){
                char c = s.charAt(i);
                if(! map.containsKey(c)){
                    stack.push(c);
                }else{
                    if(! stack.isEmpty() && stack.peek() == map.get(c)){
                        stack.pop();
                    }else{
                        return false;
                    }
                }
            }
            return stack.isEmpty();
            /*
            map.put('(',1);
            map.put(')',-1);
            map.put('[',2);
            map.put(']',-2);
            map.put('{',3);
            map.put('}',-3);
            Stack<Character> stack = new Stack<>();
            for(int i = 0;i < s.length();i ++){
                if(! map.containsKey(s.charAt(i))){
                    return false;
                }else if(map.get(s.charAt(i)) > 0){
                    stack.push(s.charAt(i));
                }else{
                    if(! stack.isEmpty() 
                    && (map.get(s.charAt(i)) + map.get(stack.peek()) == 0)){
                        stack.pop();
                    }else{
                        return false;
                    }
                }
            }
            
            if(stack.isEmpty()){
                return true;
            }else{
               return false; 
            }
            */
        }
    }
}

189. 旋转数组

时间复杂度题目要求O(n)，空间复杂度O(1)

解法1：反转数组，因此本题改成反转链表也是可以的。

k = k % nums.length，先反转[0,nums.length - 1]，再反转[0,k - 1]和[k,nums.length - 1]

class Solution {
    public void rotate(int[] nums, int k) {
        if(nums.length <= 1){
            return;
        }else{
            //忘记写下面一句
            k = k % nums.length;
            reverse(nums,0,nums.length - 1);
            reverse(nums,0,k -1);
            reverse(nums,k,nums.length - 1);
        }
    }
    public void reverse(int[] nums,int left,int right){
        int tem = 0;
        //当left = right的情况下，循环结束
        //当一开始的时候，left = right，不需要反转
        while(left < right){
            tem = nums[left];
            nums[left] = nums[right];
            nums[right] = tem;
            //忘记写下面的两句了
            left ++;
            right --;
        }
    }
}

解法2：https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode/

class Solution {
    public void rotate(int[] nums, int k) {
        if(nums.length <= 1 || k < 1){
            return;
        }else{
            //忘记写下面一句
            k = k % nums.length;
            //counter表示已经交换的个数
            int counter = 0;
            int index = 0;
            int start = 0;
            int pre;
            int tem = 0;
            while(counter < nums.length){
                index = start;
                pre = nums[start];
                do{
                    int next = (index + k) % nums.length;
                    tem = nums[next];
                    nums[next] = pre;
                    pre = tem;
                    index = next;
                    next = (next + k) % nums.length;
                    counter ++;
                } while(index != start);
                start = (start + 1) % nums.length;
            }
        }
    }
}

409. 最长回文串

解法：哈希表

class Solution {
    public int longestPalindrome(String s) {
        if(s.length() == 0 && s.length() == 1) {
            return s.length();
        }else {
            HashMap<Character,Integer> map = new HashMap<>();
            int answer = 0;
            for(int i = 0;i < s.length();i ++) {
                if(map.containsKey(s.charAt(i))) {
                    map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
                }else {
                    map.put(s.charAt(i), 1);
                }
            }
            for(char key : map.keySet()){
                answer += map.get(key) % 2;
            }
            return answer == 0 ? s.length() : s.length() - answer + 1;
        }
    }   
}

110. 平衡二叉树

解法：类似于337. 打家劫舍 III

class Solution {
    //flag表示题目所给的树是不是平衡二叉树，其值为false就表示不是平衡二叉树
    boolean flag = true;
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }else {
            //最终目的不是为了获得dp函数的返回值，因此直接调用即可
            dp(root);
            return flag;
        }
    }
    //dp函数返回的数组，第一个元素表示左子树的高
    //第二个元素表示右子树的高
    public int[] dp(TreeNode root) {
        int[] answer = new int[2];
        //root为空直接返回
        //flag为false，表示题目中的树的子树已经失衡，直接返回即可
        if(root == null || flag == false) {
            return answer;
        }else {
            int[] left = dp(root.left);
            int[] right = dp(root.right);
            if(get(left[0],left[1]) > 1 || get(right[0],right[1]) > 1){
                flag = false;
            }
            answer[0] = Math.max(left[0],left[1]) + 1;
            answer[1] = Math.max(right[0],right[1]) + 1;
            if(get(answer[0],answer[1]) > 1){
                flag = false;
            }
            return answer;
        }
    }
    public int get(int a,int b){
        return Math.abs(a - b);
    }
}

剑指 Offer 30. 包含min函数的栈

解法：辅助栈和数据栈，两个栈包含元素的数量一直一样

class MinStack {
    //辅助栈存储的元素的多少每时每刻都和数据栈一样
    //辅助栈的栈顶元素对应数据栈从栈底到栈顶的最小值
    public Stack<Integer> datastack;
    public  Stack<Integer> helpstack;
    /** initialize your data structure here. */
    public MinStack() {
        this.datastack = new Stack<>();
        this.helpstack = new Stack<>();
    }
    
    public void push(int x) {
        //加入辅助栈的条件：1.辅助栈为空或者x小于辅助栈栈顶元素
        //2.否则，也就是辅助栈不为空并且栈顶元素小于x，那么辅助栈加入栈顶元素
        if(helpstack.isEmpty() || x < helpstack.peek()) {
            helpstack.push(x);
        }else {
            helpstack.push(helpstack.peek());
        }
        //加入数据栈
        datastack.push(x);
    }
    
    public void pop() {
        if(! datastack.isEmpty() && ! helpstack.isEmpty()) {
            datastack.pop();
            helpstack.pop();
        }
    }
    
    public int top() {
        return datastack.peek();
    }
    
    public int min() {
        return helpstack.peek();
    }
}

剑指 Offer 39. 数组中出现次数超过一半的数字

投票法：

解法：设置一个counter = 1和number  = nums[0]，往后遍历，当遍历得到的数字等于number，counter ++；否则counter --。如果counter == 0，那么number = 当前遍历的数字，counter重新设置为1.

class Solution {
    public int majorityElement(int[] nums) {
        if(nums.length == 0) {
            throw new IllegalArgumentException();
        }else if(nums.length == 1) {
            return nums[0];
        }else {
            int counter = 1;
            int number = nums[0];
            for(int i = 1;i < nums.length;i ++) {
                if(nums[i] == number) {
                    counter ++;
                }else {
                    counter --;
                }
                if(counter == 0) {
                    number = nums[i];
                    counter = 1;
                }
            }
            return number;
        }
    }
}

剑指 Offer 50. 第一个只出现一次的字符

解法：关键是nums[s.charAt(i)]，也就是字符可以直接转化为int(范围是0-255)

class Solution {
    public char firstUniqChar(String s) {
        //s.equals('');
        if(s == null) {
            return ' ';
        }else {
            //用一个int的数组，来模拟HashMap
            //因为char是一个字节，二进制对应的阿西克码是0--255
            int[] array = new int[256];
            for(int i = 0;i < s.length();i ++) {
                //这是合法的，能自动把s.charAt(i)转化为对应的整数
                array[s.charAt(i)] += 1;
            }
            for(int i = 0;i < s.length();i ++) {
                if(array[s.charAt(i)] == 1) {
                    return s.charAt(i);
                }
            }
            return ' ';
        }
        
        
    }
}

[编程题]字符流中第一个不重复的字符

解法1：StringBuilder记录字符输入的顺序，int[256]对于纯字符串的问题可以当作一个HashMap

public class Solution {
    //Insert one char from stringstream
    int[] array = new int[256];
    StringBuilder sb = new StringBuilder();
    public void Insert(char ch)
    {
        array[ch] += 1;
        sb.append(ch);
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        //由于寻找的是字符流中的第一个出现一次的字符，因此下面不对
        //比如google，ggg#ll这是正确的输出，但是下面会输出ggg#le
        /*
        for(int i = 0; i < 256;i ++) {
            if(array[i] == 1) {
                return (char) i;
            }
        }
        return '#';
        */
        for(int i = 0;i < sb.length();i ++) {
            if(array[sb.charAt(i)] == 1) {
                return sb.charAt(i);
            }
        }
        return '#';
    }
}

解法2：用index存储字符出现的顺序

 

public class Solution {
    //Insert one char from stringstream
    int[] array = new int[256];
    int index = 1;
    //StringBuilder sb = new StringBuilder();
    public void Insert(char ch)
    {
        if(array[ch] == 0) {
            array[ch] = index;
        }else {
            array[ch] = -1;
        }
        //sb.append(ch);
        index ++;
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        //由于寻找的是字符流中的第一个出现一次的字符，因此下面不对
        //比如google，ggg#ll这是正确的输出，但是下面会输出ggg#le
        /*
        for(int i = 0; i < 256;i ++) {
            if(array[i] == 1) {
                return (char) i;
            }
        }
        return '#';
        */
        char answer = '';
        int minindex = Integer.MAX_VALUE;
        for(int i = 0;i < 256;i ++) {
            if(array[i] >= 1 && array[i] < minindex) {
                answer = (char) i;
                minindex = array[i];
            }
        }
        if(answer == '') {
            return '#';
        }else {
            return answer;
        }
        
    }
}

13. 罗马数字转整数

解法：https://leetcode-cn.com/problems/roman-to-integer/solution/yong-shi-9993nei-cun-9873jian-dan-jie-fa-by-donesp/

class Solution {
    public static HashMap<Character,Integer> map;
    public int romanToInt(String s) {
        if(s.length() == 0) {
            return 0;
        }else {
            map = new HashMap<>();
            map.put('I',1);
            map.put('V',5);
            map.put('X',10);
            map.put('L',50);
            map.put('C',100);
            map.put('D',500);
            map.put('M',1000);
            int prenumber = 0;
            int number = map.get(s.charAt(s.length() - 1));
            int answer = number;
            //number>=prenumber,answer += number否则asnwer -= number
            for(int i = s.length() - 2;i >= 0;i --) {
                prenumber = number;
                number = map.get(s.charAt(i));
                if(number >= prenumber) {
                    answer += number;
                }else {
                    answer -= number;
                }
            }
            return answer;
        }
    }
}

12. 整数转罗马数字

解析：见注释。

class Solution {
    public static HashMap<Integer,String> map;
    public String intToRoman(int num) {
        if(num == 0) {
            return null;
        }else {
            //关键的是把900,400,90,40,9,4的写法写出来，
            //600可以不写，因为DC是符合贪心规则的
            map = new HashMap<>();
            map.put(1000,"M");
            map.put(900,"CM");
            map.put(600,"DC");
            map.put(500,"D");
            map.put(400,"CD");
            map.put(100,"C");
            map.put(90,"XC");
            map.put(60,"LX");
            map.put(50,"L");
            map.put(40,"XL");
            map.put(10,"X");
            map.put(9,"IX");
            map.put(6,"VI");
            map.put(5,"V");
            map.put(4,"IV");
            map.put(1,"I");
            int[] array = {1000,900,600,500,400,100,90,60,50,40,10,9,6,5,4,1};
            StringBuilder sb = new StringBuilder();
            int number = 0;
            //判断条件增加一个num > 0剪枝，也可以不写
            for(int i = 0;i < array.length && num > 0;i ++) {
                number = num / array[i];
                for(int j = 0;j < number;j ++) {
                    sb.append(map.get(array[i]));
                }
                
                num = num % array[i];
            }
            return sb.toString();
        }
    }
}

剑指 Offer 09. 用两个栈实现队列

解法：定义两个栈，一个栈只负责进另外一个栈只负责出，当负责出的栈空了，就把负责进的栈的所有数据放到负责出的栈中。

class CQueue {
    //一个栈负责进栈，另一个栈负责出栈
    Stack<Integer> stackpush;
    Stack<Integer> stackpop;
    public CQueue() {
        this.stackpush = new Stack<>();
        this.stackpop = new Stack<>();
    }
    
    public void appendTail(int value) {
        stackpush.push(value);
    }
    
    public int deleteHead() {
        if(stackpop.isEmpty()) {
            if(stackpush.isEmpty()) {
                return -1;
            }else {
                while(! stackpush.isEmpty()) {
                    stackpop.push(stackpush.pop());
                }
                return stackpop.pop();
            }
        }else {
            return stackpop.pop();
        }
    }
}

225. 用队列实现栈

解法：两个栈来回倒数据，总是一个栈空一个栈有数据，或者两个栈都是空的。

//用两个栈，来回倒数，总是一个栈空另一个栈不空，或者两个栈都空
//可以认为进栈是addLast()出栈是removeFirst()
class MyStack {
    //java中LinkedList实现了Queue接口
    LinkedList<Integer> list1;
    LinkedList<Integer> list2;
    /** Initialize your data structure here. */
    public MyStack() {
        this.list1 = new LinkedList<>();
        this.list2 = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        if(list1.isEmpty()) {
            list2.addLast(x);
        }else if(list2.isEmpty()) {
            list1.addLast(x);
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        if(this.empty()) {
            return -1;
        }else if(list1.isEmpty()) {
            while(list2.size() != 1) {
                list1.addLast(list2.removeFirst());
            }
            return list2.removeLast();
        }else {
            while(list1.size() != 1) {
                list2.addLast(list1.removeFirst());
            }
            return list1.removeLast();
        }
    }
    
    /** Get the top element. */
    public int top() {
        if(this.empty()) {
            return -1;
        }else if(list1.isEmpty()) {
            return list2.peekLast();
        }else {
            return list1.peekLast();
        }
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return list1.isEmpty() && list2.isEmpty();
    }
}

剑指 Offer 31. 栈的压入、弹出序列

解法：见注释

class Solution {
    public boolean validateStackSequences(int [] pushed,int [] poped) {
      if(pushed.length != poped.length) {
          //throw new IllegalArgumentException();
          return false;
      }else if(pushed.length == 0) {
          return true;
      }else {
          Stack<Integer> stackhelp = new Stack<>();
          int index = 0;
          //pushed数组的每一个元素都是要进栈的，只是出栈的时机不同而已
          for(int i = 0;i < pushed.length;i ++) {
              stackhelp.push(pushed[i]);
              while(! stackhelp.isEmpty() && stackhelp.peek() == poped[index]) {
                  index ++;
                  stackhelp.pop();
              }
              //这个不能放到while循环之后，因为如果入栈的出栈的顺序都是12345
              //要是放到while循环之后，那么push数组的1放到栈就取不出来了
              //stackhelp.push(pushed[i]);
          }
          return stackhelp.isEmpty();
      }    
    }
    
}

150. 逆波兰表达式求值

解法：用栈模拟，最后栈中只会有一个结果

class Solution {
    //假设这个表达式总是有效的,并且表达式总会得出有效数值且不存在除数为 0 的情况。
    public int evalRPN(String[] tokens) {
        if(tokens.length == 0) {
            return 0;
        }else {
            Stack<Integer> stack1 = new Stack<>();
            //Stack<String> stack2 = new Stack<>();
            HashSet<String> set = new HashSet<>();
            set.add("+");
            set.add("-");
            set.add("*");
            set.add("/");
            int answer = 0;
            for(int i = 0;i < tokens.length;i ++) {
                //1.set的contains()方法调用的是equals方法
                if(! set.contains(tokens[i])) {
                    stack1.push(Integer.parseInt(tokens[i]));
                }else {
                    //stack2.push(tokens[i]);
                    int number1 = stack1.pop();
                    int number2 = stack1.pop();
                    //int result = 0;
                    if(tokens[i].equals("+")) {
                        answer = (number1 + number2);
                    }else if(tokens[i].equals("-")) {
                        answer = (number2 - number1);
                    }else if(tokens[i].equals("*")) {
                        answer = (number1 * number2);
                    }else {
                        //3.注意谁除以谁
                        answer = (number2 / number1);
                    }
                    //2.运算结果还要入栈，因此上面的表达式是=不是+=
                    stack1.push(answer);
                }
            }
            //4.题目给的逆波兰表达式总是有效的，因此最后栈中只有一个数字，就是答案
            return stack1.pop();
        }
    }
}

165. 比较版本号

解法：思想类似于链表实现数的加法或者字符串实现数的加法

class Solution {
    public int compareVersion(String version1, String version2) {
        //得用\.分割不能用.分割
        String[] numbers1 = version1.split("\.");
        String[] numbers2 = version2.split("\.");
        int length1 = numbers1.length;
        int length2 = numbers2.length;
        int number1 = 0;
        int number2 = 0;
        for(int i = 0;i < Math.max(length1,length2);i ++) {
            number1 = i >= length1 ? 0 : Integer.parseInt(numbers1[i]);
            number2 = i >= length2 ? 0 : Integer.parseInt(numbers2[i]); 
            if(number1 != number2) {
                return number1 > number2 ? 1 : -1;
            }           
        }
        return 0;
    }
}

 

最后

以上就是称心母鸡为你收集整理的高频率面试编程题高频率面试编程题的全部内容，希望文章能够帮你解决高频率面试编程题高频率面试编程题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。