盘点了高频的面试题

数组

Two Sum √

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have *exactly* one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
1
2
3
4
5
6
7
8
9
10
11
public int[] twoSum(int[] nums, int target) {
        int res[] =new int[2];
        HashMap<Integer,Integer> map = new HashMap();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                return new int[]{map.get(nums[i]),i};
            }
            else map.put(target-nums[i],i);
        }    
        return res;
    }

Maximum Swap √

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Example 1:

1
2
3
Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

1
2
3
Input: 9973
Output: 9973
Explanation: No swap.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int maximumSwap(int num) {
        char[] a = Integer.toString(num).toCharArray();
        char[] n=new char[a.length];
        char[] m=new char[a.length];
        for(int i=0;i<a.length;i++){
            n[i]=a[i];
            m[i]=a[i];
        }        
        Arrays.sort(n);
        for(int i=a.length-1,j=0;i>=0;i--,j++){
            if(n[i]!=m[j]){
                swap(m,j,find(m,n[i]));
                break;
            }
        }
        return Integer.valueOf(new String(m));
    }
    public int find(char[] m,char v){
        for(int i=m.length-1;i>0;i--){
            if(v==m[i]) return i;
        }
        return 0;
    }
    public void swap(char a[],int i,int j){
        char tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
    }

O(n)解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maximumSwap(int num) {
        char[] A = Integer.toString(num).toCharArray();
        int[] last = new int[10];
        for (int i = 0; i < A.length; i++) {
            last[A[i] - '0'] = i;
        }

        for (int i = 0; i < A.length; i++) {
            for (int d = 9; d > A[i] - '0'; d--) {
                if (last[d] > i) {
                    char tmp = A[i];
                    A[i] = A[last[d]];
                    A[last[d]] = tmp;
                    return Integer.valueOf(new String(A));
                }
            }
        }
        return num;
    }
}

Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;

        if (m > n) 
            return findMedianSortedArrays(nums2, nums1);

        int i = 0, j = 0, imin = 0, imax = m, half = (m + n + 1) / 2;
        double maxLeft = 0, minRight = 0;
        while(imin <= imax){
             i = imin + (imax-imin) / 2;
            j = half - i;
            if(j > 0 && i < m && nums2[j - 1] > nums1[i]){
                imin = i + 1;
            }else if(i > 0 && j < n && nums1[i - 1] > nums2[j]){
                imax = i - 1;
            }else{
                if(i == 0){
                    maxLeft = (double)nums2[j - 1];
                }else if(j == 0){
                    maxLeft = (double)nums1[i - 1];
                }else{
                    maxLeft = (double)Math.max(nums1[i - 1], nums2[j - 1]);
                }
                break;
            }
        }
        if((m + n) % 2 == 1){
            return maxLeft;
        }
        if(i == m){
            minRight = (double)nums2[j];
        }else if(j == n){
            minRight = (double)nums1[i];
        }else{
            minRight = (double)Math.min(nums1[i], nums2[j]);
        }
        return (double)(maxLeft + minRight) / 2;
    }

Swap Adjacent in LR String

In a string composed of 'L', 'R', and 'X' characters, like "RXXLRXRXL", a move consists of either replacing one occurrence of "XL" with "LX", or replacing one occurrence of "RX" with "XR". Given the starting string start and the ending string end, return True if and only if there exists a sequence of moves to transform one string to the other.

Example:

1
2
3
4
5
6
7
8
9
Input: start = "RXXLRXRXL", end = "XRLXXRRLX"
Output: True
Explanation:
We can transform start to end following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public boolean canTransform(String start, String end) {
       char[] s=start.toCharArray();
       char[] e=end.toCharArray();
       int cnt = 0;
       if(s.length!=e.length) return false;
       for(int i=0;i<s.length;i++){
           if(s[i]=='X') cnt++;
           if(e[i]=='X') cnt--;
       }        
       if(cnt!=0) return false;
       int p1 = 0;
       int p2 = 0;
      while (p1 < start.length()) {           
       while (p1 < s.length && s[p1] == 'X') p1++;
       while (p2 < e.length && e[p2] == 'X') p2++;
       if (p1 == s.length && p2 == e.length) return true; 
       if (p1 == s.length || p2 == e.length) return false;  
       if(s[p1] != e[p2]) return false;
          
       if (s[p1] == 'R' && p1 > p2) return false;
       if (s[p1] == 'L' && p1 < p2) return false;
       p1++;
       p2++;
   }
       return true;
   }

链表

Merge k Sorted Lists -

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

1
2
3
4
5
6
7
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null||lists.length==0) return null;
        PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.length, (a,b)-> a.val-b.val);
        ListNode dummy = new ListNode(0);
        ListNode tail=dummy;
         for (ListNode node:lists)
            if (node!=null)
                q.add(node);
         while (!q.isEmpty()){
            tail.next=q.poll();
            tail=tail.next;            
            if (tail.next!=null)
                q.add(tail.next);
        }
        return dummy.next;
    }

LRU -

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class LRU{
    HashMap<Integer,Node> map = new HashMap();
    int cap=0,cnt=0;
    Node tail,head;
    class Node{
        Node pre,next;
        int key,val;
        public Node(int key,int val){
            this.key=key;
            this.val=val;
        }
        public Node(){
            this(0,0);
        }
    }
    public LRU(int cap){
        this.cap=cap;
        head=new Node();
        tail=new Node();
        head.next=tail;
        tail.pre=head;
    }
    public int get(int key){
        Node tmp = map.get(key);
        if(tmp==null) return -1;
        remove(tmp);
        add(tmp);
        return tmp.val;
    }
    public void put(int key,int val){
        Node tmp = map.get(key);
        if(tmp==null){
            Node n=new Node(key,val);
            add(n);
            map.put(key,n);
            cnt++;
        }else{
            tmp.val=val;
           remove(tmp);
            add(tmp);
        }if(cnt>cap){
            map.remove(tail.pre.key);
            remove(tail.pre);            
            cnt--;
        }
    }
    public void add(Node n){
        Node next=head.next;
        head.next=n;
        n.pre=head;
        next.pre=n;
        n.next=next;
    }
    public void remove(Node n){
        Node before=n.pre,after=n.next;
        before.next=after;
        after.pre=before;
    }
}

Reverse Nodes in K-group -

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public ListNode reverseKGroup(ListNode head, int k) {
       if(head==null) return head;
       int len = calLen(head,0);
       ListNode dummy=new ListNode(0);
       dummy.next=head;
       int cyc=len/k;
       ListNode pre=dummy,l1=head,l2=head;
       for(int i=0;i<cyc;i++){            
           for(int j=1;j<k;j++){
               l2=l2.next;
           }
           ListNode next=l2.next;
           l2.next=null;
           ListNode tmp=l1;
           reverse(l1);
           pre.next=l2;
           tmp.next=next;
           pre=tmp;
           l1=next;
           l2=next;
       }
       return dummy.next;
   }
   public int calLen(ListNode head,int res){
       if(head==null) return res;
       return calLen(head.next,res+1);
   }
   public void reverse(ListNode root){
       ListNode head=new ListNode(0);
       while(root!=null){
           ListNode tmp = root.next;
           root.next=head.next;
           head.next=root;
           root=tmp;
       }       
   }

Copy List with Random Pointer -

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public Node copyRandomList(Node head) {
        if(head==null) return head;
        Node phead=head;
        while(phead!=null){
            Node next=phead.next;
            Node tmp = new Node(phead.val);
            phead.next=tmp;
            tmp.next=next;
            phead=next;
        }
        phead=head;
        while(phead!=null){
            Node next=phead.next;
            Node r=phead.random;
            if(r!=null){
              next.random=r.next;
            }            
            phead=next.next;
        }
        phead=head;
        Node res=head.next;
        while(phead!=null&&phead.next!=null){
            Node next=phead.next;
            phead.next=next.next;
            phead=next;
        }
        return res;
    }

Merge Two Sorted Lists √

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        
        ListNode head=new ListNode(0);
        ListNode res = head;
        while(l1!=null&&l2!=null){
            if(l1.val<=l2.val){
                 head.next=l1;
                l1=l1.next;
            }
            else{
                head.next=l2;
                l2=l2.next;
            } 
            head=head.next;
        }
        head.next = l1==null?l2:l1;
        return res.next;
    }

Add Two Numbers √

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int sum=0,carry=0;
        ListNode dummy = new ListNode(0);
        ListNode now = dummy;
        while(l1!=null||l2!=null||carry!=0){
            int x = l1==null?0:l1.val;
            int y = l2==null?0:l2.val;
            sum = x+y+carry;
            now.next=new ListNode(sum%10);
            now=now.next;
            carry=sum/10;
            l1 = l1==null?null:l1.next;
            l2 = l2==null?null:l2.next;
        }
        return dummy.next;
    }

Add Two Numbers II √

1
2
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack();
        Stack<Integer> s2 = new Stack();
        while(l1!=null){
            s1.push(l1.val);
            l1=l1.next;
        }
        while(l2!=null){
            s2.push(l2.val);
            l2=l2.next;
        }
        int carry=0;
        ListNode ans = new ListNode(-1);
        while(!s1.isEmpty()||!s2.isEmpty()||carry!=0){
            int x = s1.isEmpty()?0:s1.pop();
            int y = s2.isEmpty()?0:s2.pop();
            int sum = x+y+carry;
            ListNode node = new ListNode(sum%10);
            carry=sum/10;
            node.next=ans.next;
            ans.next=node;
        }
        return ans.next;
    }

Reverse Words in a String -

Given an input string, reverse the string word by word.

Example 1:

1
2
Input: "the sky is blue"
Output: "blue is sky the"

Example 2:

1
2
3
Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class Solution {
  
  public String reverseWords(String s) {
    if (s == null) return null;
    
    char[] a = s.toCharArray();
    int n = a.length;
    
    // step 1. reverse the whole string
    reverse(a, 0, n - 1);
    // step 2. reverse each word
    reverseWords(a, n);
    // step 3. clean up spaces
    return cleanSpaces(a, n);
  }
  
  void reverseWords(char[] a, int n) {
    int i = 0, j = 0;
      
    while (i < n) {
      while (i < j || i < n && a[i] == ' ') i++; // skip spaces
      while (j < i || j < n && a[j] != ' ') j++; // skip non spaces
      reverse(a, i, j - 1);                      // reverse the word
    }
  }
  
  // trim leading, trailing and multiple spaces
  String cleanSpaces(char[] a, int n) {
    int i = 0, j = 0;
      
    while (j < n) {
      while (j < n && a[j] == ' ') j++;             // skip spaces
      while (j < n && a[j] != ' ') a[i++] = a[j++]; // keep non spaces
      while (j < n && a[j] == ' ') j++;             // skip spaces
      if (j < n) a[i++] = ' ';                      // keep only one space
    }
  
    return new String(a).substring(0, i);
  }
  
  // reverse a[] from a[i] to a[j]
  private void reverse(char[] a, int i, int j) {
    while (i < j) {
      char t = a[i];
      a[i++] = a[j];
      a[j--] = t;
    }
  }  
}

Merge k Sorted Lists -

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

1
2
3
4
5
6
7
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null||lists.length==0) return null;
        PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.length, (a,b)-> a.val-b.val);
        ListNode dummy = new ListNode(0);
        ListNode tail=dummy;
         for (ListNode node:lists)
            if (node!=null)
                q.add(node);
         while (!q.isEmpty()){
            tail.next=q.poll();
            tail=tail.next;            
            if (tail.next!=null)
                q.add(tail.next);
        }
        return dummy.next;
    }

动态规划

Climbing Stairs √

1
2
3
4
5
6
7
8
9
10
11
12
public int climbStairs(int n) {
       if (n == 1) {
           return 1;
       }
       int[] dp = new int[3];
       dp[1] = 1;
       dp[2] = 2;
       for (int i = 3; i <= n; i++) {
           dp[i%3] = dp[(i - 1)%3] + dp[(i - 2)%3];
       }
       return dp[n%3];
   }

栈

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

img
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

1
2
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Simplify Path

Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.

In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level.

Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.

Example 1:

1
2
3
Input: "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.

Example 2:

1
2
3
Input: "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.

Example 3:

1
2
3
Input: "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Example 4:

1
2
Input: "/a/./b/../../c/"
Output: "/c"

Example 5:

1
2
Input: "/a/../../b/../c//.//"
Output: "/c"

Example 6:

1
2
Input: "/a//b////c/d//././/.."
Output: "/a/b/c"

二分查找

Search in Rotated Sorted Array √

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int search(int[] nums, int target) {
       if(nums.length==0) return -1;
       int lo=0,hi=nums.length-1,index=0;
       if(nums[lo]<nums[hi]) ;
       else index=srch(nums);
       if(target<=nums[hi]&&target>=nums[index])return bs(nums,index,hi,target);
       else return bs(nums,lo,index-1,target);
   }
   public int bs(int[] a,int lo,int hi,int target){
       while(lo<hi){
           int mid=(lo+hi)/2;
           if(a[mid]<target)lo=mid+1;
           else hi=mid;
       }
       return a[lo]==target?lo:-1;
   }
   public int srch(int[] a){
       int lo=0,hi=a.length-1;
       while(lo<hi){
           int mid= lo +(hi-lo)/2;
           if(a[mid]>a[a.length-1]) lo=mid+1;
           else hi=mid;
       }
       return lo;
   }

双指针

Longest Substring Without Repeating Characters √

Given a string, find the length of the longest substring without repeating characters.

Example 1:

1
2
3
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
1
2
3
4
5
6
7
8
9
10
11
12
public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> map = new HashMap();
        int res=0;
        for(int i=0,j=0;i<s.length();i++){
            if(map.containsKey(s.charAt(i))){
                j=Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            res=Math.max(res,i-j+1);
        }
        return res;
    }

搜索

Longest Palindromic Substring ×

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2
Input: "cbbd"
Output: "bb"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private int lo, maxLen;

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2)
            return s;

        for (int i = 0; i < len-1; i++) {
            extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
            extendPalindrome(s, i, i+1); //assume even length.
        }
        return s.substring(lo, lo + maxLen);
    }

    private void extendPalindrome(String s, int j, int k) {
        while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
            j--;
            k++;
        }
        if (maxLen < k - j - 1) {
            lo = j + 1;
            maxLen = k - j - 1;
        }
    }

动态规划

Maximum Subarray √

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
1
2
3
4
5
6
7
8
public int maxSubArray(int[] nums) {
       int res=Integer.MIN_VALUE,cur=0;
       for(int i=0;i<nums.length;i++){
           cur=Math.max(cur+nums[i],nums[i]);
           res=Math.max(cur,res);
       }
       return res;
   }

Regular Expression Matching √

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

1
2
'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

1
2
3
4
5
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

1
2
3
4
5
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

1
2
3
4
5
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

1
2
3
4
5
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5:

1
2
3
4
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isMatch(String s, String p) {
        int m=s.length(),n=p.length();
        boolean[][] dp=new boolean[m+1][n+1];
        char cs[]=s.toCharArray(), cp[]=p.toCharArray();
        dp[0][0]=true;
        for(int i=2;i<=n;i++){
            if(cp[i-1]=='*')dp[0][i]=dp[0][i-2];
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(cs[i-1]==cp[j-1]||cp[j-1]=='.') dp[i][j]=dp[i-1][j-1];
                if(cp[j-1]=='*'){
                    if(cp[j-2]==cs[i-1]||cp[j-2]=='.') dp[i][j]|=dp[i-1][j]||dp[i][j-1]||dp[i][j-2];
                    else dp[i][j]=dp[i][j-2];
                }
            }
        }
        return dp[m][n];
    }

排序

Kth Largest Element in an Array √

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int findKthLargest(int[] nums, int k) {
        if(k<=0||k>nums.length) return -1;
        qs(nums,nums.length-k);
        return nums[nums.length-k];
    }
    public void qs(int[] a,int k){
        int lo=0,hi=a.length-1;
        while(lo<hi){
            int mid = select(a,lo,hi);
            if(k==mid) break;
            else if(k>mid) lo=mid+1;
            else hi=mid-1;
        }
    }
    public int select(int[] a,int lo,int hi){
        int i=lo,j=hi,x=a[lo];
        while(i<j){
            while(i<j&&a[j]>=x) j--;
            if(i<j) a[i]=a[j];
            while(i<j&&a[i]<x) i++;
            if(i<j) a[j]=a[i];
        }
        a[i]=x;
        return i;
    }

数字

Reverse Integer √

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

1
2
Input: 123
Output: 321

Example 2:

1
2
Input: -123
Output: -321

Example 3:

1
2
Input: 120
Output: 21
1
2
3
4
5
6
7
8
9
10
11
12
public int reverse(int x) {
        int prevRev = 0 , rev= 0;
        while(x != 0){
            rev= rev*10 + x % 10;
            if((rev - x % 10) / 10 != prevRev){
                return 0;
            }
            prevRev = rev;
            x= x/10;
        }
        return rev;
    }

Implement Rand10() Using Rand7()

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Do NOT use system’s Math.random().

Example 1:

1
2
Input: 1
Output: [7]

Example 2:

1
2
Input: 2
Output: [8,4]

Example 3:

1
2
Input: 3
Output: [8,1,10]

Idea: rand7() -> rand49() -> rand40() -> rand10()

1
2
3
4
5
public int rand10() {
    int result = 40;
    while (result >= 40) {result = 7 * (rand7() - 1) + (rand7() - 1);}
    return result % 10 + 1;
}

Summary:
I assume rand7() represents the number from 0 to 6 which is more general in Java, please refer Random class and nextInt(int bound): knock API door

  1. Key is uniform
  2. rand7() * rand7(), rand7() + rand7() are not uniform because some numbers can be generated by different combinations
  3. rand7() + rand7() != rand7() * 2 because rand7() + rand7() is not uniform, whereas rand7() * 2 is uniform
  4. rand7()*c is uniform where c stands for constant integers. (But note: uniform here is meant by discrete numbers, to make the range continuously, we need to fill the gap by adding randc() => which then leads to OP solution)

So pattern we can conclude: k * randk + randk is uniform.(Note for the 3rd rule, don’t mix it up with (k + 1)*randk)

其实就是k^n(randk-1)+k^n-1(randk-1)+…+randk-1大于randM就行了