字節(jié)跳動(dòng)的三道編碼面試題的實(shí)現(xiàn)

發(fā)布時(shí)間：2020-04-08 16:35:20 作者：沖殺

這篇文章主要介紹了字節(jié)跳動(dòng)的三道編碼面試題的實(shí)現(xiàn)，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧

國(guó)慶節(jié)后，自己的一個(gè)小圈子微信群的伙伴們發(fā)了一張圖片，是網(wǎng)上流傳的字節(jié)跳動(dòng)的面試題編碼，閑的無(wú)事就思索了下，發(fā)現(xiàn)都不難，都是對(duì)基礎(chǔ)的數(shù)學(xué)知識(shí)的考量。先上圖吧！

當(dāng)然40分鐘，我也無(wú)法把任意兩題編碼完成，只是知道大概的解題思路，唯一能確定的，在面試規(guī)定時(shí)間內(nèi)，第二題我是肯定可以在20分鐘內(nèi)編碼完成。

題目一

基礎(chǔ)知識(shí)就是初中的平面直角坐標(biāo)系，解析思路：

計(jì)算總周長(zhǎng)；
將各邊長(zhǎng)的前后坐標(biāo)計(jì)算出來(lái)封裝好，第四步要使用；
根據(jù)K段值計(jì)算出平均分段后的長(zhǎng)度；
然后循環(huán)K次，根據(jù)平均長(zhǎng)度依次相加計(jì)算等分點(diǎn)的坐標(biāo)。

不多說(shuō)，上代碼：

先定義坐標(biāo)的Point類

class Point {
        float x;
        float y;

        public Point() {
        }

        public Point(float x, float y) {
            this.x = x;
            this.y = y;
        }

        public Point(Point point) {
            this(point.x, point.y);
        }

        @Override
        public String toString() {
            return "Point, x：" + x + " y：" + y;
        }
    }

N邊形的邊封裝類

class Line {
        Point begin;
        Point end;
        float length;

        public Line() {

        }

        public Line(Point begin, Point end, float length) {
            this.begin = begin;
            this.end = end;
            this.length = length;
        }
    }

現(xiàn)在上實(shí)現(xiàn)計(jì)算的類

這段代碼第一個(gè)版本的時(shí)候，在正方形偶數(shù)等分的時(shí)候，坐標(biāo)點(diǎn)計(jì)算不準(zhǔn)確，今晚上看著代碼思考了10分鐘的樣子，稍微改動(dòng)了下，暫時(shí)沒(méi)有這個(gè)bug了。其他的bug，期待大家一起發(fā)現(xiàn)，然后修復(fù)吧！

public class Polygon {

    /**
     * 計(jì)算邊的長(zhǎng)度
     * 
     * @return
     */
    private static float lineLength(Point a, Point b) {
        float length;

        if (a.x == b.x) {
            // 垂直線條
            length = Math.abs(a.y - b.y);
        } else {
            length = Math.abs(a.x - b.x);
        }

        return length;
    }

    /**
     * 計(jì)算 周長(zhǎng)
     * 
     * @return
     */
    private static float totalSideLength(Point[] points, Line[] lines) {
        float side = 0;

        for (int i = 1; i < points.length; i++) {
            Point prev = points[i - 1];
            Point point = points[i];

            float length = lineLength(prev, point);

            side += length;
            lines[i - 1] = new Line(prev, point, length);

            if (i == points.length - 1) {
                length = lineLength(point, points[0]);

                side += length;
                lines[i] = new Line(point, points[0], length);
            }
        }

        return side;
    }

    public static Point[] division(Point[] points, int divisionNum) {
        Point[] divisionPoint = new Point[divisionNum];

        // 計(jì)算周長(zhǎng)
        Line[] lines = new Line[points.length];
        float side = totalSideLength(points, lines);

        // 等分長(zhǎng)度
        float divisionLength = side / divisionNum;

        int lineIndex = -1;
        float sumLength = 0;

        for (int i = 0; i < divisionNum; i++) {
            if (i == 0) {
                // 第一個(gè)等分點(diǎn)直接是起始點(diǎn)坐標(biāo)
                divisionPoint[i] = new Point(points[0]);
                continue;
            }

            divisionPoint[i] = new Point();
            float lineLength = divisionLength * i;

            while (true) {
                Line line;
                if (sumLength < lineLength) {
                    lineIndex++;
                    line = lines[lineIndex];
                    sumLength += line.length;
                } else
                    line = lines[lineIndex];

                if (sumLength >= lineLength) {
                    float temp = sumLength - lineLength;

                    if (line.begin.x == line.end.x) {
                        // begin和end的坐標(biāo)點(diǎn)垂直
                        divisionPoint[i].x = line.begin.x;

                        if (line.end.y > line.begin.y)
                            divisionPoint[i].y = line.end.y - temp;
                        else
                            divisionPoint[i].y = line.end.y + temp;
                    } else {
                        // begin和end的坐標(biāo)點(diǎn)水平
                        divisionPoint[i].y = line.end.y;

                        if (line.end.x > line.begin.x)
                            divisionPoint[i].x = line.end.x - temp;
                        else
                            divisionPoint[i].x = line.end.x + temp;
                    }
                    
                    break;
                }
            }
        }

        return divisionPoint;
    }

    private static void print(Point[] points) {
        for (int i = 0; i < points.length; i++) {
            System.out.println("第" + (i + 1) + "等分點(diǎn), x：" + points[i].x + "，y：" + points[i].y);
        }
    }

    public static void main(String[] args) {
        Point[] points = new Point[] { new Point(0, 0), new Point(0, 1), new Point(1, 1), new Point(1, 0) };

        Point[] divPoints = division(points, 8);

        print(divPoints);
    }
}

題目二

解題思路：

對(duì)應(yīng)位數(shù)的數(shù)字相加，永遠(yuǎn)不會(huì)超過(guò)18，所以，我們就先把對(duì)應(yīng)位置的和計(jì)算出來(lái)，然后再反復(fù)循環(huán)找到大于9的數(shù)，向高位進(jìn)位。

這個(gè)比較簡(jiǎn)單，只是考察個(gè)位數(shù)的正整數(shù)加法永遠(yuǎn)不大于18這個(gè)細(xì)節(jié)。

上代碼：

public class LinkAddition {
    static class NumNode {
        public int num;
        public NumNode next;

        public NumNode() {
        }

        public NumNode(int num) {
            this.num = num;
        };

        public NumNode(int num, NumNode next) {
            this(num);
            this.next = next;
        }
    }

    private static int length(NumNode num) {
        int length = 0;

        NumNode temp = num;
        while (temp != null) {
            length++;
            temp = temp.next;
        }

        return length;
    }

    private static NumNode calc(NumNode a, NumNode b, int aLength, int bLength) {
        NumNode aNode = a;
        NumNode bNode = b;

        NumNode result = new NumNode();
        NumNode resultNode = result;

        // 計(jì)算b鏈表再a中的起始索引
        int aStartIndex = aLength - bLength;

        for (int i = 0; i < aLength; i++) {
            if (i >= aStartIndex) {
                resultNode.num = aNode.num + bNode.num;
                bNode = bNode.next;
            } else
                resultNode.num = aNode.num;

            aNode = aNode.next;
            if (aNode != null) {
                resultNode.next = new NumNode();
                resultNode = resultNode.next;
            }
        }

        return result;
    }

    public static NumNode addition(NumNode a, NumNode b) {
        NumNode result = null;

        // 計(jì)算位數(shù)
        int aLength = length(a);
        int bLength = length(b);

        if (aLength > bLength) {
            result = calc(a, b, aLength, bLength);
        } else {
            result = calc(b, a, bLength, aLength);
        }

        boolean isGreater9 = true;

        while (isGreater9) {
            isGreater9 = false;
            NumNode node = result;

            while (node != null) {
                // 檢查是否有大于9的節(jié)點(diǎn)
                if (node.num > 9) {
                    isGreater9 = true;
                    break;
                }

                node = node.next;
            }

            // 沒(méi)有大于9且需要進(jìn)位的節(jié)點(diǎn)
            if (!isGreater9)
                break;
            
            node = result;
            
            if (node.num > 9) {
                // 頭節(jié)點(diǎn)的內(nèi)容跟大于9，需要進(jìn)位
                result = new NumNode(1, node);

                node.num = node.num - 10;
            }

            while (node.next != null) {
                if (node.next.num > 9) {
                    node.num += 1;
                    node.next.num = node.next.num - 10;
                }
                node = node.next;
            }
        }

        return result;
    }

    private static void print(NumNode num) {
        NumNode node = num;
        while (node != null) {
            System.out.print(node.num);
            node = node.next;
        }
    }

    public static void main(String[] args) {
        NumNode a = new NumNode(9);
        a.next = new NumNode(9, new NumNode(9));

        NumNode b = new NumNode(9);
        // b.next = new NumNode(9, new NumNode(9));

        NumNode result = addition(a, b);

        print(result);
    }
}

題目三

這個(gè)我寫(xiě)的第一個(gè)版本，只契合類那個(gè)舉例，然后瞬間就被我推翻類，最后坐下思考類10分鐘，把這個(gè)按照二維數(shù)組的思路解析了。

先找到最高處，然后就以最高處為一個(gè)維度，做循環(huán)計(jì)算出水量，還是上代碼吧：

public class Water {
    public static int waterNum(int[] steps) {
        int waterNum = 0;

        int max = steps[0];
        for (int i = 1; i < steps.length; i++) {
            if (max < steps[i])
                max = steps[i];
        }

        for (int i = 0; i < max; i++) {
            int num = 0, index = 0;

            for (int n = 0; n < steps.length; n++) {
                if (steps[n] - i > 0) {
                    if (num > 0) {
                        waterNum += n - index - 1;
                    }

                    num = steps[n] - i;
                    index = n;
                }
            }
        }

        return waterNum;
    }

    public static void main(String[] args) {
        int[] steps = new int[] { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 3, 0, 1 };
        int water = waterNum(steps);

        System.out.println(water);
    }
}

總結(jié)：

其實(shí)這幾題本身的知識(shí)點(diǎn)并不難，都是平時(shí)用到的，就看怎么轉(zhuǎn)化為代碼罷了。

第一題考察的直角坐標(biāo)系上怎么計(jì)算邊長(zhǎng)，然后根據(jù)均分等長(zhǎng)從第一條邊挨著走，計(jì)算對(duì)應(yīng)的坐標(biāo)，該知識(shí)點(diǎn)在初中就已學(xué)過(guò)。

第二題則是考察每位上的正整數(shù)加法到底最大能到多少，只要明白了這一點(diǎn)，把每一位上相加后，再統(tǒng)一做進(jìn)位處理就可以了。

第三題的代碼量是最少的，我的解題思路是二位數(shù)組的方式, 也不算難。

到此這篇關(guān)于字節(jié)跳動(dòng)的三道編碼面試題的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)字節(jié)跳動(dòng)編碼面試題內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持腳本之家！