SkySea-GaoMing HomeArchivesTagsCategories
刷题总结
|秋招|

刷题分类

String.split

二分查找

数组中找位置

有重复数字的升序数组的二分查找。思路很简单就是一直从中间位置开始查找即可

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
int index1=0;
      int index2=n-1;
      int mid=(index1+index2)/2;
      while(true)
      {
         if(a[mid]>v)
             index2=mid-1;
         else if(a[mid]<v)
             index1=mid+1;
         mid=(index1+index2)/2;
         if(index1>=index2)
             break;
         if(a[mid]==v)
             break;
      }
      if(a[mid]>=v)
      {
          while(a[mid]>=v)
              mid--;
          return mid+2;
      }
      else
      {
         while(a[mid]<v)
             mid++;
         return mid+1;
      }

平方根

思路依然是找中间位置，判断中间位置和数值的关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if(x==0)
          return 0;
      long left=1;
      long right=x/2;
      while(left<right)
      {
          //这里要取右中位数
          long mid=(left+right+1)/2;
          long value=mid*mid;
          if(value>x)
              right=mid-1;
          else 
              left=mid;
         
      }
      return (int)left;

滑动窗口

滑动窗口最大值

给定一个数组nums 和滑动窗口的大小k，请找出所有滑动窗口里的最大值。如
果使用暴力破解法，那么时间复杂度是 O(nk)。优化就是在滑动时能够保证在
O(1)的时间复杂度内获取最大值。单调队列是指队列中元素之间的关系具有单
调性，而且队首和队尾都可以进行出队操作，只有队尾可以进行入队操作。遍
历数组时每轮保证单调队列deque

  1. deque仅包含窗口内的元素，每轮窗口滑动移除了元素nums[i-1]，需将
    deque内的对应元素一起删除
  2. deque非严格递减，每轮窗口滑动添加了元素nums[j+1]，需将deque内
    所有小于nums[j+1]的元素删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
if(nums.length == 0 || k == 0) return new int[0];
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
//未形成窗口时
for(int i=0;i<k;i++){
	//删除 dequedeque 内所有 < nums[j]的元素，以保持deque递减
	while(!queue.isEmpty()&& deque.peekLast() < nums[i])
		deque.removeLast();
	deque.addLast(nums[i]);
}
res[0]=queue.peekFirst();
for(int i=k;i<nums.length;i++){
	//若i>0且队首元素deque[0]=被删除元素nums[i - 1] 则队首元素出队
	if(deque.peekFirst()==nums[i-k])
		deque.removeFirst();
	//删除 dequedeque 内所有 < nums[j]的元素，以保持deque递减
	while(!queue.isEmpty()&& deque.peekLast() < nums[i])
		deque.removeLast();
	deque.addLast(nums[i]);
	res[i - k + 1] = deque.peekFirst();
}
return res;

数组

一个元素在数组中的次数大于n/2

从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个
数开始计数，总能找到最多的那个。也就是摩尔投票法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int num=1;
      int n=nums[0];
      for(int i=1;i<nums.length;i++)
      {
          if(n!=nums[i])
          {
              num--;
              if(num<0){
                  num=0;
                  n=nums[i];
              }
          }
          else
              num++;
      }

最大子序和

至少要有一个元素。最简单的是动态规划的思想

1
2
3
4
5
6
7
8
9
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
	dp[i] = Math.max(dp[i- 1] + nums[i], nums[i]);	
	if (max < dp[i]) {
		max = dp[i];
	}
}

贪心的思路跟动态规划很像

1
2
3
4
5
6
7
8
9
10
int num=0;
      int max=nums[0];
      for(int i=0;i<nums.length;i++)
      {
          if(num>0)
              num=num+nums[i];
          else
              num=nums[i];
          max=max>num?max:num;
      }

删除排序数组中重复元素

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现
一次，返回移除后数组新长度。使用快慢指针，快慢指针的意思就是定义两个
索引指针，一个走的快一个走的慢，快的就是正常遍历数组，慢的是遍历不
重复的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int index=0;
int value=nums[0];
for(int i=0;i<nums.length;i++)
{
    if(nums[i]==value)
    {
        continue;
    }
    else
    {
    	//慢指针
        index++;
        nums[index]=nums[i];
        value=nums[i];
    }
}

返回一个数组的所有子集

主要体现在遍历的设计上，先是添加空数组，然后将每一个元素加入，十分巧妙
，遍历时每遇到一个数就把该数加到所有子集中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
List<List<Integer>> res = new ArrayList<>();
      res.add(new ArrayList<>());
      for (int i = 0; i < nums.length; i++) {
         int all = res.size();
         //一开始只有空集
         //1加到所有子集上 空集 [1]
         //2加到所有子集上 空集 [2] [1,2]
         //3加到所有子集上...
          for (int j = 0; j < all; j++) {
              List<Integer> tmp = new ArrayList<>(res.get(j));
              tmp.add(nums[i]);
              res.add(tmp);
          }
      }

除自身以外数组的乘积

返回输出数组，其中output[i]等于nums中除nums[i]之外其余各元素的乘积。对
与nums[i]来说，乘积 = 当前数左边的乘积 * 当前数右边的乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int[] array=new int[nums.length];
      int help=1;
      //从左边开始获取nums[i]左边的乘积
      for(int i=0;i<nums.length;i++)
      {
          array[i]=help;
          help*=nums[i];
      }
      help=1;
      //从右边开始获取获取nums[i]右边的乘积
      for(int i=nums.length-1;i>=0;i--)
      {
          array[i]*=help;
          help*=nums[i];
      }
      return array;

盛水容器

双指针，每次都移动较短的那个柱子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int left=0;
      int right=height.length-1;
      int min=height[right]<height[left]?height[right]:height[left];
      int max=(right-left)*min;
      while(left<right)
      {
          if(height[left]<height[right])
              left++;
          else
              right--;
          min=height[left]<height[right]?height[left]:height[right];
          if(max<min*(right-left))
              max=min*(right-left);
      }
      return max;

数组中第k个最大元素

在未排序的数组中找到第k个最大的元素。构建一个大顶堆

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 int findKthLargest(int[] nums, int k) {
	//构造一个大顶堆
    for(int i=nums.length/2-1;i>=0;i--)
	  {
		sink(nums,i,nums.length);
	  }
	//每次移除最大元素
	for(int i=nums.length-1;i>nums.length-1-k;i--)
	  {
		int temp=nums[i];
		nums[i]=nums[0];
		nums[0]=temp;
		sink(nums,0,i);
	  }
        return nums[nums.length-k];
        
    }
    public void sink(int[] array,int k,int length)
  {
	for(int j=2*k+1;j<length;j=2*j+1)
	{
		if(j+1<length&&array[j]<array[j+1])
			j++;
		if(array[j]>array[k])
		{
		int temp=array[k];
		array[k]=array[j];
		array[j]=temp;
		k=j;
		}
		else
		{
			break;
		}
	}
}

两个正序数组的中位数

这个题如果要求时间复杂度为O(m+n)其实很简单，就是直接通过遍历比
较找到中间位置，但是时间复杂度要求为O(log(m+n))，应该联想到用
二分思想，首先要分奇偶来求出中位数，参考力扣一个大牛的话(m+n+1)
和(m+n+2)取平均值可以消除奇偶的影响，首先考虑如何找到数组中第k
个元素，一种思路是双指针进行比较求得第k个元素，但是时间复杂度为
O(m+n)，如果利用二分查找，先分别在两个数组中找到第k/2个元素，
比较这两个元素比如nums1[k/2] < nums2[k/2]，那么nums1数组前k/2个
一定不存在第k个元素，此时删除nums1前k/2个元素，然后继续找，这个时
候实际找的是第k-k/2个元素，因为k/2个元素已经被除去了嘛，所以接下
来查找的范围就会越来越小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      int m=nums1.length;
      int n=nums2.length;
      int left=(m+n+1)/2;
      int right=(m+n+2)/2;
      return (findk(nums1,0,nums2,0,left)+findk(nums1,0,nums2,0,right))/2.0;
  }
  public int findk(int[] nums1,int i,int[] nums2,int j,int k)
  {
      if(i>=nums1.length)
        return nums2[j+k-1];
      if(j>=nums2.length)
        return nums1[i+k-1];
      if(k==1)
        return Math.min(nums1[i],nums2[j]);
      int midindex1=(i+k/2-1<nums1.length)?nums1[i+k/2-1]:Integer.MAX_VALUE;
      int midindex2=(j+k/2-1<nums2.length)?nums2[j+k/2-1]:Integer.MAX_VALUE;
      if(midindex1<midindex2)
        return findk(nums1,i+k/2,nums2,j,k-k/2);
      else
        return findk(nums1,i,nums2,j+k/2,k-k/2);
  }

乘积最大子数组

核心思路就是以0为分界遍历数组更新最大值，对于负数的数量影响可以
想到从开头和结尾两个方向遍历解决奇数情况

  1. 负数为偶数个，则整个数组的各个值相乘为最大值
  2. 负数为奇数个，则从左边开始，乘到最后一个负数停止有一个“最大值”，
    从右边也有一个“最大值”，比较，得出最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int max=nums[0];
      int num=1;
      for(int i=0;i<nums.length;i++)
      {
          num*=nums[i];
          max=Math.max(num,max);
          if(nums[i]==0)
              num=1;
      }
      num=1;
      for(int i=nums.length-1;i>=0;i--)
      {
          num*=nums[i];
          max=Math.max(num,max);
          if(nums[i]==0)
              num=1;
      }

最大子序和

1
2
3
4
5
6
7
8
9
10
int max=nums[0];
      int num=0;
      for(int i=0;i<nums.length;i++)
      {
          if(num>=0)
              num+=nums[i];
          else
              num=nums[i];
          max=Math.max(max,num);
      }

岛屿最大面积

找到给定的二维数组中最大的岛屿面积。这道题需要利用深度优先搜索

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
public int maxAreaOfIsland(int[][] grid) {
        if(grid.length==0)
            return 0;
        int max=0;
        for(int i=0;i<grid.length;i++)
        {
            for(int j=0;j<grid[0].length;j++)
            {
                if(grid[i][j]==1)
                {
                    int num=dfs(i,j,grid);
                    max=max>num?max:num;
                }
            }
        }
        return max;
    }
    public int dfs(int i,int j,int[][] grid)
    {
        if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]==0)
            return 0;
        int num=1;
        grid[i][j]=0;
        num+=dfs(i-1,j,grid);
        num+=dfs(i+1,j,grid);
        num+=dfs(i,j+1,grid);
        num+=dfs(i,j-1,grid);
        return num;
    }

接雨水问题

给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，
下雨之后能接多少雨水。使用单调栈，单调栈分为单调递增栈和单调递减栈。
这里，当后面的柱子高度比前面的低时，是无法接雨水的，当找到一根比前
面高的柱子，就可以计算接到的雨水，所以使用单调递减栈。

  1. 对更低的柱子入栈，更低的柱子以为这后面如果能找到高柱子，这里就
    能接到雨水，所以入栈把它保存起来
  2. 当出现高于栈顶的柱子时，说明可以对前面的柱子结算了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Stack<Integer> stack = new Stack<Integer>();
int water = 0;
//特殊情况       
   if(height.length <3){
       return 0;
   }
   for(int i=0;i<height.length;i++){
   	while(!stack.isEmpty() && height[i] > height[stack.peek()]){          
           //栈顶元素
           int popnum = stack.pop(); 
           if(stack.isEmpty())
           	break;
           int l=stack.peek();
           int r=i;
           int h=Math.min(height[r],height[l])-height[popnum];
           water+=(r-l-1)*h;
       }
       stack.push(i);
   }
   return water;

字符串

反转一个字符串中的单词

你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。获取
字符串的字符数组，设置start和end两个位置，开始遍历，每次取得一个单词然后
反转字符

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
char[] array=s.toCharArray();
        int start=0;
        int end=0;
        while(end<array.length)
        {
            if((array[end]==' ')||(end==array.length-1))
            {
                int cut=end;
                if(array[end]==' ')
                end--;
            	//这个操作就是反转一个字符串的核心
                while(start<end)
                {
                    char tempt=array[end];
                    array[end]=array[start];
                    array[start]=tempt;
                    start++;
                    end--;
                }
                start=cut+1;
                end=cut+1;
            }
            else
                end++;
        }
        s=new String(array);

最长回文子串

易想到的是中心扩散法，从某个位置向两边进行扩散，但是要分两种情况
，例如aba abba

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
class Solution {
    public String longestPalindrome(String s) {
      if(s.length()<2)
      return s;
    int maxlength=1;
    int left=0;
    int right=0;
    String ss=s.substring(0,1);
    for(int i=0;i<s.length()-1;i++)
    {
        String s1=Stringcut(s,i,i+1);
        String s2=Stringcut(s,i,i);
        String max=s1.length()>s2.length()?s1:s2;
        if(max.length()>maxlength)
          {
              ss=max;
              maxlength=max.length();
          }
    }
      return ss;
    }
    public String Stringcut(String s,int left,int right)
    {
        int length=s.length();
        int i=left;
        int j=right;
        while(i>=0&&j<length)
        {
            if(s.charAt(i)==s.charAt(j))
            {
                i--;
                j++;
            }
            else
            break;
        }
        return s.substring(i+1,j);
    }
}

链表

不给前置节点条件下删除链表中的节点

这里只给了要删除的节点，没有给其前置节点，只需要把要删除节点的值设置
为下一个节点的值，然后next设置为下一个节点的next

1
2
node.val=node.next.val;
   node.next=node.next.next;

反转一个单链表

  1. 迭代方式 这个反转过程需要三个指针 pre cur next。每遍历到一个节点都要
    改变节点的pre和next，比如遍历到第一个节点，此时获取next，然后把第一个节
    点的next指向pre，然后pre更新为第一个节点，接下来遍历到下一个
    1
    2
    3
    4
    5
    6
    7
    8
    9
    while(cur!=null)
            {
                next=cur.next;
                cur.next=pre;
                pre=cur;
                cur=next;
            }
            head=pre;
            return head;
  2. 递归方式 既然使用递归首先要考虑递归的终止方式，有两个终止条件
  • 终止条件是当前节点或者下一个节点==null
  • 在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函
    数那句 head.next.next = head
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    //比如1 2 3 4 5
    public ListNode reverseList(ListNode head){
        	if(head==null||head.next==null)
        		return head;
        	//cur得到的值始终都是5
        	ListNode cur=reverseList(head.next);
        	//得到head的顺序是4 3 2 1
        	//反转相邻节点4-5 3-4 2-3 1-2
        	head.next.next=head;
        	//防止链表循环，需要将head.next设置为空，实际上就是1到2的引用必须除去
        	head.next=null;
        	return cur;
        }

k个一组反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ListNode dummy = new ListNode(0);
ListNode prev = dummy;
ListNode curr = head,;
ListNode next;
      dummy.next = head;
      int length = 0;
      while(head != null) {
          length++;
          head = head.next;
      }
      head = dummy.next;
      for(int i = 0; i < length / k; i++) {
          for(int j = 0; j < k - 1; j++) {
              next = curr.next;
              curr.next = next.next;
              next.next = prev.next;
              prev.next = next;
          }
          prev = curr;
          curr = prev.next;
      }
      return dummy.next;

合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的
两个链表的所有节点组成的。注意不能创建新节点。可以使用dummyHead，也
就是临时创建一个头节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ListNode pre=new ListNode(0);
  	ListNode prehead=pre;
  	if(l1==null)
          return l2;
      else if(l2==null)
          return l1;
      else{
      	while(l1!=null&&l2!=null){
      	if(l1.val<=l2.val){
      		pre.next=l1;
      		l1=l1.next;
      	}
      	else{
      		pre.next=l2;
      		l2=l2.next;
      	}
      	pre=pre.next;
      }
      if(l1==null)
      	pre.next=l2;
      else
      	pre.next=l1;
     }
     return prehead.next;

也可以使用递归解决，终止条件就是l1或l2为null，返回的是排序好的
链表头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }
        if(l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

找到相交链表的起始节点

如果两个链表存在相交部分，那么从相交位置开始到末尾的长度都是相同的。
我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这
个位置只能是较短链表的头结点位置。为此我们必须消除两个链表的长度差，
两个指针从相同位置开始遍历过程如果能相遇那么就有相交

1
2
3
4
5
6
7
8
9
ListNode node1=headA;
      ListNode node2=headB;
      while(node1!=node2)
      {
      	//消除长度差的本质就是各自从另一条路走
          node1=node1==null?headB:node1.next;
          node2=node2==null?headA:node2.next;
      }
      return node1;

判断一个链表是否有环

依然是使用快慢指针的思想，一个每次跳转到下一个节点，慢指针每次跳转两个
节点，最终如果有环一定可以相遇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode node=head;
      ListNode first=head;
      ListNode second=head;
      while(true)
      {
          if(first.next!=null)
              first=first.next;
          else
              return false;
          if(second.next!=null)
          {
              if(second.next.next!=null)
                  second=second.next.next;
              else
                  return false;
          }
          else
              return false;
          if(first==second)
              return true;
      }

接下来不仅判断有环，还要判断环的起始位置。

  1. fast 走的步数是slow步数的2倍，即 f= 2s
  2. fast 比 slow多走了 n个环的长度，即 f = s + nb

如果让指针从链表头部一直向前走并统计步数k，那么所有 走到链表入口节点时
的步数是：k=a+nb（先走a步到入口节点，之后每绕1圈环都会再次到入口节点）
所以第一次重合之后让快指针从head开始走a步那么就与慢指针重合，这时就是
在环的入口

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode fast = head, slow = head;
      while (true) {
          if (fast == null || fast.next == null) return null;
          fast = fast.next.next;
          slow = slow.next;
          if (fast == slow) break;
      }
      fast = head;
      while (slow != fast) {
          slow = slow.next;
          fast = fast.next;
      }
      return fast;

删除排序链表中的重复元素

注意链表是已经排序的。可以采用递归

  1. 找终止条件：当head指向链表只剩一个元素的时候，自然是不可能重复
    的，因此return
  2. 想想应该返回什么值：应该返回的自然是已经去重的链表的头节点
  3. 每一步要做什么：宏观上考虑，此时head.next已经指向一个去重的链表
    了，而根据第二步，我应该返回一个去重的链表的头节点。因此这一步应该做
    的是判断当前的head和head.next是否相等，如果相等则说明重了，返回
    head.next，否则返回head
    1
    2
    3
    4
    5
    6
    7
    8
    public ListNode deleteDuplicates(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }
            head.next = deleteDuplicates(head.next);
            if(head.val == head.next.val) head = head.next;
            return head;
        }

回文链表

请判断一个链表是否为回文链表。可以使用快慢指针，流程分为5步

  1. 找到前半部分链表的尾节点 有两种办法，第一种直接遍历整个链表得
    到链表长度，然后再遍历找到中间位置。第二种方式是通过快慢指针获取
    链表的中间位置，慢指针每次走一步快指针一次走两步，当快指针到达
    末尾时慢指针刚好到终点
  2. 反转后半部分链表 之前有一个反转链表的题
  3. 判断是否回文
  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
37
38
39
40
41
42
43
44
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);
        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }        
        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

复制带随机指针的链表

浅拷贝：返回地址一样的链表。 深拷贝：返回地址不一样，但关系一致的链
表。 所以不能直接简单粗暴的遍历复制，这样出来的复制是一样的地址。

  1. 根据遍历到的原节点创建对应的新节点，每个新创建的节点是在原节点后面
  2. 第二步是最关键的一步，用来设置新链表的随机指针，原节点i的随机指针
    (如果有的话)，指向的是原节点j，那么新节点i的随机指针，指向的是原节点
    j的next
  3. 第三步就简单了，只要将两个链表分离开，再返回新链表就可以了
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
public Node copyRandomList(Node head) {
        if(head==null) {
            return null;
        }
        Node p = head;
        //第一步，在每个原节点后面创建一个新节点
        //1->1'->2->2'->3->3'
        while(p!=null) {
            Node newNode = new Node(p.val);
            newNode.next = p.next;
            p.next = newNode;
            p = newNode.next;
        }
        p = head;
        //第二步，设置新节点的随机节点
        while(p!=null) {
            if(p.random!=null) {
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }
        Node dummy = new Node(-1);
        p = head;
        Node cur = dummy;
        //第三步，将两个链表分离
        while(p!=null) {
            cur.next = p.next;
            cur = cur.next;
            p.next = cur.next;
            p = p.next;
        }
        return dummy.next;
    }

更简单的是通过哈希表

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
class Solution {
    public Node copyRandomList(Node head) {
        if(head==null) {
            return null;
        }
        //创建一个哈希表，key是原节点，value是新节点
        Map<Node,Node> map = new HashMap<Node,Node>();
        Node p = head;
        //将原节点和新节点放入哈希表中
        while(p!=null) {
            Node newNode = new Node(p.val);
            map.put(p,newNode);
            p = p.next;
        }
        p = head;
        //遍历原链表，设置新节点的next和random
        while(p!=null) {
            Node newNode = map.get(p);
            //p是原节点，map.get(p)是对应的新节点，p.next是原节点的下一个
            //map.get(p.next)是原节点下一个对应的新节点
            if(p.next!=null) {
                newNode.next = map.get(p.next);
            }
            //p.random是原节点随机指向
            //map.get(p.random)是原节点随机指向  对应的新节点 
            if(p.random!=null) {
                newNode.random = map.get(p.random);
            }
            p = p.next;
        }
        //返回头结点，即原节点对应的value(新节点)
        return map.get(head);
    }
}

重排链表

  1. 快慢指针找到中间节点
  2. 反转后半段链表
  3. 合并前半段链表和后半段链表
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
60
61
62
63
64
class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;

        // 找到链表的中间节点
        ListNode mid = findMidNode(head);
        
        // 将整个链表分成两个链表
        ListNode head1 = head;
        ListNode head2 = mid.next;
        mid.next = null;

        // 将第二个链表进行反转
        head2 = revereList(head2);

        // 合并两个链表
        mergeList(head1, head2);
    }

    // 返回链表的中间节点
    private ListNode findMidNode(ListNode head) {
        if (head == null) return null;

        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == null) return slow;
        }
        return slow;
    }

    // 反转链表，并返回新的头节点
    private ListNode revereList(ListNode head) {
        if (head == null) return null;

        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }

    // 合并两个链表
    private void mergeList(ListNode head1, ListNode head2) {
        ListNode t1 = null, t2 = null;
        
        while (head1 != null && head2 != null) {
            // 防止链表断开
            t1 = head1.next;
            t2 = head2.next;

            head1.next = head2;
            head2.next = t1;

            head1 = t1;
            head2 = t2;
        }
    }
}

二叉树

求二叉树中最大路径和问题，LeetCode 99 恢复一棵 BST

求二叉树的最大深度

使用递归的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int maxDepth(TreeNode root) {
        if(root==null)
            return 0;
        int left=deep(root.left);
        int right=deep(root.right);
        return left>right?left+1:right+1;
    }
    public int deep(TreeNode node)
    {
        if(node==null)
            return 0;
        else
        {
            int left=deep(node.left);
            int right=deep(node.right);
            return left>right?left+1:right+1; 
        }
    }

找二叉树的最近公共祖先

这里是二叉树而不是二叉搜索树，不能直接根据节点的值判断。但是依然根据
节点的位置来判断公共祖先，遍历到某个节点时，判断左右子树中p和q的情
况，如果左右都有那么就是root，如果只有左或右那么p和q中一定有一个
是公共祖先

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 TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		//当遍历到叶结点后就会返回null
        if (root == null) {
            return root;
        }
        //当找到p或者q的是时候就会返回pq
        /*当然，值得一提的是，如果公共祖先是自己（pq），并不需要寻找另外
       一个，我们在执行前序遍历会先找上面的，后找下面的，我们会直接返回公共祖先。*/
        if (root == p || root == q) {
            return root;
        }
        //返回的结点进行保存，可能是null
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        //也可能是pq，还可能是公共祖先
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //如果左右都存在，就说明pq都出现了，这就是公共祖先
        if (left != null && right != null) {
            return root;
        //否则我们返回已经找到的那个值（存储在left，与right中），p或者q
        } else if (left != null) {
        //还有一种可能就是，由下面返回的公共祖先，并将这个值一路返回到最表层
            return left;
        } else if (right != null) {
            return right;
        }
        return null;
        
    }

第k小的元素

中序遍历得到的就是一个有序序列，最简单的思路是得到树中元素个数，
然后中序遍历存放到数组中，当遍历到第k个就停止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int index=0;
   int count=0;
   int val;
   public int kthSmallest(TreeNode root, int k) {
       count=k;
       search(root);
       return val;
   }
   public void search(TreeNode node)
   {
       if(node==null)
           return ;
       
       search(node.left);
       index++;
       if(index==count)
           {
               val=node.val;
               return ;
           }
       search(node.right);
   }

从前序与中序遍历序列构造二叉树

要利用好中序和前序的性质，注意边界关系

  1. 从左到右遍历preorder、inorder
  2. preorder的第一个元素一定是根元素
  • 2.1. 找到根元素后，可以在inorder中区分左、右子树
  • 2.2. 当前根的左子树范围：inorder[inorder未查找的最左边（从0开始），
    和根元素相等的索引位置
  • 2.3. 当前根的左子树范围：preorder(当前根索引位置（从0开始）, 当前
    根的索引位置 + inorder已知左子树长度，原因：因为preorder、inorder中
    左、右子树的长度相等（只是观察得出，为什么这么巧，还没想透彻）
  1. 当preorder的指针向右移动到”左子树长度”，说明当前根节点的左子树已经处理完毕
  2. 递归开始查找，如果没有超出左子树范围，preorder指针向右移动一位继续搜索
  • 4.1. 此时的节点最多只可能有2种身份：A + B
    A. 根节点
    B. 左节点或右节点
  • 4.2. inorder的起始节点是”最左的节点”，当preorder中的值与他相等时，可
    以判断无后续数据，结束搜索
  • 4.3 inorder指针向右移动一位（排除已使用节点），缩小搜索范围
  1. 右节点确定规则：因为上一步确定的是一个左节点，preorder顺序为根左右，
    所以preorder的下一个节点就是右节点
    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
    public TreeNode buildTree(int[] preorder, int[] inorder) {
            if(preorder.length<=0)
                return null;
            TreeNode root=new TreeNode(preorder[0]);
            int index=-1;
            for(int i=0;i<inorder.length;i++)
               { if(preorder[0]==inorder[i])
                {
                    index=i;
                    break;
                }
               }
            root.left=sear(1,index,0,index-1,preorder,inorder);
            root.right=sear(index+1,preorder.length-1,index+1,
            	inorder.length-1,preorder,inorder);
            return root;
        }
        public TreeNode sear(int left1,int right1,int left2,int right2,
        int[] preorder,int[] inorder)
        {
            if(left1>right1||left2>right2)
                return null;
            TreeNode node=new TreeNode(preorder[left1]);
            int index=left1;
            for(int i=left2;i<=right2;i++)
                {if(preorder[left1]==inorder[i])
                {
                    index=i;
                    break;
                }
                }
            node.left=sear(left1+1,left1+index-left2,left2,index-1,preorder
            ,inorder);
            node.right=sear(left1+1+index-left2,right1,index+1,right2
            ,preorder,inorder);
            return node;
        }

从中序与后序遍历序列构造二叉树

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 TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length<=0)
            return null;
        TreeNode root=new TreeNode(postorder[postorder.length-1]);
        int index=-1;
        for(int i=0;i<inorder.length;i++)
        {
            if(postorder[postorder.length-1]==inorder[i])
            {
                index=i;
                break;
            }
        }
        root.left=sear(0,index-1,0,index-1,inorder,postorder);
        root.right=sear(index+1,inorder.length-1,index,inorder.length-2,
        inorder,postorder);
        return root;
    }
    public TreeNode sear(int left1,int right1,int left2,int right2,
    int[] inorder,int[] postorder)
    {
        if(left1>right1||left2>right2)
            return null;
        TreeNode node=new TreeNode(postorder[right2]);
        int index=left1;
        for(int i=left1;i<=right1;i++)
        {
            if(inorder[i]==postorder[right2])
            {
                index=i;
                break;
            }
        }
        node.left=sear(left1,index-1,left2,left2+index-1-left1,inorder,
        postorder);
        node.right=sear(index+1,right1,left2+index-left1,right2-1,
        inorder,postorder);
        return node;
    }

重上到下打印二叉树

可以用一个flag判断当前行是从左到右还是从右到左

二叉树的右视图

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从
右侧所能看到的节点值。容易想到层次遍历，但注意只保留每层最后一个节点

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 List<Integer> rightSideView(TreeNode root) {
        List<TreeNode> list=new LinkedList<TreeNode>();
        List<Integer> list2=new LinkedList<>();
        TreeNode node=root;
        if(node==null)
            return list2;
        list.add(root);
        int temp=0;
        while(!list.isEmpty())
        {
            int num=list.size();
            while(num>0){
                node=list.remove(0);
                if(node.left!=null)
			        list.add(node.left);
		        if(node.right!=null)
			        list.add(node.right);
                num--;
                temp=node.val;
            }
            list2.add(temp);
        }
        return list2;
    }

TopK

设计题

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
前三种操作都可以完成，如何获取最小元素，每次入栈的时候都要判断这个元素是
不是最小的，如果不是最小的那么直接入栈，如果是最小的，那么首先把之前最小
的入栈，然后该元素入栈。这样做的目的是如果该元素要出栈，那么出栈时判断这
个元素是最小的，那么继续出栈就获取之前最小的元素

1
2
3
4
5
6
7
8
9
10
11
12
public void push(int x) {
      if(min>=x)
      {
          stack.push(min);
          min=x;
      }
       stack.push(x);
   }
   public void pop() {
       if(stack.pop()==min)
           min=stack.pop();
   }

两个栈实现队列

直接使用两个Stack，但是栈底的元素无法删除，所以一个添加栈用来添加
元素，当需要删除元素的时候，就把添加栈的元素转移到删除栈中，此时
元素就已经反转顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class CQueue {
    Stack<Integer> stack1,stack2;
    public CQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    public void appendTail(int value) {
        stack1.push(value);
    }
    public int deleteHead() {
        if(stack1.empty() && stack2.empty()){
            return -1;
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

LRU缓存机制

LinkedHashMap可以实现LRU，在构造参数中设置accessOrder为true，
重写removeEldestEntry表示达到限定容量时进行删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class LRUCache {
    int capacity;
    LinkedHashMap<Integer, Integer> cache;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return cache.size() > capacity;
            }
        };
    }
    public int get(int key) {
        Integer a=cache.get(key);
        if(a!=null)
            return a;
        return -1;
    }
    public void put(int key, int value) {
        cache.put(key, value);
    }
}

验证栈序列

给定 pushed 和 popped 两个序列，每个序列中的值都不重复，只有当
它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结
果时，返回 true，否则返回false

1
2
3
4
5
6
7
8
9
10
Deque<Integer> stack = new ArrayDeque<>();
      int j = 0; //索引popped
      for (int i = 0; i < pushed.length; i++) {
          stack.push(pushed[i]);
          while (!stack.isEmpty() && stack.peek() == popped[j]) {
              j++;
              stack.pop();
          }
      }
      return stack.isEmpty();

动态规划

  1. 斐波那契数列 dp[n]=dp[n−1]+dp[n−2]

二维网格找路径

1
2
3
4
5
6
7
8
int[][] array=new int[m][n];
        for(int i=0;i<m;i++)
        array[i][0]=1;
        for(int j=0;j<n;j++)
        array[0][j]=1;
        for(int i=1;i<m;i++)
            for(int j=1;j<n;j++)
             array[i][j]=array[i-1][j]+array[i][j-1];

二维网格找路径II

网格中有障碍物

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
int[][] dp=new int[obstacleGrid.length][obstacleGrid[0].length];
      int num=1;
      if(obstacleGrid[0][0]==0)
          dp[0][0]=1;
      else
          return 0;
      for(int i=1;i<obstacleGrid.length;i++)
      {
          if(obstacleGrid[i][0]==1)
              num=0;
          dp[i][0]=num;
      }
      num=1;
      for(int i=1;i<obstacleGrid[0].length;i++)
      {
          if(obstacleGrid[0][i]==1)
              num=0;
          dp[0][i]=num;
      }
      for(int i=1;i<obstacleGrid.length;i++)
      {
          for(int j=1;j<obstacleGrid[0].length;j++)
          {
              if(obstacleGrid[i][j]==1)
                  dp[i][j]=0;
              else
                  dp[i][j]=dp[i-1][j]+dp[i][j-1];
          }
      }
      return dp[dp.length-1][dp[0].length-1];

比特位计数

计算其二进制数中的1的数目并将它们作为数组返回。
这是一道典型的动态规划题，我一开始想找相邻两个数之间的关系结果不行，一个
大牛的解法就是对于一个二进制数来说，如果它的最低位为1（%2为1）,则它与
n/2的1个数相差1。如果它的最低位为0，则它与n/2的1个数相同。有些动态规划题
并不一定是相邻的数之间有关系也有可能有间隔

1
2
3
4
5
6
7
int[] array=new int[num+1];
      for(int i=0;i<=num/2;i++)
          {
              array[i*2]=array[i];
              if(i*2+1<=num)
                  array[i*2+1]=array[i]+1;
          }

做菜顺序

首先应该想到倒序排序，从最大值开始累加，如果出现负数就说明已经结束了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Arrays.sort(satisfaction);
      int num=0;
      int max=0;
      int sum=0;
      for(int i=satisfaction.length-1;i>=0;i--)
      {
          if(num>=0)
          {       
              num=num+satisfaction[i]+sum;
              sum+=satisfaction[i];
              max=Math.max(num,max);
          }
          else
              break;
      }

最长湍流子数组

核心就是找当前状态与前一个状态和前一个状态与前前一个状态的关系

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
int[] dp=new int[A.length];
      dp[0]=1;
      int max=1;
      if(A.length>1)
      {
          if(A[1]==A[0])
              dp[1]=1;
          else
              {
                  dp[1]=2;
                  max=2;
              }
      }
      for(int i=2;i<A.length;i++)
      {
          int num1=A[i]-A[i-1];
          int num2=A[i-2]-A[i-1];
          if((num1>0&&num2>0)||(num1<0&&num2<0))
              dp[i]=dp[i-1]+1;
          else if((num1>0&&num2<0)||(num1<0&&num2>0))
              dp[i]=2;
          else
          {
              if(num1==0)
                  dp[i]=1;
              else
                  dp[i]=2;
          }
          max=Math.max(max,dp[i]);
      }

最小路径和

当前位置与上一个和左一个位置的关系，但是注意选最小的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int num=0;
      int[][] dp=new int[grid.length][grid[0].length];
      dp[0][0]=grid[0][0];
      for(int i=1;i<grid.length;i++)
      {
          dp[i][0]=grid[i][0]+dp[i-1][0];
      }
      for(int i=1;i<grid[0].length;i++)
      {
          dp[0][i]=grid[0][i]+dp[0][i-1];
      }
      for(int i=1;i<grid.length;i++)
      {
          for(int j=1;j<grid[0].length;j++)
          {
              dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
          }
      }

使用最小花费爬阶梯

数组的每个下标作为一个阶梯，第i个阶梯对应着一个非负数的体力花费
值cost[i]。核心就是找到当前状态与前一个和前两个之间的关系，先得
到小问题的解，小问题是最优解最后累积为大问题的解

1
2
3
4
5
6
int[] dp=new int[cost.length+1];
      if(cost.length>2)
          dp[2]=cost[0]>cost[1]?cost[1]:cost[0];
      for(int i=3;i<=cost.length;i++)
          dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
      return dp[cost.length];

最长递增子序列

可以定义一个数组保存当前位置为止的最长上升子序列

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 lengthOfLIS(int[] nums) {
        if(nums.length==0)
            return 0;
        int[] array=new int[nums.length];
        array[0]=1;
        for(int i=1;i<nums.length;i++)
        {
            int max=1;
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {
                    max=Math.max(max,array[j]+1);
                }
            }
            array[i]=max;
        }
        int max=0;
        for(int i=0;i<array.length;i++)
        {
            if(max<array[i])
                max=array[i];
        }
        return max;
    }

最长公共子序列

给定两个字符串text1 和text2，返回这两个字符串的最长公共子序列的长度。
这是典型的动态规划问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int longestCommonSubsequence(String text1, String text2) {
        int length1=text1.length();
        int length2=text2.length();
        int[][] array=new int[length1+1][length2+1];
        for(int i=0;i<length1;i++)
        {
            for(int j=0;j<length2;j++)
            {
                if(text1.charAt(i)==text2.charAt(j))
                {
                    array[i+1][j+1]=array[i][j]+1;
                }
                else if(array[i+1][j]>array[i][j+1])
                    array[i+1][j+1]=array[i+1][j];
                else
                    array[i+1][j+1]=array[i][j+1];
            }
        }
        return array[length1][length2];

编辑距离

给你两个单词word1 和word2，请你计算出将word1 转换成word2 所使用
的最少操作数。其实跟平常的动态规划题差别不大，核心就是分析最优情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minDistance(String word1, String word2) {
        int m=word1.length();
        int n=word2.length();
        int[][] cost=new int[m+1][n+1];
        for (int i = 0; i <= m; ++i) {
            cost[i][0] = i;
        }
        for (int j = 0; j <= n; ++j) {
            cost[0][j] = j;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    cost[i][j] = cost[i-1][j-1];
                } else {
                    cost[i][j] = 1 + 
                    Math.min(cost[i-1][j-1], Math.min(cost[i][j-1], 
                    cost[i-1][j]));
                }             
            }
        }
        return cost[m][n];
    }

零钱兑换

1
2
3
4
5
6
7
8
9
10
11
public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;

    for (int coin : coins) {
      for (int x = coin; x < amount + 1; ++x) {
        dp[x] += dp[x - coin];
      }
    }
    return dp[amount];
  }

股票系列

买股票最佳时机I

区间和可以转换成求差的问题，求差问题，也可以转换成区间和的问题

1
2
3
4
5
6
7
int num=0;
   int profit=0;
   for(int i=0;i<prices.length-1;i++)
   {
       num=Math.max(0,num+prices[i+1]-prices[i]);
       profit=Math.max(num,profit);
   }

也可以用动态规划的思想，前i天的最大收益 = max{前i-1天的最大收益，第i天
的价格-前i-1天中的最小价格}

1
2
3
4
5
6
7
8
int []dp = new int[len];
      dp[0] = 0;
      int min = prices[0];
      // 前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}
      for(int i = 1; i < len; i++) {
          dp[i] = Math.max(dp[i - 1], prices[i] - min);
          min = Math.min(min, prices[i]);
      }

买股票的最佳时机II

你可以尽可能地完成更多的交易（多次买卖一支股票）。这道题的条件其实很
宽松，可以进行多次买卖，所以只关注眼前每次遇到更大的就买卖，贪心算法

1
2
3
4
5
6
7
8
9
10
11
public int maxProfit(int[] prices) {
        int sum=0;
        for(int i=0;i<prices.length-1;i++)
        {
            if(prices[i]<prices[i+1])
            {
                sum=sum+prices[i+1]-prices[i];
            }
        }
        return sum;
    }

括号系列

字节

剑指Offer

数学

只出现一次的数字，使用异或

考察异或的用法
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。
找出那个只出现了一次的元素，使用异或求解，异或的用法就是对于两个相同的数
异或结果是0，一个数跟0异或结果还是这个数

1
2
3
4
5
6
int ans=nums[0];
        for(int i=1;i<nums.length;i++)
        {
            ans=ans^nums[i];
        }
        return ans;

判断一个数是回文数

  1. 第一种方式就是将这个数变为字符串然后反转
    1
    String reversedStr = (new StringBuilder(x + "")).reverse().toString();
  2. 通过左右两边的位进行比较
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    //边界判断
          if (x < 0) return false;
          int div = 1;
          
          while (x / div >= 10) div *= 10;
          while (x > 0) {
              int left = x / div;
              int right = x % 10;
              if (left != right) return false;
              //左右各减去1位，先取余减去高位，再取整减去低位
              x = (x % div) / 10;
              div /= 100;
          }
          return true;
  3. 取出后半段数字进行反转
    1
    2
    3
    4
    5
    6
    7
    8
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;
           int revertedNumber = 0;
           while (x > revertedNumber) {
               revertedNumber = revertedNumber * 10 + x % 10;
               x /= 10;
           }
           //位数分为奇偶情况
           return x == revertedNumber || x == revertedNumber / 10;

反转一个数字

给你一个32位的有符号整数x，返回x中每位上的数字反转后的结果。结果不能超过
32位有符号数的范围，可以考虑先用long表示反转的数，然后强转为int

1
2
3
4
5
6
7
8
public int reverse(int x) {
        long n = 0;
        while(x != 0) {
            n = n*10 + x%10;
            x = x/10;
        }
        return (int)n==n? (int)n:0;
    }

平方数之和

给定一个非负整数c，你要判断是否存在两个整数a和b，使得a^2+b^2=c。
使用双指针，从左右两边开始遍历

1
2
3
4
5
6
7
8
9
10
11
int low=0,high=(int)Math.sqrt(c);
      while(low<=high){
          int sum = low*low + high*high;
          if(sum == c){
              return true;
          }else if(sum<c){
              low++;
          }else
              high--;
      }
      return false;

完美数

这个题最直接的思路就是遍历，但是会超出时间限制，实际上除了1和平方根
之外，正因子都是成对出现的，所以只需要遍历平方根之前的数就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if(num == 1) {
          return false;
      }
      int sum = 1; // 正整数一定会有一个1，同时不用考虑自身，所以单独处理
      int i = 2;
      double sqrt = Math.sqrt(num);
      for(;i < sqrt;i++) {
          if(num % i == 0) {
              sum += i;
              sum += num / i;
          }
      }
      // 此处单独处理的原因在于只需要加1次i值，如果在循环中会加2次
      if(i * i == num) {
          sum += i;
      }
      return sum == num;

卡牌分组

统计每个数出现的次数，然后求最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean hasGroupsSizeX(int[] deck) {
       int[] count = new int[10000];
       for (int c: deck)
           count[c]++;
       int g = -1;
       for (int i = 0; i < 10000; ++i)
           if (count[i] > 0) {
               if (g == -1)
                   g = count[i];
               else
                   g = gcd(g, count[i]);
           }
       return g >= 2;
   }
   public int gcd(int x, int y) {
       return x == 0 ? y : gcd(y%x, x);
   }

最大交换

把尽可能低位的最大数字与尽可能高位的小数字交换。不好理解的地方可能在于
低位的数字会存在重复，交换时因为高位换过来的是更小的数所以要保证换到
重复数字中最低位的那一个，所以要从低往高遍历记录每个位置经过交换能得
到的最大数字，因为要交换，所以数组里存的是下标

  1. 先从低位往高位遍历，保存每一位经过交换能得到的最大值的下标
  2. 再从高位往低位遍历，直到某一位小于该位可以取到的最大值，上一步保存
    了该位置最大值的下标，交换即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int maximumSwap(int num) {
        char[] nums = Integer.toString(num).toCharArray();
        int[] index_arr = new int[nums.length];
        int max_index = nums.length - 1;
        //低位往高位遍历
        for(int i = nums.length - 1; i >= 0; i--) {
            if(nums[i] > nums[max_index]) max_index = i;
            index_arr[i] = max_index;
        }
        //高位往低位遍历
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != nums[index_arr[i]]) {
                char temp = nums[i];
                nums[i] = nums[index_arr[i]];
                nums[index_arr[i]] = temp;
                break;
            }
        }
        return Integer.parseInt(new String(nums));

二进制中1的个数

这个题的n是无符号数，区分正负会有问题，最简明的思路是按位与，还有一种
思路是利用n&(n-1)，n-1的意思是二进制数字n最右边的1变成0，此1右边的0
都变成1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int hammingWeight(int n) {
        int sum=0;
        while(n!=0){
            sum=sum+(n&1);
            //无符号右移
            n=n>>>1;
        }
        return sum;
    }
    public int hammingWeight(int n) {
        int sum=0;
        while(n!=0){
            sum++;
            //每次都消去一个1
            n&=(n-1);
        }
        return sum;
    }

颠倒二进制位

循环32次，每次将右边最后1位获取保存，同时已经保存的位左移

1
2
3
4
5
6
7
8
9
10
11
public int reverseBits(int n) {
        int res=0;
        for(int i=0;i<32;i++)
        {
        	//注意在获取最后一位之前必须确保之前的结果左移
            res<<=1;
            res=res|(n&1);
            n>>>=1;
        }
        return res;
    }

三数之和

排序+双指针

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
public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> a=new ArrayList<>();
        if(nums==null)
            return a;
        if(nums.length<3)
            return a;
        Arrays.sort(nums);
        int start=0;
        int end=nums.length-1;
        for(int i=0;i<nums.length;i++)
        {
            if(nums[i]>0)
                break;
            if(i>0&&nums[i]==nums[i-1])
                continue;
            start=i+1;
            end=nums.length-1;
            while(start<end)
            {
                if(nums[i]+nums[start]+nums[end]==0)
                {
                    ArrayList<Integer> b=new ArrayList<>();
                    b.add(nums[i]);
                    b.add(nums[start]);
                    b.add(nums[end]);
                    a.add(b);
                    while(start<end&&nums[start]==nums[start+1])
                    start++;
                    while(start<end&&nums[end]==nums[end-1])
                    end--;
                    start++;
                    end--;
                }
                else if(nums[i]+nums[start]+nums[end]>0)
                    end--;
                else 
                    start++;
               
            }
        }
        return a;
    }

字典排序

给定n=13，返回[1,10,11,12,13,2,3,4,5,6,7,8,9]。N叉树前序遍历一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    ArrayList<Integer> res = new ArrayList<>();
    public List<Integer> lexicalOrder(int n) {
        for (int i = 1; i < 10; i ++){
            dfs(n, i);
        }
        return res;
    }
    private void dfs(int n, int cur){
        if (cur > n) return;
        res.add(cur);
        for (int i = 0; i < 10; i ++) {
            dfs(n, cur * 10 + i);
        }
    }
}

回溯

一组数的所有排列

回溯法 采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的
过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时
候，它将取消上一步甚至是上几步的计算。这个题中采用回溯思想

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
List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
    	//1 2 3 从第一个开始进行遍历
        for(int i=0;i<nums.length;i++)
        {
            ArrayList<Integer> array=new ArrayList<>();
            array.add(nums[i]);
            cut(array,nums);
        }
        return list;
    }
    public void cut(ArrayList<Integer> array,int[] nums)
    {
    	//回溯终止条件就是遍历完成
        if(array.size()==nums.length)
        {
            list.add(new ArrayList<Integer>(array));
            return ;
        }
        for(int i=0;i<nums.length;i++)
        {
            if(!array.contains(nums[i]))
            {
            	//满足条件加入
                array.add(nums[i]);
                //继续回溯
                cut(array,nums);
                //回退
                array.remove(array.size()-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
26
27
28
29
30
31
32
33
34
35
public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, sum, new ArrayList<>(), result);
    return result;
}

public void dfs(TreeNode root, int sum, List<Integer> list,
                List<List<Integer>> result) {
    //如果节点为空直接返回
    if (root == null)
        return;
    //把当前节点值加入到list中
    list.add(new Integer(root.val));
    //如果到达叶子节点，就不能往下走了，直接return
    if (root.left == null && root.right == null) {
        //如果到达叶子节点，并且sum等于叶子节点的值，说明我们找到了一组，
        //要把它放到result中
        if (sum == root.val)
        	//注意这里必须返回一个新对象，将一条路径上的值都赋值到新对象中
            result.add(new ArrayList(list));
        //注意别忘了把最后加入的结点值给移除掉，因为下一步直接return了，
        //不会再走最后一行的remove了，所以这里在rerurn之前提前把最后
        //一个结点的值给remove掉。
        list.remove(list.size() - 1);
        //到叶子节点之后直接返回，因为在往下就走不动了
        return;
    }
    //如果没到达叶子节点，就继续从他的左右两个子节点往下找，注意到
    //下一步的时候，sum值要减去当前节点的值
    dfs(root.left, sum - root.val, list, result);
    dfs(root.right, sum - root.val, list, result);
    //我们要理解递归的本质，当递归往下传递的时候他最后还是会往回走，
    //我们把这个值使用完之后还要把它给移除，这就是回溯
    list.remove(list.size() - 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
26
27
28
int len = A.length;
      if(len==1)
          return A;
      //1.从后往前找，如果是A[i]>=A[i-1]则继续
      //2. 碰到A[i]<A[i-1]记录下需要交换的位置
      //3. 找到比他小的再交换即可(需要找到位置最前的元素)
      // 123456这样的没法换
      //987654321 这样的可以换
      for(int i = len-1;i > 0;i--){
          while(i>0&&A[i]>=A[i-1])
              i--;
          if(i==0)
              return A;

          for(int j = len-1;j >= i;j--){//注意此处的边界
              if(A[j]<A[i-1]){
                  //swap(A,i-1,j);
                  int tmp = j;
                  for(int k = j-1;k>=i;k--){
                      if(A[k]==A[j])
                          tmp = k;
                  }
                  swap(A,tmp,i-1);
                  return A;
              }
          }
      }
      return A;

跳跃游戏

这道题的核心就是说从倒数第二个位置开始向左遍历，如果这个位置能够到达
最后指定位置，继续向左遍历，既然要到最后一个位置，那么如果能够达到在
这之前的位置，一直不断放宽条件

1
2
3
4
5
6
7
8
int last=nums.length-1;
      for(int i=nums.length-1;i>=0;i--)
      {
      	//这里要用>= 因为可以有多种选择
          if(i+nums[i]>=last)
              last=i;
      }
      return last==0;

对称数组的交换

我们可以旋转第i张多米诺，使得A[i]和B[i]的值交换。返回能使A中所有值或
者B中所有值都相同的最小旋转次数，值的范围是1到6。可以使用两个记录数组
，把元素的个数都记录在记录数组中

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
int[] array1=new int[7];
      int[] array2=new int[7];
      for(int i=0;i<A.length;i++)
      {
          array1[A[i]]++;
          array2[B[i]]++;
      }
      boolean flag=false;
      for(int i=1;i<=6;i++)
      {
          flag=false;
          if(array1[i]+array2[i]>=A.length)
          {
              for(int j=0;j<A.length;j++)
              {
                  if(A[j]!=i&&B[j]!=i)
                      {
                          flag=true;
                          break;
                      }
              }
              if(flag)
                  break;
              else
              {
                  int min=Math.min(A.length-array1[i],A.length-array2[i]);
                  return min;
              }
          }
      }
      return -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
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
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
    public int reversePairs(int[] nums) {
        if(nums.length==0)
            return 0;
        //临时数组
        int[] array=new int[nums.length];
        //暂时保存值
        int[] temp=new int[nums.length];
        for(int i=0;i<nums.length;i++)
        {
            temp[i]=nums[i];
        }
        int num=reverse(nums,array,0,nums.length-1);
        //恢复原数组
        for(int i=0;i<nums.length;i++)
        {
            nums[i]=temp[i];
        }
        return num;
    }
    public int reverse(int[] nums,int[] array,int left,int right)
    {
        if(left==right)
            return 0;
        int mid=(left+right)/2;
        int numleft=reverse(nums,array,left,mid);
        int numright=reverse(nums,array,mid+1,right);
        //这里可以判断一下是否需要合并
        if(nums[mid]<=nums[mid+1])
            return numleft+numright;
        //合并操作
        int num=merge(nums,array,left,right,mid);
        return num+numleft+numright;
    }
    public int merge(int[] nums,int[] array,int left,int right,int mid)
    {
        //逆序对总数
        int count=0;
        int index=0;
        int i=left;
        int j=mid+1;
        while(i<=mid&&j<=right)
        {
            //注意这个地方必须有=，如果没有等号会多算逆序对
            if(nums[i]<=nums[j])
                array[index++]=nums[i++];
            else
            {
                /*
                    核心在这个地方，可以这样想，比如归并的时候第一个
                    是nums[j]归并到前面，那么说明左半部分的元素都比
                    这个nums[j]大，这就有mid-i+1个逆序对，以此就可以
                    得到所有逆序对，如果nums[i]在前那么对于i来说往后
                    就不存在逆序对了
                */
                count+=(mid-i+1);
                array[index++]=nums[j++];
            }
        }
        while(i<=mid)
            array[index++]=nums[i++];
        while(j<=right)
            array[index++]=nums[j++];
        index=0;
        while(left<=right)
        {
            nums[left++]=array[index++];
        }
        return count;

    }
}

脑筋急转弯

  1. 先手必胜策略

剪绳子I

给你一根长度为n 的绳子，请把绳子剪成整数长度的m 段，求最大乘积。

  1. 动态规划
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
        public int cuttingRope(int n) {
        	//dp[i]表示长度为i的绳子剪成m段后的最大乘积
            int[] dp = new int[n + 1];
            dp[2] = 1;
            for(int i = 3; i < n + 1; i++){
            	//如果只剪掉长度为1，对最后的乘积无任何增益，所以从长度为2开始剪
                for(int j = 2; j < i; j++){
                //剪了第一段后，剩下(i - j)长度可以剪也可以不剪。如果不剪的话
                //长度乘积即为j * (i - j)；如果剪的话长度乘积即为j * dp[i - j]
                //取两者最大值max(j * (i - j), j * dp[i - j])
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
                }
            }
            return dp[n];
        }
    }
  2. 贪心算法 尽可能把绳子分成长度为3的小段，这样乘积最大
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
        public int cuttingRope(int n) {
            if(n < 4){
                return n - 1;
            }
            int res = 1;
            while(n > 4){
                res *= 3;
                n -= 3;
            }
            return res * n;
        }
    }

剪绳子II

考虑大数问题

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int cuttingRope(int n) {
        if(n < 4){
            return n - 1;
        }
        long res = 1;
        while(n > 4){
            res  = res * 3 % 1000000007;
            n -= 3;
        }
        return (int) (res * n % 1000000007);
    }
}

智力题

高楼扔鸡蛋问题

  1. 暴力法 直接从第一层开始往上遍历，用不到第二个鸡蛋
  2. 二分法 将鸡蛋从楼层中间位置扔出
  • 如果没碎，那么继续从剩下楼层的中间位置扔出
  • 如果碎了，第二个鸡蛋就从相应的位置往上遍历
  1. 均匀法 让第一个鸡蛋和第二个鸡蛋的尝试次数更均匀，比如每十层扔一次
  2. 最优解法 假设最优解法在最坏情况需要仍X次。接下来就要决定首先在第几
    层开始仍
  • 如果在第X+1层开始扔，如果碎了那么就要从第一次往上遍历，需要X+1次
  • 如果在第X-1层开始扔，事实上最优解法的情况应该保证扔X次的话那么临
    界层的高度应该至少是X，肯定比暴力法要好，所以至少应该更高
  • 从第X层开始扔 如果鸡蛋碎了那么总共就是X次，如果没碎那么还有X-1次
    机会，那么接下来就应该从X+X-1层开始扔
    1
    2
    X+(X-1)+(X-2)+...1=100
    X向上取整14

找砝码问题

二分法

  1. 分为三份 4 4 1 比较两个4，如果相等那么剩下的就是轻的
  2. 两个4不相等，将一个4分为两份继续比较
  3. 两个1找出轻的

三分法

  1. 分为三份3 3 3 比较其中的两份
  2. 继续三分

找玻璃球问题

将十组玻璃珠编号1~10，然后第一组拿一个，第二组拿两个以此类推…第十组拿
十个，将这些玻璃珠一起放到秤上称出克数x

1
2
x = 1*10 + 2*10 + 3*10 + ... + 10 * 10 - y
y就是轻的那一组

毒药问题

二进制思路，2^10 = 1024 > 1000，因此10只小白鼠即可。
给1000瓶水按照二进制编号，比如3号编为00000 00011，拿10个碗，对应10位，对
于3号水来说，最后两位是1，则把水混合进最后两个碗中。 最终把10碗水给对应的
小白鼠喝，根据最后小白鼠死亡的情况（死即为1，活即为0），即可确定出有毒的
那碗水

生成随机数问题

1
2
3
4
5
6
7
8
9
10
11
12
// 需要随机得到 1-7
public static int rand7() {
    while (true) {
      int row, col, idx;
      // rand5() 返回 1-5
      row = rand5(); // 5 * 5 = 25, 设想一个 5*5 的矩阵
      col = rand5(); // 然后找到小于25的，7的最大倍数21
      idx = col + (row - 1) * 5;
      if (idx <= 21) // 只考虑 1-21，划分成 7 份
        return 1 + (idx - 1) % 7;
    }
}

先手必胜策略

100本书，每次能够拿1-5本，怎么拿能保证最后一次是你拿？

  • 卡关键点，每次只能拿1-5本，所以当剩下6本的时候，不论对面怎么拿你
    都能赢
  • 然后推6的倍数：12、18、…、96，也就是一开始要拿4本
  • 接下来对面拿1，你就拿5，对面拿2，你就拿4，总之让你拿的和对面拿的
    加起来是6，最终就能赢

瓶子换饮料问题

  • 1000瓶饮料，3个空瓶子能够换1瓶饮料，问最多能喝几瓶？
  • 1000 % 3 = 333…1 喝掉1000瓶,可以换333瓶汽水, 余1个空瓶
  • 333 % 3 = 111…0　喝掉333瓶，可以换111瓶汽水, 余0个空瓶
  • 111 % 3 = 37…0　 喝掉111瓶，可以换37瓶汽水, 余0个空瓶
  • 37 % 3 = 12…1　 喝掉37瓶，可以换12瓶汽水, 余1个空瓶
  • 12 % 3 = 4…0 喝掉12瓶，可以换4瓶汽水, 余0个空瓶
  • 4 % 3 = 1…1 喝掉4瓶，可以换1瓶汽水, 余1个空瓶
  • 此时剩下1瓶汽水 + 3个空瓶，其中3个空瓶可以再换1瓶
  • 此时剩下2瓶，喝掉2瓶，不能再换了。 总共：
    1000 + 333 + 111 + 37 + 12 + 4 + 2 = 1499瓶

烧香确定时间问题

有两根不均匀的香，燃烧完都需要一个小时，问怎么确定15分钟的时长？
设两根香分别为A、B，先把A一端点燃，然后把B的两端都点燃，这样当B烧完
的时候，A就还剩下一半（此时能确定半小时），此时把A的另一端也点燃，
那么从此刻到A烧完的时间就是15分钟

掰巧克力问题

N*M块巧克力，每次掰一块的一行或一列，掰成1*1的巧克力需要多少次？
淘汰问题：1000个人参加辩论赛，1V1，输了就退出，需要安排多少场比赛？

  • 每次拿起一块巧克力，掰一下（无论横着还是竖着）都会变成两块，因为所有
    的巧克力共有N*M块，所以要掰N*M-1次，减1是因为最开始的一块是不用算进
    去的
  • 每一场辩论赛两个人，淘汰一个人，所以可以看作是每一场辩论赛减少一个
    人，直到最后剩下1个人，所以是1000 - 1 = 999场

海量数据题

  1. 分治：hash 后单独处理，最后合并
  2. 布隆过滤器
  3. 位图法
  4. 最大/最小堆

海量日志数据，提取出某日访问百度次数最多的那个IP

一共有2^32种IP，我们拆分成1024个文件

1
2
2^10 = 1024
2^32 / 2^10 = 2^22 = 2^2 * 2^20 = 4M

接下来我们遍历日志文件，把每个IP采用哈希方式映射到1-1024个文件中，那
么相同IP就会到达同一个文件中，然后对每个文件求IP的最大重复数，最后对
1024个文件的各个最大值再求一次最大值，得到最终结果

32位的机器，2亿个整数中找不重复数字？

必然是要遍历这2亿个整数的，这个过程中会出现三种状态：未出现、出现、重复
出现，既然是三种状态，1位不够用，我们用2位来存，00代表未出现，01代表
出现一次，10代表多次重复出现，我们首先遍历2亿个整数，然后出现的整数
就把对应位置改为01，如果当前状态已经是01，则改为10，那么这样遍历一
遍之后，我们就再遍历一遍用来存储的数据，根据状态就知道哪些是不重复
数字了，总共所需内存为 2^32*2b=1GB

如何快速判断某个数是否在40亿个整数当中？

这题就是很明显的布隆过滤器了，与前一题不同的是，我们可以不需要用两位来
表示一个整数，毕竟这里只需要存在和不存在两个情况，1 bit就足够了，所以
我们可以用类似上面的思路，先遍历40 亿个整数，出现了则将相应位置的bit
修改为1，判断的时候也只需判断对应位置的bit是0还是1。0则代表不存在，
1则代表存在,40 亿个不重复整数，我们用 40 亿个 bit 来表示

用 Rand7() 实现 Rand10()？

  1. 已知 rand_N() 可以等概率的生成[1, N]范围的随机数。那么：
    1
    (rand_X()-1)×Y+rand_Y() ==> 可以等概率的生成[1,X*Y]范围的随机数即实现了rand_XY()
  2. rand_N() 实现 Rand_2() 取余加1即可，但是N必须是偶数
  3. 要实现rand10()，就需要先实现rand_N()，并且保证N大于10且是10的倍数
    。这样再通过rand_N() % 10 + 1 就可以得到[1,10]范围的随机数了。
    1
    (rand7()-1) × 7 + rand7()  ==> rand49()
  4. 但是这样实现的N不是10的倍数啊！这该怎么处理？这里就涉及到了“拒绝
    采样”的知识了，也就是说，如果某个采样结果不在要求的范围内，则丢弃它
    1
    2
    int num = (rand7() - 1) * 7 + rand7(); // 等概率生成[1,49]范围的随机数
    if(num <= 40) return num % 10 + 1; // 拒绝采样，并返回[1,10]范围的随机数

选举算法了解吗？

选举算法是一种分布式选举算法，每次都会选出存活的进程中ID最大的候选者

20*500 个数中找出前 500 的数？

  1. 首先建立大顶堆，堆的大小为数组的个数，即为20，把每个数组最大
    的值存到堆中
  2. 接着删除堆顶元素，保存到另一个大小为 500 的数组中，然后向大顶
    堆插入删除的元素所在数组的下一个元素
  3. 重复上面的步骤，直到删除完第 500 个元素，也即找出了最大的前
    500 个数

从1亿个整数里找出100个最大的数？

  1. 100个数建堆，而且是建立成最小堆。剩下的1亿减100个数依次和堆顶元
    素比较，如果比堆顶元素小，那么不管它。如果比堆顶元素大，就用这个元
    素把堆顶元素替换掉，然后调整堆，继续保持最小堆的性质。直到剩下的所
    有元素都和堆顶元素比较完毕。那么堆中的100个数就是最大的
  2. 可以把所有1亿个数据分组存放，比如分别放在1000个文件中，然后每个
    文件找最大的100个数，进行排序
  3. 局部淘汰法 先创建一个数组，保存这1亿个数字中的前100个数字，计算
    数组的最小数字，遍历剩下的数字。如果遍历到某个数 A 大于数组的最小数
    字，那么则用A 替换掉数组的最小数字。并重新计算数组的最小数字。

从5 亿个数中找出中位数？

  1. 维护两个堆，一个大顶堆，一个小顶堆。大顶堆中最大的数小于等于小顶
    堆中最小的数，保证这两个堆中的元素个数的差不超过1。若数据总数为偶数
    ，当这两个堆建好之后，中位数就是这两个堆顶元素的平均值。当数据总数
    为奇数时，根据两个堆的大小，中位数一定在数据多的堆的堆顶
  2. 分治法 顺序读取这5 亿个数字，对于读取到的数字num，如果它对应的二
    进制中最高位为1，则把这个数字写到f1 中，否则写入f0 中。通过这一步，
    可以把这5 亿个数划分为两部分，而且f0 中的数都大于f1 中的数，中位数
    一定在多的里面，继续递归第二位是0还是1，直到剩下一个数，或者剩下两
    个数求平均

知道mapReduce吗？

它是一种编程模型，用于大规模数据集（大于1TB）的并行运算

无序双向链表转二叉树？

  1. 二叉树转换成有序的双向链表 原先指向左子结点的指针调整为链表中指
    向前一个结点的指针，原先指向右子结点的指针调整为链表中指向下一个结
    点的指针
  2. 有序单链表转换成二叉树

计算机能否微妙级别计数，不能的话原因是什么？

  1. Linux gettimeofday(struct timeval *,NULL)

字符串压缩，对字符串进行原地压缩

  1. 原地压缩 在压缩的过程中，不再多使用别的内存空间，又将这种算法称
    为原地压缩算法

rand()可以得到0和1，如何实现等概率随机数得到0-n？

rand35()实现rand47()

1
2
3
4
5
6
while(true)
       {
           int x = (rand35()-1)*35 + rand35();//rand生成0-1225
           if (x <= 47*26) //拒绝1223-1225
           {return x % 47 + 1;}
   }

求最大公约数的几种方法？

  1. 指两个或多个整数共有约数中最大的一个，如果数a能被数b整除，a就叫做
    b的倍数，b就叫做a的约数
  2. 短除法
  3. 辗转相除法 用较小数除较大数，再用出现的余数（第一余数）去除除数，
    再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为
    止，最后的除数就是这两个数的最大公约数
  4. 辗转相减法

赛马问题？

最少需要10场or11场

  1. 需8场比赛 首先把64匹马随机分为8组并标记组别，遍历组别，比赛8次
    ，并记录每组赛马名次，首先可直接剔除各组后四名赛马
  2. 需1场比赛 选出每组排名第一的赛马进行一次比赛，记录结果，不失一般
    性地，记为：A1>B1>C1>D1>E1>F1>G1>H1。根据这轮比赛结果，首先可以剔
    除E、F、G、H这四组所有赛马
  • 其次可以确定A1就是全场MVP，属全场N01，剩余15匹马待定
  • D组2-4名赛马：D2>D3>D4，不可能是Top4，可剔除这3匹，剩余15-3=12
    匹赛马待定
  • C组3-4名赛马:C3>C4，不可能是Top4，可剔除这2匹，剩余12-2=10匹赛
    马待定
  • B组第4名赛马：B4，也不可能是Top4，可剔除这1匹，剩余10-1=9匹赛马
    待定
  1. 需1场or2场比赛
  • 当前剩余待定9匹赛马：A2>A3>A4,B1>B2>B3,C1>C2,D1
  • 因为可以确定B1>C1>D1，因此挑选：A2>A3>A4,B1>B2>B3,C1>C2（ 或者
    A2>A3>A4,B1>B2>B3,C1>D1）等8匹马进行一场比赛，剩余一匹赛马D1或者
    C2待定，重点关注C1名次
  • 仅需1场比赛情形 当C1排名第3及以后，则选出本场前3名赛马，外加大佬
    A1，即为所求的Top4匹马
  • 需2场比赛情形 因为已知B1>C1,所以C1本场名次区间为[2,8]，当C1排名
    第2时，可推知B1排名本场第一，因此A1>B1>C1即为全场Top3匹马，此时可
    剔除B1,C1两匹马，剩余9-2=7匹马待定

大量的URL 中找出相同的 URL？

  1. 一般采用分治策略，即：把一个文件中的 URL 按照某个特征划分为多个
    小文件，使得每个小文件大小不超过4G，这样就可以把这个小文件读到内存
    中进行处理了
  2. 分而治之，进行哈希取余，对每个子文件进行HashSet 统计

大量数据中找出高频词？

  1. 首先遍历大文件，对遍历到的每个词x，执行 hash(x) % 5000，将结果
    为 i 的词存放到文件 ai 中。遍历结束后，我们可以得到 5000 个小文件
    。每个小文件的大小为 200KB 左右。如果有的小文件大小仍然超过1MB，则
    采用同样的方式继续进行分解
  2. 通过维护一个小顶堆来找出所有词中出现频数最高的 100 个。具体方法
    是：依次遍历每个小文件，构建一个小顶堆，堆大小为100，如果遍历到的
    词的出现次数大于堆顶词的出现次数，则用新词替换堆顶的词，然后重新
    调整为小顶堆，遍历结束后，小顶堆上的词就是出现频数最高的100个词

用4个字节存储QQ号，并管理上线和下线的状态

前31位存qq，后1一位存状态

Bitmap 算法原理？

  1. 所谓的Bit-map就是用一个bit位来标记某个元素对应的Value，而Key
    即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可
    以大大节省
  2. 与其说是算法，不如说是一种紧凑的数据存储结构。是用内存中连续的
    二进制位(bit)，用于对大量整型数据做去重和查询

布隆过滤器的用途？

它本身是一个很长的二进制向量和一系列随机映射函数，既然是二进制的
向量，那么显而易见的，存放的不是0，就是1。可以用于检索一个元素是
否在一个集合中

  1. 布隆过滤器只能判断数据是否一定不存在，而无法判断数据是否一定存在
  2. 由于存放的不是完整的数据，所以占用的内存很少，而且新增，查询速度
    够快
  3. 随着数据的增加，误判率随之增加，无法做到删除数据

布隆过滤器的应用？

网页URL的去重，垃圾邮件的判别，集合重复元素的判别，查询加速（比如基
于key-value的存储系统）、数据库防止查询击穿

1000 万条数据里面有重复的数据，如果找出重复的前十短信

Author: 高明
Link: https://skysea-gaoming.github.io/2021/01/22/%E5%88%B7%E9%A2%98%E6%80%BB%E7%BB%93/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
DataStructure