List

LeetCode刷题思路,持续更新中……

338. Counting Bits

题目

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Tag: Bit ManipulationDynamic Programming

思路

根据题目要求,即给出一个数num,计算从0~num的整数二进制形态中数字1的个数。

解法一

若使用时间复杂度为O(n*sizeof(integer))的算法,还是比较简单的。即循环0~num每个整数i,循环执行i&=(i-1),计算i二进制形态中数字1的个数。

解法二

而题目要求in linear time O(n)的线性时间算法。
我们用数组res存储最后的结果,将res[0]先置0。通过如下递推,可以获得一些规律:
































i (i-1)&i count res[i]
1 0 count=0 res[1] = res[count]+1 = res[0]+1 = 1
2 0 count=0 res[2] = res[count]+1 = res[0]+1 = 1
3 1 count++, count=1 res[3] = res[count]+1 = count[1]+1 = 2
4 0 count=0 res[4] = res[count]+1 = count[0]+1 = 1

即:若计算i&(i-1)后:

1. 结果等于零,则该二进制数中仅有1个数字1,此时将count的值置为0res[i] = res[count] + 1 = res[0] + 1 = 1;
2. 结果不等于零,则该二进制数中数字1的个数大于1。该数字i可以拆分成<i的数字。比如:
- 3 = 1 + 2
- 5 = 3 + 2
- 7 = 5 + 2

即:可以用res[j] (j < i) 来计算res[i]的值

## 解决方法

### 解法一:run time O(nsizeof(integer))

c++ Solution

class Solution {
public:
vector countBits(int num) {
vector result;
int cnt;
for(int i=0; i<=num; i++) {
int t = i;
for(cnt=0; t>0; cnt++) {
t &= (t-1);
}
result.push_back(cnt);
}
return result;
}
};

### 解法二:run time O(n)

c++ Solution

class Solution {
public:
vector countBits(int num) {
vector res;
res.push_back(0);
int count = 0;

for (int i = 1; i <= num; ++ i) {
if (((i - 1) & i) == 0) {
count = 0;
} else {
count += 1;
}
res.push_back(1 + res[count]);
}
return res;
}
};

———-


# 一 292. Nim Game

## 题目
You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.


## 思路
根据题设条件: 当n∈[1,3]时,先手必胜。

n == 4时,无论先手第一轮如何选取,下一轮都会转化为n∈[1,3]的情形,此时先手必负。

n∈[5,7]时,先手必胜,先手分别通过取走[1,3]颗石头,可将状态转化为n == 4时的情形,此时后手必负。

n == 8时,无论先手第一轮如何选取,下一轮都会转化为n∈[5,7]的情形,此时先手必负。

所以,我们仅需关注n的个数是否为4的倍数即可。

## 解决方法

c++ Solution

class Solution {
public:
bool canWinNim(int n) {
if(n%4 == 0) {
return false;
} else {
return true;
}
}
};

———-


# 二 136. Single Number

## 题目

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Tag:Hash TableBit Manipulation

## 思路

题目要求:在一个整数数组中,每个元素会出现两次或一次,要求找出仅出现一次的元素。
看到题目后第一反应是使用Hash Table来解决。但在题目Tag中提示可以使用Bit Manipulation,于是想到用位运算中异或的方法:

> A ^ B ^ A = B

将整数数组nums中的每个数循环执行异或操作,最终得到的结果就是仅出现单次的数。

## 解决方法

c++ Solution

class Solution {
public:
int singleNumber(vector& nums) {
int result = nums[0];
for(int i=1; i258. Add Digits

## 题目

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

*Tag
:Math

## 思路

拿到题目后的第一想法还是对num进行循环取模求和运算,但题目要求O(1)的时间复杂度,那么应当又是一道有规律可循的题了。

我们对一系列数的运算结果进行观察:





















































































num result
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 1
11 2
12 3
13 4
14 5
15 6
16 7
17 8
18 9
19 1
20 2

从结果可以观察出,都是1~9的循环数。因此对于某数字num得出的result应当为:

result = (num-1)%9 + 1

解决方法

c++ Solution

class Solution {
public:
    int addDigits(int num) {
        return (num-1)%9+1;
    }
};

226. Invert Binary Tree

题目

Invert a binary tree.
title
to
title
Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
Tag:Tree

思路

二叉树的反转就是将左右子树不停地调换位置,可以用递归的方式实现。

解决方法

c++ Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root) {
            //  调换左右子树位置
            TreeNode *t;
            t = root->left;
            root->left = root->right;
            root->right = t;
            //  递归
            invertTree(root->left);
            invertTree(root->right);
        }
        return root;
    }
};

283. Move Zeroes

题目

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

Tag: ArrayTwo Pointers

思路

题目不允许copy array,如果要把数字0都移动到数组末尾,第一想法还是当遇到0时,将数组循环前移,再在末尾插入0。或者直接使用vectorerase(),擦除0所在位置,并在末尾push_back(0)
But……这种方法分分钟超时了……
题目中Tag提示Two Pinters,估计就是用双指针进行数字交换了。
使用两个指针ij指向数组的下标,通过i循环nums[i],每当遇到非零数字时,交换nums[i]nums[j],并执行j++
若存在0,则能让j始终指向数字0,当i指向非0数字时,交换二者。

解决方法

解法一

c++ Solution

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int i=0, j=0; i<nums.size(); i++) {
            if(nums[i] != 0) {
                swap(nums[i], nums[j]);
                j++;
            }
        }
    }
};

解法二

c++ Solution Time Limit Exceeded

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int size = nums.size();
        for(int i=0; i<size; i++) {
            if(nums[i] == 0) {
                nums.erase(nums.begin()+i);
                nums.push_back(0);
                i = 0;
            }
        }
    }
};

237. Delete Node in a Linked List

题目

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4after calling your function.

Tag: Linked List

思路

假设链表中要删除的节点是node,想法是:找到指向node的节点(如图中值为2的结点),改变该节点的指针,指向node->next

title

然而答题区的函数只传入了一个要删除的节点,难道要遍历找到pre吗……然而也没有给我链表的首指针啊……

title

所以应该直接在给定的node上做文章。把node更改为node->next并把node->next删除~如下图所示。

title

解决方法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* t = node->next;
        *node = *t;
        delete t;
    }
};

值得一提,代码中的*node = *t非常有意思,即*node = *node->next,它等价于:

node->val = node->next->val;
node->next = node->next->next;

260. Single Number III

题目

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Tag:Bit Manipulation

思路

看到Tag中的“位操作”提示,看来又是非常interesting的一题。找出数组中仅出现一次的数的方法和上面136. Single Number一题是一样的,利用 A^B^A = B可用异或的方式找出仅出现一次的数。本题将仅出现一次的数换成2个,因此为求出这两个数,我们也应当将数组中的数分成两个group,分别求解。我们将仅出现一次的两个数设为ab

  1. 步骤一:遍历数组,异或数组中的所有元素,最终可得到值aXORb。由A^B^A=B可知,aXORb = a^b
  2. 步骤二:执行aXORb&(~(aXORb-1))找出aXORb中值为1的二进制位。假设aXORb中第i位的数字为1,则代表ab在该位上的二进制数不同。可假设a在第i位上的数为1b在第i位上的数为0
  3. 步骤三:将数组中所有数据分为两组。A组:第i位的数与a相同,B组:第i位的数与b相同;
  4. 步骤四:异或A组所有元素,得到A,异或B组所有元素,得到b

解决方法

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> result = {0, 0};
        int aXORb = 0;
        for(int i = 0; i<nums.size(); i++) {
            aXORb ^= nums[i];
        }

        int last = aXORb&(~(aXORb-1));

        for(int i = 0; i<nums.size(); i++) {
            if((last & nums[i]) != 0) {
                result[0] ^= nums[i];
            } else {
                result[1] ^= nums[i];
            }
        }

        return result;
    }
};