编程日记，尽可能保证每天最少3道leetcode题，仅此记录学习的1些题目答案与思路，尽可能用多种思路来分析解决问题，不足的地方还望指出。标红题为以后还需要再看的题目。
Reverse bits of a given 32 bits unsigned integer.
For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).
Follow up:
If this function is called many times, how would you optimize it?
Related problem: Reverse Integer
题意：给1个数字，逆转它的2进制表示位。
思路：
1、32次循环，每次循环都是现将res左移1位然后再加上num的最低位。
代码：
C++
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res=0;
for(int i=0;i<32;i++,n>>=1)
{
res=res<<1;
res |= n&1;
}
return res;
}
};结果：4ms
Remove all elements from a linked list of integers that have value val.
Example
Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6
Return: 1 –> 2 –> 3 –> 4 –> 5
题意：删除链表中值为val的元素。
思路：
直接从头开始，首先肯定头的值不是val，然后逐一遍历，如果碰到值为val的节点则利用1个前节点（Prev）来删除当前的节点。不难，但是自己写的代码很丑，3次才AC，还是贴上来好了。
代码：
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode *Prev,*Node;
if(!head) return head;
while(head)
{
if(head->val==val)
head = head->next;
else
break;
}
Node = head;
Prev = NULL;
while(Node)
{
if(Node->val==val)
{
Prev->next = Node->next;
delete Node;
Node = Prev->next;
}
else
{
Prev = Node;
Node = Node->next;
}
}
return head;
}
};结果：36ms
2、参考了https://leetcode.com/discuss/47642/simple-and-elegant-solution-in-c的做法，用1个2级指针，指针指向的是节点，最初指针指向的是head节点。当指针指向的节点等于val的的时候，指针指向的节点直接赋值为下1个节点，也就相当因而删除当前的节点；当指针指向的节点不等于val的时候，需要更改指针内寄存的内容为下1个节点。进行下1次的判断直到指针的内容为空。
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode ** list = &head;
while(*list)
{
if((*list)->val==val)
*list = (*list)->next;
else
list = &(*list)->next;
}
return head;
}
};结果：32ms
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
题意：给1个链表，判断是不是是回文。O（N）的时间和O（1）的空间。
思路：
首先，由于链表是单向的，那末要判断回文就需要将第1个节点和最后1个节点比较，然后两个节点向中间靠拢。首先我们需要找到中间的节点，即不需要逆转的最后1个节点。当节点总数是奇数的时候，例如n=7，明显我们只需要比较前3个节点和后3个节点，第4个节点不需要移动，中间节点下标是(6-0)/2=3，当n=8的时候，需要比较前4个节点和后4个节点，第4个节点不需要移动，因此中间节点下标还是(7-0)/2 = 3。因此第1步就是找到中间结点。
其次，找到中间节点以后，需要将中间节点以后的节点逆序，然后从中间节点的下1个节点开始顺次和头部节点相比较。
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(head==NULL||head->next==NULL) return true;
ListNode*slow,*fast;
slow=head,fast = head;
while(fast->next!=NULL && fast->next->next!=NULL)
{
slow = slow->next;
fast = fast->next->next;
}
slow->next = ReverseList(slow->next);
while(slow->next!=NULL)
{
if(slow->next->val!=head->val) return false;
slow = slow->next;
head = head->next;
}
return true;
}
ListNode* ReverseList(ListNode* head)
{
ListNode*Prev,*next;
Prev = NULL;
while(head!=NULL)
{
next = head->next;
head->next = Prev;
Prev = head;
head = next;
}
return Prev;
}
};结果：29ms
Write a function to find the longest common prefix string amongst an array of strings.
题意：求1组字符串的最长公共前缀
思路：
逐一字符开始比较，先比较第0个字符是不是符合，知道找到不符合的位为止返回前缀。
代码：
C++
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string prefix = "";
if(strs.size()<=0) return prefix;
//k代表判断的前缀字符数，从第0个字符开始，判断每个strs的元素的第k位是不是相等，如果全部相等了则最长公共前缀加1
for(int k = 0;k<strs[0].size();k++)
{
//i代表第i个字符串，每次循环的i需要小于strs的个数和最少为k位，由于之前的前缀已有k位了，某个字符串没有到达k位那末没必要继续计算了
int i=1;
for(;i<strs.size()&&strs[i].size()>k;i++)
{
if(strs[i][k]!=strs[0][k]) return prefix;
}
if(i==strs.size()) prefix +=strs[0][k];
}
return prefix;
}
};结果：6ms
程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作
声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！
粤ICP备14040726号-1 2015-2020 程序员人生 版权所有
