Flutter面经-算法篇_秦子帅的博客

作者 | 猫吃小鱼

地址 | juejin.im/post/5ea3971b6fb9a03c64232521

抛出问题

应广大同学要求，整理下这两周面试遇到的算法题，都是需要手写实现（java、android、flutter面经请移步 Android-Flutter面经建议使用电脑查看，内容比较多）

本人算法相当菜，面试之前也没刷题的概念，所以算法答的很不好，下面只简单说下都遇到了哪些吧

判断单链表是否有环

该问题被问到过三次，应该是相当高频的吧，第一次我只想到了下面的第一种方法，面试官很nice，引导着我给出了第二种解决方案

方法一：循环遍历节点，遍历一个便标记一个，遍历过程判断是否被标记，若已被标记则表示有环
方法说明：头指针移动，若到达之前到达过的位置则表示有环，若无环则会走到链表末端。
public class Solution {
public boolean hasCycle(ListNode head) {
//声明一个set存放已遍历的节点，即为标记节点（Set中不允许重复元素）
Set<ListNode> set = new HashSet<>();
while(head!=null) {
if(set.contains(head)) {
return true;
}else {
set.add(head);
head = head.next;
}
}
return false;
}
}

方法二：声明两个指针，一个指针走一次经过两个节点(快指针quick)，另一个走一次经过一个节点(慢指针slow)
方法说明：快指针走的比较快，若链表有环，则一定会追上慢指针，若无环，则会走到链表末端。
public class Solution {
public boolean hasCycle(ListNode head) {
==//声明两个节点从头开始遍历节点==
ListNode quick = head;
ListNode slow = head;
//当快指针能够走到头表示无环
while(quick!=null&&quick.next!=null){
quick = quick.next.next;
slow = slow.next;
if(quick==slow){
return true;
}
}
return false;
}
}

交换链表中所有相邻结点的顺序

1->2->3->4 交换之后为 2->1->4->3.（基本没有写出来，当时面试官问我你没刷题吗，我实话实话没刷过）

public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null)
            return null;
        if(head.next==null){
            return head;
        }
        ListNode newHead = head.next;
        while(head.next!=null){
            ListNode nextNode = head.next;
            if(nextNode.next==null){
                head.next = null;
            }else{
                if(nextNode.next.next==null)
                    head.next = nextNode.next;
                else
                    head.next = nextNode.next.next;
            }
            ListNode temp = head;
            head = nextNode.next;
            nextNode.next = temp;
            if(head==null){
                break;
            }
        }
        return newHead;
    }
}

package listnode;
/**
* @author Gavenyeah
* @date Start_Time：2016年4月1日下午4:22:55
* @date End_Time：2016年4月1日下午4:32:36
*/
public class SwapPairs {

public static void main(String[] args) {
Node head=ListNode.getSingleList();
ListNode.printList(head);
head=new SwapPairs().swapPairs(head);
ListNode.printList(head);
}

public Node swapPairs(Node head) {
Node root=head;
if(head!=null&&head.next!=null){
root=head.next;
Node pre=head;
Node p=null;
Node q=null;
while(head!=null&&head.next!=null){

p=head.next;
q=p.next;

pre.next=p;
p.next=head;
head.next=q;

pre=head;
head=q;
}
}
return root;
}
}

（2）改变相邻节点对的值，不改变节点指针（通过数组思维实现）

public ListNode swapPairs(ListNode head){
public ListNode swapPairs(ListNode head) {
ListNode p=head;
while(p!=null){
ListNode q=p.next;
if(q!=null){
int temp=p.val;
p.val=q.val;
q.val=temp;
p=p.next;
}
p=p.next;
}
return head;
}
}
原文链接：https://blog.csdn.net/y999666/article/details/51037888

字符串反转

被问到过两次，第一次是某公司的技术负责人，人超级好，我第一中解法用的栈实现的，然后就问我时间复杂度和空间复杂度是多少，还耐心给我讲解这两个的概念和如何计算，然后又让我想第二种解法，第二种我写的是chartAt实现，面试官又问时间复杂度和空间复杂度是多少，然后让我再想更优的解法，最后在面试官的开导下写了下面第三种实现，特感谢这位面试官。

public String reverseWithSwaps(String string) {
        final char[] array = string.toCharArray();
        final int length = array.length – 1;
        final int half = (int) Math.floor(array.length / 2);
        char c;
        for (int i = length; i >= half; i–) {
            c = array[length – i];
            array[length – i] = array[i];
            array[i] = c;
        }
        return String.valueOf(array);
    }

Java斐波那契数列1 1 2 3 5 8 13

当时大体写出来了但是临界值判断错了

public int fibonacci(int n) {
int[] res = {0, 1};
if (n < 2) {
return res[n];
}
int first = 0;
int second = 1;
int fibn = 0;
for (int i = 2; i <= n; i++) {
fibn = first + second;
first = second;
second = fibn;
}
return fibn;
}

手写parseInt

当时是写出来了，但是方法很笨，之后去看了下源码，膜拜啊

public static int parseInt(String s){
return parseInt(s, 10);
}

    public static int parseInt(String s , int radix){
        int result = 0;
        int i = 0;
        int digit ;
        boolean nagitive = false;
        int length = s.length();
        if(length > 0){
            char firstChar = s.charAt(0);
            //+,-号
            if(firstChar < ‘0’){
                if(firstChar == ‘-‘){
                    nagitive = true;
                }else if (firstChar != ‘+’){
                    throw new NumberFormatException();
                }
                //只有一个符号
                if(length == 1){
                    throw new NumberFormatException();
                }
                //向后取数值位
                i++;
            }

            while (i < length){
                //取字符串的第i个字符转int
                digit = Character.digit(s.charAt(i++), radix);
                //乘10
                result *= radix;
                //减数值
                result -= digit;
            }

        }else {
            throw new NumberFormatException();
        }
        return nagitive ? result : -result;
    }
原文链接：https://blog.csdn.net/thqtzq/java/article/details/86442001