【Lintcode刷题】算法（持续更新）

Lintcode刷题地址：http://www.lintcode.com/zh-cn/problem/#_=_

一些大厂面试时喜欢考查的，对于锻炼自己的逻辑思维也大有裨益~

发现对链表的考察较多。。

 

0.经典的二分查找法（前提为有序序列）

/** 
     * 非递归二分查找 
     *  
     * @param num 
     * @param number 
     * @return 
     */  
    public static int binarySearch(int num[], int number) {  
        if (num == null || num.length == 0) {  
            return -1;  
        }  
        int start, end, mid;  
        start = 0;  
        end = num.length - 1;  
        while (start <= end) {  
            mid = (start + end) / 2;  
            if (num[mid] == number)  
                return mid;  
            else if (num[mid] > number) {  
                end = mid - 1;  
            } else {  
                start = mid + 1;  
            }  
        }  
        return -1;  
    }  
  
    /** 
     * 递归查找 
     *  
     * @param num 
     * @param number 
     * @return 
     */  
    public static int RecursivebinarySearch(int num[], int start, int end, int key) {  
        int mid = (start + end) / 2;  
        if (num == null || num.length == 0 || key < num[start] || key > num[end]) {  
            return -1;  
        } else if (num[mid] > key) {  
            return RecursivebinarySearch(num, start, mid - 1, key);  
        } else if (num[mid] < key) {  
            return RecursivebinarySearch(num, mid + 1, end, key);  
        } else {  
            return mid;  
        }  
  
    } 

 

 

1.二叉树的路径和：

 

class TreeNode {
     public int val;
     public TreeNode left, right;
     public TreeNode(int val) {
         this.val = val;
          this.left = this.right = null;
      }
 }



public class Solution {
    /*
     * @param root: the root of binary tree
     * @param target: An integer
     * @return: all valid paths
     */
    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        // write your code here
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(null == root) return result;
        Stack<Integer> stack = new Stack<Integer>();
        
        binaryTreePathSum(result, stack, root, 0, target);
        
        return result;
    }
    
    public void binaryTreePathSum(List<List<Integer>> result, Stack stack, TreeNode root, int sum, int target) {
        sum += root.val;
        stack.push(root.val);
        
        if(sum == target && root.left==null && root.right==null) {
            List<Integer> list = new ArrayList<Integer>(stack);
            result.add(list);
            stack.pop();
            return;
        }else{
            if(root.left != null) {
                binaryTreePathSum(result, stack, root.left, sum, target);
            }
            if(root.right != null) {
                binaryTreePathSum(result, stack, root.right, sum, target);
            }
            stack.pop();
        }
    }
}

 

 

2.合并排序数组

class Solution {
    /**
     * @param A and B: sorted integer array A and B.
     * @return: A new sorted integer array
     */
    public ArrayList<Integer> mergeSortedArray(ArrayList<Integer> A, ArrayList<Integer> B) {
        // write your code here
        int bSize = B.size();
        for(int i=0;i<bSize;i++)
            A.add(B.get(i));
        Collections.sort(A);
        return A;
    }
}

 不用Java API的做法（一般是考这个）：

public int[] mergeSortedArr(int[] a, int[] b) {
  int[] result = new int[a.length + b.length];
  int i,j,k = 0;
  while(i<a.length && j<b.length) {//循环比较两个数最大长度的结果后，只会剩下一个数组的元素
    if(a[i] <= b[j]) {
      result[k++] = a[i++];
    }else {
      result[k++] = b[j++];
    }
  }

  while(i<a.length) {
    result[k++] = a[i++];
  }

  while(j<b.length) {
    result[k++] = b[j++];
  }

  return result;
}

 

 

3.翻转单链表

 

方式一：递归

 

public ListNode reverse1(ListNode head) {
        // 当为空或者本节点为末尾节点的时候
        if (head == null || head.next == null) //也是递归结束的条件
            return head;
        ListNode temp = head.next;
        ListNode reversedHead = reverse1(head.next);
        // 获取先前的下一个节点，让该节点指向自身
        temp.next = head;
        // 破坏以前自己指向下一个节点
        head.next = null;
        // 层层传递给最上面的
        return reversedHead;
    }

 方式二：非递归

 

 

public ListNode reverse(ListNode head){  
        ListNode p = head,q = null,front = null;  
        while(p!=null){  
            q = p.next;//设置q是p结点的后继结点,即用q来保持p的后继结点  
            p.next = front;//逆转,即使p.next指向p结点的前驱结点  
            front = p;//front向后移一步  
            p = q;//p向后移一步  
        }  
        head = front;//head指向原链表的最后一个结点，完成逆转  
        return head;
   }  

 

 

4.Replace With Greatest From Right

 

public class Solution {
    /*
     * @param : An array of integers.
     * @return: nothing
     */
    public void arrayReplaceWithGreatestFromRight(int[] nums) {
        // Write your code here.
        int size = nums.length;
        int max = nums[size - 1];
        nums[size - 1] = -1;
        
        for(int i=size-2; i>=0; i--) {
            int tmp = nums[i];
            nums[i] = max;
            if(tmp > max) {
                max = tmp;
            }
        }
    }
}

 

 

5.Sum of All Subsets

 

public class Solution {
    /*
     * @param : the given number
     * @return: Sum of elements in subsets
     */
    public int subSum(int n) {
        // write your code here
        if(n == 1) return 1;
        List<Integer> list = new ArrayList<>();
        for(int i=1; i<=n; i++) {
            list.add(i);
        }
        
       int subsetSum = getSubsetSum(list);
       return subsetSum;
    }
    
    public int getSubsetSum(List<Integer> list) {
        int sum = 0;
        List<List<Integer>> result = new ArrayList<>();
        for(int i=0; i<Math.pow(2, list.size()); i++) {
            List<Integer> subList = new ArrayList<>();
            int index = i;
            for(int j=0; j<list.size(); i++) {
                if((index & 1) == 1) {
                    subList.add(j);
                    sum += j;
                }
                index >>= 1;
            }
            if(subList.size() == 0) continue;
            result.add(subList);
        }
        return sum;
    }
}

 

 

6.连接两个字符串中的不同字符 

样例

给出 s1 = aacdb, s2 = gafd
返回 cbgf
给出 s1 = abcs, s2 = cxzca;
返回 bsxz

public static String concatenetedString(String s1, String s2) {
    // write your code here
    String str = "";
    
    List<Character> common = new ArrayList<>();
    char[] b = s1.toCharArray();
    for(int i=0; i<b.length; i++) {
        if(s2.indexOf(b[i]) > -1) {
            common.add(b[i]);
        }
    }
    
    List<Character> notin = new ArrayList<>();
    char[] b2 = s2.toCharArray();
    for(int i=0; i<b2.length; i++) {
        if(!common.contains(b2[i])) {
            notin.add(b2[i]);
        }
    }
    
    for(int i=0; i<b.length; i++) {
        if(!common.contains(b[i])) {
            str += b[i];
        }
    }
    
    for(int i=0; i<notin.size(); i++) {
        str += notin.get(i);
    }
    
    return str;
}

 

7.快慢指针查找中点

public class NodeListTest {
        
        public static void main(String[] args){  
        int[] array = {1,2,3,4,5,6,7};  
        Node node = NodeList.arrToNodeList(array);  

        NodeList.printNodeList(node);  
        System.out.println();
        System.out.println(NodeList.getMidNode(node));
    }  
  

}

//链表节点类
class Node {
        private Node next;//节点指向的下一个节点
        private int val;//本节点的值
        public Node getNext() {
                return next;
        }
        public void setNext(Node next) {
                this.next = next;
        }
        public int getVal() {
                return val;
        }
        public void setVal(int val) {
                this.val = val;
        }
        @Override
        public String toString() {
                return "Node [val=" + val + "]";
        }
        
}

//链表类
class NodeList { 
        private static Node head, tail, curr;
        
        /**
         * 将数组转换成链表，返回链表的头结点
         * @param arr
         * @return
         */
        public static Node arrToNodeList(int arr[]) {
                if(arr.length > 0) {
                        for(int i=0; i<arr.length; i++) {
                                curr = new Node();
                                //节点信息
                                curr.setNext(null);
                                curr.setVal(arr[i]);
                                if(head == null) {//对首节点的初始化赋值
                                        head = curr;
                                        tail = curr;
                                }else{//新的节点默认为尾节点
                                        tail.setNext(curr);
                                        tail = curr;
                                }
                        }
                }
                return head;
        }
        
        /**
         * 打印该链表的所有节点元素
         * @param head 头结点信息
         */
        public static void printNodeList(Node head) {
                System.out.print(head + ", ");
                while(head.getNext() != null) {
                        head = head.getNext();
                        System.out.print(head + ", ");
                }
        }
        
        /**
         * 根据链表信息（只包含头结点）取出中间节点的信息
         * @param head 头结点信息
         * @return
         */
        
        public static Node getMidNode(Node head) {
                //慢指针（每次走一步），快指针（每次走两步）初始状态都指向头结点
                Node stepOne=head, stepTwo = head;
                while(stepTwo!=null && stepTwo.getNext()!=null) {
                        stepTwo = stepTwo.getNext().getNext();
                        stepOne = stepOne.getNext();
                }
                return stepOne;
        }
}

 

8、判断一个链表是不是一个“环”

定义两个指针fast和slow，其中fast是快指针，slow是慢指针，二者的初始值都指向链表头，slow每前进一步，fast每次前进两步，两个指针同时向前移动，快指针每移动一次都要和慢指针比较，直到当快指针等于慢指针为止，就证明这个链表是带环的单向链表，否则，证明这个链表是不带环的循环链表(fast先行到达尾部为NULL，则为无环链表)。

public boolean isLoop(Node head){
        Node fast = head;
        Node slow = head;
        if (fast == null) {
            return false;
        }
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return !(fast == null || fast.next == null);
    }

 

 

9、查找有序序列中指定的数字第一次出现的位置

如“12345555678”查第一个“5”出现的位置（提示：二分查找法进行改进）

int myBinarySearch(int num[],int len,int key)  
{  
    int low=0;  
    int hight=len-1;  
    int mid=0;    
    int switchFind=0;  
    int index=0;      
    if (num[0]==key)  
        {  
            return 1;  
        }

    while (low<=hight)  
    {  
        mid=(hight+low)/2;  
        if (num[mid]==key)  
        {  
            switchFind=1;  
            break;  
        }  
        else if (num[mid]>key)  
        {  
            hight=mid-1;  
        }  
        else if (num[mid]<key)  
        {  
            low=mid+1;  
        }     
    }  
    while (switchFind)  
    {     
        mid--;  
          
        if (num[mid]!=key)  
        {  
            index=mid;  
            return index+2;  
        }  
    }  
    return -1;  
}  

 

10、写一个方法判断一个数是不是2的幂？

n & (n-1) == 0

附Java位运算：https://blog.csdn.net/lazyman_54/article/details/51283459

 

11、斐波那契数列递归实现与改进

是从0开始的：0，1，1，2，3，5……（不是从1开始）

public static int Recursion(int n){

        if(n==1){
            return 0;
        }

        if(n==2){
            return 1;
        }
        return Recursion(n-1)+Recursion(n-2);
    }

 时间复杂度：O（n^n）

改进：Recursion(n-1)已经包含了Recursion(n-2)的结果了，所以用递归的话又会把Recursion(n-2)展开，造成效率低下，

可以把每次加的结果给缓存起来，如下：

public static long  fil(int n){  
        long a=1;  
        long b=1;  
        long c=0;  
        if(n==1) return 1;  
        else if(n==2) return 1;  
        else if(n>2){  
            for (int i=3;i<=n;i++){  
                c=a+b;  
                a=b;  
                b=c;  
            }  
            return c;  
        }  
        else{  
            System.out.println("the number cannot be lower than zero");  
            return 0;  
        }     
    }

 

12、查找不重复的数字（其他数字都重复2遍）

对异或运算的巧妙运用（任何数异或00都得到这个数本身）：

例如：

十进制：15  转成二进制为：11111111            

十进制：2   转成二进制为：00000010          

按位进行异或操作的结果为：11111101  ——>13  

如果我们将这个结果继续与其中的一个数进行异或运算，就可以得出另外一个数！  2^15^15 = 2    or     2^15^2 = 15

public static int NumberOf1(int[] arr) {  
        int len = arr.length;  
        int res = -1;  
        if(len > 1) {  
            res = arr[0];  
            for (int i = 1; i < len; i++) {  
                res = res ^ arr[i];  
            }  
        }  
        return res;  
    } 

 

13、字符串反转（用递归）

一般会想到用数组，String的charAt, toCharArray函数。

public static String strReverseWithArray(String string){
        if(string==null||string.length()==0)return string;
        int length = string.length();
        char [] array = string.toCharArray();
        for(int i = 0;i<length;i++){
            array[i] = string.charAt(length-1-i);
        }
        return new String(array);
    }

 

用递归的方式如下：

public static String strReverseWithRecursive(String string){
        if(string==null||string.length()==0)return string;
        int length = string.length();
        if(length==1){
            return string;
        }else{
            return  strReverseWithRecursive(string.substring(1))+string.charAt(0);
        }
    }

 

14、求n的加法组合，将一个整数拆分成多个整数相加的形式

例1:
3=1+1+1
3=1+2
3=3

解决思路：https://blog.csdn.net/bluetjs/article/details/52370916

public class Sum1ToN {  
  
    private void print(List<Integer> list) {  
        for (Integer k : list) {  
            System.out.print(k + "+");  
        }  
    }  
  
    private void f(int n, List<Integer> list, int start) {  
        if (n == 1) {  
            print(list);  
            System.out.println(1);  
        } else {  
            for (int i = start; i <=n / 2; i++) {  
                list.add(i);  
                f(n - i, list, i);  
                list.remove(list.size() -1);  
            }  
            print(list);  
            System.out.println(n);  
  
        }  
    }  
  
    public static void main(String[] args) {  
        List<Integer> list = new ArrayList<Integer>();  
        new Sum1ToN().f(9,list, 1);  
    }  
  
}