Baymax0211

1.9万

bool isPalindrome(int x){

int m[100] = {};
int i = 0;
int j = 0;
if(x<0)
{return false;}

while(x){
m[i] = x%10;
x = x/10;
i += 1;
}
while(j!=i/2){
if(m[j]!=m[i-1-j])
return false;
j += 1;
}
return true;
}



int myAtoi(char* str) {
long ret = 0;
int flag = 1;//默认正数
//去除空格及判断符号位
for (; *str == 32; str++);
switch (*str) {
case 45:
flag = -1;
case 43:
str++;
}
//排除非数字的情况
if (*str < 48 || *str>57) return 0;

while (*str >= 48 && *str <= 57) {
ret = ret * 10 + (*str - 48);
//判断溢出
if ((int)ret != ret) {
return (flag == 1) ? (INT_MAX) : (INT_MIN);
}
str++;
}
ret *= flag;
return (int)ret;
}



int reverse(int x){
long res = 0;
while (x != 0) {
res = res * 10 + x % 10;
x = x / 10;
}
if (res > INT_MAX || res < INT_MIN) {
res = 0;
}
return res;
}


char* convert(char* s, int numRows)
{
int num=strlen(s),count = -1;char* ret= (char*)malloc((1+num)*sizeof(s[1]));
if(numRows==1 || numRows>num)  return s;
for (int cir = 0; cir < numRows; cir++)
{
int fir, sec; sec = 2 * cir; fir = (2 * numRows - 2) - sec;
ret[++count] = s[cir];
for (int c = cir; c < num;)
{
c = c + fir;
if (c < num && cir != (numRows - 1))    ret[++count] = s[c];
c = c + sec;
if (c < num && cir != 0)    ret[++count] = s[c];
}
}
ret[num] = '\0';
return ret;
}



void help(char *s, int N, int left, int right, int *start, int *len) {
while (left >= 0 && right < N && s[left] == s[right])
left--, right++;
if (right - left - 1 > * len) {  // 如果找到更长的子串，保存其信息
*start = left + 1;
*len = right - left - 1;
}
}
char * longestPalindrome(char * s){
int N = strlen(s), start = 0, len = 0;  // N 字符串长度， start 子串起始位置， len 子串长度
for (int i = 0; i < N; i++)     // 奇数长度的回文子串
help(s, N, i-1, i+1, &start, &len);
for (int i = 0; i < N; i++)     // 偶数长度的回文子串
help(s, N, i, i+1, &start, &len);
s[start + len] = '\0';          // 原地修改返回
return s + start;
}


int lengthOfLongestSubstring(char * s){
int i, j = 0, count = 0, max = 0, index[128] = {0}, start = 0;
for(i=0;s[i]!='\0';i++)
{
if(index[s[i]]>start)   //index用来储存出现重复字符时
{                       //子串起始下标应移动到的地方
count = i-start;
if(count>max)
{
max = count;
}
start = index[s[i]];
}
index[s[i]] = i+1;
}
count = i-start;
return count>max?count:max;
}
。


int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
for (int i = 0; i < numsSize; ++i) {
for (int j = i + 1; j < numsSize; ++j) {
if (nums[i] + nums[j] == target) {
int* ret = malloc(sizeof(int) * 2);
ret[0] = i, ret[1] = j;
*returnSize = 2;
return ret;
}
}
}
*returnSize = 0;
return NULL;
}



struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode *res = malloc(sizeof(struct ListNode));
res->val = -1;
res->next = NULL;//这里要特别注意
struct ListNode *cur = res;
int carry = 0;  //表示进位
while (l1 || l2)
{
int n1 = l1 ? l1->val : 0;
int n2 = l2 ? l2->val : 0;
int sum = n1 + n2 + carry;
carry = sum / 10;
cur->next = malloc(sizeof(struct ListNode));
cur->next->val = sum % 10;
cur->next->next = NULL;
cur = cur->next;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}

if (carry) {
cur->next = malloc(sizeof(struct ListNode));
cur->next->val = 1;
cur->next->next = NULL;
}
return res->next;   //返回真正的头结点

}


Baymax0211
2019-09-01 02:39
class UnionFind{
public:
vector<int>father;
UnionFind(int num){//num表示元素的个数
for(int i = 0; i < num; i++){
father.push_back(i);//箭头指向自己
}
}
int Find(int n){
//递归
if(father[n] == n)
return n;
father[n] = Find(father[n]);//路径压缩版本
return father[n];
}
bool Union(int a, int b){//返回a和b是否本身在一个集合里
int fa = Find(a);
int fb = Find(b);
bool res = fa==fb;
father[fb] = fa;
return res;
}
};

class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int N = edges.size();
UnionFind UF(N+1);
vector<int>res(2, 0);
for(int i = 0; i < edges.size(); i++){
int u = edges[i][0];
int v = edges[i][1];
if(UF.Union(u, v)){//冗余
res[0] = u;
res[1] = v;
}
}
return res;
}
};



Baymax0211
2019-09-01 02:37
class UnionFind{
public:
vector<int>father;
UnionFind(int num){//num表示元素的个数
for(int i = 0; i < num; i++){
father.push_back(i);//箭头指向自己
}
}
int Find(int n){
//递归
if(father[n] == n)
return n;
father[n] = Find(father[n]);//路径压缩版本
return father[n];
}
void Union(int a, int b){
int fa = Find(a);
int fb = Find(b);
father[fb] = fa;
}
};
class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
int N = M.size();
UnionFind UF(N);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(M[i][j]){
UF.Union(i, j);//两个人是朋友则合并朋友圈
}
}
}
int res = 0;
for(int i = 0; i < N; i++){
if(UF.Find(i) == i)//计算朋友圈的个数
res++;
}
return res;
}
};