醉里挑灯赏猫

努力努力再努力

0%

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

队列

1
2
3
4
Queue<Integer> que = new LinkedList();
que.offer(1);  // 添加元素
int v1 = que.poll();   // 返回第一个元素，并在队列中删除，如果队列为空，返回null
int v2 = que.peek();   // 返回第一个元素

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

HashMap 的使用，很多时候都是为了空间换时间。

有时遇到字母或者字符时，还可以利用固定长度的数组代替 HashMap，比如字符为 Object[256] , 字母的话为 Object[26] 。

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

回溯法：实现某个元素选或不选的问题。

发布： 分类： 评论： 阅读：
1. leetcode 136. Single Number
1
2
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
数组中只有一个数字出现了一次，其他数字都出现了2次。找出这个只出现一次的数字。
  • 异或。相同的两个数二进制异或为0.
  • 所有的元素进行异或，最后的值即为出现一次的元素的值。
1
2
3
4
5
6
public int singleNumber(int[] nums) {
    int res = 0;
    for(int i=0;i<nums.length;i++)
        res = res^nums[i];
    return res;
}

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

时间复杂度

一遍循环：O(n)

嵌套两遍循环：O(n*n)

1
2
3
for(int i=0;i<n;i++) 
    for(int j=0;j<n;j++)
        .....

O(log n) 与 O(n log n) 分析方法：

📍 自理解：一般这种带有 logn 都是有递归操作的。例如二分查找，就是每次我找到中间位置，然后如果查找的值大于当前值，那么我只需在后一半中继续查找，如果查找的值小于当前值，就在前一半中继续查找，每次我都可以减少一半数量的元素。其时间复杂度为 O(logn) 。像归并排序, 虽然我每次把整个array分成了两个部分，但是两个部分都需要去进行递归处理，那么时间复杂度就是 O(nlogn) 。