Sitch's Blog
0%

发表于 分类于 Valine：

字母异位分词

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"], 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"]] 说明：

所有输入均为小写字母。 不考虑答案输出的顺序。

题解分析

1. 怎么判断是不是异位分词呢? 想想异位分词具有什么特点?

---- 异位分词中, 字母出现次数相同, 字母顺序不同

---- 因此我们可以 排序后观察 / 26字母次数统计 进行比较.

当然注意别做一类扫一遍, 用个字典自动分类就可以了.

题解代码----排序+字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<string groupAnagrams(vector<string& strs) 
    {   //加字典的排序
        vector<vector<string result;
        unordered_map<string, vector<string hashmap;
        for(string s : strs)
        {
            string temp = s;
            sort(temp.begin(), temp.end());
            hashmap[temp].push_back(s);
        }
        
        for(auto i : hashmap)
        {
            result.push_back(i.second);
        }
        
        return result;
    }
};

发表于 分类于 Valine：

最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。

示例 2： 输入: "cbbd" 输出: "bb"

仿No.4切入

  • 回文序列本质上还是一个切割问题
  • 以切割点为起始,逐步比较两边是否相等即可判断回文.
  • 注意切割处可以是数, 也可以是两数之间

求解代码

题目思路较为简单,直接放出一遍撸过的代码. 

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
35
class Solution {
public:
	string longestPalindrome(string s)
	{
		string result;
		int center;
		int left;
		int right;
		if (s.length() == 0)
			return "";
        //参考题4扩展
		//[1,2,3] [1,# ,2,#,3]
		 //[2,1,1,2] [2,# ,1,#,1,#,2]
		for (center = 0; center < 2*s.length()-1; center++)
		{
			left = center / 2;
			right = (center + 1) / 2;
			while (1)
			{
				if (left < 0 || right = s.length() || s[left] != s[right])
				{
					left++;
					right--;
					break;
				}
				left--;
				right++;
			}
			if (right - left + 1  result.length())
				result.assign(s, left, right - left + 1);
		}

		return result;
	}
};
----------------- ## 错误思路反省 #### 1.条件定义错误 简单的将回文定义为 一个数在中间,两边相等 的序列, 实际上回文序列最中间可能是空而不是数. #### 2.边界特殊情况考虑不周 比如空字符串,比如没想到"aaaaa"这种字符串, 当然使用扩展分割的算法时这些情况都可以求解, 只不过如果自己能早点注意到这些特殊情况,就不需要绕弯子 , 可以直接上来就撸分割了. #### 3. 自行测试 自己在提交给OJ之前,应该自己尽量想出各种各样的测试样例, 不能写出什么就随便丢上去跑, 只有自己用心测试了之后才会发现自己的初始算法有那么多的错误.

发表于 分类于 Valine：

N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 N皇后示例-LeetCode 上图为 8 皇后问题的一种解法。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

输入: 4 输出: [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."],] 解释: 4 皇后问题存在两个不同的解法。

题目分析

  • 主要思路和数独类一样，回溯遍历

  • 放置特性：行、列、对角线不同

  • 需要注意怎么判断皇后在当前位置是否可放置呢？——使用状态表判断，三个数组构成

  1. 行列不同很简单，以行遍历为例，因为一行放了一个就到下一行，所以行不可能重复。
  2. 列检查，遍历每行的时候，检查列状态表，这列未被使用才可。bool colFlag[n]
  3. 检查主对角线，主对角线特征是行列差相同即是同一个主对角线，行列差范围在[-n+1,n-1]，因为索引有负，进行一个+n的偏移处理。diagonal[2*n]
  4. 检查次对角线，特征是行列和相同，范围在[0,2n-2]。SubDiagonal[2*n]
  5. 检查通过才可放置，同时后续假如要撤销记得收拾好记录表。

题解代码

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
public:
    vector<vector<string solveNQueens(int n) 
    {
        vector<vector<string result;
        int First=0;//第一行的Q位置
       


        while(First<n)//第一个Q的位置代表尝试轮次,第一行超过最后一格则所有遍历结束
        {
            //初始化棋盘
            vector<string tempReuslt;
            string tempString(n,'.');
            for(int i=0;i<n;i++)
            {
                tempReuslt.push_back(tempString);
            }
            //列使用情况,false代表没用过
            bool colFlag[n];
            bool diagonal[2*n];//对角线使用情况
            bool SubDiagonal[2*n];//次对角线使用情况
            memset(colFlag,0,sizeof(colFlag));
            memset(diagonal,0,sizeof(diagonal));
            memset(SubDiagonal,0,sizeof(SubDiagonal));


            //第一个Q在First位置
            tempReuslt[0][First]='Q';
            colFlag[First]=true;
            diagonal[0-First+n]=true;//偏移n,因为行减列可能是负数
            SubDiagonal[First]=true;
            int count=1;
            backTrace(result,tempReuslt,count,colFlag,n,diagonal,SubDiagonal);

            First++;
        }

        return result;
    }

    void backTrace(vector<vector<string& result,vector<string&tempReuslt,int& count,bool* colFlag,int& n,bool* diagonal,bool* SubDiagonal)
    {   
        //找齐了
        if(count==n)
            {
                result.push_back(tempReuslt);
                return ;
            }

        int i;//填入第count个数
        for(i=0;i<n;i++)
        {   
            //检查列,对角线,次对角线
            if((colFlag[i]==true || (diagonal[count-i+n]==true) || SubDiagonal[count+i]==true)==false)
            {  
                //填入一个数
                tempReuslt[count][i]='Q';
                colFlag[i]=true;
                diagonal[count-i+n]=true;
                SubDiagonal[count+i]=true;
                count++;

                //找下一个数
                backTrace(result,tempReuslt,count,colFlag,n,diagonal,SubDiagonal);

                //重置当前数
                count--;
                tempReuslt[count][i]='.';
                colFlag[i]=false;
                diagonal[count-i+n]=false;
                SubDiagonal[count+i]=false;

            }
        } 
       
    }


};

发表于 分类于 Valine：

pow(x,n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10 输出: 1024.00000

示例 2:

输入: 2.10000, 3 输出: 9.26100

示例 3:

输入: 2.00000, -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25 说明:

-100.0 < x < 100.0 n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

题目分析

数学思路, 快速幂算法

----因为xn可以分解成xn/2 * xn/2, 所以可以把n二分下去 变成logN的快速幂算法

另外注意: 数值越界, 奇偶的二分的区别

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    double myPow(double x, int n) 
    {   //????通不过45,90啊
        //只有奇偶递归的话,数值变大了就有问题
        if(n==INT_MIN)//注意-n 和 n 的越界范围不一样
            return 1/(myPow(x,INT_MAX)*x);
        else if(n<0)
            return 1/myPow(x,-n);

        
        if(n==0)
            return 1.0;
        else if(n==1)
            return x;

        double half=myPow(x,n/2);
        if(n%2==0)
            return half*half;
        else //(n%2!=0)
            return half*half*x;            
    }
};

发表于 分类于 Valine：

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

题目分析

1. 一开始我是想着，尝试双指针往中间收缩，只要收缩能增加和，那就保留当前状态，但不知道怎么描述收缩停止条件。
2. 动态规划，当累积到第i个数时,有两种情况:

2.1 吃掉之前的sum,变得更大 2.2 之前的sum为负,要它干嘛,不吃,自立门户 ##### 所以很简单，只需要判断前面的sum是否有价值就行了，因为是不能跳跃的，没价值你只能丢弃这个包袱，不能挑几项走。

题解代码

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
class Solution {
public:
    int maxSubArray(vector<int& nums) 
    {   
        //想着两边双指针逼近收缩,不过不知道怎么确定收缩停止条件,暂时搁置

        //动态规划
        //当累积到第i个数时,有两种情况:
        //1.吃掉之前的sum,变得更大
        //2.之前的sum为负,要它干嘛,不吃,自立门户
        int sum=nums[0];
        int maxResult=nums[0];
        int L=nums.size();
        for(int i=1;i<L;i++)
        {
            if(sum0)
                sum+=nums[i];
            else
                sum=nums[i];

            if(summaxResult)
                maxResult=sum;
        }

        return maxResult;


    }
};