程序员面试金典16.*

文章目录

16.01 交换数字
16.02单词频率
16.03交点
16.04 井字游戏
16.05 阶乘尾数
16.06 最小差
16.07 最大数值
16.08 整数的英文表示
16.09 运算
16.10 生存人数
16.11 跳水板
16.13 平分正方形
16.14 最佳直线（待定）
16.15珠玑妙算
16.16部分排序
16.17连续数列
16.18 模式匹配
16.19水域大小
16.20 T9键盘
16.21 交换和
16.22 兰顿蚂蚁（未做）
16.24 数对和
16.25 LRU缓存
16.26 计算器

16.01 交换数字

在这里插入图片描述
方式一：在原有的基础修改 a = a + b; b = a - b; a = a - b;

方式二：异或 a = a ^ b; b = a ^ b; a = a ^ b;

16.02单词频率

一个HashMap就行

16.03交点

数学题，太恶心了，算了。

16.04 井字游戏

在这里插入图片描述
这个题就直接模拟就好。
这个题判断赢用的是(int)‘X’ * length,不过可能会出小问题，用0和1应该会好一点,不过此时还要考虑当遇到" " 的时候返回什么。

class Solution {
    public String tictactoe(String[] board) {

        int length = board.length;
        int heng = 0; //横的和
        int zong = 0; //纵的和
        int left = 0; //左斜线
        int right = 0; //右斜线
        boolean flag = false; //记录有没有空格

        for (int i = 0; i < length; i++) {

            heng = 0; zong = 0;

            for (int j = 0; j < length; j++) {

                heng = heng +  (int) board[i].charAt(j);
                
                zong = zong + (int) board[j].charAt(i);

                if(board[i].charAt(j) == ' ') flag = true;

            }

            //横纵检查
            if (heng == (int)'X' * length || zong == (int)'X' * length) return "X";
            
            if (heng == (int)'O' * length || zong == (int)'O' * length) return "O";

            //两条斜线上的相加
            left = left + (int)board[i].charAt(i);
            right = right + (int)board[i].charAt(length - i - 1);

        }

        //两条斜线检查
        if (left == (int)'X' * length || right == (int)'X' * length) return "X";
        if (left == (int)'O' * length || right == (int)'O' * length) return "O";

        if (flag) return "Pending";
        return "Draw";

    }
}

16.05 阶乘尾数

在这里插入图片描述
0 是由 *10 得到的，而 10 是由 2 * 5 得到的
因此我们求 n！过程中存在多少个 2 * 5
因为 2 的个数必定比 5 的个数多，因此我们只求 5 的个数
n! = 1 * 2 * 3 * 4 * (1 * 5) * … * (2 * 5) * … * (3 * 5) …
当然因为存在25和125这类数，所以
count = n / 5 + n / 25 + n / 125 + …
因此可以转换为一个循环 n=n/5; count+=n;

16.06 最小差

排序，然后双指针。

16.07 最大数值

了解一下位运算，移位操作。比较一下符号位即可

16.08 整数的英文表示

没啥意思

16.09 运算

挺无语的，不用做。

16.10 生存人数

在这里插入图片描述
差分数组的思想
birth那里+1， death的下一位 -1
再对差分数组求和，求最大值即可

16.11 跳水板

太简单了，pass

16.13 平分正方形

在这里插入图片描述
求过两个正方形中心的直线即可，如果两者中心重合，取垂直于x轴的直线。再根据斜率判断与正方形哪条边相交。题目简化了很多，模拟就好。

16.14 最佳直线（待定）

对于特定的一组直线AX+BY+C=0,去求最大

16.15珠玑妙算

用一个哈希表就行

16.16部分排序

在这里插入图片描述

你可以直接排序，然后原数组与排序数组比较。也可以用下面的思路遍历一遍。

首先虽然题目没说，但是实际运行下来数列是单调递增的，所以我们下面默认数列是递增的。

那么对于元素 a[i] 来说，如果它左边存在大于 a[i] 的元素，那么 a[i] 是一定要参与到排序里去的。或者说如果它右边存在小于 a[i] 的元素，那么 a[i] 也是要参与到排序里去的。

所以我们只需要寻找最靠右的那个数（满足左边存在大于它的数），和最靠左的那个数（满足右边存在小于它的数），那么这两个数之间就是要排序的区间了。

为什么最靠右的那个（满足左边存在大于它的数）数一定能保证右边没有更小的数了呢？因为如果右边还有更小的数，那么那个更小的数才是更靠右的啊，这就矛盾了。

所以我们只需要从左到右扫描一遍，用一个变量维护一下最大值就行了，然后反向再遍历一遍，维护一个最小值。

class Solution {
    public int[] subSort(int[] array) {
        int size1=array.length;
        int minValue=Integer.MAX_VALUE;
        int maxValue=Integer.MIN_VALUE;
        int left=-1,right=-1;
        for(int i=0;i<size1;i++){
            if(maxValue<=array[i]) maxValue=array[i];
            else right=i;
        }
        if(right==-1) return new int[]{-1,-1};
        for(int i=size1-1;i>-1;i--){
            if(minValue>=array[i]) minValue=array[i];
            else left=i;
        }
        return new int[]{left,right};

    }
}

16.17连续数列

在这里插入图片描述

注意是先赋值给maxValue,再ans=0；主打一个贪心。

class Solution {
    public int maxSubArray(int[] nums) {
        int size1=nums.length;
        int ans=0;
        int maxValue=Integer.MIN_VALUE;
        for(int i=0;i<size1;i++){
            ans+=nums[i];
            if(ans>maxValue) maxValue=ans;
            if(ans<0) ans=0;    
        }
        return maxValue;

    }
}

16.18 模式匹配

这种题用python写好一点，别的语言好麻烦。

16.19水域大小

经典DFS
在这里插入图片描述

class Solution {
    public int[] pondSizes(int[][] land) {
        int aLength=land.length;
        int bLength=land[0].length;
        int count=0;
        ArrayList<Integer> array=new ArrayList<>();

        for(int i=0;i<aLength;i++){
            for(int j=0;j<bLength;j++){
                count=dfs(land,i,j);
                if(count!=0) array.add(count);
            }
        }

        int[] ans=new int[array.size()];
        for(int i=0;i<array.size();i++) ans[i]=array.get(i);
        Arrays.sort(ans);
        return ans;

    }

    public int dfs(int[][]land, int i, int j){
        if(i<0 || i>=land.length || j<0 || j>=land[0].length || land[i][j]!=0) return 0;
        land[i][j]=-1;
        int count=1;
        count+=dfs(land,i-1,j);
        count+=dfs(land,i-1,j-1);
        count+=dfs(land,i-1,j+1);
        count+=dfs(land,i,j-1);
        count+=dfs(land,i,j+1);
        count+=dfs(land,i+1,j-1);
        count+=dfs(land,i+1,j);
        count+=dfs(land,i+1,j+1);
        return count;

    }
}

16.20 T9键盘

用一个大数组先记录一下就行

16.21 交换和

排序后双指针就行

16.22 兰顿蚂蚁（未做）

题目读起来好费劲，不过应该就是一个模拟题

16.24 数对和

排序后双指针，或者用哈希表也行

16.25 LRU缓存

解决方案：链表（处理新老关系），哈希表（查询元素有没有）
用LinkedHashMap或者双向链表+哈希表
别人的博客
主要是实现一和实现三

16.26 计算器

在这里插入图片描述
用栈来模拟

class Solution {
    public int calculate(String s) {
        Deque<Integer> stack=new ArrayDeque<Integer>();
        char preSign = '+';
        int num = 0;
        int n = s.length();
        for(int i=0;i<n;i++){
            if(Character.isDigit(s.charAt(i))){
                num=num*10+s.charAt(i)-'0';
            }
            if((!Character.isDigit(s.charAt(i)) && s.charAt(i)!=' ')  || i==n-1){
                switch(preSign){
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        preSign = '*';
                        stack.push(num*stack.pop());
                        break;
                    case '/':
                        preSign = '/';
                        stack.push(stack.pop()/num);
                }
                num=0;
                preSign=s.charAt(i);

            }
        }
        int ans=0;
        while(!stack.isEmpty()){
            ans+=stack.pop();
        }
        return ans;

    }
}