醉里挑灯赏猫

努力努力再努力

0%

发布： 分类： 评论： 阅读：

之前两次面试都被问到洗牌算法，虽然不是直接问的，但都是基于洗牌算法的。结果第一次被问到之后没有重视，导致在一个地方栽了两次坑。。。😭

洗牌算法，就是给你一个1到n的序列，让你随机打乱，保证每个数出现在任意一个位置的概率相同。换句话说，经过洗牌的数组的排列组合有n!种可能。

发布： 分类： 评论： 阅读：

平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

发布： 分类： 评论： 阅读：

图，最多的遇到的面试题就是深度优先搜索和广度优先搜索，这也是最基础的。
图的一个最重要的点：设置一个 visit[] 数组，用来表示图中的每个节点是否已经被访问过。

发布： 分类： 评论： 阅读：

例题

leetcode 316. 删除字符串中的重复字符

1
2
3
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example 1:  Input: "bcabc"      Output: "abc"
Example 2:  Input: "cbacdcbc"   Output: "acdb"
  • 因为只有26个小写字母，所以可以用数组模拟 hashmap 先统计每个字符出现的次数。
  • 然后要用辅助栈。其实发现很多问题都是数组和栈辅助进行操作，来对比当前元素和栈顶元素的大小，从而进行相应的操作。删除栈顶元素还是向栈中添加元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public String removeDuplicateLetters(String s) {
    int[] count = new int[26];  // 统计每个字符出现的次数
    boolean[] visit = new boolean[26];  // 表示某个字符是否已经出现在栈中
    for(char ch : s.toCharArray())  
        count[ch-'a'] += 1;
    Stack<Character> sta = new Stack();
    for(char ch : s.toCharArray()) {
        count[ch-'a'] -= 1;
        if(visit[ch-'a']) continue;
        // 如果当前元素比栈顶元素小，并且栈顶元素次数不等0
        // 那么就把栈顶元素弹出来，把当前元素入栈
        while(!sta.isEmpty() && ch<sta.peek() && count[sta.peek()-'a']!=0) 
            visit[sta.pop()-'a'] = false;
        sta.push(ch);
        visit[ch-'a'] = true;
    }
    String res = "";
    while(!sta.isEmpty())
        res = sta.pop()+res;
    return res;
}

发布： 分类： 评论： 阅读：

数组的全排列

leetcode 31. 给出全排列的下一个排列

  • 输入1: 1,2,3,4,3,8,7,6,5 → 1,2,3,4,5,3,6,7,8
  • 输入2: 3,2,1 → 1,2,3
  • 条件：在nums数组上就地转换，并且要使用常数级辅助空间
  • 从后向前，找到递减的位置，然后从后面找到比他大的第一个元素，交换，然后对后面从小到大排序即可
  • 如果当前已经是最大，那么就输出他的最小值 从小到大排序即可
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
public void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}
    
public void reverse(int[] nums, int begin) {
    int end = nums.length-1;
    for(int i=0;i<(end-begin+1)/2;i++)
        swap(nums, begin+i, end-i);
}

public void nextPermutation(int[] nums) {
    boolean flag = true;
    for(int i=nums.length-1;i>0;i--) {
        if(nums[i]<=nums[i-1])
            continue;
        else {
            //nums[i-1]是递减的那个值
            for(int j=nums.length-1;j>=0;j--) {
                if(nums[j]>nums[i-1]) {
                    swap(nums, i-1, j);
                    flag = false;
                    break;
                }
            }
            //对后面逆序
            reverse(nums, i);
            break;
       }
    }
    if(flag)
        Arrays.sort(nums);
}