Data Structure

• 数组

  • 数组的特点是什么？
    • 内存地址连续
    • 存储相同数据
    • 元素只能覆盖，不能删除
  • two-pointer technique
    • keep original order
  • tow-pointer collision method
    • changing order
    • can reduce move operations
    • 流程
      • 将右侧不需要删除的元素，移动到，左侧需要删除的位置。
      • nums[left]是否需要删除?
        • Yes
          • 判断nums[right]是否需要删除?
            • Yes
            • No
              • 移动nums[left]=nums[right]
        • No
          • left++

  Operators Precedence

  • There all are 16 sets
    • C++ 内置运算符、优先级和关联性

  Level	Operators	Associativity
  5	*, /, %	Left
  6	+, -	Left
  7	<<, >>	Left

双指针

字符串操作

判断是否为回文字符串

双指针

// 双指针法
bool isPalindrome(const string& s, int start, int end) {
	for (int i = start, j = end; i < j; ++i, --j) {
		if (s[i] != s[j]) return false;
	}
	return true;
}

动态规划

判断[i, n]是否为回文， 需要2个条件

1. [i+1, n-1]是否为回文？
2. if (s[i] == s[n]) ?

所以构造 [i][j]二维判断查找表isPalindrome

[i,j]结果依靠[i+1, j-1], 所以i倒序，j正序

vector<vector<bool>> isPalindrome;
void computePalindrome(const string& s) {
  // isPalindrome[i][j] 代表 s[i:j](双边包括)是否是回文字串
  isPalindrome.resize(
      s.size(),
      vector<bool>(s.size(), false));  // 根据字符串s, 刷新布尔矩阵的大小
  for (int i = s.size() - 1; i >= 0; i--) {
    // 需要倒序计算, 保证在i行时, i+1行已经计算好了
    for (int j = i; j < s.size(); j++) {
      // 一些细节处理
      if (j == i) {  // 1个字符的情况
        isPalindrome[i][j] = true;
      } else if (j - i == 1) {  // 2个字符的情况
        isPalindrome[i][j] = (s[i] == s[j]);
      } else {
        isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i + 1][j - 1]);
      }
    }
  }
}

线性表